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 , , à an adversary cannot come up with a new pair 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 #include #include #ifdef linux #include #include #include #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<>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]