chiark - git - mdw - distorted-keys/blob - shamir.1

   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 .RI "1\~\(<= " thresh "\~\(<= " count "\~\(<= 255."
 140 .PP
 141 The first line contains secret-sharing parameters,
 142 which will be required in any recovery operation.
 143 These do not usually need to be kept secret
 144 (though they contain a cryptographic hash of the original input)
 145 but it's a good idea to ensure their integrity.
 146 This can be done by storing the parameters in a safe place,
 147 possibly protected by a digital signature,
 148 or by issuing each share holder with a copy of the parameters
 149 and checking that they match at recovery time.
 150 .PP
 151 The remaining lines contain share data, one per line, for
 152 .I count
 153 lines.
 154 Each share holder should be given one of these lines.
 155 .PP
 156 The following options are accepted.
 157 .TP
 158 .BI "\-H, \-\-hash-function=" hashfn
 159 The hash function to use when hashing the secret.
 160 This may be any hash function name known to OpenSSL.
 161 .PP
 162 Example:
 163 .VS
 164 \*(pr shamir issue 3/5 secret
 165 .ft R
 166 shamir-params:n=5;t=3;f=sha256;h=lbcQW/lmV4z0ZKORE5Y0/g+thgWFKr4Kv3i1vEfNkUQ=
 167 shamir-share:i=0;y=Ft3jhDQgTdMgEJ3Og3+OZ98NTSRGEWFjIN6mAQmzvHc=
 168 shamir-share:i=1;y=zHpbi0h+mFVVv0vAo0djMK296b5XRCAYRV6yMsy74Rs=
 169 shamir-share:i=2;y=FbSHVSqoXLVbxkuVZweLXacXmqAnWMEgLOP3qlSvfPc=
 170 shamir-share:i=3;y=Q0bUOCUfgSlZSFPOSwhr2YjCSfXKRjwRDmwK8PZPB48=
 171 shamir-share:i=4;y=mogI5kfJRclXMVObj0iDtIJoOuu6Wt0pZ9FPaG5bmmM=
 172 .VE
 173 .SS recover
 174 The
 175 .B recover
 176 command reads parameters and shares from standard input,
 177 computes the original secret,
 178 and writes it to standard output.
 179 .PP
 180 There are no command-line options.
 181 .PP
 182 The first line of standard input must contain the sharing parameters.
 183 Subsequent lines contain shares,
 184 one per line.
 185 The shares may be in any order.
 186 Exactly the correct
 187 .RI ( thresh )
 188 number of shares must be provided.
 189 The shares are checked for various kinds of errors
 190 (e.g., duplicate shares, out-of-range indices),
 191 and the secret is computed
 192 and checked against the hash stored with the parameters.
 193 If everything is correct,
 194 the secret is written to standard output;
 195 otherwise errors are reported to standard error,
 196 and the program exits with a nonzero status
 197 having written nothing to standard output.
 198 .PP
 199 Example:
 200 .VS
 201 \*(pr cat shares
 202 .ft R
 203 shamir-params:n=5;t=3;f=sha256;h=lbcQW/lmV4z0ZKORE5Y0/g+thgWFKr4Kv3i1vEfNkUQ=
 204 shamir-share:i=2;y=FbSHVSqoXLVbxkuVZweLXacXmqAnWMEgLOP3qlSvfPc=
 205 shamir-share:i=1;y=zHpbi0h+mFVVv0vAo0djMK296b5XRCAYRV6yMsy74Rs=
 206 shamir-share:i=4;y=mogI5kfJRclXMVObj0iDtIJoOuu6Wt0pZ9FPaG5bmmM=
 207 .ft B
 208 \*(pr shamir recover <shares >secret2
 209 \*(pr cmp secret secret2
 210 .VE
 211 .SH DATA FORMATS
 212 The
 213 .B shamir
 214 program applies a simple encoding
 215 to the various kinds of structured data it deals with,
 216 specifically to
 217 .IR secrets ,
 218 .IR parameters ,
 219 and
 220 .IR shares .
 221 .PP
 222 An encoded object has the form
 223 .IP
 224 .IB label : \c
 225 .IB slot = value \c
 226 .RB [ ; ...]
 227 .PP
 228 Encodings do not contain whitespace characters.
 229 .PP
 230 The
 231 .I label
 232 is a token which identifies the kind of object encoded.
 233 Each
 234 .I slot
 235 is named with a token
 236 (usually a single letter),
 237 and supplied with its
 238 .I value
 239 in a suitable encoding,
 240 as described below.
 241 .PP
 242 The syntax is very picky.
 243 The order of the slots is significant,
 244 and all slots must be defined.
 245 .SS Secets
 246 A
 247 .I secret
 248 object describes a secret and its sharing parameters.
 249 Secret objects are not input or output directly,
 250 but are hashed when constructing parameters objects (described below).
 251 .PP
 252 The label for a secret object is
 253 .BR shamir-secret .
 254 Its slots are as follows.
 255 .TP
 256 .B n
 257 The total number of shares issued,
 258 i.e., the
 259 .I count
 260 argument to
 261 .BR "shamir issue" ,
 262 as a decimal integer.
 263 .TP
 264 .B t
 265 The threshold required for recovery,
 266 i.e., the
 267 .I thresh
 268 argument to
 269 .BR "shamir issue" ,
 270 as a decimal integer.
 271 .TP
 272 .B s
 273 The secret itself, Base64-encoded,
 274 with no whitespace.
 275 .SS Parameters
 276 A
 277 .I parameters
 278 object describes how a secret has been split into shares
 279 and provides information about how it can be reassembled.
 280 .PP
 281 The label for a parameters object is
 282 .BR shamir-params .
 283 Its slots are as follows.
 284 .TP
 285 .B n
 286 The total number of shares issued,
 287 i.e., the
 288 .I count
 289 argument to
 290 .BR "shamir issue" ,
 291 as a decimal integer.
 292 .TP
 293 .B t
 294 The threshold required for recovery,
 295 i.e., the
 296 .I thresh
 297 argument to
 298 .BR "shamir issue" ,
 299 as a decimal integer.
 300 .TP
 301 .B f
 302 The name of the hash function
 303 used to compute the
 304 .B h
 305 slot.
 306 This may be any of the hash functions known to OpenSSL.
 307 .TP
 308 .B h
 309 The hash of a secret object,
 310 made using the hash function named by the
 311 .B f
 312 slot,
 313 and Base64 encoded.
 314 No trailing newline is included when hashing the secret object.
 315 .SS Shares
 316 A
 317 .I share
 318 object describes a single share.
 319 The label for a parameters object is
 320 .BR shamir-share .
 321 Its slots are as follows.
 322 .TP
 323 .B i
 324 The share's index,
 325 as a decimal integer;
 326 .ie t $0 <= i < "count"$.
 327 .el .RI "0\~\(<= " i "\~< " count .
 328 .TP
 329 .B y
 330 The share data, Base64 encoded.
 331 .PP
 332 .SH MATHEMATICAL BACKGROUND
 333 (This section has lots of mathematical notation
 334 and doesn't look especially good in a terminal.)
 335 .PP
 336 Let
 337 .I k
 338 be a field.
 339 Suppose we are given a secret
 340 .ie t $s member k$
 341 .el .IR s \~\*(mo\~ k
 342 which we want to split into shares
 343 such that any $t$ of them can be used to recover
 344 .IR s .
 345 Choose coefficients
 346 .ie t $a sub i member k$
 347 .el .IR a _ i \~\*(mo\~ k
 348 for
 349 .ie t $1 <= i < t$
 350 .el .RI "1\~\(<= " i \~<\~ t
 351 at random.
 352 Let
 353 .ie t $p(x) = s + a sub 1 x + ... + a sub {t-1} x sup {t-1}$.
 354 .el \{\
 355 .IR p ( x ")\~= " s "\~+ " a "_1\~+ ...\~+"
 356 .IR a _( t \-1)\~ x ^( t \-1).
 357 .\}
 358 Note that
 359 .ie t $p(0) = s$.
 360 .el .IR p "(0)\~= " s .
 361 We can evaluate
 362 .I p
 363 to obtain shares
 364 .ie t $y sub i = p( x sub i )$
 365 .el .IR y _ i "\~= " p ( x _ i )
 366 for various
 367 .ie t $x sub i member k - lbrace ~ 0 ~ rbrace$.
 368 .el .IR x _ i "\~\*(mo " k "\~\- {\~0\~}."
 369 .PP
 370 How do we recover the secret?
 371 Suppose we are given
 372 .ie t $y sub i = p( x sub i )$
 373 .el .IR y _ i "\~= " p ( x _ i )
 374 for
 375 .ie t $0 <= i < t$,
 376 .el .RI "0\~\(<= " i "\~< " t ,
 377 where the
 378 .ie t $x sub i$
 379 .el .IR x _ i
 380 are distinct.
 381 Define
 382 .ie t \{\
 383 .EQ
 384 lambda sub i (x) =
 385   sum from {pile {0 <= j < t  above j != i}}
 386   {x - x sub j} over {x sub i - x sub j}.
 387 .EN
 388 .\}
 389 .el \{\
 390 .IP
 391 .nf
 392 .\"           ---   x - x_j
 393 .\" L_i(x) =  >    ---------.
 394 .\"           ---  x_i - x_j
 395 .\"          0<j<t
 396 .\"           j=i
 397           ---   \fIx\fP \- \fIx\fP_\fIj\fP
 398 \*(*l_\fIi\fP(\fIx\fP) =  >    ---------.
 399           ---  \fIx\fP_\fIi\fP - \fIx\fP_\fIj\fP
 400          0\(<=\fIj\fP<\fIt\fP
 401           \fIj\fP\(!=\fIi\fP
 402 .fi
 403 .PP
 404 .\}
 405 Then
 406 .ie t $lambda sub i$
 407 .el .RI \*(*l_ i
 408 is a
 409 .ie t degree-$(t - 1)$
 410 .el .RI degree-( t \~\-\~1)
 411 polynomial
 412 such that
 413 .ie t $lambda sub i ( x sub i ) = 1$,
 414 .el .RI \*(*l_ i ( x _ i )\~=\~1,
 415 and
 416 .ie t $lambda sub i ( x sub j ) = 0$
 417 .el .RI \*(*l_ i ( x _ j )\~=\~0
 418 if
 419 .ie t $j != i$.
 420 .el .IR j \~\(!=\~ i .
 421 Define
 422 .ie t \{\
 423 .EQ
 424 q(x) = sum from {0 <= i < t} lambda sub i (x) y sub i .
 425 .EN
 426 .\}
 427 .el \{\
 428 .IP
 429 .nf
 430 .\"         ---
 431 .\" q(x) =  >    L_i(x) y_i.
 432 .\"         ---
 433 .\"        0<i<t
 434         ---
 435 \fIq\fP(\fIx\fP) =  >    \*(*l_\fIi\fP(\fIx\fP) \fIy\fP_\fIi\fP.
 436         ---
 437        0\(<=\fIi\fP<\fIt\fP
 438 .fi
 439 .PP
 440 .\}
 441 Note that
 442 .I q
 443 has degree
 444 .ie t $t - 1$,
 445 .el .IR t "\~\- 1"
 446 and
 447 .ie t $q( x sub i ) = y sub i = p( x sub i )$
 448 .el .IR q ( x _ i ")\~= " y _ i "\~= " p ( x _ i )
 449 for all
 450 .ie t $0 <= i < t$.
 451 .el .RI "0\~\(<= " i \~<\~ t .
 452 Hence
 453 .ie t $p - q$
 454 .el .IR p \~\-\~ q
 455 is a polynomial with degree at most
 456 .ie t $t - 1$
 457 .el .IR t \~\-\~1
 458 but with at least
 459 .I t
 460 distinct zeros;
 461 therefore
 462 .ie t $q - p$
 463 .el .IR q \~\-\~ p
 464 must be identically zero
 465 and hence
 466 .ie t $q == p$
 467 .el .IR q \~\(==\~ p
 468 and
 469 .ie t $s = q(0)$.
 470 .el .IR s "\~= " q (0).
 471 .PP
 472 Suppose we are given
 473 .ie t $t - 1$
 474 .el .IR t \~\-\~1
 475 shares.
 476 Then,
 477 for any putative secret
 478 .ie t $s'$,
 479 .el .IR s ',
 480 there exists a distinct possible value for each of the remaining shares
 481 which can be determined using the above interpolation,
 482 each of which is equally likely.
 483 .PP
 484 The polynomial interpolation technique is due to Lagrange;
 485 its use as a secret-sharing scheme is due to Adi Shamir.
 486 .PP
 487 In theory, then,
 488 this secret-sharing scheme is
 489 .IR "information-theoretically secure" ;
 490 in practice,
 491 there's a cryptographic hash of the secret in the sharing parameters,
 492 so security is limited to the computational difficulty
 493 of inverting this hash.
 494 Knowledge of fewer than
 495 .I t
 496 shares doesn't make this any easier;
 497 and there's a security benefit to
 498 knowing that a dishonest share holder
 499 can't introduce errors into the recovered secret.
 500 .PP
 501 All of the above works in any field
 502 .IR k .
 503 Computation is easiest in a small finite field
 504 (rather than, say, the rationals).
 505 This program uses the field
 506 .ie t $FIELD sub {2 sup 8}$
 507 .el GF(2^8)
 508 represented as the quotient ring
 509 .ie t $FIELD sub 2 [u]/( u sup 8 + u sup 4 + u sup 3 + u sup 2 + 1 )$.
 510 .el \{\
 511 .RI GF(2)[ u ]/( u ^8\~+
 512 .IR u ^4\~+
 513 .IR u ^3\~+
 514 .IR u ^2\~+\~1).
 515 .\}
 516 Hence, a field element fits exactly into a single byte:
 517 specifically, the field element
 518 .ie t $x = a sub 0 + a sub 1 u + ... + a sub 7 u sup 7$
 519 .el \{\
 520 .IR x \~=
 521 .IR a _0\~+
 522 .IR a _1\~ u \~+
 523 \&...\~+
 524 .IR a _7\~ u ^7
 525 .\}
 526 corresponds to the byte
 527 .ie t $B(x) = a sub 0 + 2 a sub 1 + ... + 2 sup 7 a sub 7$.
 528 .el \{\
 529 .IR B ( x )\~=
 530 .IR a _0\~+
 531 .RI 2\~ a _1\~+
 532 \&... +
 533 .RI 2^7\~ a _7.
 534 .\}
 535 Secrets longer than a single byte are shared bytewise independently,
 536 which is why the shares leak information about the secret size.
 537 .PP
 538 The program represents share indices as small integers
 539 .ie t $0 <= i < n$;
 540 .el .RI "0\~\(<= " i \~<\~ n ;
 541 specifically, the share with index
 542 .I i
 543 is generated by
 544 evaluating the polynomial
 545 .ie t $p(x)$
 546 .el .IR p ( x )
 547 where
 548 .ie t $i = B(x) - 1$.
 549 .el .IR i "\~= " B ( x )\~\-\~1.
 550 .SH AUTHOR
 551 Mark Wooding, <mdw@distorted.org.uk>
 552 .SH SEE ALSO
 553 .BR distorted-keys (7),
 554 .BR dgst (1ssl).