2
$\begingroup$

I came across some source code that loosely does the below in order to achieve a 32 bit hash.

The input string is passed through MD5 to get 16 bytes Hash (as usual). Then the 16 bytes are split into 4 byte words . Each of these words are $\oplus$ with each other in order to get a final 4 byte word, this is considered as a 32 bit hash.

The application does not really care about security in sense of pre-image resistance etc. but all it wants is Collision Resistance.

So, does the above guarantee no collisions (any better than birthday-bound)? Of course it depends on the input string's entropy etc., but given that we don't know before hand what possible strings could be passed as input: how do we analyze such scheme for collisions?

$\endgroup$
  • $\begingroup$ As for the last question, I guess we don't analyze such schemes as $2^{32}$ let alone $2^{16}$ are considered very secure. MD5 cannot be used for collision resistance anymore; as MD5 collisions can be created, it doesn't take much imagination that if you can get the same MD5 output that any deterministic algorithm performed on just the MD5 output must result in the same value, and will therefore also have collisions. $\endgroup$ – Maarten - reinstate Monica Oct 6 '14 at 17:31
  • $\begingroup$ Sounds like overkill to me. If all you want is collision resistance, then why not use a simple algorithm like djb2? $\endgroup$ – squeamish ossifrage Oct 6 '14 at 18:34
  • $\begingroup$ @squeamishossifrage do you have any references on the collision resistance of djb2? If it has not been properly vetted by the cryptographic community, then I wouldn't use it in a case where we don't want collisions (that said, a work factor of $2^{16}$ isn't much, so I wouldn't use that either). $\endgroup$ – mikeazo Oct 6 '14 at 18:44
  • $\begingroup$ @mikeazo No, but the OP doesn't seem too bothered about cryptographic hashing. (32 bits is nowhere near adequate for this purpose.) $\endgroup$ – squeamish ossifrage Oct 6 '14 at 18:51
2
$\begingroup$

As far as I understand, the scheme is:

$$MD5(x) = a_1||a_2||a_3||a_4 \, \, \Longrightarrow \, \, H(x) = a_1 \oplus a_2 \oplus a_3 \oplus a_4,$$

with $a_i$ 4-byte/32-bit words.

Obviously you can't guarantee a unique 32-bit hash from an unbounded domain, due to the pidgeonhole principle. Neither can you make finding collisions infeasible, since $2^{16}$ MD5 invocations takes a few seconds if that.

If MD5 was an ideal 128-bit hash, it wouldn't matter whether you take the first 4 bytes, XOR the 32-bit words or anything else. All of them would be ideal 32-bit hashes. However, it isn't and you can find collisions in about $2^{33}$ operations. That doesn't directly lead to an attack on this, because it's slower than brute force, but it's possible it could be extended. There's a chance the XOR could make such an attack slightly harder or easier than truncation, but it really doesn't matter with a 32-bit hash since brute force is sufficient.

Assuming you don't let an attacker control the inputs (since that would be totally broken), the question isn't about the collision resistance, but pseudorandomness of MD5. MD5 is still thought to behave like a PRF in the sense that if the input strings are chosen "randomly", the output is uniformly random as well. (Which is why HMAC-MD5 is secure.) XOR doesn't affect that, so you should have the 32-bit hash behave like a PRF as well.

So, with inputs that aren't under the attacker's control, you should see collisions at the birthday bound. No sooner or later, other than what variance you expect with a 32-bit hash. However, there's no real benefit to the XOR, so you might as well just use the first 4-byte word.

$\endgroup$
0
$\begingroup$

You cannot escape the birthday bound - it will eat your lunch lunch every time.

MD5 has a good uniform distribution, so should your algorithm. Since it outputs 32-bit values, you should expect collisions after around $\sqrt{\frac{\pi}{2}2^{32}} = 82137$ hashes.

$\endgroup$
  • 2
    $\begingroup$ Why exactly $\frac{\pi}{2}$? Never heard that before. $\endgroup$ – Nova Oct 7 '14 at 21:22
  • $\begingroup$ i have written a bruteforce approach for MD5 in java for the above and i get collisions much sooner than 65536 limit which is 2^16. with SHA-256 am not getting the same $\endgroup$ – sashank Oct 7 '14 at 21:57
  • $\begingroup$ @sashank that seems strange. Are you willing to share your code? I'd like to see what I get. $\endgroup$ – mikeazo Oct 7 '14 at 23:03
  • $\begingroup$ @mikeazo not sure if you have noticed, it is not for entire MD5 but the tweaked version mentioned above, code is here pastebin.com/fZ1LR9as $\endgroup$ – sashank Oct 8 '14 at 7:54
  • 1
    $\begingroup$ @sashank, I really hate Java, but here goes. Average for MD5 89031 and SHA-256 78676. Well within reason. $\endgroup$ – otus Oct 8 '14 at 9:06
-2
$\begingroup$

Use something more collision resistant like SHA... I can't find any hashes that are completely collision proof, but sha at least decreases the collisions...

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.