Network Working Group U. Blumenthal Internet Draft Lucent Technologies Document: draft-blumenthal-keygen-01 January 2001 Category: Experimental Secure Session Key Generation using SHA-1 Status of this Memo This document is an Internet-Draft and is in full conformance with all provisions of Section 10 of RFC2026 [1]. Internet-Drafts are working documents of the Internet Engineer- ing 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 obso- leted 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. 1. Abstract This document describes Pseudo Random Function (PRF) based on SHA-1. This PRF can be used to produce cryptographic keys for authentication/integrity and encryption. It uses pre-shared se- cret and publicly known random value (and possibly partiesÆ identities). The main advantage of this algorithm over other similar ones is that its security is formally tied to the MAC property of SHA-1. 2. Conventions used in this document The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OP- TIONAL" in this document are to be interpreted as described in RFC-2119 [2]. M - i-th message i T - MAC for i-th message i B - number of bytes extracted from one SHA iteration output IK - integrity/authentication key CK - ciphering key Blumenthal Experimental [Page 1] Internet Draft PRF and Key Generation with SHA-1 July 2001 Whenever a conversion between a string and an integer number is involved, Network Byte Order is used û i.e. all the inte- gers are MSB (Most Significant Byte first). 3. Introduction A Message Authentication Code (MAC) function produces a ôtagö T of a message M based on a pre-shared secret key. A MAC function has the property: given pairs of , , à an 1, 1 2 2 n n adversary cannot come up with a new pair within any k k reasonable time. A Pseudo Random Function (PRF) û produces a string of bits indistinguishable from random, given a secret key and any input chosen by an attacker. PRFs are typically used for session key generation following an entity authentica- tion protocol using a secret key and random challenges. Cryptographic hash-functions are typically designed to possess only collision resistance. Some are believed in addition to possess the MAC property. However a secure MAC function may not be a PRF, because its output bits could be predictable. Keyed SHA-1 is widely believed to possess the MAC property, and has been used in applications that depend on this assumption. It has withstood several years of cryptanalysis, and no weak- ness in its MAC property has been found. This proposal shows how to create a PRF from a MAC function. The security of this construction is formally tied to the secu- rity of the MAC. 4. SHA-1 based Pseudo Random Function We describe two methods to create Pseudo Random Functions. The first method is based on a secret constant A (used as a key to the universal hash function), and the second is based on a pub- lic constant A. We recommend adopting the following labeling approach for these options: . PRF-SHA-S-B û SHA-1 based PRF with secret A, extracting B bytes of output per iteration; . PRF-SHA-P-B - SHA-1 based PRF with public A, extracting B bytes of output per iteration. 4.1. PRF construction based on secret constant A Input: . Pre-shared secret key value K (up to 160 bits); . Pre-shared secret constant A (160 bits); Blumenthal Experimental [Page 2] Internet Draft PRF and Key Generation with SHA-1 July 2001 . Random value (up to 128 bits); . Function type (ôIö for authentication and/or integrity key, ôCö for ciphering key, other types if necessary) 8 bits; . Desirable output key length L in bytes; . Desirable number B of bytes extracted from each itera- tion (B is a security parameter, example B=4). Internal variable: . Internal counter (initialized to zero) 64 bits. Output: . Pseudo random stream of L bytes (B bytes at each itera- tion). Algorithm: 1. Load the registers of SHA-1 with known constants and the secret key as follows: - load the IV with standard SHA-1 constant; - load the 512-bit payload with constant 0x5C re- peated 64 times. 2. Load the secret key K as follows: - XOR the secret key K with the leftmost (Most Sig- nificant) bits of the IV. 3. Load the other values as follows: th st - XOR the given 64-bit counter into the (0 , 1 ), th th th th th th (4 , 5 ), (8 , 9 ) and (12 , 13 ) 32-bit words th of the SHA-1 payload (0 word is the least sig- th nificant, and 15 word is the most significant); - XOR the 8-bit function type into leftmost byte of nd the 2 word; - The least significant 64 bits of the random number th th are XORed into the (6 , 7 ) words, and the most th th significant 64 bits are XORed into the (10 , 11 ) words. 4. Run SHA-1 and produce 160-bit output. 5. Compute AX mod P where X is 160-bit output of SHA-1 where P is a pre-defined 161-bit prime number. Extract B least significant bytes from the result and place them into the output buffer. 6. Repeat steps 1 through 5 until the necessary amount of keying material is accumulated, incrementing the counter value by one prior to every subsequent iteration. Specified value for P to operate the PRF is: . P = 2^160 + 7. Blumenthal Experimental [Page 3] Internet Draft PRF and Key Generation with SHA-1 July 2001 4.2. PRF construction based on public constant A In some cases a public A can be used in the PRF construction outlined in section 4.1. We give some example cases where it is acceptable to use the standard (non-secret) A to create a PRF, but more detailed discussion is in [NAORR]. Basically, when the argument to the PRF is random, a public A can be used. This can happen, for instance, when session keys are generated after a mutual (entity) authentication protocol where random challenges were used on one or both sides. Public value A is: . A = 0Xc43cf6462fcad177365f411f1ceb5d8ff2045cfe; 5. Technical points . The fewer output bits (controlled by B parameter) are ex- tracted from each round, the greater security it guarantees, at the cost of performance loss. . Two key types are envisioned (authentication/integrity and ciphering) û however up to 255 different key types are tech- nically possible and can be used. . Party identities are not used in key generation, because the uniqueness of the key depends solely on the secrecy (and strength) of the pre-shared secret and the random number used in the derivation process. 6. Security Considerations Keys generated with the above algorithm do not exhibit perfect forward secrecy property û i.e. if the long-term secret is com- promised, the keys can be recovered trivially. If MAC property of SHA-1 does not hold, this algorithm is not a PRF. 7. References 1. Bradner, S., "The Internet Standards Process -- Revision 3", BCP 9, RFC 2026, October 1996. 2. Bradner, S., "Key words for use in RFCs to Indicate Require- ment Levels", BCP 14, RFC 2119, March 1997. Blumenthal Experimental [Page 4] Internet Draft PRF and Key Generation with SHA-1 July 2001 3. Use of SHA-1 for AKA f0-f5. 3GPP TSG SA WG3 Security û S3#13, May 2000, Yokohama. 4. Naor, M., Reingold, O., From unpredictability to indistin- guishability: A simple construction of pseudorandom functions from MACs, Advances in Cryptology, Crypto '98, Santa Barbara, CA 1998. 5. Naslund, M., All bits of ax+b mod p are hard, Advances in Cryptology, Crypto '95, Santa Barbara, CA 1995. 6. Secure Hash Algorithm. NIST FIPS 180-1, (April, 1995) http://csrc.nist.gov/fips/fip180-1.txt (ASCII) http://csrc.nist.gov/fips/fip180-1.ps (Postscript) 8. Acknowledgments This proposal is based on Lucent Technologies submission to the standards committees TIA TR-45, ETSI and 3GPP. We thank Daniel Bleichenbacher for his valuable commends and suggestions. 9. Author's Addresses Uri Blumenthal Lucent Technologies 67 Whippany Rd Whippany, NJ 07981 USA Email: uri@lucent.com Simon Mizikovsky Lucent Technologies 67 Whippany Rd Whippany, NJ 07981 USA Email: smizikovsky@lucent.com Sarvar Patel Lucent Technologies 67 Whippany Rd Whippany, NJ 07981 USA Email: sarvar@lucent.com Zulfikar Ramzan Lucent Technologies 67 Whippany Rd Whippany, NJ 07981 USA Blumenthal Experimental [Page 5] Internet Draft PRF and Key Generation with SHA-1 July 2001 Email: zulfikar@mit.edu Ganapathy Sundaram Lucent Technologies 67 Whippany Rd Whippany, NJ 07981 USA Email: ganeshs@lucent.com Marcus Wong Lucent Technologies 67 Whippany Rd Whippany, NJ 07981 USA Email: mw888mw@lucent.com Blumenthal Experimental [Page 6] Internet Draft PRF and Key Generation with SHA-1 July 2001 10. Full Copyright Notice Copyright (C) The Internet Society (2000). All Rights Re- served. This document and translations of it may be copied and furnished to others, and derivative works that comment on or otherwise explain it or assist in its implementation may be prepared, copied, published and distributed, in whole or in part, without restriction of any kind, provided that the above copyright notice and this paragraph are included on all such copies and derivative works. However, this document itself may not be modified in any way, such as by removing the copyright notice or references to the Internet Society or other Internet organizations, except as needed for the purpose of developing Internet standards in which case the procedures for copyrights defined in the Internet Standards process must be followed, or as required to translate it into languages other than English. The limited permissions granted above are perpetual and will not be revoked by the Internet Society or its successors or as- signs. This document and the information contained herein is provided on an "AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING TASK FORCE DISCLAIMS ALL WARRANTIES, EX- PRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. Blumenthal Experimental [Page 7]