[Date Prev][Date Next] [Thread Prev][Thread Next] [Date Index] [Thread Index]

Re: SSH keys: DSA vs RSA

Russ Allbery <rra@debian.org> writes:

> Steve Greenland <steveg@moregruel.net> writes:
>> "brian m. carlson" <sandals@crustytoothpaste.ath.cx> wrote: 
>>> Therefore, anyone who had a DSA key has had it compromised...
>> Shouldn't that be "anyone who had a DSA key *created by the flawed
>> version of openssl* has had it compromised..."? Or are you asserting
>> something stronger?
> He's asserting something stronger.  As I understand it, if you use a
> perfectly valid and strong DSA key with a weak nonce (such as from a
> broken random number generator), you just revealed your DSA key to someone
> who knows what to look for and can brute-force or otherwise determine the
> nonce.

The DSA signing uses (secret key + random) in the signature and that
sum is trivial to compute given the signed message and public key. The
security of DSA relies solely on the fact that random can't be guessed
so you can't compute the secret key from the sum.

With the bug in Debians openssl random is one of 2^15 numbers for a
given cpu and key size. If you don't know the cpu used then multiply
by 2 (32bit or 64bit) and again by 2 (big or little endian).

So all you have to do is to try out 32768 random numbers (or 131072)
and check if that gives you the secret key.

Also if you have 2 messages signed with the same random number you can
compute the secret key. It is more complicated then this but
simplified boils down to is computing k given (k + r) * Message1 ==
Signature1 and (k + r) * Message2 == Signature2.


Reply to: