Take the 2-minute tour ×
Information Security Stack Exchange is a question and answer site for Information security professionals. It's 100% free, no registration required.

I'm writing a business-language report about MD5. In my search a found a paper by Yu Sasaki and Kazumaro Aoki explaining their 2123.4 pre-image attack on MD5.

I know that it has something to do with the feasibility (or in some cases, even the possibility) of an attack, but I don't have a sound understanding of what computational complexity exactly is .

So, what's computational complexity in that context? And at which limit we can say this attack not feasible or this attack is not possible?

share|improve this question

1 Answer 1

up vote 11 down vote accepted

"Computational complexity" is a measure of the CPU / RAM effort involved in the execution of an algorithm. In the case of an attack over a cryptographic algorithm (e.g. MD5), complexity is measured relatively to the attacked algorithm. MD5 processes data by 512-bit chunks, so it has an "elementary cost" which is the amount of CPU it takes to hash a small message (of 0 to 447 bits, to be precise). Since MD5 offers a 128-bit output, so, for a preimage attack (finding m such that MD5(m) = x, where x is given), the generic "get lucky" attack has average cost 2128 times the cost of hashing a small message. Indeed, the "get lucky" attack is about choosing random m until a match is found, which, for a "perfect" hash function (a random oracle) works with probability 2-128 for each try.

Therefore, we express "CPU effort" as the number of times the attacked function could be evaluated with that many invested clock cycles. This measuring unit has the nice property of easily showing whether a function is "academically broken" or not. The "get lucky" attack is generic: it works for every hash function, regardless of its perfection. The average cost of that attack is 2n for a hash function with a n-bit output. So any attack which does better, even slightly, counts as a "break". In the case of MD5, the presented attack has cost 2123.4, which means that it is about 20 times faster than the "get lucky" attack. But it still completely infeasible in practice. Realistic limit for a powerful attacker (say, someone with the budget of Google) is around 280 invocations of MD5.

share|improve this answer
    
Thank you! This is exactly the answer I was looking for. –  Adnan Apr 18 '13 at 12:20

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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