MD6: Difference between revisions

From Wikipedia, the free encyclopedia
Browse history interactively
← Previous edit
Content deleted Content added
VisualWikitext
AnomieBOT (talk | contribs)
Bots
6,261,871 edits
m Dating maintenance tags: {{Dead link}}
MrsGusted (talk | contribs)
33 edits
Add cryptanalysis
 
(19 intermediate revisions by 15 users not shown)
Line 1: Line 1:
{{Short description|Cryptographic hash function}}
{{other uses|MD-6 (disambiguation)}}
{{Other uses|MD-6 (disambiguation){{!}}MD-6}}
{{Infobox cryptographic hash function
{{Infobox cryptographic hash function
| name = MD6
| name = MD6
Line 5: Line 6:
| caption =
| caption =
<!-- General -->
<!-- General -->
| designers = [[Ronald Rivest]], Benjamin Agre, Dan Bailey, Sarah Cheng, Christopher Crutchfield, Yevgeniy Dodis, Kermin Fleming, Asif Khan, Jayant Krishnamurthy, Yuncheng Lin, Leo Reyzin, Emily Shen, Jim Sukha, Eran Tromer, Yiqun Lisa Yin
| designers = [[Ronald Rivest]], Benjamin Agre, Dan Bailey, Sarah Cheng, Christopher Crutchfield, Yevgeniy Dodis, Kermin Fleming, Asif Khan, Jayant Krishnamurthy, Yuncheng Lin, Leo Reyzin, Emily Shen, Jim Sukha, Eran Tromer, [[Yiqun Lisa Yin]]
| publish date = 2008
| publish date = 2008
| series = [[MD2 (cryptography)|MD2]], [[MD4]], [[MD5]], MD6
| series = [[MD2 (cryptography)|MD2]], [[MD4]], [[MD5]], MD6
Line 16: Line 17:
| structure = Merkle tree
| structure = Merkle tree
| rounds = Variable. Default, Unkeyed=40+[d/4], Keyed=max(80,40+(d/4))
| rounds = Variable. Default, Unkeyed=40+[d/4], Keyed=max(80,40+(d/4))
<ref name=MD6Report>{{cite web
⚫
<ref name=MD6Report>[[Ronald L. Rivest]] et Al., [http://groups.csail.mit.edu/cis/md6/submitted-2008-10-27/Supporting_Documentation/md6_report.pdf ''The MD6 Hash Function''], Crypto 2008</ref>
| author = [[Ronald L. Rivest]]
| cryptanalysis =
| display-authors = etal
⚫
| url = http://groups.csail.mit.edu/cis/md6/submitted-2008-10-27/Supporting_Documentation/md6_report.pdf
| title = The MD6 Hash Function
| access-date = 2024-01-29
| archive-date = 2017-08-12
| archive-url = https://web.archive.org/web/20170812072847/https://groups.csail.mit.edu/cis/md6/submitted-2008-10-27/Supporting_Documentation/md6_report.pdf
| url-status = dead
⚫
}}
⚫
</ref>
| cryptanalysis = [[Key-recovery attack]] of a 14-round MD6 function in 2<sup>22</sup> operations.<ref>{{cite book | last=Aumasson | first=Jean-Philippe | last2=Dinur | first2=Itai | last3=Meier | first3=Willi | last4=Shamir | first4=Adi | title=Fast Software Encryption | chapter=Cube Testers and Key Recovery Attacks on Reduced-Round MD6 and Trivium | publisher=Springer Berlin Heidelberg | publication-place=Berlin, Heidelberg | volume=5665 | date=2009 | isbn=978-3-642-03316-2 | doi=10.1007/978-3-642-03317-9_1 | page=1–22}}</ref>
}}
}}

The '''MD6 Message-Digest Algorithm''' is a [[cryptographic hash function]]. It uses a [[Merkle tree]]-like structure to allow for immense parallel computation of hashes for very long inputs. Authors claim a performance of 28 [[cycles per byte]] for MD6-256 on an [[Intel Core 2 Duo]] and provable resistance against [[differential cryptanalysis]].<ref>
The '''MD6 Message-Digest Algorithm''' is a [[cryptographic hash function]]. It uses a [[Merkle tree]]-like structure to allow for immense parallel computation of hashes for very long inputs. Authors claim a performance of 28 [[cycles per byte]] for MD6-256 on an [[Intel Core 2 Duo]] and provable resistance against [[differential cryptanalysis]].<ref>{{cite web
{{cite web
| author = [[Ronald L. Rivest]]
| author = [[Ronald L. Rivest]]
| url = http://people.csail.mit.edu/rivest/Rivest-TheMD6HashFunction.ppt
| url = http://people.csail.mit.edu/rivest/Rivest-TheMD6HashFunction.ppt
| title = The MD6 hash function A proposal to NIST for SHA-3
| title = The MD6 hash function A proposal to NIST for SHA-3
| access-date = 2008-10-07
⚫
}}
| archive-date = 2020-11-09
(Microsoft PowerPoint file)
| archive-url = https://web.archive.org/web/20201109011321/http://people.csail.mit.edu/rivest/Rivest-TheMD6HashFunction.ppt
⚫
</ref>
| url-status = dead
}}
(Microsoft PowerPoint file)</ref> The [[source code]] of the [[reference implementation]] was released under [[MIT license]].<ref>[http://groups.csail.mit.edu/cis/md6/diffamp/README.txt readme.txt]</ref>


Speeds in excess of 1 GB/s have been reported to be possible for long messages on 16-core CPU architecture.<ref name=MD6Report/>
Speeds in excess of 1 GB/s have been reported to be possible for long messages on 16-core CPU architecture.<ref name=MD6Report/>


⚫
In December 2008, Douglas Held of [[Fortify Software]] discovered a [[buffer overflow]] in the original MD6 hash algorithm's reference implementation. This error was later made public by [[Ron Rivest]] on 19 February 2009, with a release of a corrected reference implementation in advance of the Fortify Report.<ref>{{cite web | url=http://blog.fortify.com/repo/Fortify-SHA-3-Report.pdf | title=Fortify-SHA-3-Report | url-status=dead | archiveurl=https://web.archive.org/web/20120222155656/http://blog.fortify.com/repo/Fortify-SHA-3-Report.pdf | archivedate=2012-02-22 }}</ref>
The design of [[Merkle tree]] is based on the claims from [[Intel]] describing the future of hardware processors with tens and thousands of cores instead of the conventional uni-core systems. With this in mind, Merkle tree hash structures exploit full potential of such hardware while being appropriate for current uni/dual core architectures.


⚫
MD6 was submitted to the [[NIST hash function competition|NIST SHA-3 competition]]. However, on July 1, 2009, Rivest posted a comment at NIST that MD6 is not yet ready to be a candidate for SHA-3 because of speed issues, a "gap in the proof that the submitted version of MD6 is resistant to differential attacks", and an inability to supply such a proof for a faster reduced-round version,<ref>{{cite web|url=http://groups.csail.mit.edu/cis/md6/OFFICIAL_COMMENT_MD6_2009-07-01.txt|title=OFFICIAL COMMENT: MD6|last=Rivest|first=Ronald|date=July 1, 2009|accessdate=September 27, 2011}}</ref> although Rivest also stated at the MD6 website that it is not withdrawn formally.<ref>{{cite web|url=http://www.schneier.com/blog/archives/2009/07/md6.html|title=MD6 Withdrawn from SHA-3 Competition|last=Schneier|first=Bruce|date=July 1, 2009|accessdate=July 9, 2009}}</ref> MD6 did not advance to the second round of the SHA-3 competition. In September 2011, a paper presenting an improved proof that MD6 and faster reduced-round versions are resistant to differential attacks<ref>{{cite web|url=http://eprint.iacr.org/2011/374|title=Restoring the Differential Resistance of MD6|last=Heilman|first=Ethan|date=July 10, 2011|accessdate=September 27, 2011}}</ref> was posted to the MD6 website.<ref>{{cite web|url=http://groups.csail.mit.edu/cis/md6/|title=Improved Differential Analysis|last=Heilman |first=Ethan|date=September 2011|accessdate=September 27, 2011}}</ref>
⚫
In December 2008, Douglas Held of [[Fortify Software]] discovered a [[buffer overflow]] in the original MD6 hash algorithm's reference implementation. This error was later made public by professor [[Ron Rivest]] on 19 February 2009, with a release of a corrected reference implementation in advance of the Fortify Report.<ref>http://blog.fortify.com/repo/Fortify-SHA-3-Report.pdf{{dead link|date=June 2014}}</ref>

⚫
MD6 was submitted to the [[NIST hash function competition|NIST SHA-3 competition]]. However, on July 1, 2009, Rivest posted a comment at NIST that MD6 is not yet ready to be a candidate for SHA-3 because of speed issues, a "gap in the proof that the submitted version of MD6 is resistant to differential attacks", and an inability to supply such a proof for a faster reduced-round version,<ref>{{cite web|url=http://groups.csail.mit.edu/cis/md6/OFFICIAL_COMMENT_MD6_2009-07-01.txt|title=OFFICIAL COMMENT: MD6|last=Rivest|first=Ronald|date=July 1, 2009|accessdate=September 27, 2011}}</ref> although Rivest also stated at the MD6 website that it is not withdrawn formally.<ref>{{cite web|url=http://www.schneier.com/blog/archives/2009/07/md6.html|title=MD6 Withdrawn from SHA-3 Competition|last=Schneier|first=Bruce|date=July 1, 2009|accessdate=July 9, 2009}}</ref> MD6 did not advance to the second round of the SHA-3 competition. In September 2011, a paper presenting an improved proof that MD6 and faster reduced-round versions are resistant to differential attacks<ref>{{cite web|url=http://eprint.iacr.org/2011/374|title=Restoring the Differential Resistance of MD6|last=Heilman|first=Ethan|date=July 10, 2011|accessdate=September 27, 2011}}</ref> was posted to the MD6 website.<ref>{{cite web|url=http://groups.csail.mit.edu/cis/md6/|title=Improved Differential Analysis|last=Heilman|first=Ethan|date=September 2011|accessdate=September 27, 2011}}</ref>

The algorithm's first known production use was in the [[Conficker|Conficker.B]] worm in December 2008;<ref name="mtc.sri.com">{{cite web|url=http://mtc.sri.com/Conficker/addendumC/|title=Addendum: Conficker C Analysis|authors=[[Phillip Porras]], Hassen Saidi, Vinod Yegneswaran|work=Malware Threat Center|publisher=[[SRI International]] Computer Science Laboratory|date=2009-04-04|accessdate=2013-06-14}}</ref> the worm's authors subsequently updated Conficker with the corrected implementation once the buffer overflow vulnerability became known.<ref name="mtc.sri.com"/>


== See also ==
== See also ==
* [[Comparison of cryptographic hash functions]]
* [[Comparison of cryptographic hash functions]]
* [[MD2 (cryptography)|MD2]]
* [[MD5]]


== References ==
== References ==
Line 54: Line 62:
{{DEFAULTSORT:Md6}}
{{DEFAULTSORT:Md6}}
[[Category:NIST hash function competition]]
[[Category:NIST hash function competition]]


{{crypto-stub}}

Latest revision as of 10:48, 30 January 2024

For other uses, see MD-6.
MD6
General
DesignersRonald Rivest, Benjamin Agre, Dan Bailey, Sarah Cheng, Christopher Crutchfield, Yevgeniy Dodis, Kermin Fleming, Asif Khan, Jayant Krishnamurthy, Yuncheng Lin, Leo Reyzin, Emily Shen, Jim Sukha, Eran Tromer, Yiqun Lisa Yin
First published2008
SeriesMD2, MD4, MD5, MD6
Detail
Digest sizesVariable, 0<d≤512 bits
StructureMerkle tree
RoundsVariable. Default, Unkeyed=40+[d/4], Keyed=max(80,40+(d/4)) [1]
Best public cryptanalysis
Key-recovery attack of a 14-round MD6 function in 222 operations.[2]

The MD6 Message-Digest Algorithm is a cryptographic hash function. It uses a Merkle tree-like structure to allow for immense parallel computation of hashes for very long inputs. Authors claim a performance of 28 cycles per byte for MD6-256 on an Intel Core 2 Duo and provable resistance against differential cryptanalysis.[3] The source code of the reference implementation was released under MIT license.[4]

Speeds in excess of 1 GB/s have been reported to be possible for long messages on 16-core CPU architecture.[1]

In December 2008, Douglas Held of Fortify Software discovered a buffer overflow in the original MD6 hash algorithm's reference implementation. This error was later made public by Ron Rivest on 19 February 2009, with a release of a corrected reference implementation in advance of the Fortify Report.[5]

MD6 was submitted to the NIST SHA-3 competition. However, on July 1, 2009, Rivest posted a comment at NIST that MD6 is not yet ready to be a candidate for SHA-3 because of speed issues, a "gap in the proof that the submitted version of MD6 is resistant to differential attacks", and an inability to supply such a proof for a faster reduced-round version,[6] although Rivest also stated at the MD6 website that it is not withdrawn formally.[7] MD6 did not advance to the second round of the SHA-3 competition. In September 2011, a paper presenting an improved proof that MD6 and faster reduced-round versions are resistant to differential attacks[8] was posted to the MD6 website.[9]

See also[edit]

References[edit]

  1. ^ a b Ronald L. Rivest; et al. "The MD6 Hash Function" (PDF). Archived from the original (PDF) on 2017-08-12. Retrieved 2024-01-29.
  2. ^ Aumasson, Jean-Philippe; Dinur, Itai; Meier, Willi; Shamir, Adi (2009). "Cube Testers and Key Recovery Attacks on Reduced-Round MD6 and Trivium". Fast Software Encryption. Vol. 5665. Berlin, Heidelberg: Springer Berlin Heidelberg. p. 1–22. doi:10.1007/978-3-642-03317-9_1. ISBN 978-3-642-03316-2.
  3. ^ Ronald L. Rivest. "The MD6 hash function A proposal to NIST for SHA-3". Archived from the original on 2020-11-09. Retrieved 2008-10-07. (Microsoft PowerPoint file)
  4. ^ readme.txt
  5. ^ "Fortify-SHA-3-Report" (PDF). Archived from the original (PDF) on 2012-02-22.
  6. ^ Rivest, Ronald (July 1, 2009). "OFFICIAL COMMENT: MD6". Retrieved September 27, 2011.
  7. ^ Schneier, Bruce (July 1, 2009). "MD6 Withdrawn from SHA-3 Competition". Retrieved July 9, 2009.
  8. ^ Heilman, Ethan (July 10, 2011). "Restoring the Differential Resistance of MD6". Retrieved September 27, 2011.
  9. ^ Heilman, Ethan (September 2011). "Improved Differential Analysis". Retrieved September 27, 2011.

External links[edit]

Retrieved from "https://en.wikipedia.org/w/index.php?title=MD6&oldid=1200848407"