removing need for rng in signatures
David Hopwood
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.
John Wigley
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
W T Shaw
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.
Adam Hupp
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.
George Barwood
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
Bryan Olson
John Wigley wrote:
>
> I was thinking [...] about [...]
> the requirement for a truly random number in DSA / NR /
> 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
Bryan Olson
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
George Barwood
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
John Wigley
Bryan Olson (Bryan...@nobulkmail.uptronics.nospam.com) wrote:
: John Wigley wrote:
: >
: > I was thinking [...] about [...]
: > 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
parker_rob
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
