On Sun, May 18, 2008 at 4:55 PM, "Hal Finney" <[EMAIL PROTECTED]> wrote:
A simple trick can be used to help immunize DSA signatures against
these kinds of failures. I first learned of this idea many years ago
from Phil Zimmermann, and a varient has been used for a long time in
PGP and probably other code, but aparently not OpenSSL. The idea is
to base the random k not just on the output of your RNG, but also on
the private key x. Something like:
k = hash (x, rng()).
Of course it is still necessary that k be uniformly distributed mod q
(the DSA subgroup prime order), so this can't be just a straight hash.
It might be a separate PRNG instance which gets seeded with the data
values shown. But the idea is to mix in the secret key value, x, in
addition to data from the RNG.
I've used this idea before, although in the form of using the private
key as part of the PRNG seed -- which isn't of much use if the PRNG
ignores its seeding as in this case. However, even the form
k = hash (x, rng())
isn't good enough if the PRNG is sufficiently broken. The Debian code
generated an output that was not merely predictable, but also prone to
repetition if you run a binary multiple times. With typically just
2^15 different byte streams from the PRNG, by the birthday paradox
you'd have to expect to have been reusing some k after around 2^8
iterations or so. So your DSA key would still be at risk!
While mixing in more entropy is a good idea in general, I'd like to
caution against just throwing things in without knowing the full design
end-to-end. For example, if the environment is an embedded device and
hash() introduces visible power or timing side channels, you may not
want to do this exact construction. Most of the time it is fine, though.
DSA is especially vulnerable to all kinds of subtleties with k. As you
point out, it is fatal to replay k for a given private key x. But even
worse, it is fatal if some small number of bits of k are *predictable*.
This means even if the output wasn't completely predictable, but had
merely become somewhat predictable, it would still be exploitable.
http://crypto.stanford.edu/~dabo/abstracts/dhmsb.html
http://cat.inist.fr/?aModele=afficheN&cpsidt=13872268
Mark Marson at Cryptography Research has done some great work
implementing these attacks. They're quite practical. I hope he'll give
a public talk about it some day.
You could also make k message-dependant -- i.e., feed both x and k
into the hash function:
k = hash (x, rng(), m)
This avoids that problem, and is likely to remain unbreakable even if
rng() returns just some constant. However, then you lose one
advantage of DSA, namely being able to do most of the computation in
advance, before you've even seen the message to be signed: If you've
obtained k and done the DSA exponentiation beforehand, you can create
signatures almost instantaneously; but this won't work if k depends on
the message.
This assumes the message always changes. Isn't this just getting back
to padding schemes, where you build something like PSS under your DSA to
protect against signing identical messages?
Since it appears some OpenSSL people are on this list, I'd like to ask
for more openness in the PRNG design and seeding. The current code is
crufty and arbitrary. Some minor but careful additions could have
helped reveal this bug earlier.
The code should generate warnings in the case of PURIFY being defined.
A comment should explain the security relevance of the seeding. For
example:
#ifndef PURIFY
/* SECURITY: add entropy to our pool. This is essential. (more) */
seed_PRNG(buf);
#else
#warning PRNG seeding disabled for Purify, do NOT use PRNG output!
printf("WARNING: PRNG seeding disabled for Purify, do NOT use PRNG
output!\n");
#endif
Also, there should be a TEST_MODE_INSECURE flag that outputs a debug
print of each time the PRNG is seeded and the data itself. This should
be run on a regular basis as part of automated tests. For example:
init()
{
#ifdef TEST_MODE_INSECURE
#warning PRNG seeding debug prints enabled, do NOT use PRNG output!
printf("WARNING: PRNG seeding debug prints enabled, do NOT use PRNG
output!\n");
#endif
}
seed_PRNG(src_name, buf)
{
#ifdef TEST_MODE_INSECURE
printf("PRNG seeding from %s: %s\n", src_name, hex_dump(buf));
#endif
... do seeding ...
}
Anyway, I hope this incident helps us all add more openness and paranoia
to our designs.
--
Nate
---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
