/[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.3		Revision 1.6
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.3 $	3	Version: $Revision: 1.6 $
4	Last-Modified: $Date: 2008/10/28 07:45:44 $	4	Last-Modified: $Date: 2010/01/31 09:55:43 $
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	11	Updated: November 2007, June 2008, July 2008, October 2008, January 2010
12	Updates: 44	12	Updates: 44
13	Post-History:	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
…		…
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		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	As such, it is also able to stand on it's own.
		33
30	Specification	34	Specification
31	=============	35	=============
32	The bad news	36	The bad news
33	------------	37	------------
34	First of all, I'd like to cover the bad news in checksum security.	38	First of all, I'd like to cover the bad news in checksum security.
…		…
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
54	03/2005 - 8 hours, Pentium-M 1.6Ghz = 12.8 Ghz-Hours	62	03/2005 - 8 hours, Pentium-M 1.6Ghz = 12.8 Ghz-Hours
55	11/2005 - 5 hours, Pentium-4 1.7Ghz = 8.5 Ghz-Hours	63	11/2005 - 5 hours, Pentium-4 1.7Ghz = 8.5 Ghz-Hours
56	03/2006 - 1 minute, Pentium-4 3.2Ghz = .05 Ghz-Hours	64	03/2006 - 1 minute, Pentium-4 3.2Ghz = .05 Ghz-Hours
…		…
59	If we accept a factor of 800x as a sample of how much faster a checksum	67	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	68	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	69	>2000x), then existing checksums do not stand a significant chance of
62	survival in the future. We should thus accept that whatever checksums we	70	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	71	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	72	possible. (A brief review [H04] of the SHA1 attacks indicates an
65	improvement of ~600x in the same timespan).	73	improvement of ~600x in the same timespan).
66		74
67	And for those that claim implementation of these procedures is not yet	75	And for those that claim implementation of these procedures is not yet
68	feasible, see [K06b] for an application that can produce two	76	feasible, see [K06b] for an application that can produce two
69	self-extracting .exe files, with identical MD5s, and whatever payload	77	self-extracting EXE files, with identical MD5s, and whatever payload you
70	you want.	78	want.
71		79
72	The good news	80	The good news
73	-------------	81	-------------
74	Of the checksums presently used by Manifest2, one stands close to being	82	Of the checksums presently used by Manifest2 (SHA1, SHA256, RIPEMD160),
75	completely broken: SHA1. The SHA2 series has suffered some attacks, but	83	one stands close to being completely broken: SHA1; and another is
76	still remains reasonably solid [G07],[K08]. No attacks against RIPEMD160	84	significantly weakened: RIPEMD160. The SHA2 series has suffered some
77	have been published, however it is constructed in the same manner as	85	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		86
81	To reduce the potential for future problems and any single checksum	87	To reduce the potential for future problems and any single checksum
82	break leading to a rapid decrease in security, we should incorporate the	88	break leading to a rapid decrease in security, we should incorporate the
83	strongest hash available from each family of checksums, and be prepared	89	strongest hash available from each family of checksums, and be prepared
84	to retire old checksums actively, unless there is a overriding reason to	90	to retire old checksums actively, unless there is a overriding reason to
85	keep a specific checksum.	91	keep a specific checksum, such as part of a migration plan.
86		92
87	What should be done	93	What should be done
88	-------------------	94	-------------------
89	Portage should always try to verify all supported hashes that are	95	Portage should always try to verify all supported hashes that are
90	available in a Manifest2, starting with the strongest ones as maintained	96	available in a Manifest2, starting with the strongest ones as maintained
…		…
92	from Manifest2 files, once all old Portage installations have had	98	from Manifest2 files, once all old Portage installations have had
93	sufficient time to upgrade. We should be prepared to add stronger	99	sufficient time to upgrade. We should be prepared to add stronger
94	checksums wherever possible, and to remove those that have been	100	checksums wherever possible, and to remove those that have been
95	defeated.	101	defeated.
96		102
97	An unsupported hash is not considered to be a failure unless no	103	As soon as feasible, we should add the SHA512 and WHIRLPOOL algorithms.
98	supported hashes are available.	104	In future, as stream-based checksums are developed (in response to the
		105	development by NIST [AHS]), they should be considered and used.
99		106
100	Checksum depreciation	107	The SHA512 algorithm is available in Python 2.5, which has been a
101	~~~~~~~~~~~~~~~~~~~~~	108	dependency of Portage since approximately Python 2.1.6.13.
102	For the current Portage, SHA1 should be gradually removed, as presents
103	no advantages over SHA256. Beyond one specific problem (see the next
104	paragraph), we should add SHA512 (SHA2, 512 bit size), the Whirlpool
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		109
109	There is one temporary stumbling block at hand - the existing Portage	110	The WHIRLPOOL checksum is not available within the PyCrypto library or
110	infrastructure does not support SHA384/512 or Whirlpool, thus hampering	111	hashlib that is part of Python 2.5, but there are multiple alternative
111	their immediate acceptance. SHA512 is available in Python 2.5, while	112	Python implementations available, ranging from pure Python to C-based
112	SHA1 is already available in Python 2.4. After Python2.5 is established	113	(python-mhash).
113	in a Gentoo media release, that would be a suitable time to remove SHA1	114
114	from Manifest2 files.	115	The existence unsupported hash is not considered to be a failure unless
		116	no supported hashes are available for a given Manifest entry.
		117
		118	Checksum depreciation timing
		119	----------------------------
		120	For the current Portage, both SHA1 and RIPEMD160 should be immediately
		121	removed, as they present no advantages over the already present SHA256.
		122	SHA256 cannot be replaced immediately with SHA512, as existing Portage
		123	versions need at least one supported algorithm present (SHA256 support
		124	was added in June 2006), so it must be retained for some while.
		125
		126	Immediately:
		127	- Add WHIRLPOOL and SHA512.
		128	- Remove SHA1 and RIPEMD160.
		129
		130	After the majority of Portage installations include SHA512 support:
		131	- Remove SHA256.
115		132
116	Backwards Compatibility	133	Backwards Compatibility
117	=======================	134	=======================
118	Old versions of Portage may support and expect only specific checksums.	135	Old versions of Portage may support and expect only specific checksums.
119	This is accounted for in the checksum depreciation discussion.	136	This is accounted for in the checksum depreciation discussion.
…		…
172	(ferringb): for being knowledgeable about the Portage Manifest2	189	(ferringb): for being knowledgeable about the Portage Manifest2
173	codebase.	190	codebase.
174		191
175	Copyright	192	Copyright
176	=========	193	=========
177	Copyright (c) 2006 by Robin Hugh Johnson. This material may be	194	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	195	distributed only subject to the terms and conditions set forth in the
179	Open Publication License, v1.0.	196	Open Publication License, v1.0.
180		197
181	vim: tw=72 ts=2 expandtab:	198	vim: tw=72 ts=2 expandtab:

 Legend:



Removed from v.1.3
 


changed lines


 
Added in v.1.6
 Legend:



Removed from v.1.3
 


changed lines


 
Added in v.1.6
-Removed from v.1.3
+Added in v.1.6

	ViewVC Help
Powered by ViewVC 1.1.20