Anyone knows something else worth mentioning ?
François Grieu
--
Hans Dobbertin: Cryptanalysis of MD5 Compress (1996)
<http://www-cse.ucsd.edu/users/bsy/dobbertin.ps>
<http://citeseer.ist.psu.edu/dobbertin96cryptanalysis.html>
This gives a numerical example of I, X1, X2 with
MD5compress(I,X1) = MD5compress(I,X2)
1-bit difference between X1 and X2.
Of course the value of I is not the initial MD5 value,
nor occuring in any known message, else the full MD5
would be broken.
--
Hans Dobbertin: The Status of MD5 After a Recent Attack
in CryptoBytes Volume 2 Number 2 - 1996
<ftp://ftp.rsasecurity.com/pub/cryptobytes/crypto2n2.pdf>
<http://citeseer.ist.psu.edu/243938.html>
More detailed account of the same result, with partial
explanation on how it was obtained.
--
B. den Boer and A. Bosselaers, Collisions for the compression
function of MD5.
Proceedings Eurocrypt'93
<http://citeseer.ist.psu.edu/289874.html>
<http://www.esat.kuleuven.ac.be/~cosicart/pdf/AB-9300.pdf>
This gives example, and method, to find I1, I2, X with
MD5compress(I1,X) = MD5compress(I2,X)
4-bit difference between I1 and I2.
--
P.C. van Oorschot and M.J. Wiener:
Parallel Collision Search with Cryptanalytic Applications
Journal of Cryptology, vol. 12, no. 1, 1999
<http://www.scs.carleton.ca/~paulv/papers/JoC97.pdf>
<http://www3.sympatico.ca/wienerfamily/Michael/MichaelPapers/pcs.pdf>
Expands on 1994 and 1996 works by the same authors.
This is an educated brute-force attack with cost about
2^64 hashes, and relatively little memory.
Best practical attack technique published, ongoing use at
<http://www.md5crk.com>
--
Thomas A. Berson: Differential Cryptanalysis Mod 2^32
with Applications to MD5.
Proceedings Eurocrypt'92
<http://cnscenter.future.co.kr/resource/crypto/algorithm/Symmetric/ec92Berson.pdf>
I do not even get what the author takes mod 2^32, nor what
results are claimed.
I'll add these to the md5crk site. Except for Berson's find...that's
just silly. It's trying to to DC on the mod 2^32 + operation.
JLC
Francois Grieu <fgr...@francenet.fr> wrote:
> Below is my annotated bibliography on attacks against MD5
> (or its round function).
> Anyone knows something else worth mentioning ?
> Fran?ois Grieu
> --
> --
> --
> --
> --
--
> Francois Grieu <fgr...@francenet.fr> wrote:
>> Below is my annotated bibliography on attacks against MD5
>> (or its round function).
>>
>> Anyone knows something else worth mentioning ?
>>
>> (..)
>> Thomas A. Berson: Differential Cryptanalysis Mod 2^32
>> with Applications to MD5.
>> Proceedings Eurocrypt'92
<http://cnscenter.future.co.kr/resource/crypto/algorithm/Symmetric/ec92Berson.pdf>
>>
>> I do not even get what the author takes mod 2^32, nor what
>> results are claimed.
> I'll add these to the md5crk site. Except for Berson's find...that's
> just silly. It's trying to to DC on the mod 2^32 + operation.
For each of the four MD5 round functions, Berson derives somewhat
systematically message differentials that give a high probability
of collision. He however claims no actual result on the full MD5.
While clearly not a breakthru, I do not discount Berson's work as
"silly". Reading it again, maybe now I get the idea:
consider f(m+d)-f(m) with operations caried mod 2^32, on each of the
four MD5 registers. I stand unconvinded that this approach is better
than redular DC in practice, but I'm ready to believe that it
simplifies derivation of differential probability in the case of MD5.
Sadly, I somewhat fail to exactly reproduce Berson's results.
For example the paper claims that for the message differential
W[ 8] += 1<<11;
W[12] += 1<<31;
W[13] += 1<<26;
the collision probability for the second round is 2^-2,
but experimentaly I get 2^-5. Did I miss something?
François Grieu