/[gentoo]/xml/htdocs/proj/en/glep/glep-0059.txt

Diff of /xml/htdocs/proj/en/glep/glep-0059.txt

Parent Directory | Revision Log | View Patch Patch

Revision 1.4		Revision 1.9
1	GLEP: 59	1	GLEP: 59
2	Title: Manifest2 hash policies and security implications	2	Title: Manifest2 hash policies and security implications
3	Version: $Revision: 1.4 $	3	Version: $Revision: 1.9 $
4	Last-Modified: $Date: 2010/01/13 03:26:53 $	4	Last-Modified: $Date: 2010/04/07 21:34:24 $
5	Author: Robin Hugh Johnson <robbat2@gentoo.org>,	5	Author: Robin Hugh Johnson <robbat2@gentoo.org>,
6	Status: Draft	6	Status: Draft
7	Type: Standards Track	7	Type: Standards Track
8	Content-Type: text/x-rst	8	Content-Type: text/x-rst
9	Requires: 44	9	Requires: 44
10	Created: October 2006	10	Created: October 2006
11	Updated: November 2007, June 2008, July 2008, October 2008, January 2010	11	Updated: November 2007, June 2008, July 2008, October 2008, January 2010
12	Updates: 44	12	Updates: 44
13	Post-History: December 2009	13	Post-History: December 2009, January 2010
14		14
15	Abstract	15	Abstract
16	========	16	========
17	While Manifest2 format allows multiple hashes, the question of which	17	While Manifest2 format allows multiple hashes, the question of which
18	checksums should be present, why, and the security implications of such	18	checksums should be present, why, and the security implications of such
…		…
24	==========	24	==========
25	This GLEP is being written as part of the work on signing the Portage	25	This GLEP is being written as part of the work on signing the Portage
26	tree, but is only tangentially related to the actual signing of	26	tree, but is only tangentially related to the actual signing of
27	Manifests. Checksums present one possible weak point in the overall	27	Manifests. Checksums present one possible weak point in the overall
28	security of the tree - and a comprehensive security plan is needed.	28	security of the tree - and a comprehensive security plan is needed.
		29
		30	This GLEP is not mandatory for the tree-signing specification, but
		31	instead aims to improve the security of the hashes used in Manifest2
		32	[GLEP44]. As such, it is also able to stand on it's own.
29		33
30	Specification	34	Specification
31	=============	35	=============
32	The bad news	36	The bad news
33	------------	37	------------
…		…
37	The most common position (and indeed the one previously held by myself),	41	The most common position (and indeed the one previously held by myself),
38	is that multiple checksums would be an increase in security, but we	42	is that multiple checksums would be an increase in security, but we
39	could not provably quantify the amount of security this added.	43	could not provably quantify the amount of security this added.
40	The really bad news, is that this position is completely and utterly	44	The really bad news, is that this position is completely and utterly
41	wrong. Many of you will be aghast at this. There is extremely little	45	wrong. Many of you will be aghast at this. There is extremely little
42	added security in multiple checksums [J04]. For any set of checksums,	46	added security in multiple checksums as noted by Joux [J04]. For any set
43	the actual strength lies in that of the strongest checksum.	47	of checksums, the actual strength lies in that of the strongest
		48	checksum.
		49
		50	Wang et al [W04] extended Joux's [J04] work on SHA-0 to cover MD4, MD5,
		51	HAVAL-128 and RIPEMD families of hashes.
44		52
45	How fast can MD5 be broken?	53	How fast can MD5 be broken?
46	---------------------------	54	---------------------------
47	For a general collision, not a pre-image attack, since the original	55	For a general collision, not a pre-image attack, since the announcement
48	announcement by Wang et al [W04], the time required to break MD5 has	56	by Wang et al [W04], the time required to break MD5 has been massively
49	been massively reduced. Originally at 1 hour on a near-supercomputer	57	reduced. Originally at 1 hour on a near-supercomputer (IBM P690) and
50	(IBM P690) and estimated at 64 hours with a Pentium-3 1.7Ghz. This has	58	estimated at 64 hours with a Pentium-3 1.7Ghz. This has gone down to
51	gone down to less than in two years, to 17 seconds [K06a]!	59	less than in two years, to 17 seconds [K06a].
52		60
53	08/2004 - 1 hour, IBM pSeries 690 (32x 1.7Ghz POWER4+) = 54.4 GHz-Hours	61	- 08/2004 - 1 hour, IBM pSeries 690 (32x 1.7Ghz POWER4+) = 54.4 GHz-Hours
		62
54	03/2005 - 8 hours, Pentium-M 1.6Ghz = 12.8 Ghz-Hours	63	- 03/2005 - 8 hours, Pentium-M 1.6Ghz = 12.8 Ghz-Hours
		64
