[Docs] [txt|pdf|xml|html] [Tracker] [Email] [Diff1] [Diff2] [Nits]

Versions: 00 01 02 03

Network Working Group                                          D. McGrew
Internet-Draft                                       Cisco Systems, Inc.
Intended status: Informational                                P. Patnala
Expires: June 22, 2009                                 December 19, 2008


                        Threshold Secret Sharing
                        draft-mcgrew-tss-01.txt

Status of this Memo

   This Internet-Draft is submitted to IETF in full conformance with the
   provisions of BCP 78 and BCP 79.

   Internet-Drafts are working documents of the Internet Engineering
   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 obsoleted 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.

   This Internet-Draft will expire on June 22, 2009.

Copyright Notice

   Copyright (c) 2008 IETF Trust and the persons identified as the
   document authors.  All rights reserved.

   This document is subject to BCP 78 and the IETF Trust's Legal
   Provisions Relating to IETF Documents
   (http://trustee.ietf.org/license-info) in effect on the date of
   publication of this document.  Please review these documents
   carefully, as they describe your rights and restrictions with respect
   to this document.








McGrew & Patnala          Expires June 22, 2009                 [Page 1]


Internet-Draft          Threshold Secret Sharing           December 2008


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.


Table of Contents

   1.  Introduction . . . . . . . . . . . . . . . . . . . . . . . . .  3
     1.1.  Conventions Used In This Document  . . . . . . . . . . . .  3
   2.  Operations . . . . . . . . . . . . . . . . . . . . . . . . . .  4
     2.1.  Create Shares  . . . . . . . . . . . . . . . . . . . . . .  4
     2.2.  Reconstruct Secret . . . . . . . . . . . . . . . . . . . .  4
   3.  Polynomial Interpolation over GF(256)  . . . . . . . . . . . .  5
     3.1.  Field Representation . . . . . . . . . . . . . . . . . . .  5
     3.2.  Share Generation . . . . . . . . . . . . . . . . . . . . .  7
     3.3.  Secret Reconstruction  . . . . . . . . . . . . . . . . . .  8
   4.  Robust Threshold Secret Sharing  . . . . . . . . . . . . . . . 10
     4.1.  RTSS Data Format . . . . . . . . . . . . . . . . . . . . . 10
   5.  Error Correction and Data Recovery . . . . . . . . . . . . . . 12
     5.1.  Data Recovery  . . . . . . . . . . . . . . . . . . . . . . 12
     5.2.  Error Correction . . . . . . . . . . . . . . . . . . . . . 12
     5.3.  A Repetition Code  . . . . . . . . . . . . . . . . . . . . 14
   6.  Format . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
   7.  Design and Rationale . . . . . . . . . . . . . . . . . . . . . 17
   8.  Testing  . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
   9.  Test Cases . . . . . . . . . . . . . . . . . . . . . . . . . . 19
   10. Security Considerations  . . . . . . . . . . . . . . . . . . . 20
   11. IANA Considerations  . . . . . . . . . . . . . . . . . . . . . 21
   12. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 22
   13. References . . . . . . . . . . . . . . . . . . . . . . . . . . 23
     13.1. Normative References . . . . . . . . . . . . . . . . . . . 23
     13.2. Informative References . . . . . . . . . . . . . . . . . . 23
   Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 24








McGrew & Patnala          Expires June 22, 2009                 [Page 2]


Internet-Draft          Threshold Secret Sharing           December 2008


1.  Introduction

   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 does not rely on any
   assumptions about the complexity of solving a particular
   computational problem (such as factoring); it is information-
   theoretically secure.  Each share is slightly longer than the
   original secret.

   In the context of secret sharing, the word "share" means a part of
   something, and "sharing" means the act of breaking up into parts.
   Readers may be confused if they think of "sharing" as meaning "giving
   to or posessing with others".

   TSS is especially useful whenever there is a need to ensure the
   availability of a secret, yet there is a simultaneous need to reduce
   the risk of compromise of the secret.  By dividing the secret into
   multiple shares, and distributing each share to a different trusted
   entity, TSS reduces that risk while providing for the availability of
   the secret.  At the time that the secret is divided into shares, the
   threshold defining a number of shares that are needed to reconstruct
   the secret is set.

1.1.  Conventions Used In This Document

   The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
   "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
   document are to be interpreted as described in [RFC2119].





















McGrew & Patnala          Expires June 22, 2009                 [Page 3]


Internet-Draft          Threshold Secret Sharing           December 2008


2.  Operations

   A threshold secret sharing system provides two operations: one that
   creates a set of shares given a secret, and one that reconstructs the
   secret, given a set of shares.  This section defines the inputs and
   ouputs of these operations.  The following sections describe the
   details of TSS based on a polynomial interpolation in GF(256).

2.1.  Create Shares

   This operation takes an octet string S, whose length is L octets, and
   a threshold parameter M, and generates a set of N shares, any M of
   which can be used to reconstruct the secret.

   The secret S is treated as an unstructured sequence of octets.  It is
   not expected to be null-terminated.  The number of octets in the
   secret may be anywhere from zero up to TSS_MAX_SECRET_LENGTH.

   The threshold parameter M is the number of shares that will be needed
   to reconstruct the secret.  This value may be any number between one
   and 255.

   The number of shares N that will be generated MUST be between the
   threshold value M and 255, inclusive.  The upper limit is particular
   to the TSS algorithm specified in this document.

   If the operation can not be completed successfully, then an error
   code should be returned.

2.2.  Reconstruct Secret

   The reconstruct operation reconstructs the secret from a set of
   shares.

   The number of shares N must be provided as a parameter.

   The only other parameter is the list of shares themselves.  The
   shares should be treated as unstructured octet strings.

   If the operation could be completed, then the secret value will be
   returned.

   If the operation can not be completed successfully, then an error
   code should be returned.







McGrew & Patnala          Expires June 22, 2009                 [Page 4]


Internet-Draft          Threshold Secret Sharing           December 2008


3.  Polynomial Interpolation over GF(256)

   A finite field is a set of elements with associated addition,
   multiplication, subtraction, and division operations.  Each of those
   operations acts on elements in the field, and returns an element in
   the field.  This specification uses the field GF(256), and each
   element is represented as a single octet.  There are many possible
   ways to represent a finite field; below we define the field
   arithmetic operations as having inputs and outputs that are octets.
   This fixes a particular representation, without explicitly defining
   it, and it avoids the issue of the bit-representation of octets.

3.1.  Field Representation

   The elements of the field GF(256) are represented as octets.  In the
   following, each octet is represented as a hexadecimal number with a
   leading "0x", as in ANSI/ISO C. The representation of the finite
   field that we use is defined in terms of the addition, subtraction,
   multiplication, and division operations.  We define these operations
   as taking two octets as input and returning a single octet as output.
   These operations are defined in terms of two tables, the EXP table
   (Figure 1) and the LOG table (Figure 2), which define the exponential
   function and the logarithmic function, respectively.  The ith
   elements of these tables are denoted as EXP[i] and LOG[i].  LOG takes
   a non-zero field element as input, and returns an integer, and EXP
   takes an integer and returns a field element.

   The addition operation returns the bitwise exclusive-or of its
   operands.  The subtraction operation is identical, because the field
   has characteristic two.

   The multiplication operation takes two elements X and Y as input and
   proceeds as follows.  If either X or Y is equal to 0x00, then the
   operation returns 0x00.  Otherwise, the value EXP[ (LOG[X] + LOG[Y])
   modulo 255] is returned.

   The division operation takes a dividend X and a divisor Y as input
   and computes X divided by Y as follows.  If X is equal to 0x00, then
   the operation returns 0x00.  If Y is equal to 0x00, then the input is
   invalid, and an error condition occurs.  Otherwise, the value EXP[
   (LOG[X] - LOG[Y]) modulo 255] is returned.

   The operation of raising a field element X to a power i, where i is a
   positive integer, is denoted as X^i, and it consists of multiplying X
   by itself i times.






McGrew & Patnala          Expires June 22, 2009                 [Page 5]


Internet-Draft          Threshold Secret Sharing           December 2008


         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

     Figure 1: The EXP table.  The elements are to be read from top to
     bottom and left to right.  For example, EXP[0] is 0x01, EXP[8] is
    0x1a, and so on. Note that the EXP[255] entry is present only as a
         placeholder, and is not actually used in any computation.














McGrew & Patnala          Expires June 22, 2009                 [Page 6]


Internet-Draft          Threshold Secret Sharing           December 2008


         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

    Figure 2: The LOG table.   The elements are to be read from top to
     bottom and left to right.  For example, LOG[1] is 0x00, LOG[8] is
     0x4b, and so on.  Note that the LOG[0] entry is present only as a
         placeholder, and is not actually used in any computation.

3.2.  Share Generation

   We first define how to share a single octet.

   The function f takes as input a single octet X that is not equal to
   0x00, and an array A of D+1 octets, and returns a single octet.  It
   is defined as

      f(X, A) =  SUM  A[i] * X^i
                i=0,D



McGrew & Patnala          Expires June 22, 2009                 [Page 7]


Internet-Draft          Threshold Secret Sharing           December 2008


   Because the summation takes place over GF(256), each addition uses
   the exclusive-or operation, and not integer addition.  Note that the
   successive values of X^i used in the computation of the function f
   can be computed by multiplying a value by X once for each term in the
   summation.

   To create N shares from a secret, with a threshold of M, the
   following procedure, or any equivalent method, is used:

      For each share, a distinct x-value is generated.  Each x-value is
      an octet other than the all-zero octet.  All of the x-values used
      during a share generation process MUST be distinct.

      Each share is initialized to the x-value associated with that
      share.

      For each octet of the secret, the following steps are performed.
      An array A of M+1 octets is created, in which the array element
      A[0] contains the octet of the secret, and the array elements
      A[1], ..., A[M] contain octets that are selected independently and
      uniformly at random.  For each share, the value of f(X,A) is
      computed, where X is the x-value of the share, and the resulting
      octet is appended to the share.

   After the procedure is done, each share contains one more octet than
   does the secret.  The share format can be illustrated as

        +---------+---------+---------+---------+---------+
        |    X    | f(X,A)  | f(X,B)  | f(X,C)  |   ...   |
        +---------+---------+---------+---------+---------+

   where X is the x-value of the share, and A, B, and C are arrays of
   M+1 octets; A[0] is equal to the first octet of the secret, B[0] is
   equal to the second octet of the secret, and so on.

3.3.  Secret Reconstruction

   We denote the ith Lagrange function as L_i.  This function takes as
   input a single octet X, and an array U of M octets, and is defined as

                                X - U[j]
      L_i(X, U) =   PRODUCT   -------------
                  j=0,M, j!=i  U[j] - U[i]

   Here the product runs over all of the values of j from 0 to M,
   excluding the value i.

   We denote the interpolation function as I. This function takes as



McGrew & Patnala          Expires June 22, 2009                 [Page 8]


Internet-Draft          Threshold Secret Sharing           December 2008


   input a single octet Z, two arrays U and V, each consisting of M
   octets, and returns a single octet; it is defined as

      I(X, U, V) =   SUM  L_j(X, U) * V[j].
                    j=0,M

   To reconstruct a secret from M shares, the following procedure, or
   any equivalent method, is used:

      If the shares are not equal length, then the input is
      inconsistent.  An error should be reported, and processing must
      halt.

      The output string is initialized to the empty (zero-length) octet
      string.

      The octet array U is formed by setting U[i] equal to the first
      octet of the ith share.  (Note that the ordering of the shares is
      arbitrary, but must be consistent throughout this algorithm.)

      The initial octet is stripped from each share.

      If any two elements of the array U have the same value, then an
      error condition has occurred; this fact should be reported, then
      the procedure must halt.

      For each octet of the shares, the following steps are performed.
      An array V of M+1 octets is created, in which the array element
      V[i] contains the octet from the ith share.  The value of I(0x00,
      U, V) is computed, then appended to the output string.

      The output string is returned.

   After the procedure is done, the string that is returned contains one
   fewer octet than do the shares.
















McGrew & Patnala          Expires June 22, 2009                 [Page 9]


Internet-Draft          Threshold Secret Sharing           December 2008


4.  Robust Threshold Secret Sharing

   A robust TSS system, or RTSS, is one that provides security even when
   one or more of the shares that are provided to the reconstruction
   algorithm may be crafted by a malicious adversary.  In addition, an
   RTSS system will detect unintentional corruption of the shares.

   We provide robustness by adding a pre-processing step to the TSS
   share generation step, and a post-processing step to the TSS secret
   reconstruction step.  The pre-processing consists of taking the
   secret S, then appending a hash H(S) to it.  The post-processing step
   consists of verifying that the reconstructed secret has the form S ||
   H(S), where the symbol || denotes the concatenation operation.

   An RTSS system can perform an additional operation that verifies the
   validity of a set of shares.  This operation has the same inputs as
   the Reconstruct operation.  Its output consists of an indication
   whether or not the secret could be reconstructed, but the secret
   itself is not returned.  This operation may be useful in a situation
   in where the availability of a secret must be verified, for example,
   as part of an audit.

4.1.  RTSS Data Format

   We use a data format with the following fields, in order:

   Identifier.  This field contains a variable number of octets.  It
      identifies the secret with which a share is associated.  When a
      secret is reconstructed, each of the shares used as input should
      have the same value identifier.

   Flags.  This field contains a single octet.

   Number of Shares.  This field contains a single octet.

   Threshold.  This field contains a single octet.

   Digest Algorithm.  This field contains a single octet.

   Secret Length.  This field is four octets long.

   Share Index.  This field is a single octet in length.  It contains
      the finite field element that is used as the "X" coordinate for
      the share.







McGrew & Patnala          Expires June 22, 2009                [Page 10]


Internet-Draft          Threshold Secret Sharing           December 2008


   Share Data.  This field has a length that is a variable number of
      octets.  It contains the actual share data.

   This format is illustrated in Figure 3.

                    +--------------------------------+
                    |           Identifier           |
                    |   (variable number of octets)  |
                    +--------------------------------+
                    |             Flags              |
                    |           (1 octets)           |
                    +--------------------------------+

             ........

                    +--------------------------------+
                    |                                |
                    ~           Share Data           ~
                    |   (variable number of octets)  |
                    |                                |
                    +--------------------------------+

                          Figure 3: Share Format.




























McGrew & Patnala          Expires June 22, 2009                [Page 11]


Internet-Draft          Threshold Secret Sharing           December 2008


5.  Error Correction and Data Recovery

   TSS and RTSS are suitable for the protection of long-term key
   material.  In such applications, it is highly desirable to provide
   protection against the accidental corruption of the shares.  This
   section defines data formats that can be used to protect shares.
   These formats are optional extensions to the basic TSS and RTSS
   systems.

5.1.  Data Recovery

   To protect against the corruption of the filesystem that is holding
   the shares, a "magic number" can be used as the initial part of the
   share data format.  A magic number is a constant data string that is
   chosen arbitrarily, but which is unlikely to appear in other
   contexts, and thus can be used to recognize a data format when it
   appears in an arbitrary data stream.  The use of a magic number in
   the data format for a share greatly simplifies the task of finding a
   share after a filesystem has been corrupted.

   The 8-octet magic number f628f91b52023d11 (hexadecimal) SHOULD be
   used.  The number was selected randomly from a uniform distribution.

5.2.  Error Correction

   To protect against data corruption in the underlying media, an error-
   correcting code (ECC) can be used.  An ECC system consists of an
   encoding function, which maps the data to a codeword, and a decoding
   function, which maps a (possibly corrupted) codeword to the data.
   The simplest such code is a repetition code, in which multiple copies
   of the data are stored.  In this specification, all ECCs must be
   systematic, that is, the data must appear as the initial bytes of the
   codeword.  This property allows an implementation of the ECC to avoid
   the implementation of the full decoding algorithm.

   We use a data format that incorporates the following fields, in
   order:

   Encoding Type.  This field is four octets long.  It contains an
      unsigned integer in network byte order that denotes the type of
      the encoding, i.e. the algorithm that was used during the encoding
      process.

   Data Length.  This field is four octets long.  It contains an
      unsigned integer in network byte order that denotes the number of
      octets in the Data field.





McGrew & Patnala          Expires June 22, 2009                [Page 12]


Internet-Draft          Threshold Secret Sharing           December 2008


   Redundancy Length.  This field is four octets long.  It contains an
      unsigned integer in network byte order that denotes the number of
      octets in the Redundancy field.

   Data.  This field has a length that is a variable number of octets,
      which is indicated by the Data Length field.  It contains the data
      that is intended to be conveyed by the code.  If no data
      corruption has occurred, then this field will contain the data
      that was originally encoded.

   Redundancy.  This field has a length that is a variable number of
      octets, which is indicated by the Reduncancy Length field.  It
      contains information that can be used to check whether or not
      there are any errors in the Data field, and to correct some errors
      that may have occurred.

   This format is illustrated in Figure 4.

                    +--------------------------------+
                    |         Encoding Type          |
                    |           (4 octets)           |
                    +--------------------------------+
                    |          Data Length           |
                    |           (4 octets)           |
                    +--------------------------------+
                    |       Redundancy Length        |
                    |           (4 octets)           |
                    +--------------------------------+
                    |                                |
                    ~             Data               ~
                    |   (variable number of octets)  |
                    |                                |
                    +--------------------------------+
                    |                                |
                    ~          Redundancy            ~
                    |   (variable number of octets)  |
                    |                                |
                    +--------------------------------+

                    Figure 4: Error Correction Format.

   If a code has a free parameter, the value of that parameter MUST be
   inferable from the values of the Data Length and Redundancy Length
   fields.







McGrew & Patnala          Expires June 22, 2009                [Page 13]


Internet-Draft          Threshold Secret Sharing           December 2008


5.3.  A Repetition Code

   This section defines a format for a repetition code, which is a
   particular error correcting code that is conceptually simple and easy
   to implement.

   The value of the Encoding Type field is equal to 0000001
   (hexadecimal).

   The Redundancy field contains R copies of the Data field, where R is
   an even number.  The Redundancy Length is equal to the Data Length
   times R. The value of R MAY be equal to zero, in which case no error
   detection or correction is possible (but implementation is simple).
   The value of R SHOULD be at least two.

   For example, if the data that is encoded is equal to 68656c6c6f
   (hexadecimal), then the ECF data with R=2 would be

      <- ET -><- DL -><- RL -><- Data -><--- Redundancy --->
      00000001000000050000000a68656c6c6f68656c6c6f68656c6c6f

   To check the Data field for errors, that field should be compared
   with each of its copies in the redundancy field.

   The Repetition Code can be decoded by using majority-logic decoding.
   Considering both the Data and Redundancy fields, there are R+1
   (possibly corrupted) copies of the original data, where R+1 is an odd
   number.  The decoding process independently considers each octet of
   the Data field, and the corresponding octets of the copies that
   appear in the Redundancy field.  That is, the ith octet of the Data,
   plus octets i, L+i, 2L+i, ... , RL+i, are analyzed independent from
   all other octets, where L is the value of the Data Length field.  The
   following algorithm is applied to these octets.  The binary
   representation of each octet is considered.  For each bit in that
   representation, if more of the copies have a "1" in that position
   than have a "0" in that position, then that position is decoded to
   the value "1"; otherwise, it is decoded to "0".  This process is
   repeated for all of the bit position.  After all of the bits in the
   octet have been decoded, the value of the ith octet in the output of
   the decoding algorithm is computed, using the same binary
   representation as before.

   For example, if the data that was encoded in the previous example was
   corrupted to the value

      <- ET -><- DL -><- RL -><- Data -><--- Redundancy --->
      00000001000000050000000a68656c6c2f68656c6cef68656c6c6f
                                      **        **        **



McGrew & Patnala          Expires June 22, 2009                [Page 14]


Internet-Draft          Threshold Secret Sharing           December 2008


   then decoding would proceed as follows.  The fifth octet of the Data
   field is equal to 2f, while the fifth and tenth octets of the
   Redundancy field are equal to ef and 6f, respectively.  Using a bit
   representation with the most significant bit on the left, the octets
   and the "majority" octet are as follows:

                              hex binary
       octet from Data        2f  00101111
       octet from first copy  ef  11101111
       octet from second copy 6f  01101111
       -----------------------------------
       majority               6f  01101111

   Thus the fifth octet in the output of the decoding algorithm will be
   6f.




































McGrew & Patnala          Expires June 22, 2009                [Page 15]


Internet-Draft          Threshold Secret Sharing           December 2008


6.  Format

   This section summarizes the order of processing for when secret
   sharing is performed using the facilities for robustness (RTSS),
   error correction (ECC), and data recovery (Magic Number), and
   clarifies the relationships between data formats.  This processing
   can be viewed as a layered model, as illustrated in Figure 5.  (Note
   that we have not adhered to a strictly layered model, for the sake of
   simplicity, since the format defined by RTSS is used after the shares
   are generated.)

   When RTSS is used, it is applied to the secret before the sharing
   operation (and is removed from the secret after the reconstruction
   operaation).  The RTSS data format MUST be used.

   When ECC is used, it is applied to the RTSS data after the sharing
   operation, so that the ECC Data field contains the entire RTSS Data
   Format.

   When a Magic Number is used, it is added after the ECC formatting is
   done, and it is prepended to the Error Correction Format.

                   Secret                       Secret
                      |                            ^
                      v                            |
             +------------------+         +------------------+
             |   Append Hash    |         |   Verify Hash    |
             +------------------+         +------------------+
                      |                            |
             +------------------+         +------------------+
             | Generate Shares  |         |Reconstruct Secret|
             +------------------+         +------------------+
                      |                            |
             +------------------+         +------------------+
             |   ECC Encoding   |         |   ECC Decoding   |
             +------------------+         +------------------+
                      |                            |
             +------------------+         +------------------+
             | Add Magic Number |         |Strip Magic Number|
             +------------------+         +------------------+
                      |                            ^
                      v                            |
                    Shares ----------------> Shares

                 Figure 5: The combined processing model.






McGrew & Patnala          Expires June 22, 2009                [Page 16]


Internet-Draft          Threshold Secret Sharing           December 2008


7.  Design and Rationale

   In this implementation, the secret and the shares are octet strings.
   Each octet is treated as an element of the finite field GF(256 ).
   The share-generation algorithm is applied to each octet of the secret
   independently.  Similarly, the octets are treated independently
   during the reconstruction of the secrets from the shares.

   Shamir's original description treats the secret as a large integer
   modulo a large prime number [shamir].  The advantages of using a
   vector over GF(2^8) are that the computations are more efficient and
   the encoding is simpler.  Multiplication and inversion over GF(2^8)
   can be done with two table lookups and two exors, using two fixed
   tables of 256 bytes each.  One limitation of the GF(2^8) approach is
   that the number of shares that can be generated cannot be greater
   than 255; this limitation is unlikely to be important in practice,
   since fewer than ten shares are typically used.

   The reconstruction of the secret is done using Lagrange interpolation
   polynomials.  This method is simple and easily tested.  For large
   thresholds, this method is less efficient than an optimal method
   would be.  However, performance is still good, and it is expected
   that the reconstruction of the secret will not be a performance-
   critical operation.



























McGrew & Patnala          Expires June 22, 2009                [Page 17]


Internet-Draft          Threshold Secret Sharing           December 2008


8.  Testing

   As with every crypto algorithm, it is essential to test an
   implementation of TSS or RTSS for correctness.  This section provides
   guidance for such testing.  Test cases are provided for known-answer
   tests.

   The Share Index field can never be equal to zero.  This property
   SHOULD be tested.

   There is a simple consistency test that can be run on an
   implementation that uses the Lagrange form of the interpolation
   polynomial.  Each function L_i(X,U) as defined above has the property
   that

   L_i(X,X[j]) = / unity (0x01) when i is equal to j, and
                 \ zero (0x00) otherwise.

   The random source must be tested to ensure that it has high min-
   entropy.































McGrew & Patnala          Expires June 22, 2009                [Page 18]


Internet-Draft          Threshold Secret Sharing           December 2008


9.  Test Cases

   This section provides test cases that can be used to validate an
   implementation.  All values are in hexadecimal.

   algorithm -  The algorithm used in the test case.

   secret -  The secret value to be split into shares.

   threshold -  The number of shares required to reconstruct a secret.

   share index -  A share index.  Each test case has multiple share
      values, and each share is associated with a share index.

   share -  A share value.


     algorithm = TSS
        secret = 7465737400
     threshold = 2
   share index = 1
         share = B9FA07E185
   share index = 2
         share = F5409B4511



























McGrew & Patnala          Expires June 22, 2009                [Page 19]


Internet-Draft          Threshold Secret Sharing           December 2008


10.  Security Considerations

   It is crucial for security that the source of randomness used in the
   share generation process by cryptographically strong; it MUST be
   suitable for generating cryptographic keys.  [RFC4086] provides
   guidance on the selection and implementation of random sources.

   A TSS implementation SHOULD be tested as described in Section 8.

   The confidentiality of the shares generated by TSS should be
   protected, since the exposure of too many shares will undermine the
   security of the system.  Note that, in this regard, share values are
   more comparable to secret keys than to ciphertext.






































McGrew & Patnala          Expires June 22, 2009                [Page 20]


Internet-Draft          Threshold Secret Sharing           December 2008


11.  IANA Considerations

   This document has no actions for IANA.
















































McGrew & Patnala          Expires June 22, 2009                [Page 21]


Internet-Draft          Threshold Secret Sharing           December 2008


12.  Acknowledgements

   Thanks to Brian Weis and Alfred Hines for constructive feedback.
















































McGrew & Patnala          Expires June 22, 2009                [Page 22]


Internet-Draft          Threshold Secret Sharing           December 2008


13.  References

13.1.  Normative References

   [RFC2119]  Bradner, S., "Key words for use in RFCs to Indicate
              Requirement Levels", BCP 14, RFC 2119, March 1997.

   [RFC4086]  Eastlake, D., Schiller, J., and S. Crocker, "Randomness
              Requirements for Security", BCP 106, RFC 4086, June 2005.

13.2.  Informative References

   [shamir]   Shamir, A., "How to share a secret", Communications of the
              ACM (22): 612-613, 1979.





































McGrew & Patnala          Expires June 22, 2009                [Page 23]


Internet-Draft          Threshold Secret Sharing           December 2008


Authors' Addresses

   David A. McGrew
   Cisco Systems, Inc.
   510 McCarthy Blvd.
   Milpitas, CA  95035
   US

   Phone: (408) 525 8651
   Email: mcgrew@cisco.com
   URI:   http://www.mindspring.com/~dmcgrew/dam.htm


   Praveen Patnala

   Email: praveenpatnala@yahoo.com



































McGrew & Patnala          Expires June 22, 2009                [Page 24]


Html markup produced by rfcmarkup 1.129d, available from https://tools.ietf.org/tools/rfcmarkup/