DSA2

[Robert J. Hansen]

Nicholas Cole wrote:
> Thanks for this.  What is a "hash function firewall",
> for those of us who are mere mortals? :)

In the real world we don't sign an entire message with our private key. 
  Instead we take a hash of the message and sign the hash.  Then we post 
the original message and our signature.  Other people can hash the 
original message and compare it against our signed hash.  If the two 
compare identically, then clearly it's a good signature, right?

But there's one detail we're handwaving.  How do you know what hash 
algorithm to use?  There has to be some piece of data telling you "use 
SHA512" or "use SHA-1" or...

Let's think of an attack against this scheme.  Let's say that our 
message format puts _in the message_ "use SHA-512" or whatever, and 
there's no data _in the signature_ about what hash was used.  Let's also 
say that I'm using a good hash algorithm, RIPEMD-128 [*].

How could we you the fact our format puts the hash data in the message 
to your advantage?

Hmm.  Well, you could use a very weak hash algorithm, such as MD4 [**]. 
  You take a good signature off a message I've already signed, and you 
construct a forged message whose MD4 hash comes out identical to the 
RIPEMD-128 hash of my original (good) message.

"Hi!" the message now reads.  "This is Rob, and I'd like to donate 
megabucks to the Society of Evil Geniuses Working Together For a Better 
Tomorrow.  Please empty my bank account.  Hail Eris!  Hail Discordia! 
Oh, and use MD4 to verify this message."

You then take your forged message to the bank.  They verify the (forged) 
signature to recover the original hash value.  _They have no way of 
knowing it was originally a RIPEMD-128 hash_.  So when they MD4-hash the 
message and see it's identical to the hash value in the signature, the 
bank takes it as a valid digital signature and empties my bank account.

That's what it means for a signature scheme to lack a hash function 
firewall.  A good hash function firewall makes this impossible.

A hash function firewall means the signature carries data about itself, 
protected by a digital signature to make it tamper-resistant.  If, in 
our previous example, the signature said "use RIPEMD-128", the bank 
would know to use the right hash algorithm... a strong one, resistant to 
cryptanalytic attacks.

Without a hash function firewall, any critical compromise of any hash 
algorithm in the signature system puts the entire system in jeopardy. 
With a hash function firewall, only signatures using that compromised 
hash algorithm are jeopardized.

This is why some critics think signing keys need to support firewalling.

I don't know off the top of my head whether DSA supports firewalled hash 
functions or not.  I believe that the last time I checked the spec, I 
came to the conclusion it did not.

RSA signing keys, on the other hand, do support firewalling.

This entire post has been a tremendous simplification of an esoteric 
area of cryptology.  There are a great many nuances to the subject.  I 
also haven't taken a magnifying glass to the OpenPGP spec in at least 
eighteen months, maybe more; things may have changed since then. 
Corrections from people who are up-to-date on the latest revision of the 
spec are always appreciated.




[*] RIPEMD-128 is a 128-bit shortening of RIPEMD-160.  It is at present 
believed cryptographically secure.  It shouldn't be confused with 
RIPEMD, an earlier 128-bit hash, which is no longer considered 
cryptographically secure.

[**] You can create collisions in MD4 with pen and paper.  I'm not sure 
if MD4 is really weak enough for this example, but it's just a thought 
experiment, so let's assume it is.