Re: [Cfrg] [saag] draft-mcgrew-tss-01

[David McGrew <[e-mail]>]

On Dec 23, 2008, at 4:47 PM, der Mouse wrote:

>> - The field multiplication operation is more than a little opaque.
>>  How were the EXP and LOG tables generated?  Is there any convenient
>>  way to demonstrate that that the tables are actually correct and
>>  result in an invertible operation?
>
> The simple thing to do is to build a small program that uses the
> tables, and definitions of multiplication and division, from the
> draft, and verifies that a*b/a=b and a*b/b=a whenever, respectively, a
> or b is nonzero, and that, for any nonzero a, the function x->a*x is a
> permutation on the nonzero values of x.  I've done this (test program
> source is below), and they pass.
>
> I'm hardly an expert group theorist, but I *think* that the underlying
> math will work for any tables that pass those two tests.  (Since the
> definition of multiplication is symmetric, there is no need to test
> separately that x->x*b is a permutation for any nonzero b.)
>
> As for how EXP and LOG were generated, I don't know, since I didn't
> generate them. :)  I suspect EXP was generated by computing successive
> powers of 3 in the field used by Rijndael (ie, GF(256) with reducing
> polynomial 0x11b); the values match values computed that way, so even
> if it wasn't it might as well have been.  (LOG is just the inverse of
> EXP.)  My program checks that EXP matches the powers of 3 in GF(256)
> with polynomial 0x11b, and that EXP and LOG are inverses.

that's right, it's the AES/Rijndael field representation.  The draft  
should state this, since it might be useful to other implementers.

> (I actually
> would prefer that the spec define multiplication and division in terms
> of GF(256) and a particular reducing polynomial rather than in terms  
> of
> tables, even if the operations defined are identical.)

The way that the field is currently defined, there are no bit- 
operations.  That was a conscious choice, because the bit/byte  
conversion is often a point of confusion.

Others have also commented that more info on the field should be  
included, so I think the next version will have an appendix with more  
information in it.   I'd prefer to have minimum information in the  
normative section, and then have more background in an informative  
appendix.

David

