After reading "SHA-1 is a Shambles" ( see: https://sha-mbles.github.io ), I decided to design a minimal working example of chosen-prefix collision attack. Hopefully it would cost considerably less than 1 BTC in computer time, so that students could recreate the experiment on a personal computer.

I found the following example in one sitting of about an hour:

expr1[pr_] := Hold[With[{prefix = pr}, Print["Hello World!"]]]
expr2[pr_] := Hold[With[{prefix = pr}, Print["Goodbye World!"]]]

prefix1 = "A}~ppqqrrssttuuvvwwxxyyz";
prefix2 = "{pnqorpsqtrusvtwuxvywz";
exprs = {expr1[prefix1], expr2[prefix2]};

ColumnForm[exprs]
Equal @@ (Hash[#, "Adler32"] & /@ exprs)
ReleaseHold /@ exprs; 

Output:

The hash comparison seems to prove that "Hello" = "Goodbye", but obviously this should never be true! The hash function "Adler32" can be broken, thus it is insufficient for proving identities, especially between potentially malicious executable functions. Remember Voltaire preceding La Terreur: "Certainement qui est en droit de vous rendre absurde est en droit de vous rendre injuste" (source, alternative translation: "Certainly who is in the right to render you absurd is in the right to deliver you to injustice.").

This example involves no analysis of the Adler32 standard, so better prefixes can probably be found. What are the minimal prefixes for this example? What is the algorithm for calculating minimal prefixes in any case, i.e. for any choice of a pair of executable functions?

--Brad

Idea collision! Don't know when I found this, but here is the original: https://www.win.tue.nl/hashclash/SoftIntCodeSign/