keys.delete-keeper: Only do one pass through the file system.

[distorted-keys] / shamir.1

'\" e
.\" -*-nroff-*-
.ie t \{\
.  ds o \(bu
.  if \n(.g .fam P
.\}
.el \{\
.  ds o o
.  ie '\*(.T'utf8' .ds mo ∈
.  el .ds mo \fBin\fP
.  ie '\*(.T'utf8' .ds *l \(*l
.  el .ds *l L
.\}
.de hP
.IP
\h'-\w'\fB\\$1\ \fP'u'\fB\\$1\ \fP\c
..
.de VS
.sp 1
.RS
.nf
.ft B
..
.de VE
.ft R
.fi
.RE
.sp 1
..
.ds pr $
.EQ
delim $$
tdefine member 'type "relation" \(mo'
define lbrace 'roman "{"'
define rbrace 'roman "}"'
define FIELD 'bold F'
.EN
.TH shamir 1 "3 May 2015" "distorted.org.uk key management"
.de EQ
.PP
.ce
..
.de EN
.PP
..
.SH NAME
shamir \- split a secret into shares, and recombine them
.SH SYNOPSIS
.B shamir
.I command
.PP
where
.I command
is one of:
.PP
.B help
.IB [ command\fR... ]
.br
.B issue
.RB [ \-H
.IR hashfn ]
.IB thresh / count
.RI [ secret-file ]
.br
.B recover
.SH DESCRIPTION
The
.B shamir
program implements a simple secret sharing scheme.
Given a secret,
the
.B issue
command will split it
into a number of shares
.IR n,
any
.ie t $t <= n$
.el \{\
.I t
\(<=
.I n
.\}
of which
can be used to reconstruct it, but
fewer than
.I t
shares provide no information at all
about the secret
(other than its length).
.SH COMMAND-LINE OPTIONS
The following options are recognized.
.TP
.B \-h, \-\-help
Print an overview
of the options and commands
to standard output
and exit successfully.
.TP
.B \-\-version
Print the version number
of the
.B distorted-keys
package
to standard output
and exit successfully.
.SH COMMAND REFERENCE
.SS help
The
.B help
command prints information to standard output
about the
.B shamir
program as a whole
(similar to the
.B \-\-help
option),
or about the named
.IR command s.
.SS issue
The
.B issue
command reads a secret from
.I secret-file
(or from standard input,
if
.I secret-file
is omitted or
.RB ` \- '),
and writes a number of lines to standard output.
.PP
The
.I count
is the total number of shares issued;
any
.I thresh
of them can be used to reassemble the original secret.
It must be the case that
.ie t $1 <= "thresh" <= "count" <= 255$.
.el .RI "1\~\(<= " thresh "\~\(<= " count "\~\(<= 255."
.PP
The first line contains secret-sharing parameters,
which will be required in any recovery operation.
These do not usually need to be kept secret
(though they contain a cryptographic hash of the original input)
but it's a good idea to ensure their integrity.
This can be done by storing the parameters in a safe place,
possibly protected by a digital signature,
or by issuing each share holder with a copy of the parameters
and checking that they match at recovery time.
.PP
The remaining lines contain share data, one per line, for
.I count
lines.
Each share holder should be given one of these lines.
.PP
The following options are accepted.
.TP
.BI "\-H, \-\-hash-function=" hashfn
The hash function to use when hashing the secret.
This may be any hash function name known to OpenSSL.
.PP
Example:
.VS
\*(pr shamir issue 3/5 secret
.ft R
shamir-params:n=5;t=3;f=sha256;h=lbcQW/lmV4z0ZKORE5Y0/g+thgWFKr4Kv3i1vEfNkUQ=
shamir-share:i=0;y=Ft3jhDQgTdMgEJ3Og3+OZ98NTSRGEWFjIN6mAQmzvHc=
shamir-share:i=1;y=zHpbi0h+mFVVv0vAo0djMK296b5XRCAYRV6yMsy74Rs=
shamir-share:i=2;y=FbSHVSqoXLVbxkuVZweLXacXmqAnWMEgLOP3qlSvfPc=
shamir-share:i=3;y=Q0bUOCUfgSlZSFPOSwhr2YjCSfXKRjwRDmwK8PZPB48=
shamir-share:i=4;y=mogI5kfJRclXMVObj0iDtIJoOuu6Wt0pZ9FPaG5bmmM=
.VE
.SS recover
The
.B recover
command reads parameters and shares from standard input,
computes the original secret,
and writes it to standard output.
.PP
There are no command-line options.
.PP
The first line of standard input must contain the sharing parameters.
Subsequent lines contain shares,
one per line.
The shares may be in any order.
Exactly the correct
.RI ( thresh )
number of shares must be provided.
The shares are checked for various kinds of errors
(e.g., duplicate shares, out-of-range indices),
and the secret is computed
and checked against the hash stored with the parameters.
If everything is correct,
the secret is written to standard output;
otherwise errors are reported to standard error,
and the program exits with a nonzero status
having written nothing to standard output.
.PP
Example:
.VS
\*(pr cat shares
.ft R
shamir-params:n=5;t=3;f=sha256;h=lbcQW/lmV4z0ZKORE5Y0/g+thgWFKr4Kv3i1vEfNkUQ=
shamir-share:i=2;y=FbSHVSqoXLVbxkuVZweLXacXmqAnWMEgLOP3qlSvfPc=
shamir-share:i=1;y=zHpbi0h+mFVVv0vAo0djMK296b5XRCAYRV6yMsy74Rs=
shamir-share:i=4;y=mogI5kfJRclXMVObj0iDtIJoOuu6Wt0pZ9FPaG5bmmM=
.ft B
\*(pr shamir recover <shares >secret2
\*(pr cmp secret secret2
.VE
.SH DATA FORMATS
The
.B shamir
program applies a simple encoding
to the various kinds of structured data it deals with,
specifically to
.IR secrets ,
.IR parameters ,
and
.IR shares .
.PP
An encoded object has the form
.IP
.IB label : \c
.IB slot = value \c
.RB [ ; ...]
.PP
Encodings do not contain whitespace characters.
.PP
The
.I label
is a token which identifies the kind of object encoded.
Each
.I slot
is named with a token
(usually a single letter),
and supplied with its
.I value
in a suitable encoding,
as described below.
.PP
The syntax is very picky.
The order of the slots is significant,
and all slots must be defined.
.SS Secets
A
.I secret
object describes a secret and its sharing parameters.
Secret objects are not input or output directly,
but are hashed when constructing parameters objects (described below).
.PP
The label for a secret object is
.BR shamir-secret .
Its slots are as follows.
.TP
.B n
The total number of shares issued,
i.e., the
.I count
argument to
.BR "shamir issue" ,
as a decimal integer.
.TP
.B t
The threshold required for recovery,
i.e., the
.I thresh
argument to
.BR "shamir issue" ,
as a decimal integer.
.TP
.B s
The secret itself, Base64-encoded,
with no whitespace.
.SS Parameters
A
.I parameters
object describes how a secret has been split into shares
and provides information about how it can be reassembled.
.PP
The label for a parameters object is
.BR shamir-params .
Its slots are as follows.
.TP
.B n
The total number of shares issued,
i.e., the
.I count
argument to
.BR "shamir issue" ,
as a decimal integer.
.TP
.B t
The threshold required for recovery,
i.e., the
.I thresh
argument to
.BR "shamir issue" ,
as a decimal integer.
.TP
.B f
The name of the hash function
used to compute the
.B h
slot.
This may be any of the hash functions known to OpenSSL.
.TP
.B h
The hash of a secret object,
made using the hash function named by the
.B f
slot,
and Base64 encoded.
No trailing newline is included when hashing the secret object.
.SS Shares
A
.I share
object describes a single share.
The label for a parameters object is
.BR shamir-share .
Its slots are as follows.
.TP
.B i
The share's index,
as a decimal integer;
.ie t $0 <= i < "count"$.
.el .RI "0\~\(<= " i "\~< " count .
.TP
.B y
The share data, Base64 encoded.
.PP
.SH MATHEMATICAL BACKGROUND
(This section has lots of mathematical notation
and doesn't look especially good in a terminal.)
.PP
Let
.I k
be a field.
Suppose we are given a secret
.ie t $s member k$
.el .IR s \~\*(mo\~ k
which we want to split into shares
such that any $t$ of them can be used to recover
.IR s .
Choose coefficients
.ie t $a sub i member k$
.el .IR a _ i \~\*(mo\~ k
for
.ie t $1 <= i < t$
.el .RI "1\~\(<= " i \~<\~ t
at random.
Let 
.ie t $p(x) = s + a sub 1 x + ... + a sub {t-1} x sup {t-1}$.
.el \{\
.IR p ( x ")\~= " s "\~+ " a "_1\~+ ...\~+"
.IR a _( t \-1)\~ x ^( t \-1).
.\}
Note that
.ie t $p(0) = s$.
.el .IR p "(0)\~= " s .
We can evaluate 
.I p
to obtain shares
.ie t $y sub i = p( x sub i )$
.el .IR y _ i "\~= " p ( x _ i )
for various
.ie t $x sub i member k - lbrace ~ 0 ~ rbrace$.
.el .IR x _ i "\~\*(mo " k "\~\- {\~0\~}."
.PP
How do we recover the secret?
Suppose we are given
.ie t $y sub i = p( x sub i )$
.el .IR y _ i "\~= " p ( x _ i )
for
.ie t $0 <= i < t$,
.el .RI "0\~\(<= " i "\~< " t ,
where the
.ie t $x sub i$
.el .IR x _ i
are distinct.
Define
.ie t \{\
.EQ
lambda sub i (x) =
  sum from {pile {0 <= j < t  above j != i}}
  {x - x sub j} over {x sub i - x sub j}.
.EN
.\}
.el \{\
.IP
.nf
.\"           ---   x - x_j 
.\" L_i(x) =  >    ---------.
.\"           ---  x_i - x_j
.\"          0<j<t
.\"           j=i
          ---   \fIx\fP \- \fIx\fP_\fIj\fP 
\*(*l_\fIi\fP(\fIx\fP) =  >    ---------.
          ---  \fIx\fP_\fIi\fP - \fIx\fP_\fIj\fP
         0\(<=\fIj\fP<\fIt\fP
          \fIj\fP\(!=\fIi\fP
.fi
.PP
.\}
Then 
.ie t $lambda sub i$
.el .RI \*(*l_ i
is a
.ie t degree-$(t - 1)$
.el .RI degree-( t \~\-\~1)
polynomial
such that 
.ie t $lambda sub i ( x sub i ) = 1$,
.el .RI \*(*l_ i ( x _ i )\~=\~1,
and
.ie t $lambda sub i ( x sub j ) = 0$
.el .RI \*(*l_ i ( x _ j )\~=\~0
if
.ie t $j != i$.
.el .IR j \~\(!=\~ i .
Define
.ie t \{\
.EQ
q(x) = sum from {0 <= i < t} lambda sub i (x) y sub i .
.EN
.\}
.el \{\
.IP
.nf
.\"         ---
.\" q(x) =  >    L_i(x) y_i.
.\"         ---
.\"        0<i<t
        ---
\fIq\fP(\fIx\fP) =  >    \*(*l_\fIi\fP(\fIx\fP) \fIy\fP_\fIi\fP.
        ---
       0\(<=\fIi\fP<\fIt\fP
.fi
.PP
.\}
Note that
.I q
has degree
.ie t $t - 1$,
.el .IR t "\~\- 1"
and
.ie t $q( x sub i ) = y sub i = p( x sub i )$
.el .IR q ( x _ i ")\~= " y _ i "\~= " p ( x _ i )
for all
.ie t $0 <= i < t$.
.el .RI "0\~\(<= " i \~<\~ t .
Hence
.ie t $p - q$
.el .IR p \~\-\~ q
is a polynomial with degree at most
.ie t $t - 1$
.el .IR t \~\-\~1
but with at least
.I t
distinct zeros;
therefore
.ie t $q - p$
.el .IR q \~\-\~ p
must be identically zero
and hence
.ie t $q == p$
.el .IR q \~\(==\~ p
and
.ie t $s = q(0)$.
.el .IR s "\~= " q (0).
.PP
Suppose we are given
.ie t $t - 1$
.el .IR t \~\-\~1
shares.
Then,
for any putative secret
.ie t $s'$,
.el .IR s ',
there exists a distinct possible value for each of the remaining shares
which can be determined using the above interpolation,
each of which is equally likely.
.PP
The polynomial interpolation technique is due to Lagrange;
its use as a secret-sharing scheme is due to Adi Shamir.
.PP
In theory, then,
this secret-sharing scheme is
.IR "information-theoretically secure" ;
in practice,
there's a cryptographic hash of the secret in the sharing parameters,
so security is limited to the computational difficulty
of inverting this hash.
Knowledge of fewer than
.I t
shares doesn't make this any easier;
and there's a security benefit to
knowing that a dishonest share holder
can't introduce errors into the recovered secret.
.PP
All of the above works in any field
.IR k .
Computation is easiest in a small finite field
(rather than, say, the rationals).
This program uses the field
.ie t $FIELD sub {2 sup 8}$
.el GF(2^8)
represented as the quotient ring
.ie t $FIELD sub 2 [u]/( u sup 8 + u sup 4 + u sup 3 + u sup 2 + 1 )$.
.el \{\
.RI GF(2)[ u ]/( u ^8\~+
.IR u ^4\~+
.IR u ^3\~+
.IR u ^2\~+\~1).
.\}
Hence, a field element fits exactly into a single byte:
specifically, the field element
.ie t $x = a sub 0 + a sub 1 u + ... + a sub 7 u sup 7$
.el \{\
.IR x \~=
.IR a _0\~+
.IR a _1\~ u \~+
\&...\~+
.IR a _7\~ u ^7
.\}
corresponds to the byte
.ie t $B(x) = a sub 0 + 2 a sub 1 + ... + 2 sup 7 a sub 7$.
.el \{\
.IR B ( x )\~=
.IR a _0\~+
.RI 2\~ a _1\~+
\&... +
.RI 2^7\~ a _7.
.\}
Secrets longer than a single byte are shared bytewise independently,
which is why the shares leak information about the secret size.
.PP
The program represents share indices as small integers
.ie t $0 <= i < n$;
.el .RI "0\~\(<= " i \~<\~ n ;
specifically, the share with index
.I i
is generated by
evaluating the polynomial
.ie t $p(x)$
.el .IR p ( x )
where
.ie t $i = B(x) - 1$.
.el .IR i "\~= " B ( x )\~\-\~1.
.SH AUTHOR
Mark Wooding, <mdw@distorted.org.uk>
.SH SEE ALSO
.BR distorted-keys (7),
.BR dgst (1ssl).