Ttdfjt

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?

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

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 $$
beginequation
labeleq:c_chooses_xy
tag$ast$
z_i=begincasesx_i&textif $c_i=0$;\y_i&textif $c_i=1$.endcases
endequation
$$

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:
$$
mathrmCRC(z_1Vert z_2VertdotsVert y_iVertdotsVert z_96)
=
delta_ioplus
mathrmCRC(z_1Vert z_2VertdotsVert x_iVertdotsVert z_96)
,text.
$$

Therefore,
$$
mathrmCRC(z_1Vert z_2VertdotsVert z_96)
=
mathrmCRC(x_1Vert x_2VertdotsVert 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)inmathbb 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(beginarrayc
delta_1\hline
vdots\hline
delta_96
endarrayright)
inmathbb F_2^96times32
,text.
$$

Then, for a given target CRC value $tinmathbb F_2^32$, compute a solution $gammainmathbb F_2^96$ to the equation
$$
gammacdot 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_64inmathbb 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_iinmathbb F_2$, and assembling our multicollision messages according to $eqrefeq:c_chooses_xy$ yields our desired $2^64$ messages, all with the same SHA1 hash, and all with the same chosen CRC value!