| 1 |
GLEP: 59 |
| 2 |
Title: Manifest2 hash policies and security implications |
| 3 |
Version: $Revision: 1.11 $ |
| 4 |
Last-Modified: $Date: 2008/07/13 02:23:36 $ |
| 5 |
Author: Robin Hugh Johnson <robbat2@gentoo.org>, |
| 6 |
Status: Draft |
| 7 |
Type: Standards Track |
| 8 |
Content-Type: text/x-rst |
| 9 |
Requires: 44 |
| 10 |
Created: October 2006 |
| 11 |
Updated: November 2007, June 2008, July 2008 |
| 12 |
Updates: 44 |
| 13 |
|
| 14 |
Abstract |
| 15 |
======== |
| 16 |
While Manifest2 format allows multiple hashes, the question of which |
| 17 |
checksums should be present, why, and the security implications of such |
| 18 |
have never been resolved. This GLEP covers all of these issues, and |
| 19 |
makes recommendations as to how to handle checksums both now, and in |
| 20 |
future. |
| 21 |
|
| 22 |
Motivation |
| 23 |
========== |
| 24 |
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 |
Manifests. Checksums present one possible weak point in the overall |
| 27 |
security of the tree - and a comprehensive security plan is needed. |
| 28 |
|
| 29 |
Specification |
| 30 |
============= |
| 31 |
The bad news |
| 32 |
------------ |
| 33 |
First of all, I'd like to cover the bad news in checksum security. |
| 34 |
A much discussed point, as been the simple question: What is the |
| 35 |
security of multiple independent checksums on the same data? |
| 36 |
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 |
| 38 |
could not provably quantify the amount of security this added. |
| 39 |
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 |
| 41 |
added security in multiple checksums [J04]. For any set of checksums, |
| 42 |
the actual strength lies in that of the strongest checksum. |
| 43 |
|
| 44 |
How fast can MD5 be broken? |
| 45 |
--------------------------- |
| 46 |
For a general collision, not a pre-image attack, since the original |
| 47 |
announcement by Wang et al [W04], the time required to break MD5 has |
| 48 |
been massively reduced. Originally at 1 hour on a near-supercomputer |
| 49 |
(IBM P690) and estimated at 64 hours with a Pentium-3 1.7Ghz. This has |
| 50 |
gone down to less than in two years, to 17 seconds [K06a]! |
| 51 |
|
| 52 |
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 |
| 54 |
11/2005 - 5 hours, Pentium-4 1.7Ghz = 8.5 Ghz-Hours |
| 55 |
03/2006 - 1 minute, Pentium-4 3.2Ghz = .05 Ghz-Hours |
| 56 |
04/2006 - 17 seconds, Pentium-4 3.2Ghz = .01 Ghz-Hours |
| 57 |
|
| 58 |
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 |
| 60 |
>2000x), then existing checksums do not stand a significant chance of |
| 61 |
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 |
| 63 |
possible. (A brief review [H04] of the present SHA1 attacks indicates an |
| 64 |
improvement of ~600x in the same timespan). |
| 65 |
|
| 66 |
And for those that claim implementation of these procedures is not yet |
| 67 |
feasible, see [K06b] for an application that can produce two |
| 68 |
self-extracting .exe files, with identical MD5s, and whatever payload |
| 69 |
you want. |
| 70 |
|
| 71 |
The good news |
| 72 |
------------- |
| 73 |
Of the checksums presently used by Manifest2, one stands close to being |
| 74 |
completely broken: SHA1. The SHA2 series has suffered some attacks, but |
| 75 |
still remains reasonably solid [G07],[K08]. No attacks against RIPEMD160 |
| 76 |
have been published, however it is constructed in the same manner as |
| 77 |
MD5, SHA1 and SHA2, so is also vulnerable to the new methods of |
| 78 |
cryptanalysis [H04]. |
| 79 |
|
| 80 |
To reduce the potential for future problems and any single checksum |
| 81 |
break leading to a rapid decrease in security, we should incorporate the |
| 82 |
strongest hash available from each family of checksums, and be prepared |
| 83 |
to retire old checksums actively, unless there is a overriding reason to |
| 84 |
keep a specific checksum. |
| 85 |
|
| 86 |
What should be done |
| 87 |
------------------- |
| 88 |
Portage should always try to verify all supported hashes that are |
| 89 |
available in a Manifest2, starting with the strongest ones as maintained |
| 90 |
by a preference list. Over time, the weaker checksums should be removed |
| 91 |
from Manifest2 files, once all old Portage installations have had |
| 92 |
sufficient time to upgrade. We should be prepared to add stronger |
| 93 |
checksums wherever possible, and to remove those that have been |
| 94 |
defeated. |
| 95 |
|
| 96 |
An unsupported hash is not considered to be a failure unless no |
| 97 |
supported hashes are available. |
| 98 |
|
| 99 |
Checksum depreciation |
| 100 |
~~~~~~~~~~~~~~~~~~~~~ |
| 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 |
|
| 108 |
There is one temporary stumbling block at hand - the existing Portage |
| 109 |
infrastructure does not support SHA384/512 or Whirlpool, thus hampering |
| 110 |
their immediate acceptance. SHA512 is available in Python 2.5, while |
| 111 |
SHA1 is already available in Python 2.4. After Python2.5 is established |
| 112 |
in a Gentoo media release, that would be a suitable time to remove SHA1 |
| 113 |
from Manifest2 files. |
| 114 |
|
| 115 |
Backwards Compatibility |
| 116 |
======================= |
| 117 |
Old versions of Portage may support and expect only specific checksums. |
| 118 |
This is accounted for in the checksum depreciation discussion. |
| 119 |
|
| 120 |
References |
| 121 |
========== |
| 122 |
|
| 123 |
[AHS] NIST (2007). "NIST's Plan for New Cryptographic Hash Functions", |
| 124 |
(Advanced Hash Standard). http://csrc.nist.gov/pki/HashWorkshop/ |
| 125 |
|
| 126 |
[BOBO06] Boneh, D. and Boyen, X. (2006). "On the Impossibility of |
| 127 |
Efficiently Combining Collision Resistant Hash Functions"; Proceedings |
| 128 |
of CRYPTO 2006, Dwork, C. (Ed.); Lecture Notes in Computer Science |
| 129 |
4117, pp. 570-583. Available online from: |
| 130 |
http://crypto.stanford.edu/~dabo/abstracts/hashing.html |
| 131 |
|
| 132 |
[H04] Hawkes, P. and Paddon, M. and Rose, G. (2004). "On Corrective |
| 133 |
Patterns for the SHA-2 Family". CRYPTO 2004 Cryptology ePrint Archive, |
| 134 |
Report 2004/204. Available online from: |
| 135 |
http://eprint.iacr.org/2004/207.pdf |
| 136 |
|
| 137 |
[J04] Joux, Antoie. (2004). "Multicollisions in Iterated Hash Functions |
| 138 |
- Application to Cascaded Constructions;" Proceedings of CRYPTO 2004, |
| 139 |
Franklin, M. (Ed); Lecture Notes in Computer Science 3152, pp. |
| 140 |
306-316. Available online from: |
| 141 |
http://web.cecs.pdx.edu/~teshrim/spring06/papers/general-attacks/multi-joux.pdf |
| 142 |
|
| 143 |
[K06a] Klima, V. (2006). "Tunnels in Hash Functions: MD5 Collisions |
| 144 |
Within a Minute". Cryptology ePrint Archive, Report 2006/105. |
| 145 |
Available online from: http://eprint.iacr.org/2006/105.pdf |
| 146 |
|
| 147 |
[K06b] Klima, V. (2006). "Note and links to high-speed MD5 collision |
| 148 |
proof of concept tools". Available online from: |
| 149 |
http://cryptography.hyperlink.cz/2006/trick.txt |
| 150 |
|
| 151 |
[K08] Klima, V. (2008). "On Collisions of Hash Functions Turbo SHA-2". |
| 152 |
Cryptology ePrint Archive, Report 2008/003. Available online from: |
| 153 |
http://eprint.iacr.org/2008/003.pdf |
| 154 |
|
| 155 |
[G07] Gligoroski, D. and Knapskog, S.J. (2007). "Turbo SHA-2". |
| 156 |
Cryptology ePrint Archive, Report 2007/403. Available online from: |
| 157 |
http://eprint.iacr.org/2007/403.pdf |
| 158 |
|
| 159 |
[W04] Wang, X. et al: "Collisions for Hash Functions MD4, MD5, |
| 160 |
HAVAL-128 and RIPEMD", rump session, CRYPTO 2004, Cryptology ePrint |
| 161 |
Archive, Report 2004/199, first version (August 16, 2004), second |
| 162 |
version (August 17, 2004). Available online from: |
| 163 |
http://eprint.iacr.org/2004/199.pdf |
| 164 |
|
| 165 |
Thanks to |
| 166 |
========= |
| 167 |
I'd like to thank the following folks, in no specific order: |
| 168 |
- Ciaran McCreesh (ciaranm) - for pointing out the Joux (2004) paper, |
| 169 |
and also being stubborn enough in not accepting a partial solution. |
| 170 |
- Marius Mauch (genone), Zac Medico (zmedico) and Brian Harring |
| 171 |
(ferringb): for being knowledgeable about the Portage Manifest2 |
| 172 |
codebase. |
| 173 |
|
| 174 |
Copyright |
| 175 |
========= |
| 176 |
Copyright (c) 2006 by Robin Hugh Johnson. This material may be |
| 177 |
distributed only subject to the terms and conditions set forth in the |
| 178 |
Open Publication License, v1.0. |
| 179 |
|
| 180 |
vim: tw=72 ts=2 expandtab: |
Parent Directory
| 
Revision Log