>
>
> /~\ The ASCII				  Mouse
> \ / Ribbon Campaign
> X  Against HTML		[e-mail]
> / \ Email!	     7D C8 61 52 5D E7 2D 39  4E F1 31 3E E8 B3 27 4B
>
> Here's that test program.  It prints any errors it finds, so it should
> produce no output.
>
> #include <stdio.h>
> #include <stdlib.h>
> #include <strings.h>
>
> static unsigned char EXP[] = {
>         0x01, 0x03, 0x05, 0x0f, 0x11, 0x33, 0x55, 0xff,
>         0x1a, 0x2e, 0x72, 0x96, 0xa1, 0xf8, 0x13, 0x35,
>         0x5f, 0xe1, 0x38, 0x48, 0xd8, 0x73, 0x95, 0xa4,
>         0xf7, 0x02, 0x06, 0x0a, 0x1e, 0x22, 0x66, 0xaa,
>         0xe5, 0x34, 0x5c, 0xe4, 0x37, 0x59, 0xeb, 0x26,
>         0x6a, 0xbe, 0xd9, 0x70, 0x90, 0xab, 0xe6, 0x31,
>         0x53, 0xf5, 0x04, 0x0c, 0x14, 0x3c, 0x44, 0xcc,
>         0x4f, 0xd1, 0x68, 0xb8, 0xd3, 0x6e, 0xb2, 0xcd,
>         0x4c, 0xd4, 0x67, 0xa9, 0xe0, 0x3b, 0x4d, 0xd7,
>         0x62, 0xa6, 0xf1, 0x08, 0x18, 0x28, 0x78, 0x88,
>         0x83, 0x9e, 0xb9, 0xd0, 0x6b, 0xbd, 0xdc, 0x7f,
>         0x81, 0x98, 0xb3, 0xce, 0x49, 0xdb, 0x76, 0x9a,
>         0xb5, 0xc4, 0x57, 0xf9, 0x10, 0x30, 0x50, 0xf0,
>         0x0b, 0x1d, 0x27, 0x69, 0xbb, 0xd6, 0x61, 0xa3,
>         0xfe, 0x19, 0x2b, 0x7d, 0x87, 0x92, 0xad, 0xec,
>         0x2f, 0x71, 0x93, 0xae, 0xe9, 0x20, 0x60, 0xa0,
>         0xfb, 0x16, 0x3a, 0x4e, 0xd2, 0x6d, 0xb7, 0xc2,
>         0x5d, 0xe7, 0x32, 0x56, 0xfa, 0x15, 0x3f, 0x41,
>         0xc3, 0x5e, 0xe2, 0x3d, 0x47, 0xc9, 0x40, 0xc0,
>         0x5b, 0xed, 0x2c, 0x74, 0x9c, 0xbf, 0xda, 0x75,
>         0x9f, 0xba, 0xd5, 0x64, 0xac, 0xef, 0x2a, 0x7e,
>         0x82, 0x9d, 0xbc, 0xdf, 0x7a, 0x8e, 0x89, 0x80,
>         0x9b, 0xb6, 0xc1, 0x58, 0xe8, 0x23, 0x65, 0xaf,
>         0xea, 0x25, 0x6f, 0xb1, 0xc8, 0x43, 0xc5, 0x54,
>         0xfc, 0x1f, 0x21, 0x63, 0xa5, 0xf4, 0x07, 0x09,
>         0x1b, 0x2d, 0x77, 0x99, 0xb0, 0xcb, 0x46, 0xca,
>         0x45, 0xcf, 0x4a, 0xde, 0x79, 0x8b, 0x86, 0x91,
>         0xa8, 0xe3, 0x3e, 0x42, 0xc6, 0x51, 0xf3, 0x0e,
>         0x12, 0x36, 0x5a, 0xee, 0x29, 0x7b, 0x8d, 0x8c,
>         0x8f, 0x8a, 0x85, 0x94, 0xa7, 0xf2, 0x0d, 0x17,
>         0x39, 0x4b, 0xdd, 0x7c, 0x84, 0x97, 0xa2, 0xfd,
>         0x1c, 0x24, 0x6c, 0xb4, 0xc7, 0x52, 0xf6, 0x00 };
>
> static unsigned char LOG[] = {
>         0x00, 0x00, 0x19, 0x01, 0x32, 0x02, 0x1a, 0xc6,
>         0x4b, 0xc7, 0x1b, 0x68, 0x33, 0xee, 0xdf, 0x03,
>         0x64, 0x04, 0xe0, 0x0e, 0x34, 0x8d, 0x81, 0xef,
>         0x4c, 0x71, 0x08, 0xc8, 0xf8, 0x69, 0x1c, 0xc1,
>         0x7d, 0xc2, 0x1d, 0xb5, 0xf9, 0xb9, 0x27, 0x6a,
>         0x4d, 0xe4, 0xa6, 0x72, 0x9a, 0xc9, 0x09, 0x78,
>         0x65, 0x2f, 0x8a, 0x05, 0x21, 0x0f, 0xe1, 0x24,
>         0x12, 0xf0, 0x82, 0x45, 0x35, 0x93, 0xda, 0x8e,
>         0x96, 0x8f, 0xdb, 0xbd, 0x36, 0xd0, 0xce, 0x94,
>         0x13, 0x5c, 0xd2, 0xf1, 0x40, 0x46, 0x83, 0x38,
>         0x66, 0xdd, 0xfd, 0x30, 0xbf, 0x06, 0x8b, 0x62,
>         0xb3, 0x25, 0xe2, 0x98, 0x22, 0x88, 0x91, 0x10,
>         0x7e, 0x6e, 0x48, 0xc3, 0xa3, 0xb6, 0x1e, 0x42,
>         0x3a, 0x6b, 0x28, 0x54, 0xfa, 0x85, 0x3d, 0xba,
>         0x2b, 0x79, 0x0a, 0x15, 0x9b, 0x9f, 0x5e, 0xca,
>         0x4e, 0xd4, 0xac, 0xe5, 0xf3, 0x73, 0xa7, 0x57,
>         0xaf, 0x58, 0xa8, 0x50, 0xf4, 0xea, 0xd6, 0x74,
>         0x4f, 0xae, 0xe9, 0xd5, 0xe7, 0xe6, 0xad, 0xe8,
>         0x2c, 0xd7, 0x75, 0x7a, 0xeb, 0x16, 0x0b, 0xf5,
>         0x59, 0xcb, 0x5f, 0xb0, 0x9c, 0xa9, 0x51, 0xa0,
>         0x7f, 0x0c, 0xf6, 0x6f, 0x17, 0xc4, 0x49, 0xec,
>         0xd8, 0x43, 0x1f, 0x2d, 0xa4, 0x76, 0x7b, 0xb7,
>         0xcc, 0xbb, 0x3e, 0x5a, 0xfb, 0x60, 0xb1, 0x86,
>         0x3b, 0x52, 0xa1, 0x6c, 0xaa, 0x55, 0x29, 0x9d,
>         0x97, 0xb2, 0x87, 0x90, 0x61, 0xbe, 0xdc, 0xfc,
>         0xbc, 0x95, 0xcf, 0xcd, 0x37, 0x3f, 0x5b, 0xd1,
>         0x53, 0x39, 0x84, 0x3c, 0x41, 0xa2, 0x6d, 0x47,
>         0x14, 0x2a, 0x9e, 0x5d, 0x56, 0xf2, 0xd3, 0xab,
>         0x44, 0x11, 0x92, 0xd9, 0x23, 0x20, 0x2e, 0x89,
>         0xb4, 0x7c, 0xb8, 0x26, 0x77, 0x99, 0xe3, 0xa5,
>         0x67, 0x4a, 0xed, 0xde, 0xc5, 0x31, 0xfe, 0x18,
>         0x0d, 0x63, 0x8c, 0x80, 0xc0, 0xf7, 0x70, 0x07 };
>
> static unsigned char m(unsigned char a, unsigned char b)
> {
> return((a&&b)?EXP[(LOG[a]+LOG[b])%255]:0);
> }
>
> static unsigned char d(unsigned char a, unsigned char b)
> {
> if (! b) abort();
> return(a?EXP[(255+LOG[a]-LOG[b])%255]:0);
> }
>
> int main(void);
> int main(void)
> {
> unsigned int a;
> unsigned int b;
> unsigned int p;
> unsigned int q;
> char v[256];
>
> p = 1;
> for (a=0;a<255;a++)
>  { if (EXP[a] != p)
>     { printf("EXP[%02x] = %02x, not %02x\n",a,EXP[a],p);
>     }
>    p = (p ^ ((p&0x7f)<<1)) ^ ((p&0x80) ? 0x1b : 0);
>  }
> for (a=1;a<256;a++)
>  { if (EXP[LOG[a]] != a)
>     { printf("EXP[LOG[%02x]] = %02x\n",a,EXP[LOG[a]]);
>     }
>    bzero(&v[0],256);
>    for (b=1;b<256;b++)
>     { p = m(a,b);
>       v[p] = 1;
>       q = d(p,a);
>       if (q != b)
> 	{ printf("%02x * %02x = %02x / %02x = %02x\n",a,b,p,a,q);
> 	}
>       q = d(p,b);
>       if (q != a)
> 	{ printf("%02x * %02x = %02x / %02x = %02x\n",a,b,p,b,q);
> 	}
>     }
>    for (b=1;b<256;b++)
>     { if (! v[b])
> 	{ printf("%02x * all misses %02x\n",a,b);
> 	}
>     }
>  }
> return(0);
> }
> _______________________________________________
> saag mailing list
> [e-mail]
> https://www.ietf.org/mailman/listinfo/saag

_______________________________________________
Cfrg mailing list
[e-mail]
https://www.irtf.org/mailman/listinfo/cfrg