The perils of security tools

[Nate Lawson]

> 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!

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 majordomo at metzdowd.com