Questions about generating keys (hash firewalls)
Sven Radde
sven at radde.name
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
collision.
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
compare).
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