# Partial collisions for md5

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$.

-

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
– mikeazo♦ Jun 21 '12 at 13:00

## 1 Answer

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.

-
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 32, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.3, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "plain"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9196205735206604, "perplexity_flag": "middle"}