Network Working Group T. Polk
Internet Draft L. Chen
Intended Status: Informational NIST
Expires: June 3, 2011 S. Turner
IECA
P. Hoffman
VPN Consortium
December 3, 2010
Security Considerations for the
SHA-0 and SHA-1 Message-Digest Algorithms
draft-turner-sha0-sha1-seccon-02.txt
Abstract
This document includes security considerations for the SHA-0 and SHA-
1 message digest algorithm.
Status of this Memo
This Internet-Draft is submitted in full conformance with the
provisions of BCP 78 and BCP 79. This document may contain material
from IETF Documents or IETF Contributions published or made publicly
available before November 10, 2008.
Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF), its areas, and its working groups. Note that
other groups may also distribute working documents as Internet-
Drafts.
Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as "work in progress."
The list of current Internet-Drafts can be accessed at
http://www.ietf.org/ietf/1id-abstracts.txt.
The list of Internet-Draft Shadow Directories can be accessed at
http://www.ietf.org/shadow.html.
This Internet-Draft will expire on June 3, 2011.
Polk, et al. Expires June 3, 2011 [Page 1]
Internet-Draft SHA-0 and SHA-1 Security Considerations Dec 2010
Copyright Notice
Copyright (c) 2010 IETF Trust and the persons identified as the
document authors. All rights reserved.
This document is subject to BCP 78 and the IETF Trust's Legal
Provisions Relating to IETF Documents
(http://trustee.ietf.org/license-info) in effect on the date of
publication of this document. Please review these documents
carefully, as they describe your rights and restrictions with respect
to this document. Code Components extracted from this document must
include Simplified BSD License text as described in Section 4.e of
the Trust Legal Provisions and are provided without warranty as
described in the Simplified BSD License.
1. Introduction
The Secure Hash Algorithms, SHA-1 and SHA-2 family (SHA), are
specified in [SHS]. A previous version of [SHS] also specified SHA-0.
SHA-0, first published in 1993, and SHA-1, first published in 1996,
are message digest algorithms, sometimes referred to as hash
functions or hash algorithms, that take as input a message of
arbitrary length and produce as output a 160-bit "fingerprint" or
"message digest" of the input. The published attacks against both
algorithms show that it is not prudent to use either algorithm when
collision resistance is required.
[HASH-Attack] summarizes the use of hashes in Internet protocols and
discusses how attacks against a message digest algorithm's one-way
and collision-free properties affect and do not affect Internet
protocols. Familiarity with [HASH-Attack] is assumed.
Some may find the guidance for key lengths and algorithm strengths in
[SP800-57] and [SP800-131] useful.
2. SHA-0 Security Considerations
What follows are summaries of recent attacks against SHA-0's
collision, pre-image, and second pre-image resistance. Additionally,
attacks against SHA-0 when used as a keyed-hash (e.g., HMAC-SHA-0)
are discussed.
The U.S. National Institute of Standards and Technology (NIST)
withdrew SHA-0 in 1996. That is, NIST no longer considers it
appropriate to use SHA-0 for any transitions associated with the use
of cryptography by U.S. Federal government agencies for the
protection of sensitive, but unclassified information. SHA-0 is
discussed here only for the sake of completeness.
Polk, et al. Expires June 3, 2011 [Page 2]
Internet-Draft SHA-0 and SHA-1 Security Considerations Dec 2010
Any use of SHA-0 is strongly discouraged. Analysis of SHA-0 continues
today because many see it as a weaker version of SHA-1.
2.1. Collision Resistance
The first attack on SHA-0 was published in 1998 [CHJO1998] and showed
that collisions can be found in 2^61 operations. In 2006,
[NSSYK2006] showed an improved attack that can find collisions in
2^36 operations.
In any case, the known research results indicate that SHA-0 is not as
collision resistant as expected. The collision security strength is
significantly less than an ideal hash function (i.e., 2^36 compared
to 2^80).
2.2. Pre-image and Second Pre-image Resistance
The pre-image and second pre-image attacks published on reduced
versions of SHA-0 (i.e., less than 80 rounds) indicate that the
security margin of SHA-0 is resistant to these attacks. [deCARE2008]
showed a pre-image attack on 49 out of 80 rounds with complexity of
2^159 and [AOSA2009] showed a pre-image attack on 52 out of 80 rounds
with a complexity of 2^156.
2.3. HMAC-SHA-0
The current attack vectors on HMAC can be classified as follows:
distinguishing attacks, existential forgery attacks, and key recovery
attacks. Key recovery attacks are by far the most severe.
Attacks on hash functions can be conducted entirely offline, since
the attacker can generate unlimited plaintext-ciphertext pairs.
Attacks on HMACs must be online because attackers need a large amount
of HMAC values to deduce the key. The best results for a partial key
recovery attack on HMAC-SHA0 were published at ASIACRYPT 2006 with
2^84 queries and 2^60 SHA-0 computations [COYI2006].
3. SHA-1 Security Considerations
What follows are recent attacks against SHA-1's collision, pre-image,
and second pre-image resistance. Additionally, attacks against SHA-1
when used as a keyed-hash (i.e., HMAC-SHA-1) are discussed.
It must be noted that NIST has recommended that SHA-1 not be used for
generating digital signatures after Dec 31st 2010 and has specified
that it not be used for generating digital signatures by U.S. Federal
government agencies "for the protection of sensitive, but
unclassified information" after December 31st 2013 [SP800-131].
Polk, et al. Expires June 3, 2011 [Page 3]
Internet-Draft SHA-0 and SHA-1 Security Considerations Dec 2010
3.1. Collision Resistance
The first attack on SHA-1 was published in early 2005 [RIOS2005].
This attack described a theoretical attack on a version of SHA-1
reduced to 53 rounds. The very next month [WLY2005] showed
collisions in the full 80 rounds in 2^69 operations. Since then,
many new analysis methods have been developed to improve the attack
presented in [WLY2005]. However, there are no published results that
improve upon the results found in [WLY2005]. The IACR ePrint version
[Man2008/469] of [Man2009] claimed that using the method presented in
the paper, a collision of full SHA-1 can be found in 2^51 hash
function calls. However, this claim is absent from published
conference paper [Man2009].
In any case, the known research results indicate that SHA-1 is not as
collision resistant as expected. The collision security strength is
significantly less than an ideal hash function (i.e., 2^69 compared
to 2^80).
3.2. Pre-image and Second Pre-image Resistance
There are no known pre-image or second pre-image attacks that are
specific to the full round SHA-1 algorithm. [KeSch] discovered a
general result for all narrow pipe Merkle-Damgaard hash functions
(which includes SHA-1), finding a second pre-image takes less than
2^n computations. When n = 160 as is the case for SHA-1, it will take
2^106 computations to find a second pre-image in a 60-byte message.
In the absence of full round attacks, cryptographers consider
reduced-round attacks for clues regarding an algorithm's strength.
Reduced-round attacks, where the number of reduced rounds is not more
than a few less than the full rounds, have not been shown to relate
to full-round attacks. However, the best reduced round attack
indicates a certain security margin. For example, if the best known
attack is on 60 out of 80 rounds, then the algorithm has about 20
rounds to resist improved attacks. However, the relationship between
the number of rounds an attack can reach and the number of rounds
defined in the algorithm is not linear; it does not provide a
mathematical proof. In other words, reduced round attacks indicate
how strong the algorithm is with regard to a certain attack, not how
close it is to being broken. Therefore, the following information
about reduced-round attacks is included only for completeness.
The pre-image and second pre-image attacks published on reduced
versions of SHA-1 (i.e., less than 80 rounds) indicate that SHA-1
retains a significant security margin against these attacks.
[AOSA2009] showed a pre-image attack on 48 out of 80 rounds with
complexity of 2^159.
Polk, et al. Expires June 3, 2011 [Page 4]
Internet-Draft SHA-0 and SHA-1 Security Considerations Dec 2010
3.3. HMAC-SHA-1
As of today, there is no indication that attacks on SHA-1 can be
extended to HMAC-SHA-1.
4. Guidance
SHA-1 provides less collision resistance than was originally
expected, and collision resistance has been shown to affect some (but
not all) applications that use digital signatures. Designers of IETF
protocols that use digital signature algorithms should mandate
support for a hash algorithm with greater collision resistance than
that provided by SHA-1. Of course, SHA-0 should continue to not be
used in any IETF protocol.
[Note: Protocol designers should review the current state of the art
to ensure that selected hash algorithms provide sufficient security.
At the time of publication, SHA-256 is the most commonly specified
alternative. The known (reduced round) attacks on the collision
resistance of SHA-256 indicate a significant security margin, and the
longer message digest provides increased strength.]
Nearly all IETF protocols that use signatures assume existing public
key infrastructures, and SHA-1 is still used in signatures nearly
everywhere. Therefore, it is unwise to strictly prohibit the use of
SHA-1 in signature algorithms. Protocols that permit the use of SHA-1
based digital signatures as an option should reference this
specification in the security considerations.
A protocol designer might want to consider the use of SHA-1 with
randomized hashing such as is specified in [SP800-107]. Note that
randomized hashing expands the size of signatures and requires
protocols to carry material that is not needed today.
HMAC-SHA-1 remains secure and is the preferred keyed-hash algorithm
for IETF protocol design.
5. Security Considerations
This entire document addresses security considerations.
6. IANA Considerations
None.
Polk, et al. Expires June 3, 2011 [Page 5]
Internet-Draft SHA-0 and SHA-1 Security Considerations Dec 2010
7. Acknowledgements
We'd like to thank Ran Atkinson and Sheila Frankel for their comments
and suggestions.
8. Normative References
[AOSA2009] Aoki, K., and K. Saski, "Meet-in-the-Middle
Preimage Attacks Against Reduced SHA-0 and SHA-1",
Crypto 2009.
[deCARE2008] De Canniere, C. and C. Rechberger, "Preimages for
Reduced SHA-0 and SHA-1", Crypto 2008.
[CHJO1998] Chaubad, F., and A. Joux, "Differential Collisions
in SHA-0", Crypto 1998.
[COYI2006] Contini, S., and Y. Lin, "Forgery and Partial Key-
Recovery Attacks on HMAC and NMAC Using Hash
Collisions", Asiacrypt 2006.
[HASH-Attack] Hoffman, P., and B. Schneier, "Attacks on
Cryptographic Hashes in Internet Protocols", RFC
4270, November 2005.
[KeSch] Kelsey, J., and B. Schneier, "Second Preimages on
n-Bit Hash Functions for Much Less than 2n Work",
In Cramer, R., ed.: EUROCRYPT'05. Volume 3494 of
Lecture Notes in Computer Science, Springer (2005)
474-490.
[Man2008/469] Manuell, S., "Classification and Generation of
Disturbance Vectors for Collision Attacks against
SHA-1", http://eprint.iacr.org/2008/469.pdf.
[Man2009] Manuell, S., "Classification and Generation of
Disturbance Vectors for Collision Attacks against
SHA-1", International Workshop on Coding and
Cryptography, 2009, Norway.
[MD2-His] Turner, S., and L. Chen, "MD2 to Historic Status",
draft-turner-md2-to-historic, work-in-progress.
[NSSYK2006] Naito, Y., Sasaki, Y., Shimoyama, T., Yajima, J.,
Kunihiro, N. and K. Ohta, "Improved Collision
Search for SHA-0", ASIACRYPT 2006.
Polk, et al. Expires June 3, 2011 [Page 6]
Internet-Draft SHA-0 and SHA-1 Security Considerations Dec 2010
[RIOS2005] Rijmen, V., and E. Oswald, "Update on SHA-1", CT-
RSA 2005, LNCS 3376, pp. 58-71.
[SHS] National Institute of Standards and Technology
(NIST), FIPS Publication 180-3: Secure Hash
Standard, October 2008.
[SP800-57] National Institute of Standards and Technology
(NIST), Special Publication 800-57: Recommendation
for Key Management - Part 1 (Revised), March 2007.
[SP800-131] National Institute of Standards and Technology
(NIST), Special Publication 800-131: DRAFT
Recommendation for the Transitioning of
Cryptographic Algorithms and Key Sizes, June 2010.
[SP800-107] National Institute of Standards and Technology
(NIST), Special Publication 800-107:
Recommendation for Applications using Approved
Hash Algorithms of Algorithms, February 2009.
[WLY2005] Wang, X., Yin, Y. and H. Yu. "Finding Collisions in
the Full SHA-1", Crypto 2005.
Polk, et al. Expires June 3, 2011 [Page 7]
Internet-Draft SHA-0 and SHA-1 Security Considerations Dec 2010
Authors' Addresses
Tim Polk
National Institute of Standards and Technology
100 Bureau Drive, Mail Stop 8930
Gaithersburg, MD 20899-8930
USA
EMail: tim.polk@nist.gov
Lily Chen
National Institute of Standards and Technology
100 Bureau Drive, Mail Stop 8930
Gaithersburg, MD 20899-8930
USA
EMail: lily.chen@nist.gov
Sean Turner
IECA, Inc.
3057 Nutley Street, Suite 106
Fairfax, VA 22031
USA
EMail: turners@ieca.com
Paul Hoffman
VPN Consortium
EMail: paul.hoffman@vpnc.org
Polk, et al. Expires June 3, 2011 [Page 8]