220 views

Skip to first unread message

Mar 18, 1997, 3:00:00 AM3/18/97

to

In message <3330d8bc...@news.dial.pipex.com>

george....@dial.pipex.com (George Barwood) writes:

> On 19 Mar 1997 15:02:05 GMT, jw...@ecs.soton.ac.uk (John Wigley) wrote:

[...]

> >1)Hash the message to be signed as usual and use that as the message in

> >the signature algorithm.

> >2)hash the private key using the chaining variable state left by the

> >previous hash, and use that as the random number.

> >

> >This ensures that you use a unique apparently random number for each

> >signature, except when you resign the same message when it doesn't matter.

> >You also don't have to keep any random state in the system which can be of

> >benefit to both software and hardware, and you don't need any external

> >sources of variables i.e. system date / time / key timings etc.

> It seems sensible and efficient to me, and I believe secure (provided

> the hash function used is secure). I have posted before here on this

> subject, with no response. I have not seen it described elsewhere,

> although the IEEE P1363 draft now hints at it.

It means that it's essential that the hash function be collision-free.

Normally, if a hash function used for a signature algorithm is one-way

but not collision-free, an attacker can find two messages with the same

hash, and ask you to sign one of them. The same signature will work for

the other message, which is bad, but only allows a single forgery.

However, if you use this scheme for DSA, a similar attack might allow

someone to get the private key (because they would have two messages

signed using the same random number) [*]. That means the output of the

hash function had better be long enough to prevent a birthday attack, or

else each message that is signed must contain some random bits (which

rather defeats the purpose of avoiding an RNG).

David Hopwood

david....@lmh.ox.ac.uk, hop...@zetnet.co.uk

[*] According to Applied Cryptography 2nd ed. page 492, which references

G.J. Simmons, "The Subliminal Channels of the U.S. Digital Signature

Algorithm (DSA)", Proceedings of the Third Symposium on State and Progress

of Research in Cryptography, Rome: Fondazone Ugo Bordoni, 1993, pp 35-54.

Mar 19, 1997, 3:00:00 AM3/19/97

to

I was thinking last night about an implementation of digital signatures -

re: the requirement for a truly random number in DSA / NR / most other

algo's. Why not derive the random number from the message to be signed

therefore removing the need for a hardware rng (smartcards) or a complex

and potentially fallible software attempt.

The most efficient method I came up with is as follows :

1)Hash the message to be signed as usual and use that as the message in

the signature algorithm.

2)hash the private key using the chaining variable state left by the

previous hash, and use that as the random number.

This ensures that you use a unique apparently random number for each

signature, except when you resign the same message when it doesn't matter.

You also don't have to keep any random state in the system which can be of

benefit to both software and hardware, and you don't need any external

sources of variables i.e. system date / time / key timings etc.

Can someone tell me if I am being stupid here and missing an

obvious point, or does this seem sensible and efficient.

John

Mar 19, 1997, 3:00:00 AM3/19/97

to

In article <5gov5d$p...@wapping.ecs.soton.ac.uk>, jw...@ecs.soton.ac.uk

(John Wigley) wrote:

...

> The most efficient method I came up with is as follows :

>

> 1)Hash the message to be signed as usual and use that as the message in

> the signature algorithm.

> 2)hash the private key using the chaining variable state left by the

> previous hash, and use that as the random number.

>

> This ensures that you use a unique apparently random number for each

> signature, except when you resign the same message when it doesn't matter.

> You also don't have to keep any random state in the system which can be of

> benefit to both software and hardware, and you don't need any external

> sources of variables i.e. system date / time / key timings etc.

>

>

> Can someone tell me if I am being stupid here and missing an

> obvious point, or does this seem sensible and efficient.

>

If a message and/or author of that message be put into a signature, then

it makes logical sense to have the whole and signature of comparable

length. Otherwise, it would not be unique, only obscure. A signature

should be shown to be unique and indicate particular medling in the

contents. It can be easily done, no random numbers involved.

Likewise, an encryption can be used to produce a signature as well. It is

reasonable to be able to have a returned signature from a person who

cannot read a message, but merely confirm that it was received intact.

--

WTShaw, Macintosh Crypto Programmer

wts...@htcomp.net wts...@itexas.net

To Err is Human.

To Not Correct Your Mistakes is Bad Form.

Mar 19, 1997, 3:00:00 AM3/19/97

to

On 19 Mar 1997 15:02:05 GMT, jw...@ecs.soton.ac.uk (John Wigley) wrote:

>I was thinking last night about an implementation of digital signatures -

>re: the requirement for a truly random number in DSA / NR / most other

>algo's. Why not derive the random number from the message to be signed

>therefore removing the need for a hardware rng (smartcards) or a complex

>and potentially fallible software attempt.

>The most efficient method I came up with is as follows :

>

>1)Hash the message to be signed as usual and use that as the message in

