Questions about generating keys (hash firewalls)

[Oskar L.]

That was a very good explanation of what a hash firewall and a
second-preimage attack are. But I think it gives the impression that all
the hash firewall is good for is protecting against a second-preimage
attack, and therefore is of little importance, since a successful
second-preimage attack on SHA-1 is very unlikely to happen.

A much more real threat than the second-preimage attack is the birthday
attack. The attack is based on the birthday paradox, which deals with how
many people there need to be, for the chance to be over 50% that two will
have the same birthday. The answer is 253 pairs.

So if we start with Bob, we need to have 253 more people, to be able to
make 253 different pairs of which Bob is part of. This can be compared to
the second-preimage attack; trying to find a message that hashes to a
given hash. However, if we don't need to start with anyone in particular,
and just take 23 people, we can make the same amount (253) of different
pairs from only these 23 people. This is how the birthday attack works;
trying to find any two messages that hashes to the same hash, and as shown
by the birthday paradox, this is much more likely to succeed than the
second-preimage attack.

This is how it could be used. I take two pictures, one offensive and one
nice. The resolution is 2048x1536, which means they contain 3145278
pixels. If I change a pixel 5 shades darker or brighter, it will be such a
small change that it won't be noticed. So I have 11 (original+5+5)
alternatives for each of the 3145278 pixels. This means I can make
11^3145278 versions of each picture. That's so many that not even
calculators designed to show very large numbers can show the result. Now I
compare all the hashes from one picture to all the hashes from the other.
If I find one version of the offensive picture and one version of the nice
picture that have the same hash, I sign the offensive picture and send it
to someone, and can then deny I did so and show the nice picture with the
same hash as proof.

If I have signed the picture with a key with a hash firewall, the receiver
knows (in a perfect world) that in the attack I could use different
algorithms, but am limited to using only collisions between hashes made by
the same algorithm. If I don't use a firewall the receiver knows that the
attack would be much easier for me, since I could use a "collision"
between different algorithms.

Do hash firewalls have any drawbacks (performance decrease, difficult to
implement, patent issues etc.)? What's the reason DSA doesn't have one?

Oskar



"Robert J. Hansen" wrote:

> In an RSA signature, data about what algorithm was used in a signature
> is, itself, part of the signed data.  You can't lie about a signature
> algorithm without tampering with the message and making the signature
> fail to verify.
>
> In DSA, the data is not part of the signed data.  This allows you to
> lie.  This has potential problems if one of the supported hashes becomes
> so catastrophically weak that second-preimage attacks become feasible.
>
> SHA-1 may be basically dead as far as crypto goes, but it is a _long_
> way from a second-preimage attack.
>
>
>
>
> The paranoid interpretation of this:
>
> Let's speculate that tomorrow, Shengdong University continues their
> trend of eye-popping crypto research and announces a second-preimage
> attack against SHA-1.  You migrate to RIPEMD160 or truncated SHA256 or
> what-have-you as a result.
>
> An attacker wants to forge one of your new RIPEMD160-based signatures.
> An attacker gets a good RIPEMD160-based signature from you.  This is
> basically one very long binary sequence, which says "hey, if the message
> you're reading hashes out to this binary sequence, then yes, it's for
> real."
>
> I construct a new message, saying "I, Sven Radde, agree to pay Rob
> Hansen one frosty cold pint of bitters."  I wave the dead chicken over
> it, or whatever Shengdong U. says I have to do, in order to make it hash
> out to the exact same binary sequence as the one your signature says is
> authentic.
>
> I lift your RIPEMD160 signature and place it on my new forged message.
> I proceed to then lie and say "This message used SHA-1 as a digest."
>
> I give it to your local barkeep.  He looks at the message, SHA-1s it,
> gets the binary sequence I constructed.  He compares it against your
> signature block, which says "hey, if the message you're reading hashes
> out to this binary sequence, then yes, it's for real."
>
> Your barkeep pours me a nice cold frosty pint of bitters--hey, I'm a
> barbaric American and I drink my beer _cold_, thank you very much--and
> puts the bill for it on your tab.
>
> I have now defrauded you by using a forged message.  And it's all made
> possible by the lack of a hash function firewall.
>
>
>
>
>
> The practical paranoid interpretation of this:
>
> A second-preimage attack on SHA-1 would be a mathematical advance of
> such massive proportions that worrying about its consequences for DSA
> signatures is kind of dumb.
>
> If you stay up late at night wondering what will ever happen to "Deal Or
> No Deal" in the days after a meteor hits Earth, then you're probably the
> type of person who worries about what happens to DSA signatures after a
> second-preimage attack on SHA1.  The rest of the world, however, will
> have much more important things to worry about.
>
>
>
>
> ... Personally, I myself subscribe to the practical paranoid view.
>