Network Working Group U. Blumenthal Internet Draft Lucent Technologies Document: draft-blumenthal-keygen-00 January 2001 Category: Best Current Practices 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 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. 1. Abstract This document describes Pseudo Random Function (PRF) based on SHA-1 And used to produce cryptographic keys for authentication/integrity and encryption. It uses pre-shared secret, publicly known random value and parties identities. The main advantage of this algorithm over other similar ones is that it is provably as secure as SHA-1. 2. Conventions used in this document In examples, "C:" and "S:" indicate lines sent by the client and server respectively. 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 RFC-2119 [2]. Mi - i-th message Ti - MAC for i-th message IK - integrity/authentication key CK - ciphering key Whenever a conversion between a string and an integer number is involved, Network Byte Order is used _ i.e. all the integers are MSB (Most Significant Byte first). <month> <year> 3. Introduction Cryptographically strong one-way functions (cryptographic hash- functions) are used in several cryptographic primitives: . Message Authentication Code (MAC) _ a _tag_ of a message. Both parties share a secret key and can produce MAC (tag) Ti for message Mi. MAC function property: given pairs of <M1, T1>, <M2, T2>, ..., <Mn, Tn> an adversary cannot come up with a new pair <Mk, Tk> within any reasonable time. . Pseudo Random Generator (PRG) _ produces a sequence of bits which is indistinguishable from a random bit string, given a secret seed. Typically used for challenge-response. An adversary (who does not know the secret seed) cannot predict any of the bits in a reasonable time, given bit sequence of any length. . Pseudo Random Function (PRF) _ produces a string of bits indistinguishable from random, given a secret key and any input chosen by an attacker. Typically used for session key generation. An adversary, given a sequence of outputs and known inputs, is unable to differentiate between the output sequence and a truly random string in any reasonable time (it implies his inability to predict the output given input- output pairs and the new input). 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 have PRG or PRF property, because output its bits could be predictable. Every PRG can be used as PRF and every PRF can be used as MAC. PRF is not used as MAC because PRF usually is more complex to compute. SHA-1 is widely believed to possess the MAC property, has been used in applications that depend on this assumption, and has withstood several years of cryptanalysis, and no weakness in its MAC property was found. There is a belief that SHA-1 possesses PRG property too, but the conservative approach demands relying only on its MAC property. This proposal shows how to create a PRF from a MAC function. This PRF is provably as secure as MAC _ i.e. if SHA-1 holds its MAC property, then the pseudo random function holds its PRF property. 4. SHA-1 based Pseudo Random Function Input: . Pre-shared secret value 128 bits; . Random value 64 bits; . Function type ('I' for authentication and/or integrity key, 'C' for ciphering key, other types if necessary) 8 bits; <Title> <month> <year> . Desirable output key length (must be divisible by 32, as the output is produced in 32-bit increments). Internal variable: . Internal counter (zero by default or if not specified) 64 bits. Output: . 64 bits with each iteration (typically 128 bits total). 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 repeated 64 times. 2. Load the other values as follows: - XOR the given 64-bit random value into the 6th and 7th 32-bit words of the SHA-1 payload (0th word is the least significant, and 15th word is the most significant); - XOR the 8-bit function type into the least significant byte of the 2nd word; - XOR the 64-bit counter value (initialized to zero, incremented by one with each subsequent iteration - see step 5) into the (0th, 1st) words, (4th, 5th) words, (8th, 9th) words, (12th, 13th) words; - XOR the secret key sequentially by 32-bit words into the words: 3rd, 10th, 11th, 14th (XOR first word of the key into the 3rd word of the payload, 2nd word of the key data with the 10th word of the payload, and so on). 3. Run SHA-1 and produce 160-bit output. 4. Compute AX mod P where X is 160-bit output of SHA-1, A is a pre-defined random 160-bit number and P is a pre-defined random 161-bit prime number. Extract 32 least significant bits from the result and place them into the output buffer. 5. Repeat steps 1 through 4 until the necessary amount of keying material is accumulated (four times for 128 bits of output), incrementing the counter value by one prior to every subsequent iteration. The values for A and prime P can be chosen at random - however for interoperability purposes we specify the recommended values here. Recommended values for A and P are: . A = 0xC43CF6462FCAD177365F411F1CEB5D8FF2045CFE; . P = 0x1EE728E99187144401B4B778851F2DDDD2C812F49. 5. Technical points <Title> <month> <year> . Every bit of the output is cryptographically secure, based on the widely believed properties of SHA-1. . The less output bits are extracted from each round, the greater security it guarantees, at the cost of performance loss. The recommended number of bits is 16, 32 bits being security- performance compromise. . When up to 32 bits of output is needed, the MAC property of SHA-1 is claimed and the algorithm is used directly. . When more than 32 bits are required, the SHA-1 output is whitened by linear congruential hashing procedure (AX mod P). The white SHA-1 is executed multiple times, each time producing 32 cryptographically secure bits of output. . Two key types are envisioned (authentication/integrity and ciphering) - however up to 255 different key types are technically possible and can be used. . Party identities re 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. 7. Formal Syntax The following syntax specification uses the augmented Backus-Naur Form (BNF) as described in RFC-2234 [3]. None. 8. Security Considerations Keys generated with the above algorithm do not exhibit perfect forward secrecy property - i.e. if the long-term secret is compromised, the keys can be recovered trivially. 9. 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 Requirement Levels", BCP 14, RFC 2119, March 1997 3 Crocker, D. and Overell, P.(Editors), "Augmented BNF for Syntax Specifications: ABNF", RFC 2234, Internet Mail Consortium and Demon Internet Ltd., November 1997 1. Use of SHA-1 for AKA f0-f5. 3GPP TSG SA WG3 Security _ S3#13, May 2000, Yokohama. <Title> <month> <year> 2. 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) 10. 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. 11. 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 Email: zulfikar@mit.edu Ganapathy Sundaram Lucent Technologies 67 Whippany Rd Whippany, NJ 07981 USA Email: ganeshs@lucent.com <Title> <month> <year> Marcus Wong Lucent Technologies 67 Whippany Rd Whippany, NJ 07981 USA Email: mw888mw@lucent.com <Title> <month> <year> 11. Full Copyright Notice "Copyright (C) The Internet Society (date). All Rights Reserved. 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 assigns. 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, EXPRESS 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. <Title> <month> <year>