Subject: [eap] questions about PRF in eap-sim-11.txt

From: Michael Richardson <[email-masked]>
Date: Sun, 14 Sep 2003 19:07:48 -0400

-----BEGIN PGP SIGNED MESSAGE-----

Section  17, page 50, says:

   Key derivation is based on the random number generation specified in 
   NIST Federal Information Processing Standards (FIPS) Publication 
   186-2 [12]. The pseudo-random number generator is specified in the 
   change notice 1 (2001 October 5) of [12] (Algorithm 1). As specified 
   in the change notice (page 74), when Algorithm 1 is used as a 
   general-purpose pseudo-random number generator, the "mod q" term in 
   step 3.3 is omitted. The function G used in the algorithm is 
   constructed via Secure Hash Standard as specified in Appendix 3.3 of 
*  the standard. For convenience, the random number algorithm with the 
   correct modification is cited in Annex B.  
    
   160-bit XKEY and XVAL values are used, so b = 160. On each full 
   authentication, the Master Key is used as the initial secret seed-
   key XKEY. The optional user input values (XSEED_j) in step 3.1 are 
   set to zero.  
    
May I suggest that annex B be actually fully edited to reflect all of
these settings?

In *, I assume it is a reference to 186-2?

We need a total of K_encr(128 bits), K_aut(128 bits), MSK(64 bytes), EMSK(64
bytes). A total of 1280 bytes, or m = 4.

So, the algorithm would become:

        let XKEY := MK,
            XSEED_j := 0

   Step 3: For j = 0 to 3 do 
             a. XVAL = XKEY 
             b. w_0 = SHA1(XVAL) 
             c. XKEY = (1 + XKEY + w_0) mod 2^160
             d. XVAL = XKEY 
             e. w_1 = SHA1(XVAL) 
             f. XKEY = (1 + XKEY + w_1) mod 2^160
         3.3 x_j = w_0|w_1 