55	11/2005 - 5 hours, Pentium-4 1.7Ghz = 8.5 Ghz-Hours	65	- 11/2005 - 5 hours, Pentium-4 1.7Ghz = 8.5 Ghz-Hours
		66
56	03/2006 - 1 minute, Pentium-4 3.2Ghz = .05 Ghz-Hours	67	- 03/2006 - 1 minute, Pentium-4 3.2Ghz = .05 Ghz-Hours
		68
57	04/2006 - 17 seconds, Pentium-4 3.2Ghz = .01 Ghz-Hours	69	- 04/2006 - 17 seconds, Pentium-4 3.2Ghz = .01 Ghz-Hours
58		70
59	If we accept a factor of 800x as a sample of how much faster a checksum	71	If we accept a factor of 800x as a sample of how much faster a checksum
60	may be broken over the course of 2 years (MD5 using the above data is	72	may be broken over the course of 2 years (MD5 using the above data is
61	>2000x), then existing checksums do not stand a significant chance of	73	>2000x), then existing checksums do not stand a significant chance of
62	survival in the future. We should thus accept that whatever checksums we	74	survival in the future. We should thus accept that whatever checksums we
63	are using today, will be broken in the near future, and plan as best as	75	are using today, will be broken in the near future, and plan as best as
64	possible. (A brief review [H04] of the present SHA1 attacks indicates an	76	possible. (A brief review [H04] of the SHA1 attacks indicates an
65	improvement of ~600x in the same timespan).	77	improvement of ~600x in the same timespan).
66		78
67	And for those that claim implementation of these procedures is not yet	79	And for those that claim implementation of these procedures is not yet
68	feasible, see [K06b] for an application that can produce two	80	feasible, see [K06b] for an application that can produce two
69	self-extracting .exe files, with identical MD5s, and whatever payload	81	self-extracting EXE files, with identical MD5s, and whatever payload you
70	you want.	82	want.
71		83
72	The good news	84	The good news
73	-------------	85	-------------
74	Of the checksums presently used by Manifest2, one stands close to being	86	Of the checksums presently used by Manifest2 (SHA1, SHA256, RIPEMD160),
75	completely broken: SHA1. The SHA2 series has suffered some attacks, but	87	one stands close to being completely broken: SHA1; and another is
76	still remains reasonably solid [G07],[K08]. No attacks against RIPEMD160	88	significantly weakened: RIPEMD160. The SHA2 series has suffered some
77	have been published, however it is constructed in the same manner as	89	attacks, but still remains reasonably solid [G07],[K08].
78	MD5, SHA1 and SHA2, so is also vulnerable to the new methods of
79	cryptanalysis [H04].
80		90
81	To reduce the potential for future problems and any single checksum	91	To reduce the potential for future problems and any single checksum
82	break leading to a rapid decrease in security, we should incorporate the	92	break leading to a rapid decrease in security, we should incorporate the
83	strongest hash available from each family of checksums, and be prepared	93	strongest hash available from each family of checksums, and be prepared
84	to retire old checksums actively, unless there is a overriding reason to	94	to retire old checksums actively, unless there is a overriding reason to
85	keep a specific checksum.	95	keep a specific checksum, such as part of a migration plan.
86		96
87	What should be done	97	What should be done
88	-------------------	98	-------------------
89	Portage should always try to verify all supported hashes that are	99	Portage should always try to verify all supported hashes that are
90	available in a Manifest2, starting with the strongest ones as maintained	100	available in a Manifest2, starting with the strongest ones as maintained
91	by a preference list. Over time, the weaker checksums should be removed	101	by a preference list. Over time, the weaker checksums should be removed
92	from Manifest2 files, once all old Portage installations have had	102	from Manifest2 files, once all old Portage installations have had
93	sufficient time to upgrade. We should be prepared to add stronger	103	sufficient time to upgrade. Stronger checksums shall be added as soon as
94	checksums wherever possible, and to remove those that have been	104	an implementation is available in Portage. Weak checksums may be removed
95	defeated.	105	as long as the depreciation process is followed (see below).
96		106
		107	As soon as feasible, we should add the SHA512 and WHIRLPOOL algorithms.
		108	In future, as stream-based checksums are developed (in response to the
		109	development by NIST [AHS]), they should be considered and used.
		110
		111	The SHA512 algorithm is available in Python 2.5, which has been a
		112	dependency of Portage since approximately Portage 2.1.6.13.
		113
		114	The WHIRLPOOL checksum is not available within the PyCrypto library or
		115	hashlib that is part of Python 2.5, but there are multiple alternative
		116	Python implementations available, ranging from pure Python to C-based
		117	(python-mhash).
		118
