Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

Let $h$ be a bitstring and let $P(h, n)$ be the n-bit prefix of $h$. A partial collision of length $n$, for a hash function $H$ is a pair $(x,y)$, such that $P(H(x),n)=P(H(y),n)$.

What is known about this type of collisions? I'm particularly interested in md5. Can rainbow tables be adapted to quickly look for these? What values of $n$ are feasible to bruteforce (perhaps in an optimized way, like with rainbow tables).

I'd also like to know about the pre-image case: given $x$ and $P(H(x),n)$, how to find $y$ such that it's a $n$-partial collision for $x$.

share|improve this question
1  
Silly question: we know how to make total collisions with MD5; why are you interested in partial collisions? –  poncho Jun 19 '12 at 20:45
    
@poncho: because it might be cheaper (?). Plus collisions don't solve the preimage problem. –  qwer Jun 19 '12 at 20:51
    
Take a look at HashCalc –  mikeazo Jun 21 '12 at 13:00
add comment

1 Answer 1

up vote 3 down vote accepted

If $H$ is secure in the random oracle model and of width at least $n$, then $x\mapsto P(H(x),n)$ is also secure, inasmuch as an $n$-bit hash can be (proof sketch: any attack that distinguishes $x\mapsto P(H(x),n)$ from a random oracle is trivially turned into a distinguisher for $H$). The converse is not true.


Finding a collision requires $O(2^{n/2})$ queries to the oracle (or evaluations of the inner function of $H$). More precisely it is expected to require $o(\sqrt{\pi/2}\cdot2^{n/2})$ distinct queries, and odds of success reach 50% after $o(\sqrt{\ln 4}\cdot2^{n/2})$ such queries (that's the generalized birthday problem). The standard paper on how to exhibit such collisions is Parallel Collision Search with Cryptanalytic Applications.

Finding a preimage is expected to require about $2^n$ queries to the oracle (I plan to dig out the right formulas someday). It is possible to speed-up an attack by pre-computation, e.g. with rainbow tables, in particular if the set of possible messages is known, or if $n$ is small enough.


Now we restrict to MD5, thus $n\le 128$.

The difficulty of finding collisions is about as for a good hash ($\approx 1.3\cdot2^{n/2}$ MD5 inner rounds) when the messages are tried without consideration of the inner structure of the MD5 round function (e.g. random messages or words from a dictionary). Without constraints on the message, finding collisions among messages of at least 1024-bit has been possible for any $n$ since that breakthrough, works even with some constraints, now has little cost, and was recently made possible with 512-bit messages. The lower $n$ is, the easier it gets. AFAIK there is no shortcut for heavily constrained messages, e.g. passwords of less than 10 ASCII characters.

The difficulty of finding a preimage is about as for a good hash (about $2^n$ MD5 inner rounds) when the messages are tried without consideration of the inner structure of the MD5 round function, nor knowledge on the origin of the target value. I am not aware of a practical method better than that, except when the message is in a known set smaller than $2^n$, which is when rainbow tables shine; in that case, I do not see that lowering $n$ changes the cost.

share|improve this answer
add comment

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.