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).
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 ,
, ..., an adversary cannot come up with a new
pair 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;
. 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
. 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.
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
Marcus Wong
Lucent Technologies
67 Whippany Rd
Whippany, NJ 07981
USA
Email: mw888mw@lucent.com
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.