## Commands.
dist_pkgdata_SCRIPTS += keys.conceal
dist_pkgdata_SCRIPTS += keys.delete-keeper
+dist_pkgdata_SCRIPTS += keys.forget-keeper
dist_pkgdata_SCRIPTS += keys.keeper-cards
dist_pkgdata_SCRIPTS += keys.keeper-nub
dist_pkgdata_SCRIPTS += keys.list-keepers
NAME+WIDTH Minimum width: if a value won't fit then make the entire
column wider.
-Columns names:
+Column names:
flags Various flags for the key. (Unset flags are shown as \`.')
R key has recovery information
! key nub needs recovery
case "$nubbin" in
"$nubid") ;;
*)
+ rm -f $knub.new
echo >&2 "$quis: recovery produced incorrect nub"
exit 1
;;
--- /dev/null
+.\" -*-nroff-*-
+.ie t \{\
+. ds o \(bu
+. if \n(.g .fam P
+.\}
+.el \{\
+. ds o o
+.\}
+.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
+..
+.TH distorted-keys 1 "3 May 2015" "distorted.org.uk key management"
+.SH NAME
+distorted-keys \- key-management service and utilities
+.SH DESCRIPTION
+.SS Keys and nubs
+.SS Keeper sets
+.SS Recovery keys
+.SH AUTHOR
+Mark Wooding, <mdw@distorted.org.uk>
+.SH SEE ALSO
+.BR distorted-keys (7).
checkword () { check "$1" "$R_WORD" "$2"; }
checklabel () { check "$1 label" "$R_LABEL" "$2"; }
+## Boolean canonification.
+boolify () {
+ var=$1 what=$2
+
+ eval v=\$$var
+ case $v in
+ 1 | y | yes | on | t | true) v=t ;;
+ 0 | n | no | off | f | false | nil) v=nil ;;
+ *) echo >&2 "$quis: bad boolean $what \`$v'"; exit 1 ;;
+ esac
+ eval $var=\$v
+}
+
###--------------------------------------------------------------------------
### Key storage and properties.
Delete the keeper set named KEEPER.
HELP
+## Parse the command line.
case $# in 1) ;; *) usage_err ;; esac
keeper=$1
checkword "keeper set label" "$keeper"
+## Check that the set actually exists.
cd $KEYS/keeper
if [ ! -d $keeper ]; then
echo >&2 "$quis: unknown keeper set \`$keeper'"
exit 1
fi
-unset deps
+## Make sure that there aren't recovery keys which would be orphaned by
+## deleting this keeper set. Also, build a data structure of recovery keys
+## and their instances: `$recov' is a space-separated list of recovery key
+## labels, and for each such label R, `$ri_R' is a space-separated list of
+## its instances.
+unset deps; recov=" "
if [ -d $KEYS/recov ]; then
cd $KEYS/recov
- for r in $(find . -type l -name current -print); do
- r=${r#./}; r=${r%/current}
- if ! expr >/dev/null "Q$r" : "Q$R_LABEL"; then continue; fi
+
+ ## Work through the available recovery keys.
+ for r in *; do
+ if ! expr >/dev/null "Q$r" : "Q$R_WORD"; then continue; fi
+ if [ ! -l $r/current ]; then continue; fi
+
+ ## Add the key to our list.
+ recov="$recov$r "
+
+ ## Now work through the instances.
+ ii=""
for ri in $r/*; do
- i=${ri##*/}
+ i=${ri#*/}
case "$i" in *[!0-9]*) continue ;; esac
+
+ ## Add the instance to our list.
+ ii="$ii $i"
+
+ ## For each recovery key, make sure that: either it doesn't depend on
+ ## this keeper set, or it also depends on at least one other set. If
+ ## not, add it to the `deps' list.
this=nil others=nil
- for kp in $r/current/*.param; do
+ for kp in $ri/*.param; do
k=${kp##*/}; k=${k%.param}
case $k in $keeper) this=t ;; *) others=t ;; esac
done
case $this,$others in t,nil) deps="$deps $ri" ;; esac
done
+
+ ## Record the list of instances.
+ eval "ri_$r=\$ii"
done
fi
+
+## If we found any hard dependencies, report a failure.
case "${deps+t}" in
t)
echo >&2 "$quis: deleting keeper \`$keeper' would orphan recovery keys:"
;;
esac
-if [ -d $KEYS/recov ]; then
- cd $KEYS/recov
- for r in $(find . -type l -name current -print); do
- r=${r#./}; r=${r%/current}
- if ! expr >/dev/null "Q$r" : "Q$R_LABEL"; then continue; fi
- for ri in $i/*; do
- i=${ri##*/}
- case "$i" in *[!0-9]*) continue ;; esac
- rm -f $ri/$keeper.*
- done
- changep=nil
- while read k rest; do
- case $k in $keeper) changep=t ;; *) echo "$k $rest" ;; esac
- done <$r/keepers >$r/keepers.new
- case $changep in
- t) mv $r/keepers.new $r/keepers ;;
- nil) rm $r/keepers.new ;;
- esac
- done
-fi
+## Disentangle the dependent recovery keys from this keeper set.
+for r in $recov; do
+
+ ## Remove the keeper data from the key's instances.
+ eval "ii=\$ri_$r"
+ for i in $ii; do rm -f $r/$i/$keeper.*; done
+
+ ## Work through the current keepers, and remove our keeper's name from the
+ ## list.
+ changep=nil
+ while read k rest; do
+ case $k in $keeper) changep=t ;; *) echo "$k $rest" ;; esac
+ done <$r/keepers >$r/keepers.new
+ case $changep in
+ t) mv $r/keepers.new $r/keepers ;;
+ nil) rm $r/keepers.new ;;
+ esac
+done
+## Finally, actually delete the keeper keys.
cd $KEYS/keeper
rm -r $keeper
--- /dev/null
+#! /bin/sh
+###
+### Clear out stashed keeper nubs when they've all been saved
+###
+### (c) 2015 Mark Wooding
+###
+
+###----- Licensing notice ---------------------------------------------------
+###
+### This file is part of the distorted.org.uk key management suite.
+###
+### distorted-keys is free software; you can redistribute it and/or modify
+### it under the terms of the GNU General Public License as published by
+### the Free Software Foundation; either version 2 of the License, or
+### (at your option) any later version.
+###
+### distorted-keys is distributed in the hope that it will be useful,
+### but WITHOUT ANY WARRANTY; without even the implied warranty of
+### MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+### GNU General Public License for more details.
+###
+### You should have received a copy of the GNU General Public License
+### along with distorted-keys; if not, write to the Free Software Foundation,
+### Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
+
+set -e
+case "${KEYSLIB+t}" in t) ;; *) echo >&2 "$0: KEYSLIB unset"; exit 1 ;; esac
+. "$KEYSLIB"/keyfunc.sh
+
+defhelp <<HELP
+KEEPER
+Forget keeper nubs once they've all been stashed safely.
+
+Forget the key nubs for the keeper set KEEPER, deleting them from the
+safe temporary place they were left by \`keys new-keeper.
+HELP
+
+## Parse the command line.
+case $# in 1) ;; *) usage_err ;; esac
+keeper=$1
+checkword "keeper label" "$keeper"
+
+## Check that the set is actually there.
+reqsafe
+if [ ! -d $SAFE/keys.keeper/$keeper ]; then
+ echo >&2 "$quis: no nubs available for keeper set \`$keeper'"
+ exit 1
+fi
+
+## Delete them.
+rm -rf $SAFE/keys.keeper/$keeper
+
+###----- That's all, folks --------------------------------------------------
Create a new set of keeper keys.
The key nubs are stored in a safe but temporary place where they can be
-extracted using \`keys keeper-nub'.
+extracted using \`keys keeper-nub', and, eventually, forgotten using
+\`keys forget-keeper'.
HELP
## Parse the command line.
rm -rf $rdir/new
mkdir -m755 $rdir/new
cd $tmp
-while :; do case "$#,$1" in
+while :; do
+ case "$#,$1" in
0,) break ;;
*,*,*) ;;
*,--) break ;;
esac
shift
done
-c_gensyskey $profile $rdir/new/store secret recov="$recov"
+c_gensyskey $profile $rdir/new/store secret recov="$recov" "$@"
while read keeper k; do
read n hunoz <$KEYS/keeper/$keeper/meta
$bindir/shamir issue $k/$n secret | {
--- /dev/null
+#! /bin/sh
+###
+### Retire an old recovery key
+###
+### (c) 2015 Mark Wooding
+###
+
+###----- Licensing notice ---------------------------------------------------
+###
+### This file is part of the distorted.org.uk key management suite.
+###
+### distorted-keys is free software; you can redistribute it and/or modify
+### it under the terms of the GNU General Public License as published by
+### the Free Software Foundation; either version 2 of the License, or
+### (at your option) any later version.
+###
+### distorted-keys is distributed in the hope that it will be useful,
+### but WITHOUT ANY WARRANTY; without even the implied warranty of
+### MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+### GNU General Public License for more details.
+###
+### You should have received a copy of the GNU General Public License
+### along with distorted-keys; if not, write to the Free Software Foundation,
+### Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
+
+set -e
+case "${KEYSLIB+t}" in t) ;; *) echo >&2 "$0: KEYSLIB unset"; exit 1 ;; esac
+. "$KEYSLIB"/keyfunc.sh
+
+defhelp <<HELP
+RECOV I
+Retire a non-current instance I of the recovery key RECOV.
+HELP
+
+## Parse the command line.
+case $# in 2) ;; *) usage_err ;; esac
+recov=$1 inst=$2
+checkword "recovery key label" "$recov"
+checknumber "recovery key instance" "$inst"
+
+## Check that the key exists and isn't current.
+cd $KEYS/recov
+if [ ! -l $recov/current ]; then
+ echo >&2 "$quis: unknown recovery key \`$recov'"
+ exit 1
+fi
+if [ ! -d $recov/$inst ]; then
+ echo >&2 "$quis: recovery key \`$recov' has no instance $inst"
+ exit 1
+fi
+curr=$(readlink $recov/current)
+case $curr in
+ $inst)
+ echo >&2 "$quis: $inst is current instance of recovery key \`$recov'"
+ exit 1
+ ;;
+esac
+
+## Delete all of the secrets.
+rm -rf $recov/$inst
+
+###----- That's all, folks --------------------------------------------------
--- /dev/null
+### -*-sh-*-
+###
+### Key type for OpenSSL
+###
+### (c) 2015 Mark Wooding
+###
+
+###----- Licensing notice ---------------------------------------------------
+###
+### This file is part of the distorted.org.uk key management suite.
+###
+### distorted-keys is free software; you can redistribute it and/or modify
+### it under the terms of the GNU General Public License as published by
+### the Free Software Foundation; either version 2 of the License, or
+### (at your option) any later version.
+###
+### distorted-keys is distributed in the hope that it will be useful,
+### but WITHOUT ANY WARRANTY; without even the implied warranty of
+### MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+### GNU General Public License for more details.
+###
+### You should have received a copy of the GNU General Public License
+### along with distorted-keys; if not, write to the Free Software Foundation,
+### Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
+
+R_OPT="$R_IDENT:$R_IDENT"
+R_OPTSEQ="$R_OPT\([[:space:]][[:space:]]*$R_OPT\)*"
+
+R_TYPE="[$R_IDENTCHARS[:space:]][$R_IDENTCHARS[:space:]]*"
+R_BASE64="[a-zA-Z0-9+/]*=*"
+R_PARAMS="$R_TYPE:$R_BASE64"
+
+defprops k_props <<EOF
+algorithm t $R_WORD
+opts t $R_OPTSEQ
+params t $R_PARAMS
+fresh_params_p t $R_IDENT
+cipher t $R_WORD
+sig_opts t $R_OPTSEQ
+enc_opts t $R_OPTSEQ
+EOF
+
+: ${kprop_cipher=aes-256-cbc}
+: ${kprop_fresh_params_p=nil}; boolify kprop_fresh_params_p
+have_opts_p=${kprop_opts+t}${kprop_opts-nil}
+have_params_p=${kprop_params+t}${kprop_params-nil}
+have_alg_p=${kprop_algorithm+t}${kprop_algorithm-nil}
+
+pem_to_line () {
+ ## Read an OpenSSL PEM file from stdin and write a condensed one-line
+ ## version to stdout.
+ sed '/^-----BEGIN \(.*\)-----$/s//\1:/; /^-----END .*-----$/d' |
+ tr -d '\n'
+}
+
+line_to_pem () {
+ line=$1
+ ## Write to stdout an OpenSSL PEM file corresponding to LINE.
+
+ ty=${line%%:*}
+ echo "-----BEGIN $ty-----"
+ echo "${line#*:}" | fold -w64
+ echo "-----END $ty-----";
+}
+
+intersperse_opts () {
+ flag=$1 opts=$2
+
+ args= sep=
+ for i in $opts; do args="$args$sep$flag $i" sep=" "; done
+ echo "$args"
+}
+
+k_generate() {
+ base=$1 nub=$2
+
+ ## Convert the options into OpenSSL command-line options.
+ opts=$(intersperse_opts -pkeyopt "$kprop_opts")
+
+ ## Prepare our ducks, ensuring that they're collinear.
+ case $have_params_p,$have_alg_p,$kprop_fresh_params_p,$have_opts_p in
+ t,nil,nil,nil)
+ line_to_pem "$kprop_params" >$TMP/param
+ args="-paramfile $TMP/param"
+ ;;
+ nil,t,t,*)
+ openssl genpkey -genparam -algorithm $kprop_algorithm $opts >$TMP/param
+ args="-paramfile $TMP/param"
+ ;;
+ nil,t,nil,*)
+ args="-algorithm $kprop_algorithm $opts"
+ ;;
+ *)
+ echo >&2 "$quis: invalid combination of properties"
+ exit 1
+ ;;
+ esac
+
+ ## Generate the private key.
+ openssl -cipher $kprop_cipher -pass file:"$nub" -out "$base/priv"
+
+ ## Extract the public key.
+ openssl -passin file:"$nub" -in "$base/priv" -pubout "$base/pub"
+}
+
+k_encrypt () {
+ base=$1
+
+ openssl pkeyutl -encrypt -pubin -inkey "$base/pub" \
+ $(intersperse_opts -pkeyopt "$kprop_enc_opts")
+}
+
+k_decrypt () {
+ base=$1 nub=$2
+
+ openssl pkeyutl -decrypt -passin file:"$nub" -inkey "$base/priv"
+}
+
+k_sign () {
+ base=$1 nub=$2
+
+ openssl pkeyutl -sign -passin file:"$nub" -inkey "$base/priv" \
+ $(intersperse_opts -pkeyopt "$kprop_sig_opts") >$TMP/sig
+ pem_to_line <$TMP/sig
+}
+
+k_verify () {
+ base=$1 sig=$3
+
+ line_to_pem "$3" >$TMP/sig
+ openssl pkeyutl -verify -pubin -inkey "$base/pub" -sigfile $TMP/sig
+}
+
+###----- That's all, folks --------------------------------------------------
of them can be used to reassemble the original secret.
It must be the case that
.ie t $1 <= "thresh" <= "count" <= 255$.
-.el \{\
-1
-\(<=
-.I thresh
-\(<=
-.I count
-\(<=
-255.
-.\}
+.el .RI "1\~\(<= " thresh "\~\(<= " count "\~\(<= 255."
.PP
The first line contains secret-sharing parameters,
which will be required in any recovery operation.
The share's index,
as a decimal integer;
.ie t $0 <= i < "count"$.
-.el \{\
-0 \(<=
-.I i
-<
-.IR count .
-.\}
+.el .RI "0\~\(<= " i "\~< " count .
.TP
.B y
The share data, Base64 encoded.
be a field.
Suppose we are given a secret
.ie t $s member k$
-.el \{\
-.I s
-\*(mo
-.I 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
-.I k
-.\}
+.el .IR a _ i \~\*(mo\~ k
for
.ie t $1 <= i < t$
-.el \{\
-1 \(<=
-.I i
-<
-.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 )
-=
-.I s
-+
-.IR a _1
-.I x
-+ ... +
-.IR a _( t \-1)
-.IR x ^( t \-1).
+.IR p ( x ")\~= " s "\~+ " a "_1\~+ ...\~+"
+.IR a _( t \-1)\~ x ^( t \-1).
.\}
Note that
.ie t $p(0) = s$.
-.el \{\
-.IR p (0)
-=
-.IR 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
-=
-.IR p ( x _ 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
-.I k
-\-
-{ 0 }.
-.\}
+.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
-=
-.IR p ( x _ i )
-.\}
+.el .IR y _ i "\~= " p ( x _ i )
for
.ie t $0 <= i < t$,
-.el \{\
-0 \(<=
-.I i
-<
-.IR t .
-.\}
+.el .RI "0\~\(<= " i "\~< " t ,
where the
.ie t $x sub i$
.el .IR x _ i
.el .RI \*(*l_ i
is a
.ie t degree-$(t - 1)$
-.el \{\
-.RI 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,
-.\}
+.el .RI \*(*l_ i ( x _ i )\~=\~1,
and
.ie t $lambda sub i ( x sub j ) = 0$
-.el \{\
-.RI \*(*l_ i ( x _ j )
-= 0
-.\}
+.el .RI \*(*l_ i ( x _ j )\~=\~0
if
.ie t $j != i$.
-.el \{\
-.I j
-\(!=
-.IR i .
-.\}
+.el .IR j \~\(!=\~ i .
Define
.ie t \{\
.EQ
.I q
has degree
.ie t $t - 1$,
-.el \{\
-.I 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 )
-=
-.IR y _ i
-=
-.IR p ( x _ i )
-.\}
+.el .IR q ( x _ i ")\~= " y _ i "\~= " p ( x _ i )
for all
.ie t $0 <= i < t$.
-.el \{\
-0 \(<=
-.I i
-<
-.IR t .
-.\}
+.el .RI "0\~\(<= " i \~<\~ t .
Hence
.ie t $p - q$
-.el \{\
-.I p
-\-
-.I q
-.\}
+.el .IR p \~\-\~ q
is a polynomial with degree at most
.ie t $t - 1$
-.el \{\
-.I t
-\- 1
-.\}
+.el .IR t \~\-\~1
but with at least
.I t
distinct zeros;
therefore
.ie t $q - p$
-.el \{\
-.I p
-\-
-.I q
-.\}
+.el .IR q \~\-\~ p
must be identically zero
and hence
.ie t $q == p$
-.el \{\
-.I q
-\(==
-.I p
-.\}
+.el .IR q \~\(==\~ p
and
.ie t $s = q(0)$.
-.el \{\
-.I s
-=
-.IR q (0).
-.\}
+.el .IR s "\~= " q (0).
.PP
Suppose we are given
.ie t $t - 1$
-.el \{\
-.I t
-\- 1
-.\}
+.el .IR t \~\-\~1
shares.
Then,
for any putative secret
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).
+.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 \{\
-.I x
-=
-.IR a _0
-+
-.IR a _1
-.I u
-+ ... +
-.IR a _7
-.IR u ^7
+.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
-+
-2
-.IR a _1
-+ ... +
-2^7
-.IR a _7.
+.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 \{\
-0 \(<=
-.I i
-<
-.IR n ;
-.\}
+.el .RI "0\~\(<= " i \~<\~ n ;
specifically, the share with index
.I i
is generated by
.el .IR p ( x )
where
.ie t $i = B(x) - 1$.
-.el \{\
-.I i
-=
-.IR B ( x )
-\- 1.
-.\}
+.el .IR i "\~= " B ( x )\~\-\~1.
.SH AUTHOR
Mark Wooding, <mdw@distorted.org.uk>
.SH SEE ALSO
--- /dev/null
+.\" -*-nroff-*-
+.ie t \{\
+. ds o \(bu
+. if \n(.g .fam P
+.\}
+.el \{\
+. ds o o
+.\}
+.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
+..
+.TH <name> 1 "<date>" "distorted.org.uk key management"
+.SH NAME
+<name> \- <summary>
+.SH SYNOPSIS
+...
+.SH DESCRIPTION
+...
+.SH AUTHOR
+Mark Wooding, <mdw@distorted.org.uk>
+.SH SEE ALSO
+.BR distorted-keys (7).