Network Working Group R. van Rein Request for Comments: DRAFT OpenFortress Digital signatures Category: Informational March 2005 Collision-Resistant Secure Hashing: CR-SHA1, CR-MD5, et al draft-vanrein-collision-resistant-hashes-00.txt Status of this Memo This specification is an Internet Draft. By submitting this Internet Draft. I certify that any applicable patent or other IPR claims of which I am aware have been disclosed, or will be disclosed, and any of which I become aware will be disclosed, in accordance with RFC 3668. 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. Copyright Notice Copyright (C) The Internet Society (2005). All Rights Reserved. Abstract This specification adapts hash algorithms to make them resist collision attacks. As a result, hash algorithms can be used securely for a much longer period than is currently the case. This is of particular interest to long-lived utilisations such as timestamp signatures. 1. Introduction Van Rein [Page 1] INTERNET DRAFT Collision-Resistant Hashing 24 March 2005 Hash functions are important to digital signatures, and breaking them means breaking a signature schema. The first attack against hashes is usually a collision attack, because this is computationally the least expensive form of attack. Further attacks on hash functions, notably preimage attacks, take an incredible amount of additional computational power. This means that making secure hash functions resistant against collision attacks is a practical method of prolonging their secure use. This is useful for applications such as timestamps and non-revocable signatures, because these may have to be valid for very long periods. An attacker could mount a collision attack by predicting the signature calculation and preparing two documents with colliding hash values. One document would be signed by someone other than the attacker, the other document would be exploited with that signature attached. Such attacks can be avoided if the signer makes the signing process unpredictable to the attacker. A good method to do that is to include random octets in each signature, under full control of the signer. This specification defines such variations of existing and future hash algorithms that makes them resistant against collision attacks. 2. Positioning and Definitions The solution in this specification could have been proposed at a number of places. It could have been defined as part of signing applications such as OpenPGP [1] or PKIX [2], but that would have meant that multiple descriptions (of largely the same signing process) would have had to change. And because multiple public-key algorithms are possible, not even incorporation in PKCS #1 [3] would span every possible application. Finally, it could also have been described for an individual hash function, but it is easier to make this central effort. Future hash functions are encouraged to consider also incorporating this mechanism to strengthen them against collision attacks. Since this specification spans multiple hashes, the notation will be used as a symbolic reference to the algorithm at hand, and represents the number of bits in its output. For example, if is SHA1, then is 160. This specification assumes that is a multiple of eight. This specification uses the terms "MUST", "SHOULD", and "MAY" as defined in RFC 2119. Van Rein [Page 2] INTERNET DRAFT Collision-Resistant Hashing 24 March 2005 3. Adapting Existing Hash Functions In applications such as PKCS #1 [3] and PKIX [2], hash algorithms are specified with an X.509 AlgorithmIdentifier [2]. This includes an OID for the hash algorithm, and an optional parameter field which is normally discarded or set to NULL because hash algorithms do not need a parameter. This specification uses existing hashing algorithms, but it uses the parameter in the AlgorithmIdentifier to hold the random octets to be hashed before the application data is hashed. Unlike the application data, the random octets are always under full control of the hashing (or signing) party. This diverts from the original definition of such hashes and must therefore be marked with a new OID value in the AlgorithmIdentifier structure. This is also necessary to avoid misinterpretations by software that only knows the original hashes and is not programmed with this specification in mind. Such software will not recognize the new OID and thus report something along the lines of "unsupported hash algorithm", which makes perfect sense. 3.1. Names for Collision-Resistant Hashes The outcome of a hash algorithm changes due to the added random octets. It is useful to reflect that by giving the adapted algorithm a new name. The original name should remain visible in the new name as a hint that the strength of the adapted hash still relies on the algorithm with that name. In accordance with the naming pattern of HMAC functions [4], which have names like HMAC-MD5 when derived from MD5 [5], the name of a collision-resistant version of a hash shall be known as CR-. So, when SHA1 [6] is the underlying hash function, the collision-resistant counterpart according to this specification shall be named CR-SHA1. This name is insufficient to serve as a description of how a hash can be reconstructed, so there is an additional ASCII representation of the algorithm name with the parameter. This shall be the CR- name, followed by an opening bracket, the hexadecimal representation of the random octets and a closing bracket. For example, the random octets from the first example below would be included in the full ASCII name, which is written as: CR-MD5(9de96f90aa7d08814c32fc456f9e6e6a) Note that ASN.1 annotations (tag and length headers) are not part of Van Rein [Page 3] INTERNET DRAFT Collision-Resistant Hashing 24 March 2005 this parameter representation. Applications MAY generate uppercase or lowercase hex digits and MUST accept both representations. 3.2. ASN.1 Syntax and DER Encoding Example The hash description employed in digital signature applications is usually the following combination of the hash algorithm and the hash value: DigestInfo ::= SEQUENCE { digestAlgorithm AlgorithmIdentifier, digest OCTET STRING } where the hash algorithm is further specified as AlgorithmIdentifier ::= SEQUENCE { algorithm OBJECT IDENTIFIER, parameters ANY DEFINED BY algorithm OPTIONAL } For CR- the algorithm is an OID as specified in the IANA Considerations section below, and parameters is an OCTET STRING holding the random octets to be inserted before any application data is being hashed. The number of random octets times eight MUST equal . The DER-encoded instance of the AlgorithmIdentifier for CR-MD5, with random octets represented as XX and others in hexadecimal is: 30 1f 06 0b 2b 06 01 04 01 d1 67 06 04 03 01 04 10 XX XX XX XX XX XX XX XX XX XX XX XX XX XX XX XX 3.3. Example Calculations of CR-MD5 and CR-SHA1 For development purposes, a few test cases follow. These examples show the DER-encoded parameter string in hexadecimal notation. Parameter: 04109de96f90aa7d08814c32fc456f9e6e6a InputData: f8f04799c4ea178042b604660a6fe3f166599a815aa9e2edf4 Plain MD5: 4f63cc47a5cc2d2e563b54cd0b38f5d7 CR-MD5: faa4702ab6e7fa890627192cd6cc6333 Parameter: 0410b410431339425ad15305383f58ee0555 InputData: 599052834a8cde2d22538e66ff40fe144ea0849a201f703f14 Plain MD5: fbf74ea788a00d57788cf91f96031bb5 CR-MD5: 28e1c77c959c0da8abc3cfcca3c7a7fe Van Rein [Page 4] INTERNET DRAFT Collision-Resistant Hashing 24 March 2005 Parameter: 0414c6d01cc59544c2287974715edf319761d284ce66 InputData: 5d868997906038e70f566aa5b6ae40b536d887783ceb60ea65 Plain SHA1: 3fd5e234c7016798e57c3b8152d305ea998633bf CR-SHA1: a1bfee165a568b1d88f0cec81cad2eca4031bdd8 Parameter: 0414573e10cedf2a91ab36d2c6ffd5c95361081c55ad InputData: 90356ed1b7aa65504799c44e74562ec65645faa75870f5612f Plain SHA1: 27bb4ef6aac61f09188111093ea10d584264d6d5 CR-SHA1: 56b9cb04d3816c97db6c0a50de45e429ede03e85 3.4. Generating Random Bits The quality of the random bits prepended to the hashed data is in the hands of the party generating them. The choice between true random bits from a hardware source [7] or the selection of pseudo-random number generators, or combinations thereof [8] is theirs. The secure thing to do is to collect (at least) of entropy; if a source of entropy only delivers at least half a bit of entropy per bit it outputs, the number of random bits to generate would be twice , for example 320 bits for CR-SHA1. Since it is a waste of resources to carry around more then of information, and because it may even leak patterns of the random number generator, it is wise to compress any such sequence into . One way of doing such compression is by using the hash named . Since it is not optimally secure to have less than worth of random input, and since the level of security does not improve with more random input, the number of added random bits MUST be and their expected entropy [8,7] MUST be at least 99% of . 4. Relation to Existing Technology 4.1. Differences with Plain Hash Calculations As a result of including a random value in the hashed data, the outcome of signing the same data more than once will differ. This is not a problem in signing applications, because it is common to include a time of signing in hashed data. This causes similar variations in repeated signatures, and it causes no problems in the validation process. One incompatibility issue in comparison with collision-sensitive hash algorithms concerns their APIs. The procedures of generating and verifying a collision-resistant hash are different -- when Van Rein [Page 5] INTERNET DRAFT Collision-Resistant Hashing 24 March 2005 calculating a hash value, the random octets are generated and when verifying they are taken from the AlgorithmIdentifier of the hash. The most important issue is that a hash has an API which does not treat the random values any different from application data, while a dedicated API for a CR- could choose to do so. 4.2. One-Pass Signature Processing Several techniques focus on processing digital signature in one pass over the signed content. Such applications include PKCS #7 [9] and OpenPGP's one-pass signature packets [1]. The advantage of one-pass processing is that it supports processing of large files and files stored on media without rewinding capability. This calls for special concern regarding the hashing parameter. One- pass applications must always mention the hash algorithm to be used to validate the upcoming data, and that is the best place to also introduce the hash parameter. For applications that do not refer to an AlgorithmIdentifier to introduce the hash, special precautions may be needed. As a generic approach, the full ASCII representation of CR-, including the random octets, has been defined to help solve that. 4.3. Future Hash Functions Advances in cryptanalysis make it necessary to constantly improve hash algorithms. Future hash algorithms can therefore allocate an OID for their CR- in the OID scheme described below. It is advised that such future hash algorithms define both a version with and without the collision resistance from this specification. The version without collision resistance is perfectly fine for signatures on content generated by the signer; signatures with collision resistance are useful for signatures on content generated by others. The collision-resistant OID SHOULD be allocated as soon as a new hash algorithm is introduced; one reason is that it avoids differences in support between older and newer software; another reason is that it is good to have had protection against collisions at the time a collision attack is published. 5. IANA Considerations The CR- hash functions described in this specification have a unique OID to clearly distinguish them from their collision- sensitive counterparts. All OIDs for CR- hashes fall one Van Rein [Page 6] INTERNET DRAFT Collision-Resistant Hashing 24 March 2005 level under 1.3.6.1.4.1.10471.6.4.3. The OIDs for some CR- hash functions are defined in the table below; any further numbers MUST be assigned by IANA. IANA will grant assignment requests for any (soon-to-be) publicly available, fixated specification of secure hash algorithms. Their assignment register is called collision-resistant-hashes. CR-: OID: CR-MD5 1.3.6.1.4.1.10471.6.4.3.1 CR-SHA1 1.3.6.1.4.1.10471.6.4.3.2 CR-SHA224 1.3.6.1.4.1.10471.6.4.3.3 CR-SHA256 1.3.6.1.4.1.10471.6.4.3.4 CR-SHA384 1.3.6.1.4.1.10471.6.4.3.5 CR-SHA512 1.3.6.1.4.1.10471.6.4.3.6 CR-RIPEMD128 1.3.6.1.4.1.10471.6.4.3.7 CR-RIPEMD160 1.3.6.1.4.1.10471.6.4.3.8 6. Security Considerations The inclusion of random information under control of the hashing (and possibly signing) party means that this party has serious influence on the outcome of the hash calculation. The placement of the random information at the start of the calculation comes as close as possible to setting the Initiation Vector for the hash algorithm. This initial influence on the hashing algorithm makes it impossible for an attacker to predict the context in which his data is going to be hashed. This is generally believed to render any collision attack impossible. This would not have been the case with the random bits at the end of the hash calculation -- because at that place, a weakness in the algorithm may already have been exploited to come to the same internal state for the hash algorithm on two different input documents. For this reason, the influence in the beginning is considered the most secure option. Finally, the inclusion of random data in a signature forms a potential subliminal channel; for this reason, CR- hashes SHOULD only be generated with trusted software. 7. Informational References [1] J. Callas, L. Donnerhacke, H. Finney, and R. Thayer, "OpenPGP Mes- sage Format," RFC 2440 (November 1998). [2] R. Housley, W. Ford, W. Polk, and D. Solo, "Internet X.509 Public Key Infrastructure: Certificate and CRL Profile," RFC 2459 (January Van Rein [Page 7] INTERNET DRAFT Collision-Resistant Hashing 24 March 2005 1999). [3] J. Staddon and B. Kaliski, "Public-Key Cryptography Standards (PKCS) #1: RSA Cryptography Specifications Version 2.1," RFC 3447 (October 1998). [4] H. Krawczyk, M. Bellare, and R. Canetti, "HMAC: Keyed-Hashing for Message Authentication," RFC 2104 (February 1997). [5] R. Rivest, "The MD5 Message-Digest Algorithm," RFC 1321 (April 1992). [6] United States of America, National Institute of Science and Tech- nology, "Secure Hash Standard," FIPS 180-1 (April 1993). [7] OpenFortress Digital signatures, "How to Generate Truly Random Bits," http://openfortress.org/cryptodoc/random/ (2002). [8] D. Eastlake 3rd, S. Crocker, and J. Schiller, "Randomness Recommen- dations for Security," RFC 1750 (December 1994). [9] B. Kaliski, "PKCS #7: Cryptographic Message Syntax Version 1.5," RFC 2315 (March 1998). 8. Author's Address Rick van Rein OpenFortress Digital signatures Haarlebrink 5 7544 WP Enschede The Netherlands phone: +31.53.4782239 email: rick@openfortress.nl web: http://openfortress.nl/ 9. Full Copyright Statement Copyright (C) The Internet Society (2005). This document is subject to the rights, licenses and restrictions contained in BCP 78, and except as set forth therein, the authors retain all their rights. This document and the information contained herein is provided on an "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY AND THE INTERNET ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFOR- MATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES Van Rein [Page 8] INTERNET DRAFT Collision-Resistant Hashing 24 March 2005 OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. Van Rein [Page 9]