97	An unsupported hash is not considered to be a failure unless no	119	The existence unsupported hash is not considered to be a failure unless
98	supported hashes are available.	120	no supported hashes are available for a given Manifest entry.
99		121
100	Checksum depreciation	122	Checksum depreciation timing
		123	----------------------------
		124	General principles:
101	~~~~~~~~~~~~~~~~~~~~~	125	~~~~~~~~~~~~~~~~~~~
102	For the current Portage, SHA1 should be gradually removed, as presents	126	A minimum set of depreciated checksums shall be maintained only to
103	no advantages over SHA256. Beyond one specific problem (see the next	127	support old package manager versions where needed by historically used
104	paragraph), we should add SHA512 (SHA2, 512 bit size), the Whirlpool	128	trees:
105	checksum (standardized checksum, with no known weaknesses). In future,
106	as stream-based checksums are developed (in response to the development
107	by NIST [AHS]), they should be considered and used.
108		129
109	There is one temporary stumbling block at hand - the existing Portage	130	- New package manager versions should NOT use depreciated checksums in
110	infrastructure does not support SHA384/512 or Whirlpool, thus hampering	131
111	their immediate acceptance. SHA512 is available in Python 2.5, while	132	- New trees with that have never used the depreciated checksums may omit
112	SHA1 is already available in Python 2.4. After Python2.5 is established	133	them for reasons of size, but are still strongly suggested to include
113	in a Gentoo media release, that would be a suitable time to remove SHA1	134	them.
114	from Manifest2 files.	135
		136	- Removal of depreciated checksums shall happen after no less than 18
		137	months or one major Portage version cycle, whichever is greater.
		138
		139	Immediate plans:
		140	~~~~~~~~~~~~~~~~
		141	For the current Portage, both SHA1 and RIPEMD160 should be immediately
		142	removed, as they present no advantages over the already present SHA256.
		143	SHA256 cannot be replaced immediately with SHA512, as existing Portage
		144	versions need at least one supported algorithm present (SHA256 support
		145	was added in June 2006), so it must be retained for some while.
		146
		147	Immediately:
		148
		149	- Add WHIRLPOOL and SHA512.
		150
		151	- Remove SHA1 and RIPEMD160.
		152
		153	After the majority of Portage installations include SHA512 support:
		154
		155	- Remove SHA256.
115		156
116	Backwards Compatibility	157	Backwards Compatibility
117	=======================	158	=======================
118	Old versions of Portage may support and expect only specific checksums.	159	Old versions of Portage may support and expect only specific checksums.
119	This is accounted for in the checksum depreciation discussion.	160	This is accounted for in the checksum depreciation discussion.
		161
		162	For maximum compatiability, we should only have to include each of the
		163	old algorithms that we are officially still supporting, as well as the
		164	new ones that we prefer.
120		165
121	References	166	References
122	==========	167	==========
123		168
124	[AHS] NIST (2007). "NIST's Plan for New Cryptographic Hash Functions",	169	[AHS] NIST (2007). "NIST's Plan for New Cryptographic Hash Functions",
…		…
170	and also being stubborn enough in not accepting a partial solution.	215	and also being stubborn enough in not accepting a partial solution.
171	- Marius Mauch (genone), Zac Medico (zmedico) and Brian Harring	216	- Marius Mauch (genone), Zac Medico (zmedico) and Brian Harring
172	(ferringb): for being knowledgeable about the Portage Manifest2	217	(ferringb): for being knowledgeable about the Portage Manifest2
173	codebase.	218	codebase.
174		219
		220	References
		221	==========
		222	.. [GLEP44] Mauch, M. (2005) GLEP44 - Manifest2 format.
		223	http://www.gentoo.org/proj/en/glep/glep-0044.html
		224
175	Copyright	225	Copyright
176	=========	226	=========
177	Copyright (c) 2006-2010 by Robin Hugh Johnson. This material may be	227	Copyright (c) 2006-2010 by Robin Hugh Johnson. This material may be
178	distributed only subject to the terms and conditions set forth in the	228	distributed only subject to the terms and conditions set forth in the
179	Open Publication License, v1.0.	229	Open Publication License, v1.0.
180		230
181	vim: tw=72 ts=2 expandtab:	231	.. vim: tw=72 ts=2 expandtab:

 Legend:



Removed from v.1.4
 


changed lines


 
Added in v.1.9
 Legend:



Removed from v.1.4
 


changed lines


 
Added in v.1.9
-Removed from v.1.4
+Added in v.1.9

	ViewVC Help
Powered by ViewVC 1.1.13