Difference between revisions of "MD6"

From The ECRYPT Hash Function Website
(→‎Cryptanalysis)
(33 rounds of the MD6 permutation)
 
(8 intermediate revisions by 3 users not shown)
Line 3: Line 3:
 
* Authors: Ron Rivest, Benjamin Agre, Daniel V. Bailey, Christopher Crutchfield, Yevgeniy Dodis, Kermin Elliott Fleming, Asif Khan, Jayant Krishnamurthy, Yuncheng Lin, Leo Reyzin, Emily Shen, Jim Sukha, Drew Sutherland, Eran Tromer, Yiqun Lisa Yin
 
* Authors: Ron Rivest, Benjamin Agre, Daniel V. Bailey, Christopher Crutchfield, Yevgeniy Dodis, Kermin Elliott Fleming, Asif Khan, Jayant Krishnamurthy, Yuncheng Lin, Leo Reyzin, Emily Shen, Jim Sukha, Drew Sutherland, Eran Tromer, Yiqun Lisa Yin
 
* Website: [http://groups.csail.mit.edu/cis/md6/ http://groups.csail.mit.edu/cis/md6/]  
 
* Website: [http://groups.csail.mit.edu/cis/md6/ http://groups.csail.mit.edu/cis/md6/]  
−
* Specification:
+
* NIST submission package: [http://csrc.nist.gov/groups/ST/hash/sha-3/Round1/documents/MD6.zip MD6.zip]
 +
 
  
 
<bibtex>
 
<bibtex>
Line 17: Line 18:
  
 
== Cryptanalysis ==
 
== Cryptanalysis ==
 +
 +
{| border="1" cellpadding="4" cellspacing="0" class="wikitable" style="text-align:center"                 
 +
|- style="background:#efefef;"                 
 +
|    Type of Analysis || Hash Function Part || Hash Size (n) || Parameters/Variants || Compression Function Calls || Memory Requirements ||  Reference
 +
|-                                       
 +
|  | non-randomness || reduced compression ||  || 18 rounds || ? || ? || [http://groups.csail.mit.edu/cis/md6/supmitted-2008-10-27/Supporting_Documentation/md6_report.pdf Aumasson,Meier]
 +
|-                 
 +
|  | key-recovery || reduced compression ||  || 15 rounds || ? || ? || [http://groups.csail.mit.edu/cis/md6/supmitted-2008-10-27/Supporting_Documentation/md6_report.pdf Dinur,Shamir]
 +
|-             
 +
|  | non-randomness || reduced permutation||  || 30 rounds || ? || ? || [http://www.dagstuhl.de/Materials/index.en.phtml?09031#Khovratovich,Dimitry Khovratovich]
 +
|- 
 +
|  | non-randomness || reduced permutation||  || 33 rounds || ? || ? || [http://fse2009rump.cr.yp.to/fe1a0e11287a9864c1d897a3110ebaa2.pdf, Khovratovich]
 +
|- 
 +
|  | collision || reduced compression ||  || 16 rounds || 2<sup>30</sup> || - || [http://ehash.iaik.tugraz.at/uploads/9/91/Khazaei_md6.txt Khazaei,Meier]
 +
|-                         
 +
|}                   
 +
 +
A description of this table is given [http://ehash.iaik.tugraz.at/wiki/Cryptanalysis_Categories#Individual_Hash_Function_Tables here].
  
  
−
* Aumasson, Meier: nonrandomness on the 18-round compression function (mentioned in original proposal text).
+
<bibtex>
−
* Dinur, Shamir: cube attack on the 15-round compression function (mentioned in original proposal text).
+
@misc{md6AM08,
 +
  author    = {Jean-Philippe Aumasson and Willi Meier},
 +
  title    = {Personal communication (nonrandomness on the reduced-round compression function)},
 +
  url        = {http://groups.csail.mit.edu/cis/md6/submitted-2008-10-27/Supporting_Documentation/md6_report.pdf},
 +
  howpublished = {Reported in the supporting documentation},
 +
  year      = {2008},
 +
}
 +
</bibtex>
 +
 
 +
<bibtex>
 +
@misc{md6DS08,
 +
  author    = {Itai Dinur and Adi Shamir},
 +
  title    = {Personal communication (key recovery on the reduced-round compression function)},
 +
  url        = {http://groups.csail.mit.edu/cis/md6/submitted-2008-10-27/Supporting_Documentation/md6_report.pdf},
 +
  howpublished = {Reported in the supporting documentation},
 +
  year      = {2008},
 +
}
 +
</bibtex>
 +
 
 +
<bibtex>
 +
@misc{md6K,
 +
author = {Dimitry Khovratovich},
 +
title = {Gaussian cryptanalysis of hash functions: collisions,
 +
preimages, distinguishers},
 +
url = {http://www.dagstuhl.de/Materials/index.en.phtml?09031#Khovratovich,%20Dimitry},
 +
howpublished = {Available online, abstract only},
 +
year = {2009},
 +
abstract = {Many attacks on hash functions can be reformulated in finding a hash
 +
execution with constraints being fixed values of internal variables. Those
 +
variables can be input or output bits, input of active S-boxes or AND
 +
operations, etc..
 +
 
 +
The constraints lead to a system of nonlinear equations, which sometimes
 +
can be solved with a fast algorithm resembling the Gaussian elimination. If a
 +
system has been solved then solutions can be produced with negligible time
 +
costs.
 +
 
 +
The main condition for the algorithm to succeed is relatively slow diffusion in
 +
the attacked primitive. Provided this we show how to attack AES as a hash
 +
function and prove that a 30-round MD6 compression function can be
 +
distinguished from the random oracle.
 +
 
 +
I will also show how it worked in practice in a GUI-tool.},
 +
}
 +
</bibtex>
 +
 
 +
<bibtex>
 +
@misc{md6K2,
 +
author = {Dimitry Khovratovich},
 +
title = {Nonrandomness of the 33-round MD6},
 +
url = {http://fse2009rump.cr.yp.to/fe1a0e11287a9864c1d897a3110ebaa2.pdf},
 +
howpublished = {FSE 2009 rump session, slides only},
 +
year = {2009},
 +
}
 +
</bibtex>
 +
 
 +
<bibtex>
 +
@misc{cubehashA08,
 +
  author    = {Shahram Khazaei and Willi Meier},
 +
  title    = {Collisions for 16-round MD6},
 +
  url = {http://ehash.iaik.tugraz.at/uploads/9/91/Khazaei_md6.txt},
 +
  howpublished = {NIST mailing list (local link)},
 +
  year = {2009},
 +
}
 +
</bibtex>

Latest revision as of 17:16, 3 March 2009

1 The algorithm

  • Authors: Ron Rivest, Benjamin Agre, Daniel V. Bailey, Christopher Crutchfield, Yevgeniy Dodis, Kermin Elliott Fleming, Asif Khan, Jayant Krishnamurthy, Yuncheng Lin, Leo Reyzin, Emily Shen, Jim Sukha, Drew Sutherland, Eran Tromer, Yiqun Lisa Yin
  • Website: http://groups.csail.mit.edu/cis/md6/
  • NIST submission package: MD6.zip


Ronald L. Rivest - The MD6 hash function -- A proposal to NIST for SHA-3

,2008
http://groups.csail.mit.edu/cis/md6/submitted-2008-10-27/Supporting_Documentation/md6_report.pdf
Bibtex
Author : Ronald L. Rivest
Title : The MD6 hash function -- A proposal to NIST for SHA-3
In : -
Address :
Date : 2008


2 Cryptanalysis

Type of Analysis Hash Function Part Hash Size (n) Parameters/Variants Compression Function Calls Memory Requirements Reference
non-randomness reduced compression 18 rounds ? ? Aumasson,Meier
key-recovery reduced compression 15 rounds ? ? Dinur,Shamir
non-randomness reduced permutation 30 rounds ? ? Khovratovich
non-randomness reduced permutation 33 rounds ? ? Khovratovich
collision reduced compression 16 rounds 230 - Khazaei,Meier

A description of this table is given here.


Jean-Philippe Aumasson, Willi Meier - Personal communication (nonrandomness on the reduced-round compression function)

,2008
http://groups.csail.mit.edu/cis/md6/submitted-2008-10-27/Supporting_Documentation/md6_report.pdf
Bibtex
Author : Jean-Philippe Aumasson, Willi Meier
Title : Personal communication (nonrandomness on the reduced-round compression function)
In : -
Address :
Date : 2008

Itai Dinur, Adi Shamir - Personal communication (key recovery on the reduced-round compression function)

,2008
http://groups.csail.mit.edu/cis/md6/submitted-2008-10-27/Supporting_Documentation/md6_report.pdf
Bibtex
Author : Itai Dinur, Adi Shamir
Title : Personal communication (key recovery on the reduced-round compression function)
In : -
Address :
Date : 2008

Dimitry Khovratovich - Gaussian cryptanalysis of hash functions: collisions,

preimages, distinguishers

,2009
http://www.dagstuhl.de/Materials/index.en.phtml?09031#Khovratovich,%20Dimitry
Bibtex
Author : Dimitry Khovratovich
Title : Gaussian cryptanalysis of hash functions: collisions, preimages, distinguishers
In : -
Address :
Date : 2009

Dimitry Khovratovich - Nonrandomness of the 33-round MD6

,2009
http://fse2009rump.cr.yp.to/fe1a0e11287a9864c1d897a3110ebaa2.pdf
Bibtex
Author : Dimitry Khovratovich
Title : Nonrandomness of the 33-round MD6
In : -
Address :
Date : 2009

Shahram Khazaei, Willi Meier - Collisions for 16-round MD6

,2009
http://ehash.iaik.tugraz.at/uploads/9/91/Khazaei_md6.txt
Bibtex
Author : Shahram Khazaei, Willi Meier
Title : Collisions for 16-round MD6
In : -
Address :
Date : 2009
Retrieved from "https://ehash.iaik.tugraz.at/index.php?title=MD6&oldid=3011"