| 1 |
<?xml version="1.0" encoding="utf-8" ?>
|
| 2 |
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
|
| 3 |
<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en">
|
| 4 |
|
| 5 |
<head>
|
| 6 |
<meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
|
| 7 |
<meta name="generator" content="Docutils 0.5: http://docutils.sourceforge.net/" />
|
| 8 |
<title>GLEP 59 -- Manifest2 hash policies and security implications</title>
|
| 9 |
<link rel="stylesheet" href="tools/glep.css" type="text/css" /></head>
|
| 10 |
<body bgcolor="white">
|
| 11 |
<table class="navigation" cellpadding="0" cellspacing="0"
|
| 12 |
width="100%" border="0">
|
| 13 |
<tr><td class="navicon" width="150" height="35">
|
| 14 |
<a href="http://www.gentoo.org/" title="Gentoo Linux Home Page">
|
| 15 |
<img src="http://www.gentoo.org/images/gentoo-new.gif" alt="[Gentoo]"
|
| 16 |
border="0" width="150" height="35" /></a></td>
|
| 17 |
<td class="textlinks" align="left">
|
| 18 |
[<b><a href="http://www.gentoo.org/">Gentoo Linux Home</a></b>]
|
| 19 |
[<b><a href="http://www.gentoo.org/proj/en/glep">GLEP Index</a></b>]
|
| 20 |
[<b><a href="http://www.gentoo.org/proj/en/glep/glep-0059.txt">GLEP Source</a></b>]
|
| 21 |
</td></tr></table>
|
| 22 |
<table class="rfc2822 docutils field-list" frame="void" rules="none">
|
| 23 |
<col class="field-name" />
|
| 24 |
<col class="field-body" />
|
| 25 |
<tbody valign="top">
|
| 26 |
<tr class="field"><th class="field-name">GLEP:</th><td class="field-body">59</td>
|
| 27 |
</tr>
|
| 28 |
<tr class="field"><th class="field-name">Title:</th><td class="field-body">Manifest2 hash policies and security implications</td>
|
| 29 |
</tr>
|
| 30 |
<tr class="field"><th class="field-name">Version:</th><td class="field-body">1.11</td>
|
| 31 |
</tr>
|
| 32 |
<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">2008/07/13 02:23:36</a></td>
|
| 33 |
</tr>
|
| 34 |
<tr class="field"><th class="field-name">Author:</th><td class="field-body">Robin Hugh Johnson <robbat2 at gentoo.org>,</td>
|
| 35 |
</tr>
|
| 36 |
<tr class="field"><th class="field-name">Status:</th><td class="field-body">Draft</td>
|
| 37 |
</tr>
|
| 38 |
<tr class="field"><th class="field-name">Type:</th><td class="field-body">Standards Track</td>
|
| 39 |
</tr>
|
| 40 |
<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>
|
| 41 |
</tr>
|
| 42 |
<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>
|
| 43 |
</tr>
|
| 44 |
<tr class="field"><th class="field-name">Created:</th><td class="field-body">October 2006</td>
|
| 45 |
</tr>
|
| 46 |
<tr class="field"><th class="field-name">Updated:</th><td class="field-body">November 2007, June 2008, July 2008</td>
|
| 47 |
</tr>
|
| 48 |
<tr class="field"><th class="field-name">Updates:</th><td class="field-body">44</td>
|
| 49 |
</tr>
|
| 50 |
</tbody>
|
| 51 |
</table>
|
| 52 |
<hr />
|
| 53 |
<div class="contents topic" id="contents">
|
| 54 |
<p class="topic-title first">Contents</p>
|
| 55 |
<ul class="simple">
|
| 56 |
<li><a class="reference internal" href="#abstract" id="id1">Abstract</a></li>
|
| 57 |
<li><a class="reference internal" href="#motivation" id="id2">Motivation</a></li>
|
| 58 |
<li><a class="reference internal" href="#specification" id="id3">Specification</a><ul>
|
| 59 |
<li><a class="reference internal" href="#the-bad-news" id="id4">The bad news</a></li>
|
| 60 |
<li><a class="reference internal" href="#how-fast-can-md5-be-broken" id="id5">How fast can MD5 be broken?</a></li>
|
| 61 |
<li><a class="reference internal" href="#the-good-news" id="id6">The good news</a></li>
|
| 62 |
<li><a class="reference internal" href="#what-should-be-done" id="id7">What should be done</a><ul>
|
| 63 |
<li><a class="reference internal" href="#checksum-depreciation" id="id8">Checksum depreciation</a></li>
|
| 64 |
</ul>
|
| 65 |
</li>
|
| 66 |
</ul>
|
| 67 |
</li>
|
| 68 |
<li><a class="reference internal" href="#backwards-compatibility" id="id9">Backwards Compatibility</a></li>
|
| 69 |
<li><a class="reference internal" href="#references" id="id10">References</a></li>
|
| 70 |
<li><a class="reference internal" href="#thanks-to" id="id11">Thanks to</a></li>
|
| 71 |
<li><a class="reference internal" href="#copyright" id="id12">Copyright</a></li>
|
| 72 |
</ul>
|
| 73 |
</div>
|
| 74 |
<div class="section" id="abstract">
|
| 75 |
<h1><a class="toc-backref" href="#id1">Abstract</a></h1>
|
| 76 |
<p>While Manifest2 format allows multiple hashes, the question of which
|
| 77 |
checksums should be present, why, and the security implications of such
|
| 78 |
have never been resolved. This GLEP covers all of these issues, and
|
| 79 |
makes recommendations as to how to handle checksums both now, and in
|
| 80 |
future.</p>
|
| 81 |
</div>
|
| 82 |
<div class="section" id="motivation">
|
| 83 |
<h1><a class="toc-backref" href="#id2">Motivation</a></h1>
|
| 84 |
<p>This GLEP is being written as part of the work on signing the Portage
|
| 85 |
tree, but is only tangentially related to the actual signing of
|
| 86 |
Manifests. Checksums present one possible weak point in the overall
|
| 87 |
security of the tree - and a comprehensive security plan is needed.</p>
|
| 88 |
</div>
|
| 89 |
<div class="section" id="specification">
|
| 90 |
<h1><a class="toc-backref" href="#id3">Specification</a></h1>
|
| 91 |
<div class="section" id="the-bad-news">
|
| 92 |
<h2><a class="toc-backref" href="#id4">The bad news</a></h2>
|
| 93 |
<p>First of all, I'd like to cover the bad news in checksum security.
|
| 94 |
A much discussed point, as been the simple question: What is the
|
| 95 |
security of multiple independent checksums on the same data?
|
| 96 |
The most common position (and indeed the one previously held by myself),
|
| 97 |
is that multiple checksums would be an increase in security, but we
|
| 98 |
could not provably quantify the amount of security this added.
|
| 99 |
The really bad news, is that this position is completely and utterly
|
| 100 |
wrong. Many of you will be aghast at this. There is extremely little
|
| 101 |
added security in multiple checksums [J04]. For any set of checksums,
|
| 102 |
the actual strength lies in that of the strongest checksum.</p>
|
| 103 |
</div>
|
| 104 |
<div class="section" id="how-fast-can-md5-be-broken">
|
| 105 |
<h2><a class="toc-backref" href="#id5">How fast can MD5 be broken?</a></h2>
|
| 106 |
<p>For a general collision, not a pre-image attack, since the original
|
| 107 |
announcement by Wang et al [W04], the time required to break MD5 has
|
| 108 |
been massively reduced. Originally at 1 hour on a near-supercomputer
|
| 109 |
(IBM P690) and estimated at 64 hours with a Pentium-3 1.7Ghz. This has
|
| 110 |
gone down to less than in two years, to 17 seconds [K06a]!</p>
|
| 111 |
<p>08/2004 - 1 hour, IBM pSeries 690 (32x 1.7Ghz POWER4+) = 54.4 GHz-Hours
|
| 112 |
03/2005 - 8 hours, Pentium-M 1.6Ghz = 12.8 Ghz-Hours
|
| 113 |
11/2005 - 5 hours, Pentium-4 1.7Ghz = 8.5 Ghz-Hours
|
| 114 |
03/2006 - 1 minute, Pentium-4 3.2Ghz = .05 Ghz-Hours
|
| 115 |
04/2006 - 17 seconds, Pentium-4 3.2Ghz = .01 Ghz-Hours</p>
|
| 116 |
<p>If we accept a factor of 800x as a sample of how much faster a checksum
|
| 117 |
may be broken over the course of 2 years (MD5 using the above data is
|
| 118 |
>2000x), then existing checksums do not stand a significant chance of
|
| 119 |
survival in the future. We should thus accept that whatever checksums we
|
| 120 |
are using today, will be broken in the near future, and plan as best as
|
| 121 |
possible. (A brief review [H04] of the present SHA1 attacks indicates an
|
| 122 |
improvement of ~600x in the same timespan).</p>
|
| 123 |
<p>And for those that claim implementation of these procedures is not yet
|
| 124 |
feasible, see [K06b] for an application that can produce two
|
| 125 |
self-extracting .exe files, with identical MD5s, and whatever payload
|
| 126 |
you want.</p>
|
| 127 |
</div>
|
| 128 |
<div class="section" id="the-good-news">
|
| 129 |
<h2><a class="toc-backref" href="#id6">The good news</a></h2>
|
| 130 |
<p>Of the checksums presently used by Manifest2, one stands close to being
|
| 131 |
completely broken: SHA1. The SHA2 series has suffered some attacks, but
|
| 132 |
still remains reasonably solid [G07],[K08]. No attacks against RIPEMD160
|
| 133 |
have been published, however it is constructed in the same manner as
|
| 134 |
MD5, SHA1 and SHA2, so is also vulnerable to the new methods of
|
| 135 |
cryptanalysis [H04].</p>
|
| 136 |
<p>To reduce the potential for future problems and any single checksum
|
| 137 |
break leading to a rapid decrease in security, we should incorporate the
|
| 138 |
strongest hash available from each family of checksums, and be prepared
|
| 139 |
to retire old checksums actively, unless there is a overriding reason to
|
| 140 |
keep a specific checksum.</p>
|
| 141 |
</div>
|
| 142 |
<div class="section" id="what-should-be-done">
|
| 143 |
<h2><a class="toc-backref" href="#id7">What should be done</a></h2>
|
| 144 |
<p>Portage should always try to verify all supported hashes that are
|
| 145 |
available in a Manifest2, starting with the strongest ones as maintained
|
| 146 |
by a preference list. Over time, the weaker checksums should be removed
|
| 147 |
from Manifest2 files, once all old Portage installations have had
|
| 148 |
sufficient time to upgrade. We should be prepared to add stronger
|
| 149 |
checksums wherever possible, and to remove those that have been
|
| 150 |
defeated.</p>
|
| 151 |
<p>An unsupported hash is not considered to be a failure unless no
|
| 152 |
supported hashes are available.</p>
|
| 153 |
<div class="section" id="checksum-depreciation">
|
| 154 |
<h3><a class="toc-backref" href="#id8">Checksum depreciation</a></h3>
|
| 155 |
<p>For the current Portage, SHA1 should be gradually removed, as presents
|
| 156 |
no advantages over SHA256. Beyond one specific problem (see the next
|
| 157 |
paragraph), we should add SHA512 (SHA2, 512 bit size), the Whirlpool
|
| 158 |
checksum (standardized checksum, with no known weaknesses). In future,
|
| 159 |
as stream-based checksums are developed (in response to the development
|
| 160 |
by NIST [AHS]), they should be considered and used.</p>
|
| 161 |
<p>There is one temporary stumbling block at hand - the existing Portage
|
| 162 |
infrastructure does not support SHA384/512 or Whirlpool, thus hampering
|
| 163 |
their immediate acceptance. SHA512 is available in Python 2.5, while
|
| 164 |
SHA1 is already available in Python 2.4. After Python2.5 is established
|
| 165 |
in a Gentoo media release, that would be a suitable time to remove SHA1
|
| 166 |
from Manifest2 files.</p>
|
| 167 |
</div>
|
| 168 |
</div>
|
| 169 |
</div>
|
| 170 |
<div class="section" id="backwards-compatibility">
|
| 171 |
<h1><a class="toc-backref" href="#id9">Backwards Compatibility</a></h1>
|
| 172 |
<p>Old versions of Portage may support and expect only specific checksums.
|
| 173 |
This is accounted for in the checksum depreciation discussion.</p>
|
| 174 |
</div>
|
| 175 |
<div class="section" id="references">
|
| 176 |
<h1><a class="toc-backref" href="#id10">References</a></h1>
|
| 177 |
<dl class="docutils">
|
| 178 |
<dt>[AHS] NIST (2007). "NIST's Plan for New Cryptographic Hash Functions",</dt>
|
| 179 |
<dd>(Advanced Hash Standard). <a class="reference external" href="http://csrc.nist.gov/pki/HashWorkshop/">http://csrc.nist.gov/pki/HashWorkshop/</a></dd>
|
| 180 |
<dt>[BOBO06] Boneh, D. and Boyen, X. (2006). "On the Impossibility of</dt>
|
| 181 |
<dd>Efficiently Combining Collision Resistant Hash Functions"; Proceedings
|
| 182 |
of CRYPTO 2006, Dwork, C. (Ed.); Lecture Notes in Computer Science
|
| 183 |
4117, pp. 570-583. Available online from:
|
| 184 |
<a class="reference external" href="http://crypto.stanford.edu/~dabo/abstracts/hashing.html">http://crypto.stanford.edu/~dabo/abstracts/hashing.html</a></dd>
|
| 185 |
<dt>[H04] Hawkes, P. and Paddon, M. and Rose, G. (2004). "On Corrective</dt>
|
| 186 |
<dd>Patterns for the SHA-2 Family". CRYPTO 2004 Cryptology ePrint Archive,
|
| 187 |
Report 2004/204. Available online from:
|
| 188 |
<a class="reference external" href="http://eprint.iacr.org/2004/207.pdf">http://eprint.iacr.org/2004/207.pdf</a></dd>
|
| 189 |
<dt>[J04] Joux, Antoie. (2004). "Multicollisions in Iterated Hash Functions</dt>
|
| 190 |
<dd><ul class="first simple">
|
| 191 |
<li>Application to Cascaded Constructions;" Proceedings of CRYPTO 2004,</li>
|
| 192 |
</ul>
|
| 193 |
<div class="system-message">
|
| 194 |
<p class="system-message-title">System Message: WARNING/2 (<tt class="docutils">glep-0059.txt</tt>, line 139)</p>
|
| 195 |
Bullet list ends without a blank line; unexpected unindent.</div>
|
| 196 |
<p class="last">Franklin, M. (Ed); Lecture Notes in Computer Science 3152, pp.
|
| 197 |
306-316. Available online from:
|
| 198 |
<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></p>
|
| 199 |
</dd>
|
| 200 |
<dt>[K06a] Klima, V. (2006). "Tunnels in Hash Functions: MD5 Collisions</dt>
|
| 201 |
<dd>Within a Minute". Cryptology ePrint Archive, Report 2006/105.
|
| 202 |
Available online from: <a class="reference external" href="http://eprint.iacr.org/2006/105.pdf">http://eprint.iacr.org/2006/105.pdf</a></dd>
|
| 203 |
<dt>[K06b] Klima, V. (2006). "Note and links to high-speed MD5 collision</dt>
|
| 204 |
<dd>proof of concept tools". Available online from:
|
| 205 |
<a class="reference external" href="http://cryptography.hyperlink.cz/2006/trick.txt">http://cryptography.hyperlink.cz/2006/trick.txt</a></dd>
|
| 206 |
<dt>[K08] Klima, V. (2008). "On Collisions of Hash Functions Turbo SHA-2".</dt>
|
| 207 |
<dd>Cryptology ePrint Archive, Report 2008/003. Available online from:
|
| 208 |
<a class="reference external" href="http://eprint.iacr.org/2008/003.pdf">http://eprint.iacr.org/2008/003.pdf</a></dd>
|
| 209 |
<dt>[G07] Gligoroski, D. and Knapskog, S.J. (2007). "Turbo SHA-2".</dt>
|
| 210 |
<dd>Cryptology ePrint Archive, Report 2007/403. Available online from:
|
| 211 |
<a class="reference external" href="http://eprint.iacr.org/2007/403.pdf">http://eprint.iacr.org/2007/403.pdf</a></dd>
|
| 212 |
<dt>[W04] Wang, X. et al: "Collisions for Hash Functions MD4, MD5,</dt>
|
| 213 |
<dd>HAVAL-128 and RIPEMD", rump session, CRYPTO 2004, Cryptology ePrint
|
| 214 |
Archive, Report 2004/199, first version (August 16, 2004), second
|
| 215 |
version (August 17, 2004). Available online from:
|
| 216 |
<a class="reference external" href="http://eprint.iacr.org/2004/199.pdf">http://eprint.iacr.org/2004/199.pdf</a></dd>
|
| 217 |
</dl>
|
| 218 |
</div>
|
| 219 |
<div class="section" id="thanks-to">
|
| 220 |
<h1><a class="toc-backref" href="#id11">Thanks to</a></h1>
|
| 221 |
<dl class="docutils">
|
| 222 |
<dt>I'd like to thank the following folks, in no specific order:</dt>
|
| 223 |
<dd><ul class="first last simple">
|
| 224 |
<li>Ciaran McCreesh (ciaranm) - for pointing out the Joux (2004) paper,
|
| 225 |
and also being stubborn enough in not accepting a partial solution.</li>
|
| 226 |
<li>Marius Mauch (genone), Zac Medico (zmedico) and Brian Harring
|
| 227 |
(ferringb): for being knowledgeable about the Portage Manifest2
|
| 228 |
codebase.</li>
|
| 229 |
</ul>
|
| 230 |
</dd>
|
| 231 |
</dl>
|
| 232 |
</div>
|
| 233 |
<div class="section" id="copyright">
|
| 234 |
<h1><a class="toc-backref" href="#id12">Copyright</a></h1>
|
| 235 |
<p>Copyright (c) 2006 by Robin Hugh Johnson. This material may be
|
| 236 |
distributed only subject to the terms and conditions set forth in the
|
| 237 |
Open Publication License, v1.0.</p>
|
| 238 |
<p>vim: tw=72 ts=2 expandtab:</p>
|
| 239 |
</div>
|
| 240 |
|
| 241 |
</div>
|
| 242 |
<div class="footer">
|
| 243 |
<hr class="footer" />
|
| 244 |
<a class="reference external" href="glep-0059.txt">View document source</a>.
|
| 245 |
Generated on: 2008-10-21 23:29 UTC.
|
| 246 |
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.
|
| 247 |
|
| 248 |
</div>
|
| 249 |
</body>
|
| 250 |
</html>
|
Parent Directory
| 
Revision Log
