Difference between revisions of "MD6"
From The ECRYPT Hash Function Website
m |
Crechberger (talk | contribs) (added new distinguisher) |
||
| Line 23: | Line 23: | ||
| Type of Analysis || Hash Function Part || Hash Size (n) || Parameters/Variants || Compression Function Calls || Memory Requirements || Reference | | Type of Analysis || Hash Function Part || Hash Size (n) || Parameters/Variants || Compression Function Calls || Memory Requirements || Reference | ||
|- | |- | ||
| + | | | non-randomness || reduced compression || || 30 rounds || ? || ? || [http://www.dagstuhl.de/Materials/index.en.phtml?09031#Khovratovich,%20Dimitry Khovratovich] | ||
| + | |- | ||
| | non-randomness || reduced compression || || 18 rounds || ? || ? || [http://groups.csail.mit.edu/cis/md6/supmitted-2008-10-27/Supporting_Documentation/md6_report.pdf Aumasson,Meier] | | | 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] | | | key-recovery || reduced compression || || 15 rounds || ? || ? || [http://groups.csail.mit.edu/cis/md6/supmitted-2008-10-27/Supporting_Documentation/md6_report.pdf Dinur,Shamir] | ||
|- | |- | ||
| Line 49: | Line 51: | ||
howpublished = {Reported in the supporting documentation}, | howpublished = {Reported in the supporting documentation}, | ||
year = {2008}, | 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> | ||
Revision as of 13:43, 11 January 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
BibtexAuthor : 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 | 30 rounds | ? | ? | Khovratovich | |
| non-randomness | reduced compression | 18 rounds | ? | ? | Aumasson,Meier | |
| key-recovery | reduced compression | 15 rounds | ? | ? | Dinur,Shamir |
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
BibtexAuthor : 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
BibtexAuthor : 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
