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

From: David McGrew <[email-masked]>
Date: Fri, 19 Dec 2008 09:55:25 -0800

Correcting the SAAG address.

On Dec 19, 2008, at 9:39 AM, David McGrew wrote:

> Hello,
>
> this new draft describes a threshold secret sharing method. I  
> suggest that this draft be the basis for an RFC (informational would  
> be fine, I expect), and I welcome comments on it.
>
> best regards,
>
> David
>
> Begin forwarded message:
>
>> From: IETF I-D Submission Tool <[email-masked]>
>> Date: December 19, 2008 9:21:58 AM PST
>> To: [email-masked]
>> Cc: [email-masked]
>> Subject: New Version Notification for draft-mcgrew-tss-01
>>
>>
>> A new version of I-D, draft-mcgrew-tss-01.txt has been successfuly  
>> submitted by David McGrew and posted to the IETF repository.
>>
>> Filename:	 draft-mcgrew-tss
>> Revision:	 01
>> Title:		 Threshold Secret Sharing
>> Creation_date:	 2008-12-19
>> WG ID:		 Independent Submission
>> Number_of_pages: 24
>>
>> Abstract:
>> Threshold secret sharing (TSS) provides a way to generate N shares
>> from a value, so that any M of those shares can be used to
>> reconstruct the original value, but any M-1 shares provide no
>> information about that value.  This method can provide shared access
>> control on key material and other secrets that must be strongly
>> protected.
>>
>> This note defines a threshold secret sharing method based on
>> polynomial interpolation in GF(256) and a format for the storage and
>> transmission of shares.  It also provides usage guidance, describes
>> how to test an implementation, and supplies test cases.
>>
>>
>>
>> The IETF Secretariat.
>>
>>
>
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> https://www.irtf.org/mailman/listinfo/cfrg

_______________________________________________
saag mailing list
[email-masked]
https://www.ietf.org/mailman/listinfo/saag

---

From: Jeffrey Hutzelman <[email-masked]>
Date: Tue, 23 Dec 2008 18:32:47 -0500

>> be fine, I expect), and I welcome comments on it.

In general, this seems like a good idea.  I don't believe we have a good 
TSS algorithm suitable for use in IETF protocols, and I can think of some 
possible uses for one.

Just a few thoughts...

- The definition of the exponentiation operation fails to take into
  account the case where i is 0.

- 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?

I'm afraid I'm being dragged out the door before having a chance to finish 
reading; I'll comment on the rest if/when I have more to add.

-- Jeff

---

From: der Mouse <[email-masked]>
Date: Tue, 23 Dec 2008 19:47:00 -0500 (EST)

> - 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.  (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 ASCII				  Mouse
\ / Ribbon Campaign
 X  Against HTML		[email-masked]
/ \ 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
[email-masked]
https://www.ietf.org/mailman/listinfo/saag