>the signature algorithm.

>2)hash the private key using the chaining variable state left by the

>previous hash, and use that as the random number.

>

>This ensures that you use a unique apparently random number for each

>signature, except when you resign the same message when it doesn't matter.

>You also don't have to keep any random state in the system which can be of

>benefit to both software and hardware, and you don't need any external

>sources of variables i.e. system date / time / key timings etc.

>

>

> Can someone tell me if I am being stupid here and missing an

>obvious point, or does this seem sensible and efficient.

>

> John

The random numbers are used in key generation, not in the actual

signing process.

Mar 20, 1997, 3:00:00 AM3/20/97

to

On 19 Mar 1997 15:02:05 GMT, jw...@ecs.soton.ac.uk (John Wigley) wrote:

>I was thinking last night about an implementation of digital signatures -

>re: the requirement for a truly random number in DSA / NR / most other

>algo's. Why not derive the random number from the message to be signed

>therefore removing the need for a hardware rng (smartcards) or a complex

>and potentially fallible software attempt.

>The most efficient method I came up with is as follows :

>

>1)Hash the message to be signed as usual and use that as the message in

>the signature algorithm.

>2)hash the private key using the chaining variable state left by the

>previous hash, and use that as the random number.

>

>This ensures that you use a unique apparently random number for each

>signature, except when you resign the same message when it doesn't matter.

>You also don't have to keep any random state in the system which can be of

>benefit to both software and hardware, and you don't need any external

>sources of variables i.e. system date / time / key timings etc.

It seems sensible and efficient to me, and I believe secure (provided

the hash function used is secure). I have posted before here on this

subject, with no response. I have not seen it described elsewhere,

although the IEEE P1363 draft now hints at it.

Using this technique means that signing is deterministic, which may

have some practical advantages.

I would be grateful to hear of any confirmation that this technique is

thought to be secure.

George Barwood

Mar 20, 1997, 3:00:00 AM3/20/97

to

John Wigley wrote:

>

> I was thinking [...] about [...]

> the requirement for a truly random number in DSA / NR /

> 1)Hash the message to be signed as usual and use that as the message in

> the signature algorithm.

> 2)hash the private key using the chaining variable state left by the

> previous hash, and use that as the random number.

> the signature algorithm.

> 2)hash the private key using the chaining variable state left by the

> previous hash, and use that as the random number.

I think it should be secure, provided the hash and underlying

signature algorithm are secure. I think you could informally

argue it with reasonable assumptions. In particular, assume

that the hash H() is strong enough that H(K,x1), H(K,x2),...

is computationally indistinguishable from a random sequence,

for unknown K and known (or chosen) distinct x1, x2, x3... .

If your scheme is weak while the same signature scheme with

true random numbers is strong, then you could construct the

distinguisher.

The major downside of the method is that you can no longer

precompute using the (pseudo) random number, since you need

the message in order to generate it. Using DSA,

precomputation can speed the on-demand signing step by a

factor of over 100.

--Bryan

Mar 20, 1997, 3:00:00 AM3/20/97

to

I wrote (without really thinking):

> I think you could informally

> argue it with reasonable assumptions. In particular, assume

> that the hash H() is strong enough that H(K,x1), H(K,x2),...

> is computationally indistinguishable from a random sequence,

> for unknown K and known (or chosen) distinct x1, x2, x3... .

> If your scheme is weak while the same signature scheme with

> true random numbers is strong, then you could construct the

> distinguisher.

But since you use the same K as the signature key, I'd have

to know it to build the distinguisher, which of course I don't.

The logic would hold if you used a different key in the hash, but

that defeats much of the purpose. Using the same key, there's

still the possibility of unfortunate interaction between the

hash and the exponential, which is the sort of thing that

rarely exists, but is hard to disprove.

--Bryan

Mar 21, 1997, 3:00:00 AM3/21/97

to

On 19 Mar 1997 21:35:03 -0700, ah...@winternet.com (Adam Hupp) wrote:

>On 19 Mar 1997 15:02:05 GMT, jw...@ecs.soton.ac.uk (John Wigley) wrote in part:

>

>>I was thinking last night about an implementation of digital signatures -

>>re: the requirement for a truly random number in DSA / NR / most other

>>algo's. Why not derive the random number from the message to be signed

>>therefore removing the need for a hardware rng (smartcards) or a complex

>>and potentially fallible software attempt.

>> [..]

>

>The random numbers are used in key generation, not in the actual

>signing process.

Well you can call it that, but a new one-time key pair is required for

each signature.

George Barwood

Mar 21, 1997, 3:00:00 AM3/21/97

to

Bryan Olson (Bryan...@nobulkmail.uptronics.nospam.com) wrote:

: John Wigley wrote:

: >

: > I was thinking [...] about [...]

: > the requirement for a truly random number in DSA / NR /

: [...] : > 1)Hash the message to be signed as usual and use that as the message in

