/[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.1		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.1 $	3	Version: $Revision: 1.6 $
4	Last-Modified: $Date: 2008/10/21 23:30:47 $	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	11	Updated: November 2007, June 2008, July 2008, October 2008, January 2010
12	Updates: 44	12	Updates: 44
		13	Post-History: December 2009, January 2010
13		14
14	Abstract	15	Abstract
15	========	16	========
16	While Manifest2 format allows multiple hashes, the question of which	17	While Manifest2 format allows multiple hashes, the question of which
17	checksums should be present, why, and the security implications of such	18	checksums should be present, why, and the security implications of such
…		…
24	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
25	tree, but is only tangentially related to the actual signing of	26	tree, but is only tangentially related to the actual signing of
26	Manifests. Checksums present one possible weak point in the overall	27	Manifests. Checksums present one possible weak point in the overall
27	security of the tree - and a comprehensive security plan is needed.	28	security of the tree - and a comprehensive security plan is needed.
28		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
29	Specification	34	Specification
30	=============	35	=============
31	The bad news	36	The bad news
32	------------	37	------------
33	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.
…		…
36	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),
37	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
38	could not provably quantify the amount of security this added.	43	could not provably quantify the amount of security this added.
39	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
40	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
41	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
42	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.
43		52
44	How fast can MD5 be broken?	53	How fast can MD5 be broken?
45	---------------------------	54	---------------------------
46	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
47	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
48	been massively reduced. Originally at 1 hour on a near-supercomputer	57	reduced. Originally at 1 hour on a near-supercomputer (IBM P690) and
49	(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
50	gone down to less than in two years, to 17 seconds [K06a]!	59	less than in two years, to 17 seconds [K06a].
51		60
52	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
53	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
54	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
55	03/2006 - 1 minute, Pentium-4 3.2Ghz = .05 Ghz-Hours	64	03/2006 - 1 minute, Pentium-4 3.2Ghz = .05 Ghz-Hours
…		…
58	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
59	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
60	>2000x), then existing checksums do not stand a significant chance of	69	>2000x), then existing checksums do not stand a significant chance of
61	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
62	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
63	possible. (A brief review [H04] of the present SHA1 attacks indicates an	72	possible. (A brief review [H04] of the SHA1 attacks indicates an
64	improvement of ~600x in the same timespan).	73	improvement of ~600x in the same timespan).
65		74
66	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
67	feasible, see [K06b] for an application that can produce two	76	feasible, see [K06b] for an application that can produce two
68	self-extracting .exe files, with identical MD5s, and whatever payload	77	self-extracting EXE files, with identical MD5s, and whatever payload you
69	you want.	78	want.
70		79
71	The good news	80	The good news
72	-------------	81	-------------
73	Of the checksums presently used by Manifest2, one stands close to being	82	Of the checksums presently used by Manifest2 (SHA1, SHA256, RIPEMD160),
74	completely broken: SHA1. The SHA2 series has suffered some attacks, but	83	one stands close to being completely broken: SHA1; and another is
75	still remains reasonably solid [G07],[K08]. No attacks against RIPEMD160	84	significantly weakened: RIPEMD160. The SHA2 series has suffered some
76	have been published, however it is constructed in the same manner as	85	attacks, but still remains reasonably solid [G07],[K08].
77	MD5, SHA1 and SHA2, so is also vulnerable to the new methods of
78	cryptanalysis [H04].
79		86
80	To reduce the potential for future problems and any single checksum	87	To reduce the potential for future problems and any single checksum
81	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
82	strongest hash available from each family of checksums, and be prepared	89	strongest hash available from each family of checksums, and be prepared
83	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
84	keep a specific checksum.	91	keep a specific checksum, such as part of a migration plan.
85		92
86	What should be done	93	What should be done
87	-------------------	94	-------------------
88	Portage should always try to verify all supported hashes that are	95	Portage should always try to verify all supported hashes that are
89	available in a Manifest2, starting with the strongest ones as maintained	96	available in a Manifest2, starting with the strongest ones as maintained
…		…
91	from Manifest2 files, once all old Portage installations have had	98	from Manifest2 files, once all old Portage installations have had
92	sufficient time to upgrade. We should be prepared to add stronger	99	sufficient time to upgrade. We should be prepared to add stronger
93	checksums wherever possible, and to remove those that have been	100	checksums wherever possible, and to remove those that have been
94	defeated.	101	defeated.
95		102
96	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.
97	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.
98		106
99	Checksum depreciation	107	The SHA512 algorithm is available in Python 2.5, which has been a
100	~~~~~~~~~~~~~~~~~~~~~	108	dependency of Portage since approximately Python 2.1.6.13.
101	For the current Portage, SHA1 should be gradually removed, as presents
102	no advantages over SHA256. Beyond one specific problem (see the next
103	paragraph), we should add SHA512 (SHA2, 512 bit size), the Whirlpool
104	checksum (standardized checksum, with no known weaknesses). In future,
105	as stream-based checksums are developed (in response to the development
106	by NIST [AHS]), they should be considered and used.
107		109
108	There is one temporary stumbling block at hand - the existing Portage	110	The WHIRLPOOL checksum is not available within the PyCrypto library or
109	infrastructure does not support SHA384/512 or Whirlpool, thus hampering	111	hashlib that is part of Python 2.5, but there are multiple alternative
110	their immediate acceptance. SHA512 is available in Python 2.5, while	112	Python implementations available, ranging from pure Python to C-based
111	SHA1 is already available in Python 2.4. After Python2.5 is established	113	(python-mhash).
112	in a Gentoo media release, that would be a suitable time to remove SHA1	114
113	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.
114		132
115	Backwards Compatibility	133	Backwards Compatibility
116	=======================	134	=======================
117	Old versions of Portage may support and expect only specific checksums.	135	Old versions of Portage may support and expect only specific checksums.
118	This is accounted for in the checksum depreciation discussion.	136	This is accounted for in the checksum depreciation discussion.
…		…
132	[H04] Hawkes, P. and Paddon, M. and Rose, G. (2004). "On Corrective	150	[H04] Hawkes, P. and Paddon, M. and Rose, G. (2004). "On Corrective
133	Patterns for the SHA-2 Family". CRYPTO 2004 Cryptology ePrint Archive,	151	Patterns for the SHA-2 Family". CRYPTO 2004 Cryptology ePrint Archive,
134	Report 2004/204. Available online from:	152	Report 2004/204. Available online from:
135	http://eprint.iacr.org/2004/207.pdf	153	http://eprint.iacr.org/2004/207.pdf
136		154
137	[J04] Joux, Antoie. (2004). "Multicollisions in Iterated Hash Functions	155	[J04] Joux, Antoie. (2004). "Multicollisions in Iterated Hash
138	- Application to Cascaded Constructions;" Proceedings of CRYPTO 2004,	156	Functions - Application to Cascaded Constructions;" Proceedings of
139	Franklin, M. (Ed); Lecture Notes in Computer Science 3152, pp.	157	CRYPTO 2004, Franklin, M. (Ed); Lecture Notes in Computer Science
140	306-316. Available online from:	158	3152, pp. 306-316. Available online from:
141	http://web.cecs.pdx.edu/~teshrim/spring06/papers/general-attacks/multi-joux.pdf	159	http://web.cecs.pdx.edu/~teshrim/spring06/papers/general-attacks/multi-joux.pdf
142		160
143	[K06a] Klima, V. (2006). "Tunnels in Hash Functions: MD5 Collisions	161	[K06a] Klima, V. (2006). "Tunnels in Hash Functions: MD5 Collisions
144	Within a Minute". Cryptology ePrint Archive, Report 2006/105.	162	Within a Minute". Cryptology ePrint Archive, Report 2006/105.
145	Available online from: http://eprint.iacr.org/2006/105.pdf	163	Available online from: http://eprint.iacr.org/2006/105.pdf
…		…
171	(ferringb): for being knowledgeable about the Portage Manifest2	189	(ferringb): for being knowledgeable about the Portage Manifest2
172	codebase.	190	codebase.
173		191
174	Copyright	192	Copyright
175	=========	193	=========
176	Copyright (c) 2006 by Robin Hugh Johnson. This material may be	194	Copyright (c) 2006-2010 by Robin Hugh Johnson. This material may be
177	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
178	Open Publication License, v1.0.	196	Open Publication License, v1.0.
179		197
180	vim: tw=72 ts=2 expandtab:	198	vim: tw=72 ts=2 expandtab:

 Legend:



Removed from v.1.1
 


changed lines


 
Added in v.1.6
 Legend:



Removed from v.1.1
 


changed lines


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

	ViewVC Help
Powered by ViewVC 1.1.20