The perils of security tools

[Bodo Moeller]

On Sun, May 18, 2008 at 4:55 PM, "Hal Finney" <hal at finney.org> 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!

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.

Bodo

---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com