Network Working Group U. Blumenthal
Internet Draft Lucent Technologies
Document: draft-blumenthal-keygen-02 October 2001
Category: Experimental
Secure Session Key Generation.
Creating PRF from MAC Function.
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
MAC function (keyed iterated hash function), and offers a ref-
erence implementation of PRF based on SHA-1.
This PRF can be used to produce cryptographic keys for authen-
tication/integrity and encryption. It uses pre-shared secret
and publicly known random value (and possibly partiesÆ identi-
ties). The main advantage of this algorithm over other similar
ones is that its security is formally tied to the MAC property
of the underlying function.
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).
A Universal Hash Function is a cryptographic iterated hash
function, such as MD5, SHA-1, SHA-256, RIPEMD, etc.
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 <M1,T1>, <M2,T2>, à <Mn,Tn> an
adversary cannot come up with a new pair <Mk,Tk> within any
reasonable time, without knowledge of the secret key. A Pseudo
Random Function (PRF) û produces a string of bits that an at-
tacker cannot distinguish from random bit string (without
knowledge of the secret key). PRFs are typically used for ses-
sion key generation following an entity authentication 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 may be distinguishable from a
random bit string.
Often cryptographic hash functions (such as SHA-1) are con-
verted to MAC functions by mixing a secret key with the func-
tion input.
For example, keyed SHA-1 (that is widely used as MAC function)
is 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 weakness 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.
This proposal also provides an example of a PRF function built
from SHA-1, and includes the source code and the test vectors
for the PRF.
Blumenthal Experimental [Page 2]
Internet Draft PRF and Key Generation with SHA-1 July 2001
4. Pseudo Random Function from Universal Hash 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-SHAn-S-B-X û SHA-n (SHA-1, SHA-256, etc) based PRF
with secret A, extracting B bytes of output per iteration,
where X is ôGö for computing whitening modulo polynomial
in Galois field, or ôPö for computing whitening modulo
over prime;
. PRF-SHAn-P-B-X - SHA-n based PRF with public A, extract-
ing B bytes of output per iteration, where X is ôGö for
computing whitening modulo polynomial in Galois field, or
ôPö for computing whitening modulo over prime.
For PRF based on MD5 (or any other hash-function), MD5 (or the
name of that function) will be used in the identifier instead
of SHA.
4.1. PRF construction based on secret constant A
Input:
. Pre-shared secret key value K (up to hash-function out-
put size, that is 160 bits for SHA-1);
. Pre-shared secret constant A (hash-function output size,
160 bits for SHA-1);
. Random value (up to 256 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 hash-function registers with known constants
and the secret key as follows:
- load the IV with standard constant according to
the hash-function definition;
Blumenthal Experimental [Page 3]
Internet Draft PRF and Key Generation with SHA-1 July 2001
- load the payload (512-bit for SHA-1) with constant
0x5C repeated 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:
- XOR the given 64-bit counter into the (0-th, 1-st)
and (4-th, 5-th), 32-bit words of the hash-
function payload (0-th word is the least signifi-
cant, and 15-th word is the most significant);
- XOR the 8-bit function type into leftmost byte of
the 2-nd word;
- The 256-bit random input value is divided into 64-
bit quantities. The least significant 64 bits of
the random number are XORed into the (6-th, 7-th)
words, the next 64 bits û into the (8-th, 9-th)
and (10-th, 11-th) 32-bit words, and the most sig-
nificant 64 bits are XORed into the (12-th, 13-th)
words.
4. Run hash-function compression function and produce the
output.
5. Compute AX mod P where X is the output of the hash-
function. P is a pre-defined (n+1)-bit prime number,
where n is the output size of the hash-function. Extract
B least significant bytes from the result and place them
into the output buffer. Instead of computing multiplica-
tion modulo prime, one can use modulo polynomial.
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^n + 7; where n is the output size of the hash
function.
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 values of A and P for SHA-1 are:
. A = 0Xc43cf6462fcad177365f411f1ceb5d8ff2045cfe;
. P = 2^160 + 7;
Blumenthal Experimental [Page 4]
Internet Draft PRF and Key Generation with SHA-1 July 2001
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 256 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 numbers
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 the underlying keyed hash-function does not
hold, this algorithm is not provably a PRF (i.e. it may or may
not be 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.
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 and 3GPP2. We thank Daniel Blei-
chenbacher for his valuable comments and suggestions.
Blumenthal Experimental [Page 5]
Internet Draft PRF and Key Generation with SHA-1 July 2001
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
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]
Internet Draft PRF and Key Generation with SHA-1 July 2001
11. Appendix A. Source code example of PRF-SHA1-P32P
#include <stdio.h>
#include <string.h>
#include <time.h>
#ifdef linux
#include <ctype.h>
#include <sys/types.h>
#include <sys/time.h>
#endif /* linux */
typedef unsigned long int word32;
typedef unsigned char byte;
#ifdef linux
typedef u_int64_t word64;
#else
typedef unsigned __int64 word64;
#endif /* linux */
typedef union _uword64 {
word64 llword;
struct _lwords {
word32 low;
word32 high;
} lwords;
} UWord64;
#define ADD32(c,a) c += a; if( c < a ) add32(&c + 1,1);
#define IV0 0x67452301 /* standard 160 bit IV */
#define IV1 0xEFCDAB89
#define IV2 0x98BADCFE
#define IV3 0x10325476
#define IV4 0xC3D2E1F0
#define A0 0xC43CF646 /*constant for AX+B in key scheduling */
#define A1 0x2FCAD177 /*constant for AX+B in key scheduling */
#define A2 0x365F411F /*constant for AX+B in key scheduling */
#define A3 0x1CEB5D8F /*constant for AX+B in key scheduling */
#define A4 0xF2045CFE /*constant for AX+B in key scheduling */
#define B0 0x0
#define B1 0x0
#define B2 0x0
#define B3 0x0
#define B4 0x0
#define ALLONES 0xFFFFFFFF
#define C1 0x5a827999 /* constant ( 2**(1/2)/4)*(2**32) 0-19*/
#define C2 0x6ed9eba1 /* constant ( 3**(1/2)/4)*(2**32) 20-39*/
#define C3 0x8f1bbcdc /* constant ( 5**(1/2)/4)*(2**32) 40-59*/
#define C4 0xca62c1d6 /* constant (10**(1/2)/4)*(2**32) 60-79*/
Blumenthal Experimental [Page 8]
Internet Draft PRF and Key Generation with SHA-1 July 2001
#define R(v,l,r) ((v<<l)|(v>>r)) /* rotate function */
#define F(w,x,y) ((w&(x^y))^y) /* non linear function 0-19 */
#define G(w,x,y) (((w|x)&y)|(w&x)) /* non linear func 20-39, 60-79*/
#define H(w,x,y) (w^x^y) /* non linear function 40-59 */
#define I(i) (R((W[i-3]^W[i-8]^W[i-14]^W[i-16]),1,31))
#define J(j,k,l,m) (R((W[j]^W[k]^W[l]^W[m]),1,31))
#define R0(v,w,x,y,z,i) (z+=F(w,x,y)+W[i]+C1+R(v,5,27), \
w=R(w,30,2))
#define R1(v,w,x,y,z,i) (z+=F(w,x,y)+(W[i]=I(i))+C1+R(v,5,27), \
w=R(w,30,2))
#define R2(v,w,x,y,z,i,j,k,l,m) (z+=H(w,x,y)+(W[i]=J(j,k,l,m))\
+ C2 + R(v,5,27), w=R(w,30,2))
#define R3(v,w,x,y,z,i) (z+=G(w,x,y)+(W[i]=I(i))+C3+R(v,5,27),\
w=R(w,30,2))
#define R4(v,w,x,y,z,i) (z+=H(w,x,y)+(W[i]=I(i))+C4+R(v,5,27),\
w=R(w,30,2))
void poly(word32 *a,word32 *b);
void extract(word32 *result,unsigned char *keybuffer, int blk);
int keygen_sha1(word32 *TEMP, word32 *iv, word32 *sha512)
{
word32 W[80];
word32 a,b,c,d,e;
int i;
/*initialize data value */
for (i=0;i<16;i++)
W[i] = sha512[i];
for(i=16;i<80;i++)
W[i] = 0L;
a=iv[0]; b=iv[1]; c=iv[2]; d=iv[3]; e=iv[4];
R0(a,b,c,d,e, 0); R0(e,a,b,c,d, 1);
R0(d,e,a,b,c, 2); R0(c,d,e,a,b, 3);
R0(b,c,d,e,a, 4); R0(a,b,c,d,e, 5);
R0(e,a,b,c,d, 6); R0(d,e,a,b,c, 7);
R0(c,d,e,a,b, 8); R0(b,c,d,e,a, 9);
R0(a,b,c,d,e,10); R0(e,a,b,c,d,11);
R0(d,e,a,b,c,12); R0(c,d,e,a,b,13);
R0(b,c,d,e,a,14); R0(a,b,c,d,e,15);
R1(e,a,b,c,d,16); R1(d,e,a,b,c,17);
R1(c,d,e,a,b,18); R1(b,c,d,e,a,19);
R2(a,b,c,d,e,20,17,12,6,4); R2(e,a,b,c,d,21,18,13,7,5);
R2(d,e,a,b,c,22,19,14,8,6); R2(c,d,e,a,b,23,20,15,9,7);
R2(b,c,d,e,a,24,21,16,10,8); R2(a,b,c,d,e,25,22,17,11,9);
R2(e,a,b,c,d,26,23,18,12,10); R2(d,e,a,b,c,27,24,19,13,11);
R2(c,d,e,a,b,28,25,20,14,12); R2(b,c,d,e,a,29,26,21,15,13);
R2(a,b,c,d,e,30,27,22,16,14); R2(e,a,b,c,d,31,28,23,17,15);
R2(d,e,a,b,c,32,29,24,18,16); R2(c,d,e,a,b,33,30,25,19,17);
Blumenthal Experimental [Page 9]
Internet Draft PRF and Key Generation with SHA-1 July 2001
R2(b,c,d,e,a,34,31,26,20,18); R2(a,b,c,d,e,35,32,27,21,19);
R2(e,a,b,c,d,36,33,28,22,20); R2(d,e,a,b,c,37,34,29,23,21);
R2(c,d,e,a,b,38,35,30,24,22); R2(b,c,d,e,a,39,36,31,25,23);
R3(a,b,c,d,e,40); R3(e,a,b,c,d,41);
R3(d,e,a,b,c,42); R3(c,d,e,a,b,43);
R3(b,c,d,e,a,44); R3(a,b,c,d,e,45);
R3(e,a,b,c,d,46); R3(d,e,a,b,c,47);
R3(c,d,e,a,b,48); R3(b,c,d,e,a,49);
R3(a,b,c,d,e,50); R3(e,a,b,c,d,51);
R3(d,e,a,b,c,52); R3(c,d,e,a,b,53);
R3(b,c,d,e,a,54); R3(a,b,c,d,e,55);
R3(e,a,b,c,d,56); R3(d,e,a,b,c,57);
R3(c,d,e,a,b,58); R3(b,c,d,e,a,59);
R4(a,b,c,d,e,60); R4(e,a,b,c,d,61);
R4(d,e,a,b,c,62); R4(c,d,e,a,b,63);
R4(b,c,d,e,a,64); R4(a,b,c,d,e,65);
R4(e,a,b,c,d,66); R4(d,e,a,b,c,67);
R4(c,d,e,a,b,68); R4(b,c,d,e,a,69);
R4(a,b,c,d,e,70); R4(e,a,b,c,d,71);
R4(d,e,a,b,c,72); R4(c,d,e,a,b,73);
R4(b,c,d,e,a,74); R4(a,b,c,d,e,75);
R4(e,a,b,c,d,76); R4(d,e,a,b,c,77);
R4(c,d,e,a,b,78); R4(b,c,d,e,a,79);
TEMP[0] = iv[0]+a;
TEMP[1] = iv[1]+b;
TEMP[2] = iv[2]+c;
TEMP[3] = iv[3]+d;
TEMP[4] = iv[4]+e;
return(0);
}
/* poly()
*
* DESCRIPTION
*
* This routine performs polynomial (AX+B)mod(2**160+7)
*
*/
void poly(word32 *a,word32 *b)
{
UWord64 p;
word32 c[10];
int i;
/* initialize product coefficients */
for (i = 0; i < 10; i++)
c[i] = 0l;
/* complete c[0] */
Blumenthal Experimental [Page 10]
Internet Draft PRF and Key Generation with SHA-1 July 2001
p.llword = (word64) a[0] * (word64) A0 ;
c[0] = p.lwords.low;
c[1] = p.lwords.high;
/* complete c[1] */
p.llword = (word64) a[1] * (word64) A0;
add32(c+1, p.lwords.low);
add32(c+2, p.lwords.high);
p.llword = (word64) a[0] * (word64) A1;
add32(c+1, p.lwords.low);
add32(c+2, p.lwords.high);
/* complete c[2] */
p.llword = (word64) a[2] * (word64) A0;
add32(c+2, p.lwords.low);
add32(c+3, p.lwords.high);
p.llword = (word64) a[1] * (word64) A1;
add32(c+2, p.lwords.low);
add32(c+3, p.lwords.high);
p.llword = (word64) a[0] * (word64) A2;
add32(c+2, p.lwords.low);
add32(c+3, p.lwords.high);
/* complete c[3] */
p.llword = (word64) a[3] * (word64) A0;
add32(c+3, p.lwords.low);
add32(c+4, p.lwords.high);
p.llword = (word64) a[2] * (word64) A1;
add32(c+3, p.lwords.low);
add32(c+4, p.lwords.high);
p.llword = (word64) a[1] * (word64) A2;
add32(c+3, p.lwords.low);
add32(c+4, p.lwords.high);
p.llword = (word64) a[0] * (word64) A3;
add32(c+3, p.lwords.low);
add32(c+4, p.lwords.high);
/* complete c[4] */
p.llword = (word64) a[4] * (word64) A0;
add32(c+4, p.lwords.low);
add32(c+5, p.lwords.high);
Blumenthal Experimental [Page 11]
Internet Draft PRF and Key Generation with SHA-1 July 2001
p.llword = (word64) a[3] * (word64) A1;
add32(c+4, p.lwords.low);
add32(c+5, p.lwords.high);
p.llword = (word64) a[2] * (word64) A2;
add32(c+4, p.lwords.low);
add32(c+5, p.lwords.high);
p.llword = (word64) a[1] * (word64) A3;
add32(c+4, p.lwords.low);
add32(c+5, p.lwords.high);
p.llword = (word64) a[0] * (word64) A4;
add32(c+4, p.lwords.low);
add32(c+5, p.lwords.high);
/* complete c[5] */
p.llword = (word64) a[4] * (word64) A1;
add32(c+5, p.lwords.low);
add32(c+6, p.lwords.high);
p.llword = (word64) a[3] * (word64) A2;
add32(c+5, p.lwords.low);
add32(c+6, p.lwords.high);
p.llword = (word64) a[2] * (word64) A3;
add32(c+5, p.lwords.low);
add32(c+6, p.lwords.high);
p.llword = (word64) a[1] * (word64) A4;
add32(c+5, p.lwords.low);
add32(c+6, p.lwords.high);
/* complete c[6] */
p.llword = (word64) a[4] * (word64) A2;
add32(c+6, p.lwords.low);
add32(c+7, p.lwords.high);
p.llword = (word64) a[3] * (word64) A3;
add32(c+6, p.lwords.low);
add32(c+7, p.lwords.high);
p.llword = (word64) a[2] * (word64) A4;
add32(c+6, p.lwords.low);
add32(c+7, p.lwords.high);
/* complete c[7] */
p.llword = (word64) a[4] * (word64) A3;
add32(c+7, p.lwords.low);
add32(c+8, p.lwords.high);
p.llword = (word64) a[3] * (word64) A4;
Blumenthal Experimental [Page 12]
Internet Draft PRF and Key Generation with SHA-1 July 2001
add32(c+7, p.lwords.low);
add32(c+8, p.lwords.high);
/* complete c[8] and c[9]*/
p.llword = (word64) a[4] * (word64) A4;
add32(c+8, p.lwords.low);
add32(c+9, p.lwords.high);
/* AX + B */
add32(c, B0);
add32(c+1,B1);
add32(c+2,B2);
add32(c+3,B3);
add32(c+4,B4);
modn(c);
for (i=0;i<5;i++)
b[i] = c[i];
}
/* extract()
*
* DESCRIPTION
*
* This routine extracts the least significant blksiz bytes from
* 160 bits of input
*
*/
void extract(word32 *result,unsigned char *keybuffer, int blksiz)
{
int full_blk = blksiz / 4;
int left_bytes = blksiz % 4;
int i = 0;
for (i = 0; i < full_blk; i++) {
*(keybuffer++) = (unsigned char)
((result[i]) &0xFF);
*(keybuffer++) = (unsigned char)
((result[i])>> 8L&0xFF);
*(keybuffer++) = (unsigned char)
((result[i])>>16L&0xFF);
*(keybuffer++) = (unsigned char)
((result[i])>>24L&0xFF);
}
for (i = 0; i < left_bytes; i++) {
*(keybuffer++) = (unsigned char)
((result[full_blk] >> (i*8)) & 0xFF);
}
}
/*****************************************************************/
Blumenthal Experimental [Page 13]
Internet Draft PRF and Key Generation with SHA-1 July 2001
/* ROUTINE add32
*
* DESCRIPTION
* This routine executes *c += a for a, c, 32-bit numbers,
* and recursively adds any carry to *(c+1) until no
* carry exists.
*/
int add32(word32 *c, const word32 a)
{
*c += a;
if ( *c < a )
add32(c+1,1);
}
#define ADD32(c,a) c += a; if( c < a ) add32(&c + 1,1);
void inc64(word32 c[2])
{
c[0] += 1; if (c[0] < 1) c[1] += 1;
}
/* ROUTINE sub32
*
* DESCRIPTION
* This routine executes *c -= a for a, c, 32-bit numbers,
* and recursively continues any borrow to *(c+1) until no
* borrow exists.
*/
int sub32(word32 *c, const word32 a, word32 *limit)
{
if (c==limit)
return (1);
if ( *c < a ) {
*c -= a;
return(sub32(c+1,1,limit));
}
*c -= a;
return (0);
}
/* ROUTINE modn
*
* DESCRIPTION
* This routine takes a 320-bit number mod n, where
* n = (2 ^ 160) + 7
*/
int modn(word32 *c)
{
UWord64 p;
Blumenthal Experimental [Page 14]
Internet Draft PRF and Key Generation with SHA-1 July 2001
word32 s[6];
int borrow = 0;
/* find subtraction coefficients */
p.llword = (word64) c[5] * 7;
s[0] = p.lwords.low; s[1] = p.lwords.high;
p.llword = (word64) c[6] * 7;
s[2] = p.lwords.high;
/*add32(&s[1], p.lwords.low);*/
ADD32(s[1], p.lwords.low);
p.llword = (word64) c[7] * 7;
s[3] = p.lwords.high;
/*add32(&s[2], p.lwords.low);*/
ADD32(s[2], p.lwords.low);
p.llword = (word64) c[8] * 7;
s[4] = p.lwords.high;
/*add32(&s[3], p.lwords.low);*/
ADD32(s[3], p.lwords.low);
p.llword = (word64) c[9] * 7;
s[5] = p.lwords.high;
/*add32(&s[4], p.lwords.low);*/
ADD32(s[4], p.lwords.low);
borrow |= sub32(c, s[0], c+5);
borrow |= sub32(c+1, s[1], c+5);
borrow |= sub32(c+2, s[2], c+5);
borrow |= sub32(c+3, s[3], c+5);
borrow |= sub32(c+4, s[4], c+5);
s[5] += borrow;
c[5] = 0;
sub32(c+5, s[5], c+6);
if (s[5] != 0) {
s[0] = s[5] * 7;
c[5] = 0;
add32(c+0, s[0]);
}
return(0);
}
/**************************************************************/
/* PRF-SHA-P-32P */
/* */
/* deficiencies: */
/* allows only (2^32 - 1) * blksize bytes of output */
Blumenthal Experimental [Page 15]
Internet Draft PRF and Key Generation with SHA-1 July 2001
/**************************************************************/
int
prf_sha1_p32p(byte *secret_key, /* byte array */
int key_len, /* length of the key in bytes */
byte *random, /* random value */
int rand_len, /* how many random bytes we got */
byte *output, /* where to put output PR sequence */
int output_len, /* bow many bytes of PR to produce */
char function_type, /* `C', `I', etc. */
int blksize) /* how many bytes extract p/iteration */
{
int i = 0;
int cnt = 0, lim = 0;
word32 temp[5];
word32 result[5];
word32 IV[5]; /* SHA-1 IV */
word32 sha_in[16]; /* SHA-1 payload */
word32 sha_out[5]; /* SHA-1 output */
int seed_count;
word32 counter[2]; /* 64-bit iteration counter */
word32 rand[8];
/* implementation simplification: */
if ((output_len % blksize) != 0) return -1;
if ((rand_len % 4) != 0) return -1;
/* determine how many iterations of SHA to make */
lim = output_len / blksize;
/* seed_count is the number of 32 bit words needed
to convert seed_len bytes of session key from
char to unsigned 32 bit words */
seed_count = key_len / 4 + (key_len%4!=0);
for (i=0; i<5; i++)
temp[i] = 0L;
for(i=0; i < seed_count; i++) {
temp[i] |= (word32)(*((secret_key)++));
temp[i] |= (word32)(*((secret_key)++))<< 8L;
temp[i] |= (word32)(*((secret_key)++))<<16L;
temp[i] |= (word32)(*((secret_key)++))<<24L;
}
/* prepare the random value, reuse seed_count */
seed_count = (rand_len / 4);
if (seed_count > 8) seed_count = 8;
for (i = 0; i < 8; i++) rand[i] = 0L;
for(i=0; i < seed_count; i++) {
Blumenthal Experimental [Page 16]
Internet Draft PRF and Key Generation with SHA-1 July 2001
rand[i] |= (word32)(*((random)++));
rand[i] |= (word32)(*((random)++))<< 8L;
rand[i] |= (word32)(*((random)++))<<16L;
rand[i] |= (word32)(*((random)++))<<24L;
}
if (seed_count < 4)
for (i = 0; i < 4; i++) rand[i+4] = rand[i];
/* main PRF loop */
do {
/* initialize the IV with the key */
IV[0] = IV0^ temp[0];
IV[1] = IV1^ temp[1];
IV[2] = IV2^ temp[2];
IV[3] = IV3^ temp[3];
IV[4] = IV4^ temp[4];
/* prepare the payload */
for (i = 0; i < 16; i++)
sha_in[i] = 0x5C5C5C5C;
/* initialize the payload with
function type and counter */
sha_in[2] ^= function_type;
sha_in[0] ^= counter[0]; sha_in[4] ^= counter[0];
sha_in[1] ^= counter[1]; sha_in[5] ^= counter[1];
/* initialize the payload with random number */
sha_in[6] ^= rand[0]; sha_in[7] ^= rand[1];
sha_in[8] ^= rand[2]; sha_in[9] ^= rand[3];
sha_in[10] ^= rand[4]; sha_in[11] ^= rand[5];
sha_in[12] ^= rand[6]; sha_in[13] ^= rand[7];
keygen_sha1(sha_out, IV, sha_in); /* run sha1 */
poly(sha_out, result); /* whiten the output */
/* extract the bits to the output buffer */
extract(result, output, blksize);
/* increment the counter and pointers */
inc64(counter);
output += blksize;
} while (++cnt < lim); /* end of loop */
}
/***********************************************************/
int main(void)
{
word32 msg_i[2];
Blumenthal Experimental [Page 17]
Internet Draft PRF and Key Generation with SHA-1 July 2001
word32 msg_o[10];
word32 TEMP[5],iv[5],sha512[16];
char *enckey="ABCDEFG";
int i, k;
time_t start, finish;
double duration;
unsigned char msg_in[8];
unsigned char msg_out[40];
start = time(0);
msg_i[0]=0xAC4182B6;
msg_i[1]=0x00006EB1;
printf("Secret key is: \"%s\"\n", enckey);
printf("64 bit random input is: %08x %08x\n\n",
msg_i[1], msg_i[0]);
for (i = 0; i < 4; i++) {
msg_in[3-i] = (unsigned char)
((msg_i[1] >> i) & 0xFF);
msg_in[7-i] = (unsigned char)
((msg_i[0] >> i) & 0xFF);
}
//for(i=1; i<=1000000; i++) /* if performance is measured */
prf_sha1_p32p(enckey, strlen(enckey), /* secret key to use */
msg_in, 8, /* 8 bytes of random input */
msg_out, 40, /* want 40 bytes of PRF output */
'I', /* function type 'I' */
4); /* extract 4 bytes per round */
for (i = 0; i < 10; i++) msg_o[i] = 0L;
for (i = 0, k = 0; i < 10; i++) {
msg_o[i] |= (word32)(msg_out[k++]);
msg_o[i] |= (word32)(msg_out[k++] << 8L);
msg_o[i] |= (word32)(msg_out[k++] << 16L);
msg_o[i] |= (word32)(msg_out[k++] << 24L);
}
printf("PRF output mask is: \n");
printf("%08x %08x %08x %08x %08x\n",
msg_o[9], msg_o[8], msg_o[7],
msg_o[6], msg_o[5]);
printf("%08x %08x %08x %08x %08x\n",
msg_o[4], msg_o[3], msg_o[2],
msg_o[1], msg_o[0]);
finish = time(0);
Blumenthal Experimental [Page 18]
Internet Draft PRF and Key Generation with SHA-1 July 2001
duration = difftime(finish, start);
// printf("%f SEC, %ld\n", duration, clock());
exit(0);
}
Test Vector
Secret key is: "ABCDEFG"
64 bit random input is: 00006eb1 ac4182b6
PRF output mask is:
a5b3b73f 01ab06c1 b12abd51 f99117a2 049a84f0
51b65b27 7e6a74a2 a60a5728 43a208cd 0834a993
Blumenthal Experimental [Page 19]