| 1 | '\" e |
| 2 | .\" -*-nroff-*- |
| 3 | .ie t \{\ |
| 4 | . ds o \(bu |
| 5 | . if \n(.g .fam P |
| 6 | .\} |
| 7 | .el \{\ |
| 8 | . ds o o |
| 9 | . ie '\*(.T'utf8' .ds mo ∈ |
| 10 | . el .ds mo \fBin\fP |
| 11 | . ie '\*(.T'utf8' .ds *l \(*l |
| 12 | . el .ds *l L |
| 13 | .\} |
| 14 | .de hP |
| 15 | .IP |
| 16 | \h'-\w'\fB\\$1\ \fP'u'\fB\\$1\ \fP\c |
| 17 | .. |
| 18 | .de VS |
| 19 | .sp 1 |
| 20 | .RS |
| 21 | .nf |
| 22 | .ft B |
| 23 | .. |
| 24 | .de VE |
| 25 | .ft R |
| 26 | .fi |
| 27 | .RE |
| 28 | .sp 1 |
| 29 | .. |
| 30 | .ds pr $ |
| 31 | .EQ |
| 32 | delim $$ |
| 33 | tdefine member 'type "relation" \(mo' |
| 34 | define lbrace 'roman "{"' |
| 35 | define rbrace 'roman "}"' |
| 36 | define FIELD 'bold F' |
| 37 | .EN |
| 38 | .TH shamir 1 "3 May 2015" "distorted.org.uk key management" |
| 39 | .de EQ |
| 40 | .PP |
| 41 | .ce |
| 42 | .. |
| 43 | .de EN |
| 44 | .PP |
| 45 | .. |
| 46 | .SH NAME |
| 47 | shamir \- split a secret into shares, and recombine them |
| 48 | .SH SYNOPSIS |
| 49 | .B shamir |
| 50 | .I command |
| 51 | .PP |
| 52 | where |
| 53 | .I command |
| 54 | is one of: |
| 55 | .PP |
| 56 | .B help |
| 57 | .IB [ command\fR... ] |
| 58 | .br |
| 59 | .B issue |
| 60 | .RB [ \-H |
| 61 | .IR hashfn ] |
| 62 | .IB thresh / count |
| 63 | .RI [ secret-file ] |
| 64 | .br |
| 65 | .B recover |
| 66 | .SH DESCRIPTION |
| 67 | The |
| 68 | .B shamir |
| 69 | program implements a simple secret sharing scheme. |
| 70 | Given a secret, |
| 71 | the |
| 72 | .B issue |
| 73 | command will split it |
| 74 | into a number of shares |
| 75 | .IR n, |
| 76 | any |
| 77 | .ie t $t <= n$ |
| 78 | .el \{\ |
| 79 | .I t |
| 80 | \(<= |
| 81 | .I n |
| 82 | .\} |
| 83 | of which |
| 84 | can be used to reconstruct it, but |
| 85 | fewer than |
| 86 | .I t |
| 87 | shares provide no information at all |
| 88 | about the secret |
| 89 | (other than its length). |
| 90 | .SH COMMAND-LINE OPTIONS |
| 91 | The following options are recognized. |
| 92 | .TP |
| 93 | .B \-h, \-\-help |
| 94 | Print an overview |
| 95 | of the options and commands |
| 96 | to standard output |
| 97 | and exit successfully. |
| 98 | .TP |
| 99 | .B \-\-version |
| 100 | Print the version number |
| 101 | of the |
| 102 | .B distorted-keys |
| 103 | package |
| 104 | to standard output |
| 105 | and exit successfully. |
| 106 | .SH COMMAND REFERENCE |
| 107 | .SS help |
| 108 | The |
| 109 | .B help |
| 110 | command prints information to standard output |
| 111 | about the |
| 112 | .B shamir |
| 113 | program as a whole |
| 114 | (similar to the |
| 115 | .B \-\-help |
| 116 | option), |
| 117 | or about the named |
| 118 | .IR command s. |
| 119 | .SS issue |
| 120 | The |
| 121 | .B issue |
| 122 | command reads a secret from |
| 123 | .I secret-file |
| 124 | (or from standard input, |
| 125 | if |
| 126 | .I secret-file |
| 127 | is omitted or |
| 128 | .RB ` \- '), |
| 129 | and writes a number of lines to standard output. |
| 130 | .PP |
| 131 | The |
| 132 | .I count |
| 133 | is the total number of shares issued; |
| 134 | any |
| 135 | .I thresh |
| 136 | of them can be used to reassemble the original secret. |
| 137 | It must be the case that |
| 138 | .ie t $1 <= "thresh" <= "count" <= 255$. |
| 139 | .el \{\ |
| 140 | 1 |
| 141 | \(<= |
| 142 | .I thresh |
| 143 | \(<= |
| 144 | .I count |
| 145 | \(<= |
| 146 | 255. |
| 147 | .\} |
| 148 | .PP |
| 149 | The first line contains secret-sharing parameters, |
| 150 | which will be required in any recovery operation. |
| 151 | These do not usually need to be kept secret |
| 152 | (though they contain a cryptographic hash of the original input) |
| 153 | but it's a good idea to ensure their integrity. |
| 154 | This can be done by storing the parameters in a safe place, |
| 155 | possibly protected by a digital signature, |
| 156 | or by issuing each share holder with a copy of the parameters |
| 157 | and checking that they match at recovery time. |
| 158 | .PP |
| 159 | The remaining lines contain share data, one per line, for |
| 160 | .I count |
| 161 | lines. |
| 162 | Each share holder should be given one of these lines. |
| 163 | .PP |
| 164 | The following options are accepted. |
| 165 | .TP |
| 166 | .BI "\-H, \-\-hash-function=" hashfn |
| 167 | The hash function to use when hashing the secret. |
| 168 | This may be any hash function name known to OpenSSL. |
| 169 | .PP |
| 170 | Example: |
| 171 | .VS |
| 172 | \*(pr shamir issue 3/5 secret |
| 173 | .ft R |
| 174 | shamir-params:n=5;t=3;f=sha256;h=lbcQW/lmV4z0ZKORE5Y0/g+thgWFKr4Kv3i1vEfNkUQ= |
| 175 | shamir-share:i=0;y=Ft3jhDQgTdMgEJ3Og3+OZ98NTSRGEWFjIN6mAQmzvHc= |
| 176 | shamir-share:i=1;y=zHpbi0h+mFVVv0vAo0djMK296b5XRCAYRV6yMsy74Rs= |
| 177 | shamir-share:i=2;y=FbSHVSqoXLVbxkuVZweLXacXmqAnWMEgLOP3qlSvfPc= |
| 178 | shamir-share:i=3;y=Q0bUOCUfgSlZSFPOSwhr2YjCSfXKRjwRDmwK8PZPB48= |
| 179 | shamir-share:i=4;y=mogI5kfJRclXMVObj0iDtIJoOuu6Wt0pZ9FPaG5bmmM= |
| 180 | .VE |
| 181 | .SS recover |
| 182 | The |
| 183 | .B recover |
| 184 | command reads parameters and shares from standard input, |
| 185 | computes the original secret, |
| 186 | and writes it to standard output. |
| 187 | .PP |
| 188 | There are no command-line options. |
| 189 | .PP |
| 190 | The first line of standard input must contain the sharing parameters. |
| 191 | Subsequent lines contain shares, |
| 192 | one per line. |
| 193 | The shares may be in any order. |
| 194 | Exactly the correct |
| 195 | .RI ( thresh ) |
| 196 | number of shares must be provided. |
| 197 | The shares are checked for various kinds of errors |
| 198 | (e.g., duplicate shares, out-of-range indices), |
| 199 | and the secret is computed |
| 200 | and checked against the hash stored with the parameters. |
| 201 | If everything is correct, |
| 202 | the secret is written to standard output; |
| 203 | otherwise errors are reported to standard error, |
| 204 | and the program exits with a nonzero status |
| 205 | having written nothing to standard output. |
| 206 | .PP |
| 207 | Example: |
| 208 | .VS |
| 209 | \*(pr cat shares |
| 210 | .ft R |
| 211 | shamir-params:n=5;t=3;f=sha256;h=lbcQW/lmV4z0ZKORE5Y0/g+thgWFKr4Kv3i1vEfNkUQ= |
| 212 | shamir-share:i=2;y=FbSHVSqoXLVbxkuVZweLXacXmqAnWMEgLOP3qlSvfPc= |
| 213 | shamir-share:i=1;y=zHpbi0h+mFVVv0vAo0djMK296b5XRCAYRV6yMsy74Rs= |
| 214 | shamir-share:i=4;y=mogI5kfJRclXMVObj0iDtIJoOuu6Wt0pZ9FPaG5bmmM= |
| 215 | .ft B |
| 216 | \*(pr shamir recover <shares >secret2 |
| 217 | \*(pr cmp secret secret2 |
| 218 | .VE |
| 219 | .SH DATA FORMATS |
| 220 | The |
| 221 | .B shamir |
| 222 | program applies a simple encoding |
| 223 | to the various kinds of structured data it deals with, |
| 224 | specifically to |
| 225 | .IR secrets , |
| 226 | .IR parameters , |
| 227 | and |
| 228 | .IR shares . |
| 229 | .PP |
| 230 | An encoded object has the form |
| 231 | .IP |
| 232 | .IB label : \c |
| 233 | .IB slot = value \c |
| 234 | .RB [ ; ...] |
| 235 | .PP |
| 236 | Encodings do not contain whitespace characters. |
| 237 | .PP |
| 238 | The |
| 239 | .I label |
| 240 | is a token which identifies the kind of object encoded. |
| 241 | Each |
| 242 | .I slot |
| 243 | is named with a token |
| 244 | (usually a single letter), |
| 245 | and supplied with its |
| 246 | .I value |
| 247 | in a suitable encoding, |
| 248 | as described below. |
| 249 | .PP |
| 250 | The syntax is very picky. |
| 251 | The order of the slots is significant, |
| 252 | and all slots must be defined. |
| 253 | .SS Secets |
| 254 | A |
| 255 | .I secret |
| 256 | object describes a secret and its sharing parameters. |
| 257 | Secret objects are not input or output directly, |
| 258 | but are hashed when constructing parameters objects (described below). |
| 259 | .PP |
| 260 | The label for a secret object is |
| 261 | .BR shamir-secret . |
| 262 | Its slots are as follows. |
| 263 | .TP |
| 264 | .B n |
| 265 | The total number of shares issued, |
| 266 | i.e., the |
| 267 | .I count |
| 268 | argument to |
| 269 | .BR "shamir issue" , |
| 270 | as a decimal integer. |
| 271 | .TP |
| 272 | .B t |
| 273 | The threshold required for recovery, |
| 274 | i.e., the |
| 275 | .I thresh |
| 276 | argument to |
| 277 | .BR "shamir issue" , |
| 278 | as a decimal integer. |
| 279 | .TP |
| 280 | .B s |
| 281 | The secret itself, Base64-encoded, |
| 282 | with no whitespace. |
| 283 | .SS Parameters |
| 284 | A |
| 285 | .I parameters |
| 286 | object describes how a secret has been split into shares |
| 287 | and provides information about how it can be reassembled. |
| 288 | .PP |
| 289 | The label for a parameters object is |
| 290 | .BR shamir-params . |
| 291 | Its slots are as follows. |
| 292 | .TP |
| 293 | .B n |
| 294 | The total number of shares issued, |
| 295 | i.e., the |
| 296 | .I count |
| 297 | argument to |
| 298 | .BR "shamir issue" , |
| 299 | as a decimal integer. |
| 300 | .TP |
| 301 | .B t |
| 302 | The threshold required for recovery, |
| 303 | i.e., the |
| 304 | .I thresh |
| 305 | argument to |
| 306 | .BR "shamir issue" , |
| 307 | as a decimal integer. |
| 308 | .TP |
| 309 | .B f |
| 310 | The name of the hash function |
| 311 | used to compute the |
| 312 | .B h |
| 313 | slot. |
| 314 | This may be any of the hash functions known to OpenSSL. |
| 315 | .TP |
| 316 | .B h |
| 317 | The hash of a secret object, |
| 318 | made using the hash function named by the |
| 319 | .B f |
| 320 | slot, |
| 321 | and Base64 encoded. |
| 322 | No trailing newline is included when hashing the secret object. |
| 323 | .SS Shares |
| 324 | A |
| 325 | .I share |
| 326 | object describes a single share. |
| 327 | The label for a parameters object is |
| 328 | .BR shamir-share . |
| 329 | Its slots are as follows. |
| 330 | .TP |
| 331 | .B i |
| 332 | The share's index, |
| 333 | as a decimal integer; |
| 334 | .ie t $0 <= i < "count"$. |
| 335 | .el \{\ |
| 336 | 0 \(<= |
| 337 | .I i |
| 338 | < |
| 339 | .IR count . |
| 340 | .\} |
| 341 | .TP |
| 342 | .B y |
| 343 | The share data, Base64 encoded. |
| 344 | .PP |
| 345 | .SH MATHEMATICAL BACKGROUND |
| 346 | (This section has lots of mathematical notation |
| 347 | and doesn't look especially good in a terminal.) |
| 348 | .PP |
| 349 | Let |
| 350 | .I k |
| 351 | be a field. |
| 352 | Suppose we are given a secret |
| 353 | .ie t $s member k$ |
| 354 | .el \{\ |
| 355 | .I s |
| 356 | \*(mo |
| 357 | .I k |
| 358 | .\} |
| 359 | which we want to split into shares |
| 360 | such that any $t$ of them can be used to recover |
| 361 | .IR s . |
| 362 | Choose coefficients |
| 363 | .ie t $a sub i member k$ |
| 364 | .el \{\ |
| 365 | .IR a _ i |
| 366 | \*(mo |
| 367 | .I k |
| 368 | .\} |
| 369 | for |
| 370 | .ie t $1 <= i < t$ |
| 371 | .el \{\ |
| 372 | 1 \(<= |
| 373 | .I i |
| 374 | < |
| 375 | .I t |
| 376 | .\} |
| 377 | at random. |
| 378 | Let |
| 379 | .ie t $p(x) = s + a sub 1 x + ... + a sub {t-1} x sup {t-1}$. |
| 380 | .el \{\ |
| 381 | .IR p ( x ) |
| 382 | = |
| 383 | .I s |
| 384 | + |
| 385 | .IR a _1 |
| 386 | .I x |
| 387 | + ... + |
| 388 | .IR a _( t \-1) |
| 389 | .IR x ^( t \-1). |
| 390 | .\} |
| 391 | Note that |
| 392 | .ie t $p(0) = s$. |
| 393 | .el \{\ |
| 394 | .IR p (0) |
| 395 | = |
| 396 | .IR s . |
| 397 | .\} |
| 398 | We can evaluate |
| 399 | .I p |
| 400 | to obtain shares |
| 401 | .ie t $y sub i = p( x sub i )$ |
| 402 | .el \{\ |
| 403 | .IR y _ i |
| 404 | = |
| 405 | .IR p ( x _ i ) |
| 406 | .\} |
| 407 | for various |
| 408 | .ie t $x sub i member k - lbrace ~ 0 ~ rbrace$. |
| 409 | .el \{\ |
| 410 | .IR x _ i |
| 411 | \*(mo |
| 412 | .I k |
| 413 | \- |
| 414 | { 0 }. |
| 415 | .\} |
| 416 | .PP |
| 417 | How do we recover the secret? |
| 418 | Suppose we are given |
| 419 | .ie t $y sub i = p( x sub i )$ |
| 420 | .el \{\ |
| 421 | .IR y _ i |
| 422 | = |
| 423 | .IR p ( x _ i ) |
| 424 | .\} |
| 425 | for |
| 426 | .ie t $0 <= i < t$, |
| 427 | .el \{\ |
| 428 | 0 \(<= |
| 429 | .I i |
| 430 | < |
| 431 | .IR t . |
| 432 | .\} |
| 433 | where the |
| 434 | .ie t $x sub i$ |
| 435 | .el .IR x _ i |
| 436 | are distinct. |
| 437 | Define |
| 438 | .ie t \{\ |
| 439 | .EQ |
| 440 | lambda sub i (x) = |
| 441 | sum from {pile {0 <= j < t above j != i}} |
| 442 | {x - x sub j} over {x sub i - x sub j}. |
| 443 | .EN |
| 444 | .\} |
| 445 | .el \{\ |
| 446 | .IP |
| 447 | .nf |
| 448 | .\" --- x - x_j |
| 449 | .\" L_i(x) = > ---------. |
| 450 | .\" --- x_i - x_j |
| 451 | .\" 0<j<t |
| 452 | .\" j=i |
| 453 | --- \fIx\fP \- \fIx\fP_\fIj\fP |
| 454 | \*(*l_\fIi\fP(\fIx\fP) = > ---------. |
| 455 | --- \fIx\fP_\fIi\fP - \fIx\fP_\fIj\fP |
| 456 | 0\(<=\fIj\fP<\fIt\fP |
| 457 | \fIj\fP\(!=\fIi\fP |
| 458 | .fi |
| 459 | .PP |
| 460 | .\} |
| 461 | Then |
| 462 | .ie t $lambda sub i$ |
| 463 | .el .RI \*(*l_ i |
| 464 | is a |
| 465 | .ie t degree-$(t - 1)$ |
| 466 | .el \{\ |
| 467 | .RI degree-( t |
| 468 | \- 1) |
| 469 | .\} |
| 470 | polynomial |
| 471 | such that |
| 472 | .ie t $lambda sub i ( x sub i ) = 1$, |
| 473 | .el \{\ |
| 474 | .RI \*(*l_ i ( x _ i ) |
| 475 | = 1, |
| 476 | .\} |
| 477 | and |
| 478 | .ie t $lambda sub i ( x sub j ) = 0$ |
| 479 | .el \{\ |
| 480 | .RI \*(*l_ i ( x _ j ) |
| 481 | = 0 |
| 482 | .\} |
| 483 | if |
| 484 | .ie t $j != i$. |
| 485 | .el \{\ |
| 486 | .I j |
| 487 | \(!= |
| 488 | .IR i . |
| 489 | .\} |
| 490 | Define |
| 491 | .ie t \{\ |
| 492 | .EQ |
| 493 | q(x) = sum from {0 <= i < t} lambda sub i (x) y sub i . |
| 494 | .EN |
| 495 | .\} |
| 496 | .el \{\ |
| 497 | .IP |
| 498 | .nf |
| 499 | .\" --- |
| 500 | .\" q(x) = > L_i(x) y_i. |
| 501 | .\" --- |
| 502 | .\" 0<i<t |
| 503 | --- |
| 504 | \fIq\fP(\fIx\fP) = > \*(*l_\fIi\fP(\fIx\fP) \fIy\fP_\fIi\fP. |
| 505 | --- |
| 506 | 0\(<=\fIi\fP<\fIt\fP |
| 507 | .fi |
| 508 | .PP |
| 509 | .\} |
| 510 | Note that |
| 511 | .I q |
| 512 | has degree |
| 513 | .ie t $t - 1$, |
| 514 | .el \{\ |
| 515 | .I t |
| 516 | \- 1, |
| 517 | .\} |
| 518 | and |
| 519 | .ie t $q( x sub i ) = y sub i = p( x sub i )$ |
| 520 | .el \{\ |
| 521 | .IR q ( x _ i ) |
| 522 | = |
| 523 | .IR y _ i |
| 524 | = |
| 525 | .IR p ( x _ i ) |
| 526 | .\} |
| 527 | for all |
| 528 | .ie t $0 <= i < t$. |
| 529 | .el \{\ |
| 530 | 0 \(<= |
| 531 | .I i |
| 532 | < |
| 533 | .IR t . |
| 534 | .\} |
| 535 | Hence |
| 536 | .ie t $p - q$ |
| 537 | .el \{\ |
| 538 | .I p |
| 539 | \- |
| 540 | .I q |
| 541 | .\} |
| 542 | is a polynomial with degree at most |
| 543 | .ie t $t - 1$ |
| 544 | .el \{\ |
| 545 | .I t |
| 546 | \- 1 |
| 547 | .\} |
| 548 | but with at least |
| 549 | .I t |
| 550 | distinct zeros; |
| 551 | therefore |
| 552 | .ie t $q - p$ |
| 553 | .el \{\ |
| 554 | .I p |
| 555 | \- |
| 556 | .I q |
| 557 | .\} |
| 558 | must be identically zero |
| 559 | and hence |
| 560 | .ie t $q == p$ |
| 561 | .el \{\ |
| 562 | .I q |
| 563 | \(== |
| 564 | .I p |
| 565 | .\} |
| 566 | and |
| 567 | .ie t $s = q(0)$. |
| 568 | .el \{\ |
| 569 | .I s |
| 570 | = |
| 571 | .IR q (0). |
| 572 | .\} |
| 573 | .PP |
| 574 | Suppose we are given |
| 575 | .ie t $t - 1$ |
| 576 | .el \{\ |
| 577 | .I t |
| 578 | \- 1 |
| 579 | .\} |
| 580 | shares. |
| 581 | Then, |
| 582 | for any putative secret |
| 583 | .ie t $s'$, |
| 584 | .el .IR s ', |
| 585 | there exists a distinct possible value for each of the remaining shares |
| 586 | which can be determined using the above interpolation, |
| 587 | each of which is equally likely. |
| 588 | .PP |
| 589 | The polynomial interpolation technique is due to Lagrange; |
| 590 | its use as a secret-sharing scheme is due to Adi Shamir. |
| 591 | .PP |
| 592 | In theory, then, |
| 593 | this secret-sharing scheme is |
| 594 | .IR "information-theoretically secure" ; |
| 595 | in practice, |
| 596 | there's a cryptographic hash of the secret in the sharing parameters, |
| 597 | so security is limited to the computational difficulty |
| 598 | of inverting this hash. |
| 599 | Knowledge of fewer than |
| 600 | .I t |
| 601 | shares doesn't make this any easier; |
| 602 | and there's a security benefit to |
| 603 | knowing that a dishonest share holder |
| 604 | can't introduce errors into the recovered secret. |
| 605 | .PP |
| 606 | All of the above works in any field |
| 607 | .IR k . |
| 608 | Computation is easiest in a small finite field |
| 609 | (rather than, say, the rationals). |
| 610 | This program uses the field |
| 611 | .ie t $FIELD sub {2 sup 8}$ |
| 612 | .el GF(2^8) |
| 613 | represented as the quotient ring |
| 614 | .ie t $FIELD sub 2 [u]/( u sup 8 + u sup 4 + u sup 3 + u sup 2 + 1 )$. |
| 615 | .el \{\ |
| 616 | .RI GF(2)[ u ]/( u ^8 |
| 617 | + |
| 618 | .IR u ^4 |
| 619 | + |
| 620 | .IR u ^3 |
| 621 | + |
| 622 | .IR u ^2 |
| 623 | + |
| 624 | 1). |
| 625 | .\} |
| 626 | Hence, a field element fits exactly into a single byte: |
| 627 | specifically, the field element |
| 628 | .ie t $x = a sub 0 + a sub 1 u + ... + a sub 7 u sup 7$ |
| 629 | .el \{\ |
| 630 | .I x |
| 631 | = |
| 632 | .IR a _0 |
| 633 | + |
| 634 | .IR a _1 |
| 635 | .I u |
| 636 | + ... + |
| 637 | .IR a _7 |
| 638 | .IR u ^7 |
| 639 | .\} |
| 640 | corresponds to the byte |
| 641 | .ie t $B(x) = a sub 0 + 2 a sub 1 + ... + 2 sup 7 a sub 7$. |
| 642 | .el \{\ |
| 643 | .IR B ( x ) |
| 644 | = |
| 645 | .IR a _0 |
| 646 | + |
| 647 | 2 |
| 648 | .IR a _1 |
| 649 | + ... + |
| 650 | 2^7 |
| 651 | .IR a _7. |
| 652 | .\} |
| 653 | Secrets longer than a single byte are shared bytewise independently, |
| 654 | which is why the shares leak information about the secret size. |
| 655 | .PP |
| 656 | The program represents share indices as small integers |
| 657 | .ie t $0 <= i < n$; |
| 658 | .el \{\ |
| 659 | 0 \(<= |
| 660 | .I i |
| 661 | < |
| 662 | .IR n ; |
| 663 | .\} |
| 664 | specifically, the share with index |
| 665 | .I i |
| 666 | is generated by |
| 667 | evaluating the polynomial |
| 668 | .ie t $p(x)$ |
| 669 | .el .IR p ( x ) |
| 670 | where |
| 671 | .ie t $i = B(x) - 1$. |
| 672 | .el \{\ |
| 673 | .I i |
| 674 | = |
| 675 | .IR B ( x ) |
| 676 | \- 1. |
| 677 | .\} |
| 678 | .SH AUTHOR |
| 679 | Mark Wooding, <mdw@distorted.org.uk> |
| 680 | .SH SEE ALSO |
| 681 | .BR distorted-keys (7), |
| 682 | .BR dgst (1ssl). |