: > the signature algorithm.

: > 2)hash the private key using the chaining variable state left by the

: > previous hash, and use that as the random number.

: I think it should be secure, provided the hash and underlying

: signature algorithm are secure. I think you could informally

: argue it with reasonable assumptions. In particular, assume

: that the hash H() is strong enough that H(K,x1), H(K,x2),...

: is computationally indistinguishable from a random sequence,

: for unknown K and known (or chosen) distinct x1, x2, x3... .

: If your scheme is weak while the same signature scheme with

: true random numbers is strong, then you could construct the

: distinguisher.

: The major downside of the method is that you can no longer

: precompute using the (pseudo) random number, since you need

: the message in order to generate it. Using DSA,

: precomputation can speed the on-demand signing step by a

: factor of over 100.

: --Bryan

Good point (one that I hadn't thought of), however if you are prepared

to store a bit of temporary state then you can use the currently generated

ran. number for the next signature (and the previous one for the current

signature) and that way you can still precompute the ephemeral key pair.

Or you could use a combination to avoid storing state i.e. if you are only

doing one signature then you can probably afford it to be slow, but if you

are doing a lot in the same session then you could use the above staggered

method.

John

Mar 21, 1997, 3:00:00 AM3/21/97

to

Adam Hupp (ah...@winternet.com) wrote:

>On 19 Mar 1997 15:02:05 GMT, jw...@ecs.soton.ac.uk (John Wigley) wrote:

>>I was thinking last night about an implementation of digital signatures -

>>re: the requirement for a truly random number in DSA / NR / most other

>>algo's. Why not derive the random number from the message to be signed

>>therefore removing the need for a hardware rng (smartcards) or a complex

>>and potentially fallible software attempt.

>>The most efficient method I came up with is as follows :

>>

>>1)Hash the message to be signed as usual and use that as the message in

>>the signature algorithm.

>>2)hash the private key using the chaining variable state left by the

>>previous hash, and use that as the random number.

This might be a little tricky, since the internal state is not usually

accessible (unless you hack on the hash algorithm itself) and you have to

deal with the padding at the end. But it would probably be equivalent to

compute h = H(m), and r = H(h,key) (or some variation, like H(key,h,key)).

>>This ensures that you use a unique apparently random number for each

>>signature, except when you resign the same message when it doesn't matter.

>>You also don't have to keep any random state in the system which can be of

>>benefit to both software and hardware, and you don't need any external

>>sources of variables i.e. system date / time / key timings etc.

You might have cases where you need a larger number than the hash can

provide. In such cases it might make sense to generate part of the

random number from the hash, and generate the rest randomly. You couldn't

have a collision in the random number unless the hash portion collided

(which is rare enough it shouldn't be a problem).

This might be beneficial in some signature systems where using the same

random number for two signatures would allow the key to be broken. If

a signature system is vulnerable when the same message is signed using

two different random numbers, this system (using only deterministic

values in the "random" numbers, not random padding) would ensure the

same random number would be produced when re-signing the same message.

(I'm not sure if that is really necessary, though, since you could

eliminate the possibility by including random padding in the "message",

and/or using a random prefix and/or suffix in the text before computing

the hash; then you provide these values as part of the signature. That

would ensure that even if the same text is given to you again, the

"message" you sign would not be the same.)

You have to be careful though. In some systems the "random" number might

be provided as part of the signature. If this gives them H(H(m),key),

then they might be able to learn something about your key. If the hash

function is secure, then this should be ok, but if someone finds a way

to attack the hash function in the future, they may also be able to find

your key more easily. I don't see any obvious problems where the random

number is to be kept secret, but I may be missing something.

An alternate method might be to use H(H(m),key) to initialize a BBS RNG,

and generate the "random" number(s) (that you want to be deterministic)

from that. Using your private key keeps the BBS from being predicted

by someone else (who knows H(m)), and the BBS RNG protects against the

results from being backtracked to find H(H(m),key). I'm not sure if this

is ultimately any more secure than your approach (though you can get more

bits out of it, after using enough hash values to fill out an intitial

value under a secure modulus). It's also quite a bit slower to use

a BBS RNG than to just compute a secure hash.

>> Can someone tell me if I am being stupid here and missing an

>>obvious point, or does this seem sensible and efficient.

>

>The random numbers are used in key generation, not in the actual

>signing process.

Actually, most digital signature systems seem to require the use of a

random value for each separate signature. RSA is one that does not

(and I can't think of any others off the top of my head, having just

read the relevant section of "Applied Cryptography" recently). Of course,

even with RSA signatures it is a good idea to pad the "message" with

random bits (since the modulus is usually much longer than the hash).

-Rob Parker

Jul 14, 2020, 5:26:18 AM7/14/20

to

Ok

Reply all

Reply to author

Forward

0 new messages

Search

Clear search

Close search

Google apps

Main menu