5
$\begingroup$

I'm aware that individually, each has its weaknesses (especially CRC32), but is it feasible that a file could be created to falsely match all three?

$\endgroup$
  • $\begingroup$ I think it would be difficult to actively intend to get a simultaneous clash on all three given that they use different algorithms. Clashes are possible in each, sure, and you can engineer a clash in each if you are determined but I would have thought it would be difficult to get a clash in all three at the same time. It feels like the sort of thing that might be possible but technically unfeasible given the amount of effort required. Personally I'd be curious to see how probable this is. $\endgroup$ – Mokubai Aug 12 '19 at 15:01
  • 2
    $\begingroup$ this Q&A has the (positive) answer except for the CRC part $\endgroup$ – SEJPM Aug 12 '19 at 15:22
  • $\begingroup$ Is this is some attempt at synthesizing a "faster" hash because the old/simpler algorithms are quicker? They're not. $\endgroup$ – Nick T Aug 13 '19 at 4:05
  • 1
    $\begingroup$ @NickT These old, inscecure hashes are being used for compatibility with old software. Removing these hashes is not an option, so I was asking to find out if it is worth adding something better. I'd rather not have to add another one as it means extra work for people using the old software - they'd have to use different software to generate the new hash (e.g. SHA256). As I understand it, its not feasible for the common person to find a collision for all three at the same time. $\endgroup$ – Hiccup Aug 13 '19 at 13:51
8
$\begingroup$

Finding a simultaneous collision for all three would take the effort of approximately $2^{72}$ SHA-1 compression function evaluations.

The overall idea would be to take the general $2^{67}$ idea found in the answer to How hard is it to generate a simultaneous MD5 and SHA1 collision? and perform the attack 33 successive times (generating 33 places in the hash image where we can take either $X_i$ or $Y_i$ without affecting either the MD5 or SHA-1 hash).

That'll give us a total of $2^{33}$ images with all the same MD5 and SHA-1 hash; there must be a pair of images with the same CRC-32 value as well, and so that solves the problem.

Whether $2^{72}$ operations is in the realm of feasibility is another question entirely...

| improve this answer | |
$\endgroup$
  • $\begingroup$ I was brought here by the curiosity of the question and I'm a bit hung up on the feasibility side. Yes it is technically possible but 2^72 is a number that my mind just spits back as "impossibly huge". Does this mean it is within the realms of a guy sitting in a basement with an old i3 box or is it all the computers in the world running until the eventual heat death of the universe? $\endgroup$ – user71151 Aug 12 '19 at 15:47
  • 2
    $\begingroup$ @Mokubai: it's probably closer to 'if the NSA (or possibly Goggle or Amazon) decide to devote all their assets on this one problem, they could probably do it in a not-unreasonable amount of time...'. $\endgroup$ – poncho Aug 12 '19 at 15:56
  • 1
    $\begingroup$ Okay, so it's within the realms of possibility of nation-state actors, but probably beyond your average malware or script-kiddie. That is unless he has a pretty large botnet... Not unreasonable to achieve, but probably costs far more than it is ever going to worth unless the target is a) incredibly paranoid (to be using/checking all three hashes) and b) extremely high value. Thank you for indulging my curiosity :) $\endgroup$ – user71151 Aug 12 '19 at 16:14
  • 5
    $\begingroup$ The Bitcoin network has a hash rate of $2^{72}$ hashes every three days. It's more than one guy in a basement but far less than heat death of the universe. It's also probably far less than what the NSA could manage. $\endgroup$ – djao Aug 12 '19 at 18:51
  • 4
    $\begingroup$ I was half expecting to see an answer of "Yeah, these two files." $\endgroup$ – Joshua Aug 12 '19 at 22:26
4
$\begingroup$

The following method is faster than poncho's answer, and it allows you to choose the CRC value.

  1. First, generate a $2^{96}$ SHA1 multicollision.

  2. Using linearity of CRCs, find a set of $\approx 2^{64}$ distinct messages in the multicollision with the target CRC value. See below for details.

  3. Simply look for an MD5 collision within this set of $\approx 2^{64}$ messages.

What do we gain? Instead of running the full SHA1/MD5 simultaneous collision attack $33$ times, we only run it once with an increased effort in steps 1 and 3.
More precisely, using the value of $2^{63.1}$ SHA1 compressions from the SHAttered paper, we require the equivalent of $\approx 2^{69.7}$ SHA1 compressions in step 1, and $\approx 2^{70}$ MD5 compressions in step 3. Ignoring the ridiculously high memory cost of naïve birthday search in step 3, and sloppily equating the costs of SHA1 and MD5 compressions, the total cost comes out as $\approx 2^{70.9}$ compression function calls.

(Note that this number cannot be compared directly with poncho's coarser estimate; in reality, the speedup factor should be closer to $\approx10$.)


Step 2

Let us look at how taking different combinations of the multicollision blocks affects the CRC value. Suppose at position $i$ we have a choice between two blocks $x_i$ and $y_i$, and that we use a bit $c_i$ to select between the two. Thus, set $$ \begin{equation} \label{eq:c_chooses_xy} \tag{$\ast$} z_i=\begin{cases}x_i&\text{if $c_i=0$;}\\y_i&\text{if $c_i=1$.}\end{cases} \end{equation} $$

It is well-known that CRCs are linear. Concretely, this means that for each block $i$ of the multicollision, choosing between $x_i$ and $y_i$ incurs a fixed differential $\delta_i$ in the final output, independent of the other choices: $$ \mathrm{CRC}(z_1\Vert z_2\Vert\dots\Vert y_i\Vert\dots\Vert z_{96}) = \delta_i\oplus \mathrm{CRC}(z_1\Vert z_2\Vert\dots\Vert x_i\Vert\dots\Vert z_{96}) \,\text. $$

Therefore, $$ \mathrm{CRC}(z_1\Vert z_2\Vert\dots\Vert z_{96}) = \mathrm{CRC}(x_1\Vert x_2\Vert\dots\Vert x_{96}) \oplus \bigoplus_{i=1}^{96} c_i \delta_i \,\text, $$ which is a linear equation over $\mathbb F_2$ in the variables $c_1,\dots,c_{96}$!


To find $2^{64}$ solutions $(c_1\ \dots\ c_{96})\in\mathbb F_2^{96}$, first compute all the $\delta_i$-values, interpreted as length-$32$ vectors over $\mathbb F_2$, to form the matrix $$ M := \left(\begin{array}{c} \delta_1\\\hline \vdots\\\hline \delta_{96} \end{array}\right) \in\mathbb F_2^{96\times32} \,\text. $$

Then, for a given target CRC value $t\in\mathbb F_2^{32}$, compute a solution $\gamma\in\mathbb F_2^{96}$ to the equation $$ \gamma\cdot M = t-s \,\text. $$ Note that such a solution is almost guaranteed to exist since the probability that $M$ has the maximal possible rank $32$ is greater than $1-2^{-64}$ when modelling the $\delta_i$ as uniformly random in $\mathbb F_2^{32}$. Also compute $64$ independent vectors $v_1,\dots,v_{64}\in\mathbb F_2^{96}$ in the (left) kernel of $M$. (These always exist due to the dimensions.)

Now finally, letting $c$ run through all vectors of the form $$ c = \gamma + \sum_{i=1}^{64} \alpha_i v_i \,\text, $$ where $\alpha_i\in\mathbb F_2$, and assembling our multicollision messages according to $\eqref{eq:c_chooses_xy}$ yields our desired $2^{64}$ messages, all with the same SHA1 hash, and all with the same chosen CRC value!

| improve this answer | |
$\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.