Assuming that I'm correct, I would strongly suggest that this be documented
in this way. This makes it trivial to code without wandering through 150
pages of FIPS documents. 

]      Out and about in Ottawa.    hmmm... beer.                |  firewalls  [
]   Michael Richardson, Sandelman Software Works, Ottawa, ON    |net architect[
] [email-masked] http://www.sandelman.ottawa.on.ca/ |device driver[
] panic("Just another Debian/notebook using, kernel hacking, security guy");  [

_______________________________________________
eap mailing list
[email-masked]
http://mail.frascone.com/mailman/listinfo/eap

---

From: "Joseph Salowey" <[email-masked]>
Date: Mon, 15 Sep 2003 16:29:01 -0700

Unfortunately this is not quite as trivial as it seems. The NIST
documents are confusing. 

Although the function G is derived from SHA-1 my interpretation of  FIPS
186-2 Appendix 3.3 is that it is slightly different.  In particular in
SHA-1 the length is appended to the message and in function G it is not.
The message block processed by SHA-1 is XKEY plus zero padding out to
512 bits with no message length appended. 

This also seems to be supported by the test vectors listed in:

http://csrc.nist.gov/CryptoToolkit/dss/Examples-1024bit.pdf

In re-reading the NIST specs I have to say that this is not all that
clear.  We definitely need to include a better description in the
appendix and some test vectors.  If you have a simpler way of expressing
this it would be great (or if you find that the spec actually uses
unmodified SHA-1). 

Thanks,

Joe

> -----Original Message-----
> From: [email-masked] [mailto:[email-masked]] 
> On Behalf Of Michael Richardson
> Sent: Sunday, September 14, 2003 4:08 PM
> To: [email-masked]
> Subject: [eap] questions about PRF in eap-sim-11.txt
> 
> 
> May I suggest that annex B be actually fully edited to 
> reflect all of these settings?
> 
> We need a total of K_encr(128 bits), K_aut(128 bits), MSK(64 
> bytes), EMSK(64 bytes). A total of 1280 bytes, or m = 4.
> 
> Assuming that I'm correct, I would strongly suggest that this 
> be documented in this way. This makes it trivial to code 
> without wandering through 150 pages of FIPS documents. 
> 
> ] [email-masked] 
> http://www.sandelman.ottawa.on.ca/ |device > driver[ ] 
> panic("Just another Debian/notebook using, kernel hacking, 
> security guy");  [
> 
> 
> -----BEGIN PGP SIGNATURE-----
> Version: GnuPG v1.2.2 (GNU/Linux)
> Comment: Finger me for keys - custom hacks make this fully PGP2 compat
> 
> iQCVAwUBP2T0rYqHRg3pndX9AQENtgP/ep9cRmhDycJOrq9M3HYBncKOJBRBxsgK
> MZoutlwGJ2oXdQZRTaRaPkDdDnCnOLIiwvonucG0OfRz1AB6gmodZU+Zm3wpXjTM
> y0ymFKFnyjTdw+wpHfaOHDqu2XMRBA9sBbcVRUbOF/qlXgyyjcRYzf/oj5ORF1O/
> 7zxY5Up3Kn4=
> =D0m6
> -----END PGP SIGNATURE-----

---

From: Michael Richardson <[email-masked]>
Date: Mon, 15 Sep 2003 23:01:21 -0400

-----BEGIN PGP SIGNED MESSAGE-----

>>>>> "Joseph" == Joseph Salowey <[email-masked]> writes:
    Joseph> Unfortunately this is not quite as trivial as it seems. The NIST
    Joseph> documents are confusing. 

    Joseph> Although the function G is derived from SHA-1 my interpretation
    Joseph> of  FIPS 186-2 Appendix 3.3 is that it is slightly different.  In
    Joseph> particular in SHA-1 the length is appended to the message and in
    Joseph> function G it is not. 

  Aha. Thank you for this explanation.
  After a bit of code reading, I have the following code:

(regular sha1.c code...)

void SHA1FinalNoLen(unsigned char digest[20], SHA1_CTX* context)
{
  unsigned long i, j;

    for (i = 0; i < 20; i++) {
        digest[i] = (unsigned char)
         ((context->state[i>>2] >> ((3-(i & 3)) * 8) ) & 255);
    }

    /* Wipe variables */
    i = j = 0;
    memset(context->buffer, 0, 64);
    memset(context->state, 0, 20);
    memset(context->count, 0, 8);

#ifdef SHA1HANDSOFF  /* make SHA1Transform overwrite it's own static vars */
    SHA1Transform(context->state, context->buffer);
#endif
}

/*
 * we do it in 8-bit chunks, because we have to keep the numbers
 * in network byte order (i.e. MSB)
 *
 * make it a structure so that we can do structure assignments.
 */
typedef struct onesixty {
	u_int8_t p[20];
} onesixty;

static void onesixty_add_mod(onesixty *sum, onesixty *a, onesixty *b)
{
	u_int32_t s;
	int i, carry;

	carry = 0;
	for(i=19; i>=0; i--) { 
		s = a->p[i] + b->p[i] + carry;
		sum->p[i] = s & 0xff;
		carry = s >> 8;
	}
}

void fips186_2prf(u_int8_t mk[20], u_int8_t finalkey[160])
{
	SHA1_CTX context;
	int j, s;
	onesixty xval, xkey, w_0, w_1, sum, one;
	u_int8_t *f;
	char zeros[64];
	
	/*
	 * let XKEY := MK,
	 *
	 * Step 3: For j = 0 to 3 do 	 
         *   a. XVAL = XKEY 
         *   b. w_0 = SHA1(XVAL) 
         *   c. XKEY = (1 + XKEY + w_0) mod 2^160
         *   d. XVAL = XKEY 
         *   e. w_1 = SHA1(XVAL) 
         *   f. XKEY = (1 + XKEY + w_1) mod 2^160
         * 3.3 x_j = w_0|w_1 
	 *
	 */
	memcpy(&xkey, mk, sizeof(xkey));
	
	/* make the value 1 */
	memset(&one,  0, sizeof(one));
	one.p[19]=1;
	
	f=finalkey;
	
	for(j=0; j<3; j++) {
		/*   a. XVAL = XKEY  */
		xval = xkey;
		
		/*   b. w_0 = SHA1(XVAL)  */
		SHA1Init(&context);

		memset(zeros, 0, sizeof(zeros));
		memcpy(zeros, xval.p, 20);
		SHA1Transform(context.state, zeros);
		SHA1FinalNoLen(w_0.p, &context);
		
		/*   c. XKEY = (1 + XKEY + w_0) mod 2^160 */
		onesixty_add_mod(&sum,  &xkey, &w_0);
		onesixty_add_mod(&xkey, &sum,  &one);
		
		/*   d. XVAL = XKEY  */
		xval = xkey;
		
		/*   e. w_1 = SHA1(XVAL)  */
		SHA1Init(&context);

		memset(zeros, 0, sizeof(zeros));
		memcpy(zeros, xval.p, 20);
		SHA1Transform(context.state, zeros);
		SHA1FinalNoLen(w_1.p, &context);
		
		/*   f. XKEY = (1 + XKEY + w_1) mod 2^160 */
		onesixty_add_mod(&sum,  &xkey, &w_1);
		onesixty_add_mod(&xkey, &sum,  &one);
		
		/* now store it away */
		memcpy(f, &w_0, 20);
		f += 20;
		
		memcpy(f, &w_1, 20);
		f += 20;
	}
}