idnits 2.17.1 draft-mcgrew-tss-03.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- ** You're using the IETF Trust Provisions' Section 6.b License Notice from 12 Sep 2009 rather than the newer Notice from 28 Dec 2009. (See https://trustee.ietf.org/license-info/) Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- No issues found here. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year == Line 659 has weird spacing: '... hex bina...' -- The document seems to lack a disclaimer for pre-RFC5378 work, but may have content which was first submitted before 10 November 2008. If you have contacted all the original authors and they are all willing to grant the BCP78 rights to the IETF Trust, then this is fine, and you can ignore this comment. If not, you may need to add the pre-RFC5378 disclaimer. (See the Legal Provisions document at https://trustee.ietf.org/license-info for more information.) -- The document date (March 3, 2010) is 5167 days in the past. Is this intentional? Checking references for intended status: Informational ---------------------------------------------------------------------------- == Missing Reference: 'X' is mentioned on line 228, but not defined == Missing Reference: 'Y' is mentioned on line 228, but not defined -- Looks like a reference, but probably isn't: '0' on line 353 -- Looks like a reference, but probably isn't: '8' on line 306 -- Looks like a reference, but probably isn't: '255' on line 269 -- Looks like a reference, but probably isn't: '1' on line 339 == Missing Reference: 'M-1' is mentioned on line 340, but not defined Summary: 1 error (**), 0 flaws (~~), 5 warnings (==), 6 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Network Working Group D. McGrew 3 Internet-Draft Cisco Systems, Inc. 4 Intended status: Informational P. Patnala 5 Expires: September 4, 2010 Consultant 6 A. Hoenes 7 TR-Sys 8 March 3, 2010 10 Threshold Secret Sharing 11 draft-mcgrew-tss-03.txt 13 Abstract 15 Threshold Secret Sharing (TSS) provides a way to generate N shares 16 from a value, so that any M of those shares can be used to 17 reconstruct the original value, but any M-1 shares provide no 18 information about that value. This method can provide shared access 19 control on key material and other secrets that must be strongly 20 protected. 22 This note defines a threshold secret sharing method based on 23 polynomial interpolation in GF(256) and a format for the storage and 24 transmission of shares. It also provides usage guidance, describes 25 how to test an implementation, and supplies test cases. 27 Status of this Memo 29 This Internet-Draft is submitted to IETF in full conformance with the 30 provisions of BCP 78 and BCP 79. 32 Internet-Drafts are working documents of the Internet Engineering 33 Task Force (IETF), its areas, and its working groups. Note that 34 other groups may also distribute working documents as Internet- 35 Drafts. 37 Internet-Drafts are draft documents valid for a maximum of six months 38 and may be updated, replaced, or obsoleted by other documents at any 39 time. It is inappropriate to use Internet-Drafts as reference 40 material or to cite them other than as "work in progress." 42 The list of current Internet-Drafts can be accessed at 43 http://www.ietf.org/ietf/1id-abstracts.txt. 45 The list of Internet-Draft Shadow Directories can be accessed at 46 http://www.ietf.org/shadow.html. 48 This Internet-Draft will expire on September 4, 2010. 50 Copyright Notice 52 Copyright (c) 2010 IETF Trust and the persons identified as the 53 document authors. All rights reserved. 55 This document is subject to BCP 78 and the IETF Trust's Legal 56 Provisions Relating to IETF Documents 57 (http://trustee.ietf.org/license-info) in effect on the date of 58 publication of this document. Please review these documents 59 carefully, as they describe your rights and restrictions with respect 60 to this document. Code Components extracted from this document must 61 include Simplified BSD License text as described in Section 4.e of 62 the Trust Legal Provisions and are provided without warranty as 63 described in the BSD License. 65 Table of Contents 67 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 68 1.1. Conventions Used In This Document . . . . . . . . . . . . 3 69 2. Operations . . . . . . . . . . . . . . . . . . . . . . . . . . 4 70 2.1. Create Shares . . . . . . . . . . . . . . . . . . . . . . 4 71 2.2. Reconstruct Secret . . . . . . . . . . . . . . . . . . . . 4 72 3. Polynomial Interpolation over GF(256) . . . . . . . . . . . . 5 73 3.1. Field Representation . . . . . . . . . . . . . . . . . . . 5 74 3.2. Share Generation . . . . . . . . . . . . . . . . . . . . . 7 75 3.3. Secret Reconstruction . . . . . . . . . . . . . . . . . . 8 76 4. Robust Threshold Secret Sharing . . . . . . . . . . . . . . . 10 77 4.1. RTSS Data Format . . . . . . . . . . . . . . . . . . . . . 10 78 5. Error Correction and Data Recovery . . . . . . . . . . . . . . 13 79 5.1. Data Recovery . . . . . . . . . . . . . . . . . . . . . . 13 80 5.2. Error Correction . . . . . . . . . . . . . . . . . . . . . 13 81 5.3. A Repetition Code . . . . . . . . . . . . . . . . . . . . 15 82 6. Format . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 83 7. Design and Rationale . . . . . . . . . . . . . . . . . . . . . 18 84 8. Testing . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 85 9. Test Cases . . . . . . . . . . . . . . . . . . . . . . . . . . 20 86 10. Security Considerations . . . . . . . . . . . . . . . . . . . 21 87 11. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 22 88 12. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 23 89 13. References . . . . . . . . . . . . . . . . . . . . . . . . . . 24 90 13.1. Normative References . . . . . . . . . . . . . . . . . . . 24 91 13.2. Informative References . . . . . . . . . . . . . . . . . . 24 92 Appendix A. Mathematical Background . . . . . . . . . . . . . . . 25 93 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 26 95 1. Introduction 97 Threshold secret sharing (TSS) provides a way to generate N shares 98 from a value, so that any M of those shares can be used to 99 reconstruct the original value, but any M-1 shares provide no 100 information about that value. This method does not rely on any 101 assumptions about the complexity of solving a particular 102 computational problem (such as factoring); it is information- 103 theoretically secure. Each share is slightly longer than the 104 original secret. 106 In the context of secret sharing, the word "share" means a part of 107 something, and "sharing" means the act of breaking up into parts. 108 Readers may be confused if they think of "sharing" as meaning "giving 109 to or possessing with others". 111 TSS is especially useful whenever there is a need to ensure the 112 availability of a secret, yet there is a simultaneous need to reduce 113 the risk of compromise of the secret. By dividing the secret into 114 multiple shares, and distributing each share to a different trusted 115 entity, TSS reduces that risk while providing for the availability of 116 the secret. At the time that the secret is divided into shares, the 117 threshold defining a number of shares that are needed to reconstruct 118 the secret is set. 120 TSS can be applied to any secret key, such as one used to encrypt 121 data at rest, or to any private key, such as the signing key used by 122 a certificate authority. It can be used to create a "backup" copy of 123 a key, to protect against the loss or corruption of an "active" copy 124 of the key. Alternatively, TSS can be applied to a key, and then the 125 original key can be deleted, as a means of enforcing shared access 126 control on that key. 128 1.1. Conventions Used In This Document 130 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 131 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 132 document are to be interpreted as described in [RFC2119]. 134 2. Operations 136 A threshold secret sharing system provides two operations: one that 137 creates a set of shares given a secret, and one that reconstructs the 138 secret, given a set of shares. This section defines the inputs and 139 outputs of these operations. The following sections describe the 140 details of TSS based on a polynomial interpolation in GF(256). 142 2.1. Create Shares 144 This operation takes an octet string S, whose length is L octets, and 145 a threshold parameter M, and generates a set of N shares, any M of 146 which can be used to reconstruct the secret. 148 The secret S is treated as an unstructured sequence of octets. It is 149 not expected to be null-terminated. The number of octets in the 150 secret may be anywhere from zero up to 65,534 (that is, two less than 151 2^16). 153 The threshold parameter M is the number of shares that will be needed 154 to reconstruct the secret. This value may be any number between one 155 and 255, inclusive. 157 The number of shares N that will be generated MUST be between the 158 threshold value M and 255, inclusive. The upper limit is particular 159 to the TSS algorithm specified in this document. 161 If the operation can not be completed successfully, then an error 162 code should be returned. 164 2.2. Reconstruct Secret 166 The reconstruct operation reconstructs the secret from a set of 167 shares. 169 The number of shares N must be provided as a parameter. 171 The only other parameter is the list of shares themselves. The 172 shares should be treated as unstructured octet strings. 174 If the operation could be completed successfully, then the secret 175 value will be returned. 177 If the operation can not be completed successfully, then an error 178 code should be returned. 180 3. Polynomial Interpolation over GF(256) 182 A finite field is a set of elements with associated addition, 183 multiplication, subtraction, and division operations. Each of those 184 operations acts on elements in the field, and returns an element in 185 the field. This specification uses the field GF(256), and each 186 element is represented as a single octet. There are many possible 187 ways to represent a finite field; below we define the field 188 arithmetic operations as having inputs and outputs that are octets. 189 This fixes a particular representation, without explicitly defining 190 it, and it avoids the issue of the bit-representation of octets. In 191 this representation, the zero field element is the zero octet, and 192 the unity field element is 0x01 (hexadecimal). 194 3.1. Field Representation 196 Each element of the field GF(256) is represented as an octet. In the 197 following, each octet is represented as a hexadecimal number with a 198 leading "0x", as in ANSI/ISO C. The representation of the finite 199 field that we use is defined in terms of the addition, subtraction, 200 multiplication, and division operations. We define these operations 201 as taking two octets as input and returning a single octet as output. 202 In order to distinguish GF(256) arithmetic from integer arithmetic, 203 we denote addition and multiplication in GF(256) as (+) and (*), 204 respectively. We also refer to the summation and product operations 205 in GF(256) as GF_SUM and GF_PRODUCT, respectively. 207 The multiplication in GF(256) and its inverse operation (division) 208 are defined in terms of two tables, the EXP table (Figure 1) and the 209 LOG table (Figure 2), which define the exponential function and the 210 logarithmic function, respectively. The ith elements of these tables 211 are denoted as EXP[i] and LOG[i]. LOG takes a non-zero field element 212 as input, and returns an integer, and EXP takes an integer and 213 returns a field element. 215 The addition operation returns the bitwise exclusive-or of its 216 operands. The subtraction operation is identical, because the field 217 has characteristic two. 219 The multiplication operation takes two elements X and Y as input and 220 proceeds as follows. If either X or Y is equal to 0x00, then the 221 operation returns 0x00. Otherwise, the value EXP[ (LOG[X] + LOG[Y]) 222 modulo 255] is returned. 224 The division operation takes a dividend X and a divisor Y as input 225 and computes X divided by Y as follows. If X is equal to 0x00, then 226 the operation returns 0x00. If Y is equal to 0x00, then the input is 227 invalid, and an error condition occurs. Otherwise, the value EXP[ 228 (LOG[X] - LOG[Y]) modulo 255] is returned. 230 The operation of raising a field element X to a power i, where i is a 231 positive integer, is denoted as X^i, and it consists of multiplying X 232 by itself i times. 234 0x01, 0x03, 0x05, 0x0f, 0x11, 0x33, 0x55, 0xff, 235 0x1a, 0x2e, 0x72, 0x96, 0xa1, 0xf8, 0x13, 0x35, 236 0x5f, 0xe1, 0x38, 0x48, 0xd8, 0x73, 0x95, 0xa4, 237 0xf7, 0x02, 0x06, 0x0a, 0x1e, 0x22, 0x66, 0xaa, 238 0xe5, 0x34, 0x5c, 0xe4, 0x37, 0x59, 0xeb, 0x26, 239 0x6a, 0xbe, 0xd9, 0x70, 0x90, 0xab, 0xe6, 0x31, 240 0x53, 0xf5, 0x04, 0x0c, 0x14, 0x3c, 0x44, 0xcc, 241 0x4f, 0xd1, 0x68, 0xb8, 0xd3, 0x6e, 0xb2, 0xcd, 242 0x4c, 0xd4, 0x67, 0xa9, 0xe0, 0x3b, 0x4d, 0xd7, 243 0x62, 0xa6, 0xf1, 0x08, 0x18, 0x28, 0x78, 0x88, 244 0x83, 0x9e, 0xb9, 0xd0, 0x6b, 0xbd, 0xdc, 0x7f, 245 0x81, 0x98, 0xb3, 0xce, 0x49, 0xdb, 0x76, 0x9a, 246 0xb5, 0xc4, 0x57, 0xf9, 0x10, 0x30, 0x50, 0xf0, 247 0x0b, 0x1d, 0x27, 0x69, 0xbb, 0xd6, 0x61, 0xa3, 248 0xfe, 0x19, 0x2b, 0x7d, 0x87, 0x92, 0xad, 0xec, 249 0x2f, 0x71, 0x93, 0xae, 0xe9, 0x20, 0x60, 0xa0, 250 0xfb, 0x16, 0x3a, 0x4e, 0xd2, 0x6d, 0xb7, 0xc2, 251 0x5d, 0xe7, 0x32, 0x56, 0xfa, 0x15, 0x3f, 0x41, 252 0xc3, 0x5e, 0xe2, 0x3d, 0x47, 0xc9, 0x40, 0xc0, 253 0x5b, 0xed, 0x2c, 0x74, 0x9c, 0xbf, 0xda, 0x75, 254 0x9f, 0xba, 0xd5, 0x64, 0xac, 0xef, 0x2a, 0x7e, 255 0x82, 0x9d, 0xbc, 0xdf, 0x7a, 0x8e, 0x89, 0x80, 256 0x9b, 0xb6, 0xc1, 0x58, 0xe8, 0x23, 0x65, 0xaf, 257 0xea, 0x25, 0x6f, 0xb1, 0xc8, 0x43, 0xc5, 0x54, 258 0xfc, 0x1f, 0x21, 0x63, 0xa5, 0xf4, 0x07, 0x09, 259 0x1b, 0x2d, 0x77, 0x99, 0xb0, 0xcb, 0x46, 0xca, 260 0x45, 0xcf, 0x4a, 0xde, 0x79, 0x8b, 0x86, 0x91, 261 0xa8, 0xe3, 0x3e, 0x42, 0xc6, 0x51, 0xf3, 0x0e, 262 0x12, 0x36, 0x5a, 0xee, 0x29, 0x7b, 0x8d, 0x8c, 263 0x8f, 0x8a, 0x85, 0x94, 0xa7, 0xf2, 0x0d, 0x17, 264 0x39, 0x4b, 0xdd, 0x7c, 0x84, 0x97, 0xa2, 0xfd, 265 0x1c, 0x24, 0x6c, 0xb4, 0xc7, 0x52, 0xf6, 0x00 267 Figure 1: The EXP table. The elements are to be read from top to 268 bottom and left to right. For example, EXP[0] is 0x01, EXP[8] is 269 0x1a, and so on. Note that the EXP[255] entry is present only as a 270 placeholder, and is not actually used in any computation. 272 0, 0, 25, 1, 50, 2, 26, 198, 273 75, 199, 27, 104, 51, 238, 223, 3, 274 100, 4, 224, 14, 52, 141, 129, 239, 275 76, 113, 8, 200, 248, 105, 28, 193, 276 125, 194, 29, 181, 249, 185, 39, 106, 277 77, 228, 166, 114, 154, 201, 9, 120, 278 101, 47, 138, 5, 33, 15, 225, 36, 279 18, 240, 130, 69, 53, 147, 218, 142, 280 150, 143, 219, 189, 54, 208, 206, 148, 281 19, 92, 210, 241, 64, 70, 131, 56, 282 102, 221, 253, 48, 191, 6, 139, 98, 283 179, 37, 226, 152, 34, 136, 145, 16, 284 126, 110, 72, 195, 163, 182, 30, 66, 285 58, 107, 40, 84, 250, 133, 61, 186, 286 43, 121, 10, 21, 155, 159, 94, 202, 287 78, 212, 172, 229, 243, 115, 167, 87, 288 175, 88, 168, 80, 244, 234, 214, 116, 289 79, 174, 233, 213, 231, 230, 173, 232, 290 44, 215, 117, 122, 235, 22, 11, 245, 291 89, 203, 95, 176, 156, 169, 81, 160, 292 127, 12, 246, 111, 23, 196, 73, 236, 293 216, 67, 31, 45, 164, 118, 123, 183, 294 204, 187, 62, 90, 251, 96, 177, 134, 295 59, 82, 161, 108, 170, 85, 41, 157, 296 151, 178, 135, 144, 97, 190, 220, 252, 297 188, 149, 207, 205, 55, 63, 91, 209, 298 83, 57, 132, 60, 65, 162, 109, 71, 299 20, 42, 158, 93, 86, 242, 211, 171, 300 68, 17, 146, 217, 35, 32, 46, 137, 301 180, 124, 184, 38, 119, 153, 227, 165, 302 103, 74, 237, 222, 197, 49, 254, 24, 303 13, 99, 140, 128, 192, 247, 112, 7 305 Figure 2: The LOG table. The elements are to be read from top to 306 bottom and left to right. For example, LOG[1] is 0, LOG[8] is 75, 307 and so on. Note that the LOG[0] entry is present only as a 308 placeholder, and is not actually used in any computation. 310 3.2. Share Generation 312 We first define how to share a single octet. 314 The function f takes as input a single octet X that is not equal to 315 0x00, and an array A of M octets, and returns a single octet. It is 316 defined as 318 f(X, A) = GF_SUM A[i] (*) X^i 319 i=0,M-1 321 Because the GF_SUM summation takes place over GF(256), each addition 322 uses the exclusive-or operation, and not integer addition. Note that 323 the successive values of X^i used in the computation of the function 324 f can be computed by multiplying a value by X once for each term in 325 the summation. 327 To create N shares from a secret, with a threshold of M, the 328 following procedure, or any equivalent method, is used: 330 For each share, a distinct Share Index is generated. Each Share 331 Index is an octet other than the all-zero octet. All of the Share 332 Indexes used during a share generation process MUST be distinct. 334 Each share is initialized to the Share Index associated with that 335 share. 337 For each octet of the secret, the following steps are performed. 338 An array A of M octets is created, in which the array element A[0] 339 contains the octet of the secret, and the array elements A[1], 340 ..., A[M-1] contain octets that are selected independently and 341 uniformly at random. For each share, the value of f(X,A) is 342 computed, where X is the Share Index of the share, and the 343 resulting octet is appended to the share. 345 After the procedure is done, each share contains one more octet than 346 does the secret. The share format can be illustrated as 348 +---------+---------+---------+---------+---------+ 349 | X | f(X,A) | f(X,B) | f(X,C) | ... | 350 +---------+---------+---------+---------+---------+ 352 where X is the Share Index of the share, and A, B, and C are arrays 353 of M octets; A[0] is equal to the first octet of the secret, B[0] is 354 equal to the second octet of the secret, and so on. 356 3.3. Secret Reconstruction 358 We define the function L_i (for i from 0 to M-1, inclusive) that 359 takes as input an array U of M pairwise distinct octets, and is 360 defined as 362 U[j] 363 L_i(U) = GF_PRODUCT ------------- 364 j=0,M-1, j!=i U[j] (+) U[i] 366 Here the product runs over all of the values of j from 0 to M-1, 367 excluding the value i. (This function is equal to ith Lagrange 368 function, evaluated at zero.) Note that the denominator in the above 369 expression is never equal to zero because U[i] is not equal to U[j] 370 whenever i is not equal to j. 372 We denote the interpolation function as I. This function takes as 373 input two arrays U and V, each consisting of M octets, and returns a 374 single octet; it is defined as 376 I(U, V) = GF_SUM L_i(U) (*) V[i]. 377 i=0,M-1 379 To reconstruct a secret from a set of shares, the following 380 procedure, or any equivalent method, is used: 382 If the number of shares provided as input to the secret 383 reconstruction operation is greater than the threshold M, then M 384 of those shares are selected for use in the operation. The method 385 used to select the shares can be arbitrary. 387 If the shares are not equal length, then the input is 388 inconsistent. An error should be reported, and processing must 389 halt. 391 The output string is initialized to the empty (zero-length) octet 392 string. 394 The octet array U is formed by setting U[i] equal to the first 395 octet of the ith share. (Note that the ordering of the shares is 396 arbitrary, but must be consistent throughout this algorithm.) 398 The initial octet is stripped from each share. 400 If any two elements of the array U have the same value, then an 401 error condition has occurred; this fact should be reported, then 402 the procedure must halt. 404 For each octet of the shares, the following steps are performed. 405 An array V of M octets is created, in which the array element V[i] 406 contains the octet from the ith share. The value of I(U, V) is 407 computed, then appended to the output string. 409 The output string is returned. 411 After the procedure is done, the string that is returned contains one 412 fewer octet than do the shares. 414 4. Robust Threshold Secret Sharing 416 A robust TSS system, or RTSS, is one that provides security even when 417 one or more of the shares that are provided to the reconstruction 418 algorithm may be crafted by a malicious adversary. In addition, an 419 RTSS system will detect unintentional corruption of the shares. 421 We provide robustness by adding a pre-processing step to the TSS 422 share generation step, and a post-processing step to the TSS secret 423 reconstruction step. The pre-processing consists of taking the 424 secret S, then appending a hash H(S) to it. The post-processing step 425 consists of verifying that the reconstructed secret has the form S || 426 H(S), where the symbol || denotes the concatenation operation. The 427 hash function must be collision-resistant; all RTSS implementations 428 MUST support the SHA-256 hash algorithm [SHS]. 430 If the robust reconstruction operation fails, and the number of 431 shares that are available is greater than the threshold, then the 432 operation MAY be tried on a different set of shares. 434 An RTSS system can perform an additional operation that verifies the 435 validity of a set of shares. This operation has the same inputs as 436 the Reconstruct operation. Its output consists of an indication 437 whether or not the secret could be reconstructed, but the secret 438 itself is not returned. This operation may be useful in a situation 439 in where the availability of a secret must be verified, for example, 440 as part of an audit. 442 4.1. RTSS Data Format 444 We use a data format with the following fields, in order: 446 Identifier. This field contains 16 octets. It identifies the secret 447 with which a share is associated. All of the shares associated 448 with a particular secret MUST use the same value Identifier. When 449 a secret is reconstructed, the Identifier fields of each of the 450 shares used as input MUST have the same value. The value of the 451 Identifier should be chosen so that it is unique, but the details 452 on how it is chosen are out of scope of this document. 454 Hash Algorithm Identifier. This field contains a single octet that 455 indicates the hash function used in the RTSS processing, if any. 456 A value of zero indicates that no hash algorithm was used, no hash 457 was appended to the secret, and no RTSS check should be performed 458 after the reconstruction of the secret. Other values are defined 459 in the table below. 461 Threshold. This field contains a single octet that indicates the 462 number of shares required to reconstruct the secret. This field 463 MUST be checked during the reconstruction process, and that 464 process MUST halt and return an error if the number of shares 465 available is fewer than the value indicated in this field. 467 Share Length. This field is two octets long. It contains the number 468 of octets in the Share Data field, represented as an unsigned 469 integer in network byte order. 471 Share Data. This field has a length that is a variable number of 472 octets. It contains the actual share data. 474 This format is illustrated in Figure 3. 476 0 1 2 3 477 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 478 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 479 | | 480 | Identifier | 481 | | 482 | | 483 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 484 | Hash Alg. Id. | Threshold | Share Length | 485 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 486 : : 487 : Share Data : 488 : : 489 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 491 Figure 3: Share Format. 493 The correspondence between the Hash Algorithm Identifier field and 494 the hash algorithm used in RTSS is defined by the table below. Each 495 hash function outputs a fixed number of octets; the length of the 496 output of each hash is indicated in the table. 498 +-----------------+---------------------------+-----------------+ 499 | Hash Algorithm | Hash Algorithm Identifier | Length (octets) | 500 +-----------------+---------------------------+-----------------+ 501 | NULL_HASH | 0 | 0 | 502 | | | | 503 | SHA-1 [SHS] | 1 | 20 | 504 | | | | 505 | SHA-256 [SHS] | 2 | 32 | 506 | | | | 507 | RESERVED | 3-127 | not applicable | 508 | | | | 509 | Vendor specific | 128-255 | not applicable | 510 +-----------------+---------------------------+-----------------+ 512 5. Error Correction and Data Recovery 514 TSS and RTSS are suitable for the protection of long-term key 515 material. In such applications, it is highly desirable to provide 516 protection against the accidental corruption of the shares. This 517 section defines data formats that can be used to protect shares. 518 These formats are optional extensions to the basic TSS and RTSS 519 systems. 521 5.1. Data Recovery 523 To protect against the corruption of the filesystem that is holding 524 the shares, a "magic number" can be used as the initial part of the 525 share data format [FILESIG]. A magic number is a constant data 526 string that is chosen arbitrarily, but which is unlikely to appear in 527 other contexts, and thus can be used to recognize a data format when 528 it appears in an arbitrary data stream. The use of a magic number in 529 the data format for a share greatly simplifies the task of finding a 530 share after a filesystem has been corrupted. 532 The 8-octet magic number f628f91b52023d11 (hexadecimal) SHOULD be 533 used. The number was selected randomly from a uniform distribution. 535 5.2. Error Correction 537 To protect against data corruption in the underlying media, an error- 538 correcting code (ECC) can be used. An ECC system consists of an 539 encoding function, which maps the data to a codeword, and a decoding 540 function, which maps a (possibly corrupted) codeword to the data. 541 The simplest such code is a repetition code, in which multiple copies 542 of the data are stored. In this specification, all ECCs must be 543 systematic, that is, the data must appear as the initial bytes of the 544 codeword. This property allows an implementation of the ECC to avoid 545 the implementation of the full decoding algorithm. 547 We use a data format that incorporates the following fields, in 548 order: 550 Encoding Type. This field is four octets long. It contains an 551 unsigned integer in network byte order that denotes the type of 552 the encoding, i.e. the algorithm that was used during the encoding 553 process. 555 Data Length. This field is four octets long. It contains an 556 unsigned integer in network byte order that denotes the number of 557 octets in the Data field. 559 Redundancy Length. This field is four octets long. It contains an 560 unsigned integer in network byte order that denotes the number of 561 octets in the Redundancy field. 563 Data. This field has a length that is a variable number of octets, 564 which is indicated by the Data Length field. It contains the data 565 that is intended to be conveyed by the code. If no data 566 corruption has occurred, then this field will contain the data 567 that was originally encoded. 569 Redundancy. This field has a length that is a variable number of 570 octets, which is indicated by the Redundancy Length field. It 571 contains information that can be used to check whether or not 572 there are any errors in the Data field, and to correct some errors 573 that may have occurred. 575 This format is illustrated in Figure 4. 577 +--------------------------------+ 578 | Encoding Type | 579 | (4 octets) | 580 +--------------------------------+ 581 | Data Length | 582 | (4 octets) | 583 +--------------------------------+ 584 | Redundancy Length | 585 | (4 octets) | 586 +--------------------------------+ 587 | | 588 ~ Data ~ 589 | (variable number of octets) | 590 | | 591 +--------------------------------+ 592 | | 593 ~ Redundancy ~ 594 | (variable number of octets) | 595 | | 596 +--------------------------------+ 598 Figure 4: Error Correction Format. 600 If a code has a free parameter, the value of that parameter MUST be 601 inferable from the values of the Data Length and Redundancy Length 602 fields. 604 5.3. A Repetition Code 606 This section defines a format for a repetition code, which is a 607 particular error correcting code that is conceptually simple and easy 608 to implement. 610 The value of the Encoding Type field is equal to 0000001 611 (hexadecimal). 613 The Redundancy field contains R copies of the Data field, where R is 614 an even number. The Redundancy Length is equal to the Data Length 615 times R. The value of R MAY be equal to zero, in which case no error 616 detection or correction is possible (but implementation is simple). 617 The value of R SHOULD be at least two. 619 For example, if the data that is encoded is equal to 68656c6c6f 620 (hexadecimal), then the ECF data with R=2 would be 622 <- ET -><- DL -><- RL -><- Data -><--- Redundancy ---> 623 00000001000000050000000a68656c6c6f68656c6c6f68656c6c6f 625 To check the Data field for errors, that field should be compared 626 with each of its copies in the redundancy field. 628 The Repetition Code can be decoded by using majority-logic decoding. 629 Considering both the Data and Redundancy fields, there are R+1 630 (possibly corrupted) copies of the original data, where R+1 is an odd 631 number. The decoding process independently considers each octet of 632 the Data field, and the corresponding octets of the copies that 633 appear in the Redundancy field. That is, the ith octet of the Data, 634 plus octets i, L+i, 2L+i, ... , RL+i, are analyzed independent from 635 all other octets, where L is the value of the Data Length field. The 636 following algorithm is applied to these octets. The binary 637 representation of each octet is considered. For each bit in that 638 representation, if more of the copies have a "1" in that position 639 than have a "0" in that position, then that position is decoded to 640 the value "1"; otherwise, it is decoded to "0". This process is 641 repeated for all of the bit position. After all of the bits in the 642 octet have been decoded, the value of the ith octet in the output of 643 the decoding algorithm is computed, using the same binary 644 representation as before. 646 For example, if the data that was encoded in the previous example was 647 corrupted to the value 649 <- ET -><- DL -><- RL -><- Data -><--- Redundancy ---> 650 00000001000000050000000a68656c6c2f68656c6cef68656c6c6f 651 ** ** ** 653 then decoding would proceed as follows. The fifth octet of the Data 654 field is equal to 2f, while the fifth and tenth octets of the 655 Redundancy field are equal to ef and 6f, respectively. Using a bit 656 representation with the most significant bit on the left, the octets 657 and the "majority" octet are as follows: 659 hex binary 660 octet from Data 2f 00101111 661 octet from first copy ef 11101111 662 octet from second copy 6f 01101111 663 ---------------------------------------- 664 majority 6f 01101111 666 Thus the fifth octet in the output of the decoding algorithm will be 667 6f. 669 6. Format 671 This section summarizes the order of processing for when secret 672 sharing is performed using the facilities for robustness (RTSS), 673 error correction (ECC), and data recovery (Magic Number), and 674 clarifies the relationships between data formats. This processing 675 can be viewed as a layered model, as illustrated in Figure 5. (Note 676 that we have not adhered to a strictly layered model, for the sake of 677 simplicity, since the format defined by RTSS is used after the shares 678 are generated.) 680 When RTSS is used, it is applied to the secret before the sharing 681 operation (and is removed from the secret after the reconstruction 682 operation). The RTSS data format MUST be used. 684 When ECC is used, it is applied to the RTSS data after the sharing 685 operation, so that the ECC Data field contains the entire RTSS Data 686 Format. 688 When a Magic Number is used, it is added after the ECC formatting is 689 done, and it is prepended to the Error Correction Format. 691 Secret Secret 692 | ^ 693 v | 694 +------------------+ +------------------+ 695 | Append Hash | | Verify Hash | 696 +------------------+ +------------------+ 697 | | 698 +------------------+ +------------------+ 699 | Generate Shares | |Reconstruct Secret| 700 +------------------+ +------------------+ 701 | | 702 +------------------+ +------------------+ 703 | ECC Encoding | | ECC Decoding | 704 +------------------+ +------------------+ 705 | | 706 +------------------+ +------------------+ 707 | Add Magic Number | |Strip Magic Number| 708 +------------------+ +------------------+ 709 | ^ 710 v | 711 Shares ----------------> Shares 713 Figure 5: The combined processing model. 715 7. Design and Rationale 717 In this implementation, the secret and the shares are octet strings. 718 Each octet is treated as an element of the finite field GF(256). The 719 share-generation algorithm is applied to each octet of the secret 720 independently. Similarly, the octets are treated independently 721 during the reconstruction of the secrets from the shares. 723 Shamir's original description treats the secret as a large integer 724 modulo a large prime number [shamir]. The advantages of using a 725 vector over GF(256) are that the computations are more efficient and 726 the encoding is simpler. Multiplication and inversion over GF(256) 727 can be done with two table lookups and two exors, using two fixed 728 tables of 256 bytes each. One limitation of the GF(256) approach is 729 that the number of shares that can be generated cannot be greater 730 than 255; this limitation is unlikely to be important in practice, 731 since fewer than ten shares are typically used. 733 The reconstruction of the secret is done using Lagrange interpolation 734 polynomials. This method is simple and easily tested. For large 735 thresholds, this method is less efficient than an optimal method 736 would be. However, performance is still good, and it is expected 737 that the reconstruction of the secret will not be a performance- 738 critical operation. 740 8. Testing 742 As with every crypto algorithm, it is essential to test an 743 implementation of TSS or RTSS for correctness. This section provides 744 guidance for such testing. 746 The Secret Reconstruction algorithm can be tested using Known Answer 747 Tests (KATs). Test cases are provided in Section 9. 749 The Share Generation algorithm cannot be directly tested using a KAT. 750 It can be indirectly tested by generating secret values uniformly at 751 random, then applying the Share Generation process to them to 752 generate a set of shares, then applying the Share Reconstruction 753 algorithm to the shares, then finally comparing the reconstructed 754 secret to the original secret. Implementations SHOULD perform this 755 test, using a variety of thresholds and secret lengths. 757 The Share Index (the initial octet of each share) can never be equal 758 to zero. This property SHOULD be tested. 760 The random source must be tested to ensure that it has high min- 761 entropy. 763 9. Test Cases 765 This section provides test cases that can be used to validate an 766 implementation of the Secret Reconstruction algorithm. All values 767 are in hexadecimal. 769 algorithm - The algorithm used in the test case. 771 secret - The secret value to be split into shares. 773 threshold - The number of shares required to reconstruct a secret; 774 above, this value is associated with the variable M. 776 num. shares - The number of shares included in the example; above, 777 this value is associated with the variable N. 779 share index - A share index. Each test case has multiple distinct 780 share values, and each share is associated with a distinct share 781 index. 783 share - A share value, which corresponds to the share index value 784 immediately above it. 786 algorithm = TSS 787 secret = 7465737400 788 threshold (M) = 2 789 num. shares (N) = 2 790 share index = 1 791 share = B9FA07E185 792 share index = 2 793 share = F5409B4511 795 10. Security Considerations 797 It is crucial for security that the source of randomness used in the 798 share generation process by cryptographically strong; it MUST be 799 suitable for generating cryptographic keys. [RFC4086] provides 800 guidance on the selection and implementation of random sources. 802 A TSS implementation SHOULD be tested as described in Section 8. 804 The confidentiality of the shares generated by TSS should be 805 protected, since the exposure of too many shares will undermine the 806 security of the system. Note that, in this regard, share values are 807 more comparable to secret keys than to ciphertext. 809 11. IANA Considerations 811 This document has no actions for IANA. 813 12. Acknowledgements 815 Thanks to Brian Weis and Jack Lloyd for constructive feedback. 817 13. References 819 13.1. Normative References 821 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 822 Requirement Levels", BCP 14, RFC 2119, March 1997. 824 [RFC4086] Eastlake, D., Schiller, J., and S. Crocker, "Randomness 825 Requirements for Security", BCP 106, RFC 4086, June 2005. 827 [SHS] "FIPS 180-3: Secure Hash Standard,", Federal Information 828 Processing Standard (FIPS) http://csrc.nist.gov/ 829 publications/fips/fips180-2/fips180-3.pdf, 2008. 831 13.2. Informative References 833 [FILESIG] Kessler, G., "File Signatures Table", Web 834 page http://www.garykessler.net/library/file_sigs.html, 835 2007. 837 [POLY] Seroussi, G., "Table of Low-Weight Binary Irreducible 838 Polynomials", Hewlett-Packard Computer Systems Laboratory 839 Technical Report HPL-98-135, 1998. 841 [shamir] Shamir, A., "How to share a secret", Communications of the 842 ACM (22): 612-613, 1979. 844 Appendix A. Mathematical Background 846 In abstract algebra, a finite field is an algebraic structure for 847 which the operations of addition, subtraction, multiplication and 848 division are defined and satisfy certain axioms. 850 The field GF(256) has exactly 256 elements in it. There is only one 851 field with that number of elements, but there are many different ways 852 in which the elements of the field can be represented. This document 853 uses a polynomial representation in which the field polynomial is the 854 unique irreducible polynomial with minimum weight of degree 8 over 855 GF(2) [POLY], hence it is the 'canonical' choice for a polynomial 856 base representation of GF(256). This field representation is also 857 used by the Advanced Encryption Standard (AES). 859 Authors' Addresses 861 David A. McGrew 862 Cisco Systems, Inc. 863 510 McCarthy Blvd. 864 Milpitas, CA 95035 865 US 867 Email: mcgrew@cisco.com 868 URI: http://www.mindspring.com/~dmcgrew/dam.htm 870 Praveen Patnala 871 Consultant 873 Email: praveenpatnala@yahoo.com 875 Alfred Hoenes 876 TR-Sys 877 Gerlinger Str. 12 878 Ditzingen D-71254 879 Germany 881 Email: ah@TR-Sys.de