Questions about generating keys (hash firewalls)

Sven Radde sven at
Sat Aug 25 09:11:07 CEST 2007

Oskar L. schrieb:
> No, in my example I used two, not one messages (pictures) and created
> permutations of both, and then compared both groups of hashes against each
> other.

This appears to be somewhere in the middle between a birthday attack and
a preimage attack.
It looks like a preimage attack on a large set of preimages.

Thinking it in the terms of the classical birthday paradoxon would mean
to put men and women in a room and check all couples of both sexes for a
matching birthday.
I am not sure how many, but it definitely needs more people than
checking for the same birthday within the whole group.

NOT having a hash firewall would reduce the complexity of that attack by
a constant factor: You can try all available hash functions to find the
This makes a difference in practice only if you can do the hash
calculations in parallel (it doesn't really help you to try both SHA-1
and RIPEMD-160, if you could do two SHA-1 calculations in the same time).

Thinking this in the "classical" setting again, it would mean to
associate more than one date to each person, besides the birthdate (say,
birthdate of boyfriend/girlfriend, etc). This appears to reduce the
amount of needed persons in proportion to the number of dates that you
associate to each (to keep the same number of dates/hashes available to

Given the complexities of the task of finding collisions in cryptography
and the number of available hash functions, this reduction does not
appear to be very significant.
It makes mainly sense if you can actually substitute a weak hash function.

cu, Sven

More information about the Gnupg-users mailing list