1 |
cardoe |
1.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 |
robbat2 |
1.4 |
<meta name="generator" content="Docutils 0.6: http://docutils.sourceforge.net/" /> |
8 |
cardoe |
1.1 |
<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 |
robbat2 |
1.8 |
<tr class="field"><th class="field-name">Version:</th><td class="field-body">1.6</td> |
31 |
cardoe |
1.1 |
</tr> |
32 |
robbat2 |
1.8 |
<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/01/31 09:55:43</a></td> |
33 |
cardoe |
1.1 |
</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 |
robbat2 |
1.4 |
<tr class="field"><th class="field-name">Updated:</th><td class="field-body">November 2007, June 2008, July 2008, October 2008, January 2010</td> |
47 |
cardoe |
1.1 |
</tr> |
48 |
|
|
<tr class="field"><th class="field-name">Updates:</th><td class="field-body">44</td> |
49 |
|
|
</tr> |
50 |
robbat2 |
1.5 |
<tr class="field"><th class="field-name">Post-History:</th><td class="field-body">December 2009, January 2010</td> |
51 |
robbat2 |
1.3 |
</tr> |
52 |
cardoe |
1.1 |
</tbody> |
53 |
|
|
</table> |
54 |
|
|
<hr /> |
55 |
|
|
<div class="contents topic" id="contents"> |
56 |
|
|
<p class="topic-title first">Contents</p> |
57 |
|
|
<ul class="simple"> |
58 |
|
|
<li><a class="reference internal" href="#abstract" id="id1">Abstract</a></li> |
59 |
|
|
<li><a class="reference internal" href="#motivation" id="id2">Motivation</a></li> |
60 |
|
|
<li><a class="reference internal" href="#specification" id="id3">Specification</a><ul> |
61 |
|
|
<li><a class="reference internal" href="#the-bad-news" id="id4">The bad news</a></li> |
62 |
|
|
<li><a class="reference internal" href="#how-fast-can-md5-be-broken" id="id5">How fast can MD5 be broken?</a></li> |
63 |
|
|
<li><a class="reference internal" href="#the-good-news" id="id6">The good news</a></li> |
64 |
robbat2 |
1.5 |
<li><a class="reference internal" href="#what-should-be-done" id="id7">What should be done</a></li> |
65 |
|
|
<li><a class="reference internal" href="#checksum-depreciation-timing" id="id8">Checksum depreciation timing</a></li> |
66 |
cardoe |
1.1 |
</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 |
robbat2 |
1.8 |
<p>This GLEP is not mandatory for the tree-signing specification, but |
89 |
|
|
instead aims to improve the security of the hashes used in Manifest2. |
90 |
|
|
As such, it is also able to stand on it's own.</p> |
91 |
cardoe |
1.1 |
</div> |
92 |
|
|
<div class="section" id="specification"> |
93 |
|
|
<h1><a class="toc-backref" href="#id3">Specification</a></h1> |
94 |
|
|
<div class="section" id="the-bad-news"> |
95 |
|
|
<h2><a class="toc-backref" href="#id4">The bad news</a></h2> |
96 |
|
|
<p>First of all, I'd like to cover the bad news in checksum security. |
97 |
|
|
A much discussed point, as been the simple question: What is the |
98 |
|
|
security of multiple independent checksums on the same data? |
99 |
|
|
The most common position (and indeed the one previously held by myself), |
100 |
|
|
is that multiple checksums would be an increase in security, but we |
101 |
|
|
could not provably quantify the amount of security this added. |
102 |
|
|
The really bad news, is that this position is completely and utterly |
103 |
|
|
wrong. Many of you will be aghast at this. There is extremely little |
104 |
robbat2 |
1.5 |
added security in multiple checksums as noted by Joux [J04]. For any set |
105 |
|
|
of checksums, the actual strength lies in that of the strongest |
106 |
|
|
checksum.</p> |
107 |
|
|
<p>Wang et al [W04] extended Joux's [J04] work on SHA-0 to cover MD4, MD5, |
108 |
|
|
HAVAL-128 and RIPEMD families of hashes.</p> |
109 |
cardoe |
1.1 |
</div> |
110 |
|
|
<div class="section" id="how-fast-can-md5-be-broken"> |
111 |
|
|
<h2><a class="toc-backref" href="#id5">How fast can MD5 be broken?</a></h2> |
112 |
robbat2 |
1.5 |
<p>For a general collision, not a pre-image attack, since the announcement |
113 |
|
|
by Wang et al [W04], the time required to break MD5 has been massively |
114 |
|
|
reduced. Originally at 1 hour on a near-supercomputer (IBM P690) and |
115 |
|
|
estimated at 64 hours with a Pentium-3 1.7Ghz. This has gone down to |
116 |
|
|
less than in two years, to 17 seconds [K06a].</p> |
117 |
cardoe |
1.1 |
<p>08/2004 - 1 hour, IBM pSeries 690 (32x 1.7Ghz POWER4+) = 54.4 GHz-Hours |
118 |
|
|
03/2005 - 8 hours, Pentium-M 1.6Ghz = 12.8 Ghz-Hours |
119 |
|
|
11/2005 - 5 hours, Pentium-4 1.7Ghz = 8.5 Ghz-Hours |
120 |
|
|
03/2006 - 1 minute, Pentium-4 3.2Ghz = .05 Ghz-Hours |
121 |
|
|
04/2006 - 17 seconds, Pentium-4 3.2Ghz = .01 Ghz-Hours</p> |
122 |
|
|
<p>If we accept a factor of 800x as a sample of how much faster a checksum |
123 |
|
|
may be broken over the course of 2 years (MD5 using the above data is |
124 |
|
|
>2000x), then existing checksums do not stand a significant chance of |
125 |
|
|
survival in the future. We should thus accept that whatever checksums we |
126 |
|
|
are using today, will be broken in the near future, and plan as best as |
127 |
robbat2 |
1.5 |
possible. (A brief review [H04] of the SHA1 attacks indicates an |
128 |
cardoe |
1.1 |
improvement of ~600x in the same timespan).</p> |
129 |
|
|
<p>And for those that claim implementation of these procedures is not yet |
130 |
|
|
feasible, see [K06b] for an application that can produce two |
131 |
robbat2 |
1.5 |
self-extracting EXE files, with identical MD5s, and whatever payload you |
132 |
|
|
want.</p> |
133 |
cardoe |
1.1 |
</div> |
134 |
|
|
<div class="section" id="the-good-news"> |
135 |
|
|
<h2><a class="toc-backref" href="#id6">The good news</a></h2> |
136 |
robbat2 |
1.5 |
<p>Of the checksums presently used by Manifest2 (SHA1, SHA256, RIPEMD160), |
137 |
|
|
one stands close to being completely broken: SHA1; and another is |
138 |
|
|
significantly weakened: RIPEMD160. The SHA2 series has suffered some |
139 |
|
|
attacks, but still remains reasonably solid [G07],[K08].</p> |
140 |
cardoe |
1.1 |
<p>To reduce the potential for future problems and any single checksum |
141 |
|
|
break leading to a rapid decrease in security, we should incorporate the |
142 |
|
|
strongest hash available from each family of checksums, and be prepared |
143 |
|
|
to retire old checksums actively, unless there is a overriding reason to |
144 |
robbat2 |
1.5 |
keep a specific checksum, such as part of a migration plan.</p> |
145 |
cardoe |
1.1 |
</div> |
146 |
|
|
<div class="section" id="what-should-be-done"> |
147 |
|
|
<h2><a class="toc-backref" href="#id7">What should be done</a></h2> |
148 |
|
|
<p>Portage should always try to verify all supported hashes that are |
149 |
|
|
available in a Manifest2, starting with the strongest ones as maintained |
150 |
|
|
by a preference list. Over time, the weaker checksums should be removed |
151 |
|
|
from Manifest2 files, once all old Portage installations have had |
152 |
|
|
sufficient time to upgrade. We should be prepared to add stronger |
153 |
|
|
checksums wherever possible, and to remove those that have been |
154 |
|
|
defeated.</p> |
155 |
robbat2 |
1.5 |
<p>As soon as feasible, we should add the SHA512 and WHIRLPOOL algorithms. |
156 |
|
|
In future, as stream-based checksums are developed (in response to the |
157 |
|
|
development by NIST [AHS]), they should be considered and used.</p> |
158 |
|
|
<p>The SHA512 algorithm is available in Python 2.5, which has been a |
159 |
robbat2 |
1.9 |
dependency of Portage since approximately Portage 2.1.6.13.</p> |
160 |
robbat2 |
1.5 |
<p>The WHIRLPOOL checksum is not available within the PyCrypto library or |
161 |
|
|
hashlib that is part of Python 2.5, but there are multiple alternative |
162 |
|
|
Python implementations available, ranging from pure Python to C-based |
163 |
|
|
(python-mhash).</p> |
164 |
|
|
<p>The existence unsupported hash is not considered to be a failure unless |
165 |
|
|
no supported hashes are available for a given Manifest entry.</p> |
166 |
|
|
</div> |
167 |
|
|
<div class="section" id="checksum-depreciation-timing"> |
168 |
|
|
<h2><a class="toc-backref" href="#id8">Checksum depreciation timing</a></h2> |
169 |
|
|
<p>For the current Portage, both SHA1 and RIPEMD160 should be immediately |
170 |
|
|
removed, as they present no advantages over the already present SHA256. |
171 |
|
|
SHA256 cannot be replaced immediately with SHA512, as existing Portage |
172 |
|
|
versions need at least one supported algorithm present (SHA256 support |
173 |
|
|
was added in June 2006), so it must be retained for some while.</p> |
174 |
|
|
<p>Immediately: |
175 |
|
|
- Add WHIRLPOOL and SHA512. |
176 |
|
|
- Remove SHA1 and RIPEMD160.</p> |
177 |
|
|
<p>After the majority of Portage installations include SHA512 support: |
178 |
|
|
- Remove SHA256.</p> |
179 |
cardoe |
1.1 |
</div> |
180 |
|
|
</div> |
181 |
|
|
<div class="section" id="backwards-compatibility"> |
182 |
|
|
<h1><a class="toc-backref" href="#id9">Backwards Compatibility</a></h1> |
183 |
|
|
<p>Old versions of Portage may support and expect only specific checksums. |
184 |
|
|
This is accounted for in the checksum depreciation discussion.</p> |
185 |
robbat2 |
1.9 |
<p>For maximum compatiability, we should only have to include each of the |
186 |
|
|
old algorithms that we are officially still supporting, as well as the |
187 |
|
|
new ones that we prefer.</p> |
188 |
cardoe |
1.1 |
</div> |
189 |
|
|
<div class="section" id="references"> |
190 |
|
|
<h1><a class="toc-backref" href="#id10">References</a></h1> |
191 |
|
|
<dl class="docutils"> |
192 |
|
|
<dt>[AHS] NIST (2007). "NIST's Plan for New Cryptographic Hash Functions",</dt> |
193 |
|
|
<dd>(Advanced Hash Standard). <a class="reference external" href="http://csrc.nist.gov/pki/HashWorkshop/">http://csrc.nist.gov/pki/HashWorkshop/</a></dd> |
194 |
|
|
<dt>[BOBO06] Boneh, D. and Boyen, X. (2006). "On the Impossibility of</dt> |
195 |
|
|
<dd>Efficiently Combining Collision Resistant Hash Functions"; Proceedings |
196 |
|
|
of CRYPTO 2006, Dwork, C. (Ed.); Lecture Notes in Computer Science |
197 |
|
|
4117, pp. 570-583. Available online from: |
198 |
|
|
<a class="reference external" href="http://crypto.stanford.edu/~dabo/abstracts/hashing.html">http://crypto.stanford.edu/~dabo/abstracts/hashing.html</a></dd> |
199 |
|
|
<dt>[H04] Hawkes, P. and Paddon, M. and Rose, G. (2004). "On Corrective</dt> |
200 |
|
|
<dd>Patterns for the SHA-2 Family". CRYPTO 2004 Cryptology ePrint Archive, |
201 |
|
|
Report 2004/204. Available online from: |
202 |
|
|
<a class="reference external" href="http://eprint.iacr.org/2004/207.pdf">http://eprint.iacr.org/2004/207.pdf</a></dd> |
203 |
robbat2 |
1.2 |
<dt>[J04] Joux, Antoie. (2004). "Multicollisions in Iterated Hash</dt> |
204 |
|
|
<dd>Functions - Application to Cascaded Constructions;" Proceedings of |
205 |
|
|
CRYPTO 2004, Franklin, M. (Ed); Lecture Notes in Computer Science |
206 |
|
|
3152, pp. 306-316. Available online from: |
207 |
|
|
<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> |
208 |
cardoe |
1.1 |
<dt>[K06a] Klima, V. (2006). "Tunnels in Hash Functions: MD5 Collisions</dt> |
209 |
|
|
<dd>Within a Minute". Cryptology ePrint Archive, Report 2006/105. |
210 |
|
|
Available online from: <a class="reference external" href="http://eprint.iacr.org/2006/105.pdf">http://eprint.iacr.org/2006/105.pdf</a></dd> |
211 |
|
|
<dt>[K06b] Klima, V. (2006). "Note and links to high-speed MD5 collision</dt> |
212 |
|
|
<dd>proof of concept tools". Available online from: |
213 |
|
|
<a class="reference external" href="http://cryptography.hyperlink.cz/2006/trick.txt">http://cryptography.hyperlink.cz/2006/trick.txt</a></dd> |
214 |
|
|
<dt>[K08] Klima, V. (2008). "On Collisions of Hash Functions Turbo SHA-2".</dt> |
215 |
|
|
<dd>Cryptology ePrint Archive, Report 2008/003. Available online from: |
216 |
|
|
<a class="reference external" href="http://eprint.iacr.org/2008/003.pdf">http://eprint.iacr.org/2008/003.pdf</a></dd> |
217 |
|
|
<dt>[G07] Gligoroski, D. and Knapskog, S.J. (2007). "Turbo SHA-2".</dt> |
218 |
|
|
<dd>Cryptology ePrint Archive, Report 2007/403. Available online from: |
219 |
|
|
<a class="reference external" href="http://eprint.iacr.org/2007/403.pdf">http://eprint.iacr.org/2007/403.pdf</a></dd> |
220 |
|
|
<dt>[W04] Wang, X. et al: "Collisions for Hash Functions MD4, MD5,</dt> |
221 |
|
|
<dd>HAVAL-128 and RIPEMD", rump session, CRYPTO 2004, Cryptology ePrint |
222 |
|
|
Archive, Report 2004/199, first version (August 16, 2004), second |
223 |
|
|
version (August 17, 2004). Available online from: |
224 |
|
|
<a class="reference external" href="http://eprint.iacr.org/2004/199.pdf">http://eprint.iacr.org/2004/199.pdf</a></dd> |
225 |
|
|
</dl> |
226 |
|
|
</div> |
227 |
|
|
<div class="section" id="thanks-to"> |
228 |
|
|
<h1><a class="toc-backref" href="#id11">Thanks to</a></h1> |
229 |
|
|
<dl class="docutils"> |
230 |
|
|
<dt>I'd like to thank the following folks, in no specific order:</dt> |
231 |
|
|
<dd><ul class="first last simple"> |
232 |
|
|
<li>Ciaran McCreesh (ciaranm) - for pointing out the Joux (2004) paper, |
233 |
|
|
and also being stubborn enough in not accepting a partial solution.</li> |
234 |
|
|
<li>Marius Mauch (genone), Zac Medico (zmedico) and Brian Harring |
235 |
|
|
(ferringb): for being knowledgeable about the Portage Manifest2 |
236 |
|
|
codebase.</li> |
237 |
|
|
</ul> |
238 |
|
|
</dd> |
239 |
|
|
</dl> |
240 |
|
|
</div> |
241 |
|
|
<div class="section" id="copyright"> |
242 |
|
|
<h1><a class="toc-backref" href="#id12">Copyright</a></h1> |
243 |
robbat2 |
1.4 |
<p>Copyright (c) 2006-2010 by Robin Hugh Johnson. This material may be |
244 |
cardoe |
1.1 |
distributed only subject to the terms and conditions set forth in the |
245 |
|
|
Open Publication License, v1.0.</p> |
246 |
|
|
<p>vim: tw=72 ts=2 expandtab:</p> |
247 |
|
|
</div> |
248 |
|
|
|
249 |
|
|
</div> |
250 |
|
|
<div class="footer"> |
251 |
|
|
<hr class="footer" /> |
252 |
|
|
<a class="reference external" href="glep-0059.txt">View document source</a>. |
253 |
robbat2 |
1.9 |
Generated on: 2010-02-02 05:44 UTC. |
254 |
cardoe |
1.1 |
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. |
255 |
|
|
|
256 |
|
|
</div> |
257 |
|
|
</body> |
258 |
|
|
</html> |