diff options
Diffstat (limited to 'xml/htdocs/proj/en/glep/glep-0059.html')
-rw-r--r-- | xml/htdocs/proj/en/glep/glep-0059.html | 296 |
1 files changed, 296 insertions, 0 deletions
diff --git a/xml/htdocs/proj/en/glep/glep-0059.html b/xml/htdocs/proj/en/glep/glep-0059.html new file mode 100644 index 00000000..9afcc078 --- /dev/null +++ b/xml/htdocs/proj/en/glep/glep-0059.html @@ -0,0 +1,296 @@ +<?xml version="1.0" encoding="utf-8" ?> +<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"> +<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en"> + +<head> + <meta http-equiv="Content-Type" content="text/html; charset=utf-8" /> + <meta name="generator" content="Docutils 0.6: http://docutils.sourceforge.net/" /> + <title>GLEP 59 -- Manifest2 hash policies and security implications</title> + <link rel="stylesheet" href="tools/glep.css" type="text/css" /></head> +<body bgcolor="white"> +<table class="navigation" cellpadding="0" cellspacing="0" + width="100%" border="0"> +<tr><td class="navicon" width="150" height="35"> +<a href="http://www.gentoo.org/" title="Gentoo Linux Home Page"> +<img src="http://www.gentoo.org/images/gentoo-new.gif" alt="[Gentoo]" + border="0" width="150" height="35" /></a></td> +<td class="textlinks" align="left"> +[<b><a href="http://www.gentoo.org/">Gentoo Linux Home</a></b>] +[<b><a href="http://www.gentoo.org/proj/en/glep">GLEP Index</a></b>] +[<b><a href="http://www.gentoo.org/proj/en/glep/glep-0059.txt">GLEP Source</a></b>] +</td></tr></table> +<table class="rfc2822 docutils field-list" frame="void" rules="none"> +<col class="field-name" /> +<col class="field-body" /> +<tbody valign="top"> +<tr class="field"><th class="field-name">GLEP:</th><td class="field-body">59</td> +</tr> +<tr class="field"><th class="field-name">Title:</th><td class="field-body">Manifest2 hash policies and security implications</td> +</tr> +<tr class="field"><th class="field-name">Version:</th><td class="field-body">1.9</td> +</tr> +<tr class="field"><th class="field-name">Last-Modified:</th><td class="field-body"><a class="reference external" href="http://www.gentoo.org/cgi-bin/viewcvs.cgi/xml/htdocs/proj/en/glep/glep-0059.txt?cvsroot=gentoo">2010/04/07 21:34:24</a></td> +</tr> +<tr class="field"><th class="field-name">Author:</th><td class="field-body">Robin Hugh Johnson <robbat2 at gentoo.org>,</td> +</tr> +<tr class="field"><th class="field-name">Status:</th><td class="field-body">Draft</td> +</tr> +<tr class="field"><th class="field-name">Type:</th><td class="field-body">Standards Track</td> +</tr> +<tr class="field"><th class="field-name">Content-Type:</th><td class="field-body"><a class="reference external" href="glep-0002.html">text/x-rst</a></td> +</tr> +<tr class="field"><th class="field-name">Requires:</th><td class="field-body"><a class="reference external" href="http://www.gentoo.org/proj/en/glepglep-0044.html">44</a></td> +</tr> +<tr class="field"><th class="field-name">Created:</th><td class="field-body">October 2006</td> +</tr> +<tr class="field"><th class="field-name">Updated:</th><td class="field-body">November 2007, June 2008, July 2008, October 2008, January 2010</td> +</tr> +<tr class="field"><th class="field-name">Updates:</th><td class="field-body">44</td> +</tr> +<tr class="field"><th class="field-name">Post-History:</th><td class="field-body">December 2009, January 2010</td> +</tr> +</tbody> +</table> +<hr /> +<div class="contents topic" id="contents"> +<p class="topic-title first">Contents</p> +<ul class="simple"> +<li><a class="reference internal" href="#abstract" id="id2">Abstract</a></li> +<li><a class="reference internal" href="#motivation" id="id3">Motivation</a></li> +<li><a class="reference internal" href="#specification" id="id4">Specification</a><ul> +<li><a class="reference internal" href="#the-bad-news" id="id5">The bad news</a></li> +<li><a class="reference internal" href="#how-fast-can-md5-be-broken" id="id6">How fast can MD5 be broken?</a></li> +<li><a class="reference internal" href="#the-good-news" id="id7">The good news</a></li> +<li><a class="reference internal" href="#what-should-be-done" id="id8">What should be done</a></li> +<li><a class="reference internal" href="#checksum-depreciation-timing" id="id9">Checksum depreciation timing</a><ul> +<li><a class="reference internal" href="#general-principles" id="id10">General principles:</a></li> +<li><a class="reference internal" href="#immediate-plans" id="id11">Immediate plans:</a></li> +</ul> +</li> +</ul> +</li> +<li><a class="reference internal" href="#backwards-compatibility" id="id12">Backwards Compatibility</a></li> +<li><a class="reference internal" href="#references" id="id13">References</a></li> +<li><a class="reference internal" href="#thanks-to" id="id14">Thanks to</a></li> +<li><a class="reference internal" href="#id1" id="id15">References</a></li> +<li><a class="reference internal" href="#copyright" id="id16">Copyright</a></li> +</ul> +</div> +<div class="section" id="abstract"> +<h1><a class="toc-backref" href="#id2">Abstract</a></h1> +<p>While Manifest2 format allows multiple hashes, the question of which +checksums should be present, why, and the security implications of such +have never been resolved. This GLEP covers all of these issues, and +makes recommendations as to how to handle checksums both now, and in +future.</p> +</div> +<div class="section" id="motivation"> +<h1><a class="toc-backref" href="#id3">Motivation</a></h1> +<p>This GLEP is being written as part of the work on signing the Portage +tree, but is only tangentially related to the actual signing of +Manifests. Checksums present one possible weak point in the overall +security of the tree - and a comprehensive security plan is needed.</p> +<p>This GLEP is not mandatory for the tree-signing specification, but +instead aims to improve the security of the hashes used in Manifest2 +[GLEP44]. As such, it is also able to stand on it's own.</p> +</div> +<div class="section" id="specification"> +<h1><a class="toc-backref" href="#id4">Specification</a></h1> +<div class="section" id="the-bad-news"> +<h2><a class="toc-backref" href="#id5">The bad news</a></h2> +<p>First of all, I'd like to cover the bad news in checksum security. +A much discussed point, as been the simple question: What is the +security of multiple independent checksums on the same data? +The most common position (and indeed the one previously held by myself), +is that multiple checksums would be an increase in security, but we +could not provably quantify the amount of security this added. +The really bad news, is that this position is completely and utterly +wrong. Many of you will be aghast at this. There is extremely little +added security in multiple checksums as noted by Joux [J04]. For any set +of checksums, the actual strength lies in that of the strongest +checksum.</p> +<p>Wang et al [W04] extended Joux's [J04] work on SHA-0 to cover MD4, MD5, +HAVAL-128 and RIPEMD families of hashes.</p> +</div> +<div class="section" id="how-fast-can-md5-be-broken"> +<h2><a class="toc-backref" href="#id6">How fast can MD5 be broken?</a></h2> +<p>For a general collision, not a pre-image attack, since the announcement +by Wang et al [W04], the time required to break MD5 has been massively +reduced. Originally at 1 hour on a near-supercomputer (IBM P690) and +estimated at 64 hours with a Pentium-3 1.7Ghz. This has gone down to +less than in two years, to 17 seconds [K06a].</p> +<ul class="simple"> +<li>08/2004 - 1 hour, IBM pSeries 690 (32x 1.7Ghz POWER4+) = 54.4 GHz-Hours</li> +<li>03/2005 - 8 hours, Pentium-M 1.6Ghz = 12.8 Ghz-Hours</li> +<li>11/2005 - 5 hours, Pentium-4 1.7Ghz = 8.5 Ghz-Hours</li> +<li>03/2006 - 1 minute, Pentium-4 3.2Ghz = .05 Ghz-Hours</li> +<li>04/2006 - 17 seconds, Pentium-4 3.2Ghz = .01 Ghz-Hours</li> +</ul> +<p>If we accept a factor of 800x as a sample of how much faster a checksum +may be broken over the course of 2 years (MD5 using the above data is +>2000x), then existing checksums do not stand a significant chance of +survival in the future. We should thus accept that whatever checksums we +are using today, will be broken in the near future, and plan as best as +possible. (A brief review [H04] of the SHA1 attacks indicates an +improvement of ~600x in the same timespan).</p> +<p>And for those that claim implementation of these procedures is not yet +feasible, see [K06b] for an application that can produce two +self-extracting EXE files, with identical MD5s, and whatever payload you +want.</p> +</div> +<div class="section" id="the-good-news"> +<h2><a class="toc-backref" href="#id7">The good news</a></h2> +<p>Of the checksums presently used by Manifest2 (SHA1, SHA256, RIPEMD160), +one stands close to being completely broken: SHA1; and another is +significantly weakened: RIPEMD160. The SHA2 series has suffered some +attacks, but still remains reasonably solid [G07],[K08].</p> +<p>To reduce the potential for future problems and any single checksum +break leading to a rapid decrease in security, we should incorporate the +strongest hash available from each family of checksums, and be prepared +to retire old checksums actively, unless there is a overriding reason to +keep a specific checksum, such as part of a migration plan.</p> +</div> +<div class="section" id="what-should-be-done"> +<h2><a class="toc-backref" href="#id8">What should be done</a></h2> +<p>Portage should always try to verify all supported hashes that are +available in a Manifest2, starting with the strongest ones as maintained +by a preference list. Over time, the weaker checksums should be removed +from Manifest2 files, once all old Portage installations have had +sufficient time to upgrade. Stronger checksums shall be added as soon as +an implementation is available in Portage. Weak checksums may be removed +as long as the depreciation process is followed (see below).</p> +<p>As soon as feasible, we should add the SHA512 and WHIRLPOOL algorithms. +In future, as stream-based checksums are developed (in response to the +development by NIST [AHS]), they should be considered and used.</p> +<p>The SHA512 algorithm is available in Python 2.5, which has been a +dependency of Portage since approximately Portage 2.1.6.13.</p> +<p>The WHIRLPOOL checksum is not available within the PyCrypto library or +hashlib that is part of Python 2.5, but there are multiple alternative +Python implementations available, ranging from pure Python to C-based +(python-mhash).</p> +<p>The existence unsupported hash is not considered to be a failure unless +no supported hashes are available for a given Manifest entry.</p> +</div> +<div class="section" id="checksum-depreciation-timing"> +<h2><a class="toc-backref" href="#id9">Checksum depreciation timing</a></h2> +<div class="section" id="general-principles"> +<h3><a class="toc-backref" href="#id10">General principles:</a></h3> +<p>A minimum set of depreciated checksums shall be maintained only to +support old package manager versions where needed by historically used +trees:</p> +<ul class="simple"> +<li>New package manager versions should NOT use depreciated checksums in</li> +<li>New trees with that have never used the depreciated checksums may omit +them for reasons of size, but are still strongly suggested to include +them.</li> +<li>Removal of depreciated checksums shall happen after no less than 18 +months or one major Portage version cycle, whichever is greater.</li> +</ul> +</div> +<div class="section" id="immediate-plans"> +<h3><a class="toc-backref" href="#id11">Immediate plans:</a></h3> +<p>For the current Portage, both SHA1 and RIPEMD160 should be immediately +removed, as they present no advantages over the already present SHA256. +SHA256 cannot be replaced immediately with SHA512, as existing Portage +versions need at least one supported algorithm present (SHA256 support +was added in June 2006), so it must be retained for some while.</p> +<p>Immediately:</p> +<ul class="simple"> +<li>Add WHIRLPOOL and SHA512.</li> +<li>Remove SHA1 and RIPEMD160.</li> +</ul> +<p>After the majority of Portage installations include SHA512 support:</p> +<ul class="simple"> +<li>Remove SHA256.</li> +</ul> +</div> +</div> +</div> +<div class="section" id="backwards-compatibility"> +<h1><a class="toc-backref" href="#id12">Backwards Compatibility</a></h1> +<p>Old versions of Portage may support and expect only specific checksums. +This is accounted for in the checksum depreciation discussion.</p> +<p>For maximum compatiability, we should only have to include each of the +old algorithms that we are officially still supporting, as well as the +new ones that we prefer.</p> +</div> +<div class="section" id="references"> +<h1><a class="toc-backref" href="#id13">References</a></h1> +<dl class="docutils"> +<dt>[AHS] NIST (2007). "NIST's Plan for New Cryptographic Hash Functions",</dt> +<dd>(Advanced Hash Standard). <a class="reference external" href="http://csrc.nist.gov/pki/HashWorkshop/">http://csrc.nist.gov/pki/HashWorkshop/</a></dd> +<dt>[BOBO06] Boneh, D. and Boyen, X. (2006). "On the Impossibility of</dt> +<dd>Efficiently Combining Collision Resistant Hash Functions"; Proceedings +of CRYPTO 2006, Dwork, C. (Ed.); Lecture Notes in Computer Science +4117, pp. 570-583. Available online from: +<a class="reference external" href="http://crypto.stanford.edu/~dabo/abstracts/hashing.html">http://crypto.stanford.edu/~dabo/abstracts/hashing.html</a></dd> +<dt>[H04] Hawkes, P. and Paddon, M. and Rose, G. (2004). "On Corrective</dt> +<dd>Patterns for the SHA-2 Family". CRYPTO 2004 Cryptology ePrint Archive, +Report 2004/204. Available online from: +<a class="reference external" href="http://eprint.iacr.org/2004/207.pdf">http://eprint.iacr.org/2004/207.pdf</a></dd> +<dt>[J04] Joux, Antoie. (2004). "Multicollisions in Iterated Hash</dt> +<dd>Functions - Application to Cascaded Constructions;" Proceedings of +CRYPTO 2004, Franklin, M. (Ed); Lecture Notes in Computer Science +3152, pp. 306-316. Available online from: +<a class="reference external" href="http://web.cecs.pdx.edu/~teshrim/spring06/papers/general-attacks/multi-joux.pdf">http://web.cecs.pdx.edu/~teshrim/spring06/papers/general-attacks/multi-joux.pdf</a></dd> +<dt>[K06a] Klima, V. (2006). "Tunnels in Hash Functions: MD5 Collisions</dt> +<dd>Within a Minute". Cryptology ePrint Archive, Report 2006/105. +Available online from: <a class="reference external" href="http://eprint.iacr.org/2006/105.pdf">http://eprint.iacr.org/2006/105.pdf</a></dd> +<dt>[K06b] Klima, V. (2006). "Note and links to high-speed MD5 collision</dt> +<dd>proof of concept tools". Available online from: +<a class="reference external" href="http://cryptography.hyperlink.cz/2006/trick.txt">http://cryptography.hyperlink.cz/2006/trick.txt</a></dd> +<dt>[K08] Klima, V. (2008). "On Collisions of Hash Functions Turbo SHA-2".</dt> +<dd>Cryptology ePrint Archive, Report 2008/003. Available online from: +<a class="reference external" href="http://eprint.iacr.org/2008/003.pdf">http://eprint.iacr.org/2008/003.pdf</a></dd> +<dt>[G07] Gligoroski, D. and Knapskog, S.J. (2007). "Turbo SHA-2".</dt> +<dd>Cryptology ePrint Archive, Report 2007/403. Available online from: +<a class="reference external" href="http://eprint.iacr.org/2007/403.pdf">http://eprint.iacr.org/2007/403.pdf</a></dd> +<dt>[W04] Wang, X. et al: "Collisions for Hash Functions MD4, MD5,</dt> +<dd>HAVAL-128 and RIPEMD", rump session, CRYPTO 2004, Cryptology ePrint +Archive, Report 2004/199, first version (August 16, 2004), second +version (August 17, 2004). Available online from: +<a class="reference external" href="http://eprint.iacr.org/2004/199.pdf">http://eprint.iacr.org/2004/199.pdf</a></dd> +</dl> +</div> +<div class="section" id="thanks-to"> +<h1><a class="toc-backref" href="#id14">Thanks to</a></h1> +<dl class="docutils"> +<dt>I'd like to thank the following folks, in no specific order:</dt> +<dd><ul class="first last simple"> +<li>Ciaran McCreesh (ciaranm) - for pointing out the Joux (2004) paper, +and also being stubborn enough in not accepting a partial solution.</li> +<li>Marius Mauch (genone), Zac Medico (zmedico) and Brian Harring +(ferringb): for being knowledgeable about the Portage Manifest2 +codebase.</li> +</ul> +</dd> +</dl> +</div> +<div class="section" id="id1"> +<h1><a class="toc-backref" href="#id15">References</a></h1> +<table class="docutils citation" frame="void" id="glep44" rules="none"> +<colgroup><col class="label" /><col /></colgroup> +<tbody valign="top"> +<tr><td class="label">[GLEP44]</td><td>Mauch, M. (2005) GLEP44 - Manifest2 format. +<a class="reference external" href="http://www.gentoo.org/proj/en/glep/glep-0044.html">http://www.gentoo.org/proj/en/glep/glep-0044.html</a></td></tr> +</tbody> +</table> +</div> +<div class="section" id="copyright"> +<h1><a class="toc-backref" href="#id16">Copyright</a></h1> +<p>Copyright (c) 2006-2010 by Robin Hugh Johnson. This material may be +distributed only subject to the terms and conditions set forth in the +Open Publication License, v1.0.</p> +<!-- vim: tw=72 ts=2 expandtab: --> +</div> + +</div> +<div class="footer"> +<hr class="footer" /> +<a class="reference external" href="glep-0059.txt">View document source</a>. +Generated on: 2010-04-07 21:54 UTC. +Generated by <a class="reference external" href="http://docutils.sourceforge.net/">Docutils</a> from <a class="reference external" href="http://docutils.sourceforge.net/rst.html">reStructuredText</a> source. + +</div> +</body> +</html> |