Network Working Group T. Polk
Internet Draft L. Chen
Intended Status: Informational NIST
Expires: March 30, 2011 S. Turner
IECA
September 30, 2010
Security Considerations for the
SHA-0 and SHA-1 Message-Digest Algorithms
draft-turner-sha0-sha1-seccon-00.txt
Abstract
This document updates the security considerations for the SHA-1
message digest algorithm. Additionally, it discusses security
considerations for the SHA-0 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 March 30, 2011.
Copyright Notice
Copyright (c) 2010 IETF Trust and the persons identified as the
document authors. All rights reserved.
Turner & Chen Expires March 30, 2011 [Page 1]
Internet-Draft SHA-0 and SHA-1 Security Considerations Sept 2010
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]. This document also makes assertions about SHA-0,
which was documented in an earlier version of [SHS]. NIST withdrew
SHA-0 in 1996. SHA-0 and SHA-1 are message digest algorithms that
take as input a message of arbitrary length and produces 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 them when collision resistance is required.
[HASH-Attack] summarizes the use of hashes in many protocols and
discusses how attacks against a message digest algorithm's one-way
and collision-free properties affect and do not affect Internet
protocols.
Some may find the guidance for key lengths and algorithm strengths in
[SP800-57] and [SP800-131] useful.
1.1. Requirements Terminology
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
"SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
document are to be interpreted as described in [WORDS].
2. SHA-0 Security Considerations
What follows are recent attacks against SHA-0's collision, pre-image,
and second pre-image resistance. Additionally, attacks against SHA-0
used in message authentication with a shared secret (i.e., HMAC-SHA-
0) are discussed.
It must be noted that the discussions about SHA-0 is for completeness
only. NIST withdrew SHA-0 in 1996. Any use of SHA-0 is strongly
discouraged.
Polk, et al. Expires January 30, 2011 [Page 2]
Internet-Draft SHA-0 and SHA-1 Security Considerations Sept 2010
2.1. Collision Resistance
SHA-0 was published in 1993 by NIST. The first attacks were
published in 1998 [CHJO1998] and showed collisions can be found in
2^61 operations. In 2006, [NSSYK2006] showed an improved attack that
can find collisions in 2^36 operations.
2.2. Pre-image and Second Pre-image Resistance
Even though SHA-0 has been withdrawn, it has been studied as a weaker
version of SHA-1 in many research literatures. The main results
obtained on pre-image and second pre-image attack are on reduced
versions of SHA-0. [deCARE2008] showed a pre-image attack on 49 out
of 80 rounds of SHA-0 with a complexity of 2^159 and [AOSA2009]
showed a pre-image attack on 52 out of 80 rounds of SHA-0 with a
complexity of 2^156. These results are considered as assertions on
security margins of SHA-0 on pre-image resistance.
2.3. HMAC-SHA-0
The attacks on HMAC presented so far can be classified in three
types: distinguishing attacks, existential forgery attacks, and key
recovery attacks. Of course, among all these attacks, key recovery
attacks are the most severe attacks.
As opposed to attacking a hash function, which can be conducted
through purely offline computations, an attack on HMAC would need to
query a large amount of HMAC values, since the keys are unknown. The
best results on partial key recovery attacks 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
used in message authentication with a shared secret (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 mandated
that it not be used for generating digital signatures after December
31st 2013 [SP800-131].
3.1. Collision Resistance
SHA-1 was published by NIST in 1995. The first attack was published
in early 2005 [RIOS2005]. It described a theoretical shortcut attack
Polk, et al. Expires January 30, 2011 [Page 3]
Internet-Draft SHA-0 and SHA-1 Security Considerations Sept 2010
on a version of SHA-1 reduced to 53 rounds. The very next month
[WLY2005] showed collisions in the full 80 round SHA-1 in 2^69
operations. Since then, many new analysis methods have been
developed to improve the attack presented in [WLY2005]. However,
there is no formal claimed complexity in finding collision for full
version SHA-1 in less complexity than the result presented 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, the claimed
bound is removed when it was published at a conference [Man2009].
In any case, the known research results indicated that SHA-1 is not
as collision resistant as expected. The collision security strength
is significantly less than an ideal hash function, and its use in
digital signature generation after 2010 has been deprecated by NIST.
3.2. Pre-image and Second Pre-image Resistance
The preimage and second preimage attacks published so far on reduced
versions of SHA-1 just indicate the security margin of SHA-1 in
resistance to these attacks. [AOSA2009] showed a preimage attack on
48 out of 80 steps with complexity of 2^159.
[KeSch] discovered for a narrow pipe Merkle-Damgaard hash functions,
finding a second preimage takes less than 2^n computations. This
result applies to all the narrow pipe Merkle-Damgaard hash functions
and not specific for SHA-1. When n = 160 in case of SHA-1, for 60
byte message, it will take 2^106 computations to find a second
preimage.
3.3. HMAC-SHA-1
So far, there is no indication that attacks and analysis results on
SHA-1 can be extended to HMAC-SHA-1.
4. Guidance
SHA-1 no longer provides an acceptable security level when used in
digital signature applications. IETF protocol designers SHOULD NOT
specify digital signature algorithms using SHA-1 as mandatory to
implement. IETF protocols that rely on SHA-1 based digital
signatures MUST include countermeasures that mitigate SHA-1's reduced
collision resistance by randomized hashing (e.g., as specified in
[SP800-107]).
HMAC-SHA-1 remains secure and is the preferred keyed hash algorithm
for IETF protocol design.
Polk, et al. Expires January 30, 2011 [Page 4]
Internet-Draft SHA-0 and SHA-1 Security Considerations Sept 2010
As noted above, any use of SHA-0 is strongly discouraged. Discussions
regarding the strength of SHA-0 were included for completeness only.
SHA-0 has no functional or performance advantage, and SHA-1 is
considered significantly more secure.
5. Security Considerations
This entire document addresses security considerations.
6. IANA Considerations
None.
7. 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.
Polk, et al. Expires January 30, 2011 [Page 5]
Internet-Draft SHA-0 and SHA-1 Security Considerations Sept 2010
[NSSYK2006] Naito, Y., Sasaki, Y., Shimoyama, T., Yajima, J.,
Kunihiro, N. and K. Ohta, "Improved Collision
Search for SHA-0", ASIACRYPT 2006.
[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.
[WORDS] Bradner, S., "Key words for use in RFCs to Indicate
Requirement Levels", BCP 14, RFC 2119, March 1997.
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
Polk, et al. Expires January 30, 2011 [Page 6]
Internet-Draft SHA-0 and SHA-1 Security Considerations Sept 2010
Sean Turner
IECA, Inc.
3057 Nutley Street, Suite 106
Fairfax, VA 22031
USA
EMail: turners@ieca.com
Polk, et al. Expires January 30, 2011 [Page 7]
