1
$\begingroup$

So I've heard that MD5 is broken because it's possible to engineer collisions. So instead we should use, say, SHA256. The problem which SHA256 digests is that they are long. So I've come up with this:

function mdsha( input ) { return md5( sha256( input ) ); }

So I can retain MD5 digest lengths and avoid malicious collisions.

Is my scheme sound?

$\endgroup$
10
  • 1
    $\begingroup$ It depends. Do you consider $2^{64}$ SHA-256 evaluations to be infeasible (given that the current complete bitcoin mining network does something in a similar scale every second)? If not this scheme isn't sound. $\endgroup$ – SEJPM May 9 '16 at 19:06
  • $\begingroup$ Why is it 2^64? MD5 digests are 128 bit... $\endgroup$ – John Elliot V May 9 '16 at 19:23
  • $\begingroup$ @JohnElliotV Collision resistance on the other hand is half the amount of bits because of the birthday problem. That's why hash function outputs are generally double the size of keys for symmetric ciphers. E.g. take a look at keylength.com / ECRYPT II recommendations. $\endgroup$ – Maarten Bodewes May 9 '16 at 19:26
  • $\begingroup$ I was thinking that I'll use the last 160 bits (40 hex chars) of a SHA256 digest for my purposes. Would that at least be more secure against malicious collisions than MD5? $\endgroup$ – John Elliot V May 9 '16 at 19:29
  • 2
    $\begingroup$ Absolutely. As indicated, it's more standardized to use the first 40 characters though (i.e. the first 160 bits). Note that MD5 hashes are 128 bits, not 160 bits, so you would go outside of MD5 output size. SHA-1 uses 160 bits. $\endgroup$ – Maarten Bodewes May 9 '16 at 19:31
4
$\begingroup$

Your scheme is likely sound as the SHA-256 hash limits the input to the MD5 hashing function. If this was not so it could be possible (though very hard) to create a collision because of the break.

Generally it is more secure to simply use the 128 leftmost bits of the output of SHA-256. SHA-3 - or rather SHAKE256 - would be even better if available.

Keep in mind that 128 bits is relatively small with regards to collision resistance due to the birthday problem. The birthday problem will reduce the collision resistance to half the output size. It may not directly be an issue, but you may want to consider upgrading your protocol to use a larger hash value.

$\endgroup$
11
  • 1
    $\begingroup$ The last paragraph is important. 128-bit hash means ~$2^{64}$ collision attack, which is expensive, but plausible. One option to increase collision resistance would be an iterated hash. $\endgroup$ – otus May 9 '16 at 19:23
  • $\begingroup$ I tried searching for "iterated hash" but still don't understand what that means. How do I do an iterated hash..? $\endgroup$ – John Elliot V May 9 '16 at 19:46
  • $\begingroup$ @JohnElliotV H(H(H...H(M)...)) where the number of hashes is large, e.g. 10K or 100K. The idea is that an attacker also needs to perform all those hashes, but $2^{64}$ times to perform the attack. Needless to say, this will cost you CPU cycles. $\endgroup$ – Maarten Bodewes May 9 '16 at 19:50
  • $\begingroup$ Got it. Thanks. I have rather humble security requirements (I'm not trying to beat the NSA!) and I'd rather avoid paying the computational tax I would have to pay to do the iterated hashing so I think I'll just take 168 bits from SHA256 and be done. (Because: 42!) $\endgroup$ – John Elliot V May 9 '16 at 19:58
  • 1
    $\begingroup$ @JohnElliotV if you want computation to be faster, and you have a 64-bit system, SHA-512 will be faster with 64-bit code $\endgroup$ – Richie Frame May 9 '16 at 23:53

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.