From: Mark Wooding Date: Thu, 5 May 2016 09:20:54 +0000 (+0100) Subject: Found in crybaby's working tree. X-Git-Url: http://www.chiark.greenend.org.uk/ucgi/~mdw/git/distorted-keys/commitdiff_plain/aa8478931ce8fa13b56f260da29241f38c18ab76?ds=sidebyside Found in crybaby's working tree. --- diff --git a/Makefile.am b/Makefile.am index aa7982b..62032bf 100644 --- a/Makefile.am +++ b/Makefile.am @@ -109,6 +109,7 @@ keyfunc.sh: keyfunc.sh.in Makefile ## 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 diff --git a/cryptop.list b/cryptop.list index abb51af..045a78c 100755 --- a/cryptop.list +++ b/cryptop.list @@ -47,7 +47,7 @@ separator character determines the behaviour as shown below. The default is 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 diff --git a/cryptop.recover b/cryptop.recover index c4b1e7f..f1fc9db 100755 --- a/cryptop.recover +++ b/cryptop.recover @@ -72,6 +72,7 @@ nubbin=$(nubid <$knub.new) case "$nubbin" in "$nubid") ;; *) + rm -f $knub.new echo >&2 "$quis: recovery produced incorrect nub" exit 1 ;; diff --git a/distorted-keys.7 b/distorted-keys.7 new file mode 100644 index 0000000..3070e31 --- /dev/null +++ b/distorted-keys.7 @@ -0,0 +1,35 @@ +.\" -*-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, +.SH SEE ALSO +.BR distorted-keys (7). diff --git a/keyfunc.sh.in b/keyfunc.sh.in index dca8dee..c68fec1 100644 --- a/keyfunc.sh.in +++ b/keyfunc.sh.in @@ -187,6 +187,19 @@ checkident () { check "$1" "$R_IDENT" "$2"; } 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. diff --git a/keys.delete-keeper b/keys.delete-keeper index 1e3f3ec..908e22e 100755 --- a/keys.delete-keeper +++ b/keys.delete-keeper @@ -32,34 +32,61 @@ KEEPER 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:" @@ -68,27 +95,26 @@ case "${deps+t}" in ;; 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 diff --git a/keys.forget-keeper b/keys.forget-keeper new file mode 100755 index 0000000..a6970c1 --- /dev/null +++ b/keys.forget-keeper @@ -0,0 +1,53 @@ +#! /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 <&2 "$quis: no nubs available for keeper set \`$keeper'" + exit 1 +fi + +## Delete them. +rm -rf $SAFE/keys.keeper/$keeper + +###----- That's all, folks -------------------------------------------------- diff --git a/keys.new-keeper b/keys.new-keeper index 78e792d..e14bb70 100755 --- a/keys.new-keeper +++ b/keys.new-keeper @@ -32,7 +32,8 @@ defhelp <&2 "$0: KEYSLIB unset"; exit 1 ;; esac +. "$KEYSLIB"/keyfunc.sh + +defhelp <&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 -------------------------------------------------- diff --git a/ktype.openssl b/ktype.openssl new file mode 100644 index 0000000..b058dbd --- /dev/null +++ b/ktype.openssl @@ -0,0 +1,134 @@ +### -*-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 <$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 -------------------------------------------------- diff --git a/shamir.1 b/shamir.1 index ce71a1e..dc5effc 100644 --- a/shamir.1 +++ b/shamir.1 @@ -136,15 +136,7 @@ any 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. @@ -332,12 +324,7 @@ Its slots are as follows. 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. @@ -351,85 +338,42 @@ Let 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 @@ -463,30 +407,17 @@ Then .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 @@ -511,72 +442,36 @@ Note that .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 @@ -613,54 +508,36 @@ This program uses the field 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 @@ -669,12 +546,7 @@ evaluating the polynomial .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, .SH SEE ALSO diff --git a/skel.1 b/skel.1 new file mode 100644 index 0000000..18ac4b1 --- /dev/null +++ b/skel.1 @@ -0,0 +1,35 @@ +.\" -*-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 1 "" "distorted.org.uk key management" +.SH NAME + \- +.SH SYNOPSIS +... +.SH DESCRIPTION +... +.SH AUTHOR +Mark Wooding, +.SH SEE ALSO +.BR distorted-keys (7).