Re: How to Calculate Signatures?

[Konrad Rosenbaum <[e-mail]>]

On Sunday 03 April 2005 20:50, Ben Laurie wrote:
> Konrad Rosenbaum wrote:
> > Simple: you don't. DSA was designed to be used with SHA-1, which is 160
> > bit. Since SHA-1 is theoretically broken (practically will probably
> > follow in a few months) one should see what the NIST makes of it.
> > Supplanting a broken hash with another hash doesn't make much sense
> > with DSA, since it does not contain the ID of the hash (as PKCS#1 does
> > for RSA) - so any attacker could find a collission with the broken hash
> > and then simply change the hash ID in the signature packet.
>
> The hash does include the ID of the hash, and hence the signature does.

That does not prevent a downgrade attack.

Presume the following scenario:

The signature S is under Text A with hash algorithm H. The hash is deemed 
secure.

So s contains the number of H and the content of A. The structure looks like 
this:

Text packet A
Signature packet S
 Hash number H
 signed(Hash_H(H_number || A)) # or something very similiar

Now we want the signature to refer to Text B and we know that hash algorithm 
X is insecure (and we know how to use that). What we need to do now is we 
need to find a text C that consists of the the number of X, and B plus some 
"random" that is chosen in a way that does not distort the meaning (eg. a 
"geek code block" below the actual eMail text). The structure will look 
like:

Text packet C ( = B || "random")
Signature packet S'
 Hash number X
 signed(Hash_H(H_number || A)) == signed(Hash_X(X_number || C))

...and that all because a weak Hash X will enable us to find a text that 
creates the same hash sum in X that we want to supplant for a hash sum of H 
- regardless of whether we hash the hash number, a "magic" code or my grand 
mothers birthday into it.

MD5 is already beaten down to 33 bit, it is only a question of time till 
SHA-1 is there as well (granted, we'll probably have some months left). 
Currently we are only save because there is no 160-bit Hash in OpenPGP that 
is vulnerable enough to make the attack worthwhile.

The days of DSA with a 160-bit p are counted. Period.


	Konrad

PS.: please view my DSA signature on this mail as my last action of respect 
to DSA. It was a good fellow... ;-)