Commit | Line | Data |
---|---|---|
3f98ee81 MW |
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). |