--- /dev/null
+COPYING
+Makefile.in
+aclocal.m4
+autom4te.cache
+configure
+config
--- /dev/null
+COPYING
+config/auto-version
+config/confsubst
--- /dev/null
+### -*-makefile-*-
+###
+### Build script for distorted.org.uk key management
+###
+### (c) 2011 Mark Wooding
+###
+
+###----- Licensing notice ---------------------------------------------------
+###
+### This program 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.
+###
+### This program 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 this program; if not, write to the Free Software Foundation,
+### Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
+
+bin_SCRIPTS =
+dist_pkglib_SCRIPTS =
+pkglib_DATA =
+noinst_SCRIPTS =
+
+EXTRA_DIST =
+CLEANFILES =
+DISTCLEANFILES =
+
+###--------------------------------------------------------------------------
+### Substitution of configuration data.
+
+confsubst = $(top_srcdir)/config/confsubst
+EXTRA_DIST += config/confsubst
+
+SUBSTVARS = \
+ PACKAGE="$(PACKAGE)" VERSION="$(VERSION)" \
+ PYTHON="$(PYTHON)" \
+ bindir="$(bindir)" \
+ pkgconfdir="$(sysconfdir)/$(PACKAGE)" \
+ pkglibdir="$(pkglibdir)"
+
+SUBST = $(AM_V_GEN)$(confsubst)
+
+###--------------------------------------------------------------------------
+### Utility programs.
+
+## Shamir secret-sharing.
+bin_SCRIPTS += shamir
+EXTRA_DIST += shamir.in
+CLEANFILES += shamir
+shamir: shamir.in Makefile
+ $(SUBST) $(srcdir)/shamir.in $(SUBSTVARS) >shamir.new && \
+ chmod +x shamir.new && mv shamir.new shamir
+
+###--------------------------------------------------------------------------
+### Main driver program and commands.
+
+## Main driver.
+bin_SCRIPTS += keys
+EXTRA_DIST += keys.in
+CLEANFILES += keys
+keys: keys.in Makefile
+ $(SUBST) $(srcdir)/keys.in $(SUBSTVARS) >keys.new && \
+ chmod +x keys.new && mv keys.new keys
+
+## Utilities library.
+pkglib_DATA += keyfunc.sh
+EXTRA_DIST += keyfunc.sh.in
+CLEANFILES += keyfunc.sh
+keyfunc.sh: keyfunc.sh.in Makefile
+ $(SUBST) $(srcdir)/keyfunc.sh.in $(SUBSTVARS) >keyfunc.sh.new && \
+ mv keyfunc.sh.new keyfunc.sh
+
+## Commands.
+dist_pkglib_SCRIPTS += keeper-cards
+dist_pkglib_SCRIPTS += new-keeper
+dist_pkglib_SCRIPTS += new-recov
+dist_pkglib_SCRIPTS += reveal
+
+###----- That's all, folks --------------------------------------------------
--- /dev/null
+distorted.org.uk KEY MANAGEMENT
+
+The various files are organized into subdirectories as follows.
+
+infra/ Infrastructure keys used to keep this system going.
+recov/
+
+File extensions used are as follows.
+
+.pub Seccure public key. (See description of Seccure data
+ formats below.)
+
+.recov Seccure ciphertext of key
+
+
+
+recov.pub `seccure' public key for recovery
+
+krb5-master Kerberos master password
+bkp-LABEL LUKS keyfile for backup volume LABEL
+disk-HOST LUKS keyfile for HOST's disk
+
+keys/
+|- keeper/
+| '- KEEPER/
+| |- meta
+| '- I.pub
+|- key/
+| '- ???
+'- recov/
+ '- RECOV/
+ |- keepers
+ |- current@
+ '- I/
+ |- pub
+ |- KEEPER.param
+ |- KEEPER.I.share
+ '- SECRET.recov
+
+
+* Reference
+
+** Asymmetric cryptography
+
+I've used B. Poettering's Seccure package for my asymmetric
+cryptography. It's been in Debian for a fair while and seems sane. If
+you're interested in what it does, I wrote my own implementation in
+Python. It seems pretty sensible, actually. It uses ECIES with AES
+in counter mode, and SHA256-HMAC for asymmetric encryption, and a
+variant of ECDSA with SHA512 for signatures.
+
+Seccure wants to read a single line of stuff as a passphrase. I use
+this rune to generate a public key.
+
+ dd if=/dev/random of=master bs=1 count=512 |
+ openssl sha384 -binary >priv
+
+To derive the public key, I say this:
+
+ openssl base64 -in priv | seccure-key -q -F/dev/stdin -cp256 >pub
+
+For encryption, I use a 128-bit MAC. For decryption, you need this rune.
+
+ openssl base64 -in priv |
+ seccure-decrypt -q -F/dev/stdin -m128 ciphertext
+
+** Secret sharing
+
+I've written my own tool for doing Shamir secret sharing. The
+underlying machinery is compatible with Daniel Silverstone's `gfshare'
+program and my Catacomb library's secret sharing. My `shamir' program
+has a number of important differences:
+
+ * it produces output as plain text files which can be transported
+ easily and so on;
+
+ * it includes metadata, such as the number of shares, the threshold,
+ and a hash of the final secret, along with the share data;
+
+ * it stores the share index with the share data too, rather than
+ encoding it in the file name where it's likely to be lost; and
+
+ * it doesn't choose random share indices when issuing shares,
+ because that's pointless.
+
+The `shamir issue' command writes one line for each share that it
+produces. I use this rune to split them into separate files.
+
+ shamir issue 3/5 master |
+ sed 's/^.*;i=\([^;]*\);/\1 &/' |
+ while read i share; do
+ echo $share >master.$i
+ done
+
+You can recover the original secret by feeding shares, one per line,
+into `shamir recover'. All of the parameters are in the share data,
+so you don't need to know any of them. (I used the defaults anyway,
+since I carefully chose them to match what I wanted.)
+
+A share line has the following format:
+
+ shamir-share:KEY=VALUE;KEY=VALUE;...
+
+where the following keys are defined (they must appear in this order):
+
+ * n = total number of shares issued;
+ * t = threshold (i.e., number of shares needed for recovery);
+ * f = hash function name (an OpenSSL name, e.g., `sha256');
+ * h = base-64 encoded hash of the secret (using hash function `f');
+ * i = index of this share (starting from 0); and
+ * y = base-64 share data.
+
+You can turn such a file of such lines into files suitable for
+`gfcombine' like this:
+
+ sed 's/^.*;i=\(.*\);y=\(.*\)$/\1 \2/' |
+ while read i sh; do
+ ix=$(printf %03d $((i + 1)))
+ echo $sh | openssl base64 -d >tmp/share.$ix
+ done
--- /dev/null
+dnl -*-autoconf-*-
+dnl
+dnl Configuration script for distorted.org.uk key management
+dnl
+dnl (c) 2011 Mark Wooding
+dnl
+
+dnl----- Licensing notice ---------------------------------------------------
+dnl
+dnl This program is free software; you can redistribute it and/or modify
+dnl it under the terms of the GNU General Public License as published by
+dnl the Free Software Foundation; either version 2 of the License, or
+dnl (at your option) any later version.
+dnl
+dnl This program is distributed in the hope that it will be useful,
+dnl but WITHOUT ANY WARRANTY; without even the implied warranty of
+dnl MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+dnl GNU General Public License for more details.
+dnl
+dnl You should have received a copy of the GNU General Public License
+dnl along with this program; if not, write to the Free Software Foundation,
+dnl Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
+
+dnl--------------------------------------------------------------------------
+dnl Initialization.
+
+mdw_AUTO_VERSION
+AC_INIT([distorted-keys], AUTO_VERSION, [mdw@distorted.org.uk])
+AC_CONFIG_SRCDIR([shamir.in])
+AC_CONFIG_AUX_DIR([config])
+AM_INIT_AUTOMAKE([foreign])
+mdw_SILENT_RULES
+
+dnl--------------------------------------------------------------------------
+dnl Python programming environment.
+
+AC_PATH_PROG([PYTHON], [python])
+AX_PROG_PYTHON_VERSION([2.5],,
+ [AC_MSG_ERROR([Failed to find suitable Python.])])
+
+dnl--------------------------------------------------------------------------
+dnl Output.
+
+AC_CONFIG_FILES(
+ [Makefile])
+AC_OUTPUT
+
+dnl----- That's all, folks --------------------------------------------------
--- /dev/null
+#! /bin/sh
+###
+### Issue cards containing a bunch of keeper secrets
+###
+### (c) 2011 Mark Wooding
+###
+
+###----- Licensing notice ---------------------------------------------------
+###
+### This program 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.
+###
+### This program 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 this program; 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 [INDICES ...]
+Typeset cards for a set of keeper secrets.
+
+This program writes a file KEEPER.ps which will contain private keys from the
+keeper set KEEPER, specifically the keys with the given INDICES. Elements of
+the list are either simple integers or ranges [LOW]-[HIGH]; if LOW is
+omitted, it means 0, and if HIGH is omitted, it means the highest possible
+index. If no INDICES are given then all secret keys are written.
+
+The public keys are found in $KEYS/keeper/KEEPER/I.pub;
+private keys are read from KEEPER/I in the current directory.
+HELP
+dohelp
+
+## Parse the command line.
+case $# in 0) echo >&2 "$usage"; exit 1 ;; esac
+keeper=$1; shift
+checkword "keeper set label" "$keeper"
+read n hunoz <$KEYS/keeper/$keeper/meta
+
+## Build a colon-separated list of the indices we actually want.
+want=:
+case $# in 0) set 0- ;; esac
+for range in "$@"; do
+ case "$range" in
+ *[!-0-9]* | *[!0-9]*-* | *-*[!0-9]*)
+ echo >&2 "$quis: bad index range \`$range'"
+ exit 1
+ ;;
+ *-*)
+ low=${range%-*} high=${range#*-}
+ ;;
+ *)
+ low=$range high=$range
+ ;;
+ esac
+ case "$low" in ?*) ;; *) low=0 ;; esac
+ case "$high" in ?*) ;; *) high=$((n - 1)) ;; esac
+ if [ 0 -gt $low -o $low -gt $high -o $high -ge $n ]; then
+ echo >&2 "$quis: invalid index range \`$range'"
+ exit 1
+ fi
+ i=$((low + 0))
+ while [ $i -le $high ]; do
+ case $want in *:"$i":*) ;; *) want=$want$i: ;; esac
+ i=$((i + 1))
+ done
+done
+
+## Start working on the output file. This will contain deep secrets, so
+## don't leave stuff easily readable.
+tmp=$(mktmp); cleanup rmtmp
+umask 077
+exec 3>$tmp/$keeper.tex
+cat >&3 <<'EOF'
+\documentclass[a4paper, landscape, 12pt]{article}
+\usepackage[utf8]{inputenc}
+\usepackage[T1]{fontenc}
+\usepackage[palatino, helvetica, courier, maths = cmr]{mdwfonts}
+\usepackage{graphicx}
+
+%% Report errors with enough context that we can debug them.
+\errorcontextlines=999
+
+%% Basic layout for the cards. We use the paragraph filling machinery, but
+%% don't actually need most of the trimmings.
+\parindent=0pt
+\parfillskip=0pt
+\pagestyle{empty}
+
+%% Page layout: try to use most of the page. The document class will already
+%% have set up the paper size, but we do the rest here.
+\hoffset=-1in \voffset=-1in
+\oddsidemargin=20mm
+\textwidth=\paperwidth \advance\textwidth by -2\oddsidemargin
+\topmargin=20mm
+\headheight=0pt \headsep=0pt
+\textheight=\paperheight \advance\textheight by -2\topmargin
+\AtBeginDocument{\special{papersize=\the\paperwidth,\the\paperheight}}
+
+%% Parameters for the cards and guide rules.
+\newdimen\cardwd \cardwd=82mm
+\newdimen\cardht \cardht=49mm
+\newdimen\guidelen \guidelen=10mm
+\newdimen\rulewd \rulewd=0.6pt
+
+%% Typesetting the secret as text. The macro \snarf TOKEN T0 T1 ... T7
+%% gathers T0 T1 ... T7 into a single argument and passes them to TOKEN, as
+%% long as T0 is not \relax. We use this to process the secret text in a
+%% continuation-passing style.
+\def\snarf#1#2{%
+ \ifx#2\relax\let\next\empty%
+ \else\def\next{\snarfdo#1#2}%
+ \fi%
+ \next%
+}
+\def\snarfdo#1#2#3#4#5#6#7#8#9{#1{#2#3#4#5#6#7#8#9}}
+
+%% Print the left and right halves of the line, with a separator. Use boxes
+%% for the lines so that TeX will work out the width of the enclosing vbox
+%% for us. The basic usage is \line TEXT \relax ... \relax, with eight
+%% \relax tokens: this is enough to complete both \snarf calls.
+\def\line{\snarf\lineleft}
+\def\lineleft#1{\hbox\bgroup#1 \snarf\lineright}
+\def\lineright#1{#1\egroup\line}
+
+%% Typeset a card containing a secret. Usage is \card{INDEX}{SECRET}.
+\def\card#1#2{%
+ %%
+ %% Make sure we're setting a paragraph.
+ \leavevmode%
+ %%
+ %% Initial material: a stretchy space on the left.
+ \hbox{}\nobreak\hfil%
+ %%
+ %% An alignment for the guide markers surrounding the actual card.
+ \vbox{\halign{&##\cr%
+ %%
+ %% Top left guides.
+ \vrule width \guidelen height \rulewd depth 0pt%
+ \vrule width \rulewd depth 0pt height \guidelen%
+ &%
+ %%
+ %% Top centre gap.
+ \hfil%
+ &%
+ %%
+ %% Top right guides.
+ \vrule width \rulewd depth 0pt height \guidelen%
+ \vrule width \guidelen height \rulewd depth 0pt%
+ \cr%
+ %%
+ %% Left gap.
+ &%
+ %%
+ %% The actual card.
+ \vbox to \cardht{%
+ %%
+ %% We actually do more or less sensible typesetting. TeX will set the
+ %% box width from the hsize, and we should leave a small margin all
+ %% around.
+ \parfillskip=0pt plus 1fil%
+ \leftskip=1em \rightskip=1em%
+ \hsize=\cardwd%
+ %%
+ %% The heading.
+ \hrule height 0pt \prevdepth = 0pt%
+ \medskip%
+ {\large\bfseries\textsf{\keeper} secret #1/\total}%
+ %%
+ %% The QR-code and the text of the secret.
+ \vfil%
+ $%
+ \vcenter{\hbox{\includegraphics[scale = 2.4]{#1.eps}}}%
+ \hfil%
+ \vcenter{\ttfamily%
+ \line#2%
+ \relax\relax\relax\relax\relax\relax\relax\relax%
+ }%
+ $%
+ %%
+ %% And we're done.
+ \vfil%
+ }%
+ &%
+ %%
+ %% Right gap.
+ \cr%
+ %%
+ %% Bottom left guides.
+ \vrule width \guidelen depth \rulewd height 0pt%
+ \vrule width \rulewd depth \guidelen height 0pt%
+ &%
+ %% Bottom centre gap.
+ \hfil%
+ &%
+ %% Bottom right guides.
+ \vrule width \rulewd depth \guidelen height 0pt%
+ \vrule width \guidelen depth \rulewd height 0pt%
+ \cr%
+ %%
+ %% Leave a small vertical space at the bottom to separate lines of cards.
+ \strut \cr%
+ }}%
+ %%
+ %% End material: a stretchy space to match the one at the start, and then
+ %% allow a break.
+ \nobreak\hfil\hbox{}%
+ \penalty0%
+}
+EOF
+
+## Write the basic configuration stuff.
+cat >&3 <<EOF
+
+%% General configuration for the cards.
+\def\keeper{$keeper}
+\def\total{$n}
+EOF
+
+## Start the document body.
+cat >&3 <<'EOF'
+
+%% The actual content.
+\begin{document}
+EOF
+
+## Work through the requested indices.
+i=0
+while [ $i -lt $n ]; do
+ case $want in
+ *:"$i":*)
+ read secret <$keeper/$i
+ tr -d '\n' <$keeper/$i | qrencode -m0 -s1 -o$tmp/$i.png
+ convert $tmp/$i.png $tmp/$i.eps
+ cat >&3 <<EOF
+\card{$i}{$secret}
+EOF
+ esac
+ i=$((i + 1))
+done
+
+## Wrap up and build the document.
+cat >&3 <<'EOF'
+\end{document}
+EOF
+exec 3>&-
+if ! (cd $tmp
+ exec </dev/null >tex.out 2>&1
+ latex $keeper.tex && dvips -o$keeper.ps $keeper.dvi); then
+ echo >&2 "$quis: document formatting failed"
+ sed >&2 's/^/| /' $tmp/tex.out
+ exit 1
+fi
+cp $tmp/$keeper.ps .
+
+###----- That's all, folks --------------------------------------------------
--- /dev/null
+### -*-sh-*-
+###
+### Common key management functions.
+###
+### (c) 2011 Mark Wooding
+###
+
+###----- Licensing notice ---------------------------------------------------
+###
+### This program 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.
+###
+### This program 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 this program; if not, write to the Free Software Foundation,
+### Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
+
+quis=${0##*/}
+
+###--------------------------------------------------------------------------
+### Configuration variables.
+
+PACKAGE="@PACKAGE@" VERSION="@VERSION@"
+pkgconfdir="@pkgconfdir@" pkglibdir="@pkglibdir@"
+bindir="@bindir@"
+
+case ":$PATH:" in *:"$bindir":*) ;; *) PATH=$bindir:$PATH ;; esac
+
+###--------------------------------------------------------------------------
+### Cleanup handling.
+
+cleanups=""
+cleanup () { cleanups="$cleanups $1"; }
+trap 'rc=$?; for i in $cleanups; do $i; done; exit $rc' EXIT
+trap 'exit 127' INT TERM
+
+###--------------------------------------------------------------------------
+### Utility functions.
+
+## Temporary directory.
+unset tmp
+rmtmp () { cd /; rm -rf $tmp; }
+mktmp () {
+ ## Make and return the name of a temporary directory.
+
+ case "${tmp+t}" in t) echo "$tmp"; return ;; esac
+ mem=$(userv root claim-mem-dir)
+ tmp="$mem/keys.tmp.$$"
+ rm -rf "$tmp"
+ mkdir -m700 "$tmp"
+ echo "$tmp"
+}
+
+###--------------------------------------------------------------------------
+### Input validation functions.
+
+checknumber () {
+ what=$1 thing=$2
+ case "$thing" in
+ "" | [!1-9]* | *[!0-9]*)
+ echo >&2 "$quis: bad $what \`$thing'"
+ exit 1
+ ;;
+ esac
+}
+
+checkword () {
+ what=$1 thing=$2
+ case "$thing" in
+ "" | *[!-0-9a-zA-Z_!%@+=]*)
+ echo >&2 "$quis: bad $what: \`$thing'"
+ exit 1
+ ;;
+ esac
+}
+
+###--------------------------------------------------------------------------
+### Crypto operations.
+###
+### We use Seccure for this, but it's interface is Very Annoying.
+
+run_seccure () {
+ op=$1; shift
+ ## run_seccure OP ARG ...
+ ##
+ ## Run a Seccure program, ensuring that its stderr is reported if it had
+ ## anything very interesting to say, but suppressed if it was boring.
+
+ ## We need a temporary place for the error output.
+ case ${tmp+t} in
+ t) ;;
+ *)
+ echo >&2 "$quis (INTERNAL): run_seccure called without tmpdir"
+ exit 127
+ ;;
+ esac
+
+ ## Run the program.
+ set +e; seccure-$op "$@" 2>$tmp/seccure.out; rc=$?; set -e
+ grep -v '^WARNING: Cannot obtain memory lock' $tmp/seccure.out >&2 || :
+ return $rc
+}
+
+ec_public () {
+ private=$1
+ ## Write the public key corresponding to PRIVATE to stdout.
+
+ run_seccure key -q -cp256 -F"$private"
+}
+
+ec_keygen () {
+ private=$1 public=$2
+ ## Make a new key, write private key to PRIVATE and public key to PUBLIC.
+
+ dd if=/dev/random bs=1 count=512 2>/dev/null |
+ openssl sha384 -binary |
+ (umask 077 && openssl base64 >"$private")
+ ec_public "$private" >"$public"
+}
+
+ec_encrypt () {
+ public=$1; shift
+ ## Encrypt stuff using the PUBLIC key. Use -i/-o or redirection.
+
+ run_seccure encrypt -q -cp256 -m128 "$@" -- $(cat "$public")
+}
+
+ec_decrypt () {
+ private=$1; shift
+ ## Decrypt stuff using the PRIVATE key. Use -i/-o or redirection.
+
+ run_seccure decrypt -q -cp256 -m128 -F"$private" "$@"
+}
+
+###--------------------------------------------------------------------------
+### Help text.
+
+dohelp () {
+ case "$KEYS_HELP" in t) ;; *) return ;; esac
+ help; exit
+}
+
+defhelp () { read umsg; usage="usage: $quis${umsg+ }$umsg"; help=$(cat); }
+help () { showhelp; }
+showhelp () {
+ cat <<EOF
+$usage
+
+$help
+EOF
+}
+
+###----- That's all, folks --------------------------------------------------
--- /dev/null
+#! /bin/sh
+###
+### Front-end dispatch for key-management scripts
+###
+### (c) 2011 Mark Wooding
+###
+
+###----- Licensing notice ---------------------------------------------------
+###
+### This program 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.
+###
+### This program 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 this program; if not, write to the Free Software Foundation,
+### Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
+
+set -e
+
+quis=${0##*/}
+PACKAGE=@PACKAGE@
+VERSION=@VERSION@
+
+: ${KEYS=@pkgconfdir@}
+: ${KEYSLIB=@pkglibdir@}
+export KEYS KEYSLIB
+
+###--------------------------------------------------------------------------
+### Help.
+
+usage="usage: $quis COMMAND [ARGUMENTS ...]"
+
+version () {
+ echo "$PACKAGE version $VERSION"
+}
+
+help () {
+ rc=0
+ version
+ case $# in
+ 0)
+ cat <<EOF
+
+$usage
+
+Options:
+ -h Show this help text.
+ -v Show the program version number.
+
+Commands installed:
+EOF
+ cd "$KEYSLIB"
+ for i in *; do
+ case "$i" in *.*) continue ;; esac
+ if [ ! -x "$i" ]; then continue; fi
+ sed -n "/<<HELP/{n;s/^/ $i /;p;q;}" "$i"
+ done
+ ;;
+ *)
+ for i in "$@"; do
+ echo
+ if [ ! -x "$KEYSLIB"/"$i" ]; then
+ echo >&2 "$quis: unrecognized command \`$i'"
+ rc=1
+ continue
+ elif ! KEYS_HELP=t "$KEYSLIB"/"$i"; then
+ rc=1
+ fi
+ done
+ ;;
+ esac
+ return $rc
+}
+
+###--------------------------------------------------------------------------
+### Command dispatch.
+
+while getopts "hv" opt; do
+ case "$opt" in
+ h) help; exit ;;
+ v) version; exit ;;
+ *) echo >&2 "$usage"; exit 1 ;;
+ esac
+done
+shift $((OPTIND - 1))
+
+case $# in 0) echo >&2 "$usage"; exit 1 ;; esac
+cmd=$1; shift
+case "$cmd" in help) help "$@"; exit ;; esac
+if [ ! -x "$KEYSLIB"/"$cmd" ]; then
+ echo >&2 "$quis: unrecognized command \`$cmd'"
+ exit 1
+fi
+
+unset KEYS_HELP
+exec "$KEYSLIB"/"$cmd" "$@"
+
+###----- That's all, folks --------------------------------------------------
--- /dev/null
+#! /bin/sh
+###
+### Construct a new set of keeper keys
+###
+### (c) 2011 Mark Wooding
+###
+
+###----- Licensing notice ---------------------------------------------------
+###
+### This program 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.
+###
+### This program 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 this program; 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 N
+Create a new set of keeper keys.
+
+The private keys are stored in KEEPER/I for each 0 <= I < N in the current
+directory; presumably you'll do something sensible with them. A new
+directory $KEYS/keeper/KEEPER is created (it is an error if it already
+exists), containing the public keys I.pub and some metadata meta.
+HELP
+dohelp
+
+## Parse the command line.
+case $# in 2) ;; *) echo >&2 "$usage"; exit 1 ;; esac
+keeper=$1 n=$2
+checkword "keeper set label" "$keeper"
+checknumber "set size" "$n"
+
+## Preflight checking.
+if [ -e $KEYS/keeper/$keeper ]; then
+ echo >&2 "$0: keeper set \`$keeper' already exists"
+ exit 1
+fi
+if [ -e $keeper ]; then
+ echo >&2 "$0: destination \`$keeper' already exists"
+ exit 1
+fi
+
+## Generate the private keys, one per file, and compute the public keys.
+tmp=$(mktmp); cleanup rmtmp
+rm -rf $keeper.new
+mkdir -m700 $keeper.new
+mkdir -p -m755 $KEYS/keeper/$keeper.new
+echo $n >$KEYS/keeper/$keeper.new/meta
+i=0
+while [ $i -lt $n ]; do
+ ec_keygen $keeper.new/$i $KEYS/keeper/$keeper.new/$i.pub
+ i=$(( i + 1 ))
+done
+mv $keeper.new $keeper
+mv $KEYS/keeper/$keeper.new $KEYS/keeper/$keeper
+
+###----- That's all, folks --------------------------------------------------
--- /dev/null
+#! /bin/sh
+###
+### Generate a new recovery key and split it among keepers
+###
+### (c) 2011 Mark Wooding
+###
+
+###----- Licensing notice ---------------------------------------------------
+###
+### This program 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.
+###
+### This program 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 this program; 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 [KEEPER:K ...]
+Generate a new recovery secret, and split it among the available keepers.
+
+The new secret will be called RECOV. For each KEEPER set, the private key
+wil be split into shares, and encrypted with the KEEPER's public keys; any K
+of these shares can be used to reveal the original key.
+
+If there is already a recovery key called RECOV then it will be rolled over.
+The previous key must already be revealed. If KEEPERs are listed, these
+replace the existing keeper sets; otherwise the same keepers as before are
+used.
+
+If there is not a recovery key called RECOV then at least one keeper set must
+be specified.
+HELP
+dohelp
+
+## Parse the command line.
+case $# in 0) echo >&2 "$usage"; exit 1 ;; esac
+recov=$1; shift
+checkword "recovery key label" "$recov"
+for k in "$@"; do
+ case "$k" in
+ *:*) ;;
+ *) echo >&2 "$quis: bad keeper spec \`$k'"; exit 1 ;;
+ esac
+ keeper=${k%:*} t=${k#*:}
+ checkword "keeper set label" "$keeper"
+ checknumber "keeper quorum" "$t"
+done
+
+## Establish the keeper parameters.
+rdir=$KEYS/recov/$recov
+if [ ! -d $rdir ]; then mkdir -m755 -p $rdir; fi
+case $# in
+ 0)
+ kparam=$rdir/keepers
+ ;;
+ *)
+ for k in "$@"; do
+ keeper=${k%:*} t=${k#*:}
+ echo $keeper $t
+ done >$rdir/keepers.new
+ kparam=$rdir/keepers.new
+ ;;
+esac
+if [ ! -f $kparam ]; then echo >&2 "$quis: no keepers specified"; exit 1; fi
+
+## Make the new key and issue the shares.
+tmp=$(mktmp); cleanup rmtmp
+rm -rf $rdir/new
+mkdir -m755 $rdir/new
+cd $tmp
+ec_keygen secret $rdir/new/pub
+while read keeper k; do
+ read n hunoz <$KEYS/keeper/$keeper/meta
+ shamir issue $k/$n secret | {
+ read param
+ echo "$param" >$rdir/new/$keeper.param
+ i=0
+ while read share; do
+ echo $share |
+ ec_encrypt $KEYS/keeper/$keeper/$i.pub -o$rdir/new/$keeper.$i.share
+ i=$(( i + 1 ))
+ done
+ }
+done <$kparam
+rm -f secret
+
+## If there's an existing instance of this key, transfer the recovery blobs.
+if [ ! -d $rdir/current ]; then
+ seq=0
+else
+ seq=$(readlink $rdir/current)
+ mem=$(userv root claim-mem-dir)
+ reveal=$mem/keys.reveal.$recov.current/secret
+ if [ ! -f $reveal ]; then
+ echo >&2 "$quis: current $recov key not revealed"
+ exit 1
+ fi
+ find $rdir/current -type f -name '*.recov' -print | while read name; do
+ name=${name#$rdir/current/}
+ case "$name" in */*) mkdir -p -m755 $rdir/new/${name%/*} ;; esac
+ ec_decrypt $reveal -i$rdir/current/$name |
+ ec_encrypt $rdir/new/pub -o$rdir/new/$name
+ done
+fi
+
+## Tidy up and commit.
+cd $rdir
+while [ -d $seq ]; do seq=$(( seq + 1 )); done
+case $kparam in *.new) mv keepers.new keepers ;; esac
+rm -f next
+ln -s $seq next
+mv new $seq
+mv next current
+
+###----- That's all, folks --------------------------------------------------
--- /dev/null
+#! /bin/sh
+###
+### Reveal shares of a secret distributed among keepers
+###
+### (c) 2011 Mark Wooding
+###
+
+###----- Licensing notice ---------------------------------------------------
+###
+### This program 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.
+###
+### This program 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 this program; 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 KEEPER [KEY]
+Reveal a share of a recovery key distributed among keepers.
+
+If enough shares have been revealed, reconstruct the recovery private key.
+The key is read from KEY, or stdin if KEY is omitted or \`-'.
+HELP
+dohelp
+
+## Parse the command line.
+case $# in
+ 2) if [ -t 0 ]; then echo >&2 "$quis: stdin is a terminal"; exit 1; fi ;;
+ 3) ;;
+ *) echo >&2 "$usage"; exit 1 ;;
+esac
+recov=$1 keeper=$2; shift 2
+case "$recov" in
+ *[!-0-9a-zA-Z_!%@+=/]* | */ | /* | \
+ *[!-0-9a-zA-Z_!%@+=]*/* | */*[!-0-9a-zA-Z_!%@+=]*)
+ echo >&2 "$quis: bad recovery key label \`$recov'"
+ exit 1
+ ;;
+ */*)
+ ;;
+ *)
+ recov=$recov/current
+esac
+checkword "keeper set label" "$keeper"
+
+## Grab the key, because we'll need to read it several times.
+tmp=$(mktmp); cleanup rmtmp
+secret=$(cat "$@")
+pub=$(ec_public /dev/stdin <<EOF
+$secret
+EOF
+)
+
+## Read the threshold from the recovery metadata.
+read param <$KEYS/recov/$recov/$keeper.param
+case "$param" in
+ shamir-params:*) ;;
+ *)
+ echo >&2 "$quis: secret sharing parameter file damaged (wrong header)"
+ exit 1
+ ;;
+esac
+t=";${param#*:}"
+case "$t" in
+ *";t="*) ;;
+ *)
+ echo >&2 "$quis: secret sharing parameter file damaged (missing t)"
+ exit 1
+ ;;
+esac
+t=${t#*;t=}
+t=${t%%;*}
+
+## Find out which keeper index it corresponds to.
+read n hunoz <$KEYS/keeper/$keeper/meta
+i=0
+foundp=nil
+while [ $i -lt $n ]; do
+ read cand <$KEYS/keeper/$keeper/$i.pub
+ case "$pub" in "$cand") foundp=t; break ;; esac
+ i=$(( i + 1 ))
+done
+case $foundp in
+ nil) echo >&2 "$quis: key doesn't match keeper \`$keeper'"; exit 1 ;;
+esac
+
+## Establish the recovery staging area. See whether we've done enough
+## already.
+mem=$(userv root claim-mem-dir)
+tag=$(echo $recov | tr / .)
+if [ -d $mem/keys.reveal.$tag ]; then
+ echo >&2 "$quis: secret $recov already revealed"
+ exit 1
+fi
+reveal=$mem/keys.reveal.$tag.$keeper
+if [ ! -d $reveal ]; then mkdir -m700 $reveal; fi
+cd $reveal
+if [ -f share.$i ]; then
+ echo >&2 "$quis: share $i already revealed"
+ exit 1
+fi
+
+## Decrypt the share.
+ec_decrypt /dev/stdin \
+ -i$KEYS/recov/$recov/$keeper.$i.share \
+ -oshare.$i.new <<EOF
+$secret
+EOF
+mv share.$i.new share.$i
+
+## See if there's enough for a recovery.
+n=0
+for j in share.*; do if [ -f "$j" ]; then n=$(( n + 1 )); fi; done
+if [ $n -lt $t ]; then
+ echo >&2 "$quis: share $i revealed; $(( t - n )) more required"
+else
+ cat $KEYS/recov/$recov/$keeper.param share.* | shamir recover >secret
+ pubx=$(ec_public secret)
+ puby=$(cat $KEYS/recov/$recov/pub)
+ case "$pubx" in
+ "$puby") ;;
+ *)
+ echo >&2 "quis: recovered secret key doesn't match public key"
+ exit 1
+ ;;
+ esac
+ cd ..
+ mv keys.reveal.$tag.$keeper keys.reveal.$tag
+ echo >&2 "$quis: secret $recov revealed"
+fi
+
+###----- That's all, folks --------------------------------------------------
--- /dev/null
+#! @PYTHON@
+###
+### Shamir secret sharing
+###
+### (c) 2011 Mark Wooding
+###
+
+###----- Licensing notice ---------------------------------------------------
+###
+### This program 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.
+###
+### This program 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 this program; if not, write to the Free Software Foundation,
+### Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
+
+from __future__ import with_statement
+
+import sys as SYS
+import os as OS
+import hashlib as H
+import base64 as B
+from cStringIO import StringIO
+import optparse as OPT
+
+###--------------------------------------------------------------------------
+### Arithmetic in GF(2^8).
+###
+### These functions implement arithmetic in a field containing exactly 256
+### elements. This is convenient, because there's exactly one field element
+### for each one-byte value.
+###
+### Actually, we only implement multiplication and division, because addition
+### and subtraction are trivial -- they're the XOR operation that Python
+### already has. Multiplication and (especially) division are fiddly if you
+### do them directly, but the field is easily small enough that log tables
+### are a feasible alternative.
+###
+### There are many (isomorphic) representations of the field GF(2^8). The
+### one we use here is a field of residue classes of binary polynomials:
+### GF(2)[x]/(x^8 + x^4 + x^3 + x^2 + 1). Usefully, the element [x] (i.e.,
+### the residue class containing x) generates the multiplicative group of the
+### field: every nonzero element can be written in the form x^k for some
+### integer 0 <= k < 255. Multiplication by x is especially easy, so this is
+### a good choice as a base of logarithms.
+###
+### More precisely, we use an integer encoding of the residue classes. Each
+### class contains exactly one polynomial of degree less than 8, called the
+### principal representative. If the principal representative of a residue
+### class is a_7 x^7 + ... + a_1 x + a_0, with each a_i either 0 or 1, then
+### the encoding of the representative is 2^7 a_7 + ... + 2 a_1 + a_0. It is
+### easily verified that this mapping is invertible.
+
+def gf28_log_tables():
+ """Build the log tables used to implement GF(2^8) arithmetic."""
+ global GF28_LOG, GF28_EXP
+ log = [0] * 256
+ exp = [0] * 256
+ x = 1
+ for i in xrange(255):
+ exp[i] = x
+ log[x] = i
+ x <<= 1
+ if x & 0x100:
+ x ^= 0x11d
+ GF28_LOG = log
+ GF28_EXP = exp[:255] * 2
+gf28_log_tables()
+
+def gf28_mul(x, y):
+ """Multiply two elements X and Y of GF(2^8), retturning their product."""
+ if x == 0 or y == 0: return 0
+ else: return GF28_EXP[GF28_LOG[x] + GF28_LOG[y]]
+
+def gf28_div(x, y):
+ """
+ Divide element X by Y in GF(2^8), returning the quotient.
+
+ Raise `ZeroDivisionError' if Y is zero.
+ """
+ if y == 0: raise ZeroDivisionError
+ elif x == 0: return 0
+ else: return GF28_EXP[GF28_LOG[x] + 255 - GF28_LOG[y]]
+
+###--------------------------------------------------------------------------
+### Secret sharing machinery.
+###
+### Shamir's secret sharing scheme uses polynomial interpolation. Let K be a
+### finite field, and let s -- the `secret' -- be an element of K. Let t --
+### the `threshold' -- be a positive integer. A degree-(t - 1) polynomial
+### p(x) over K has the general form a_{t-1} x^{t-1} + ... + a_1 x + a_0; we
+### then have p(0) = a_0. If we choose a_0 = s, and the other a_i uniformly
+### at random from K, then we have chosen a degree-(t - 1) polynomial
+### uniformly at random, subject to the restrictiion that it evaluates to s
+### at 0. We can issue shares of the form (x, p(x)) for 0 < x < #K.
+###
+### Any collection of t shares can be used to reconstruct the polynomial. We
+### can use Lagrange interpolation to do this. Suppose that we're given t
+### different shares (x_i, y_i) for 0 <= i < t. Firstly, set
+###
+### ------- x - x_j
+### l_i(x) = | | ---------
+### | | x_i - x_j
+### 0 <= j < t
+### j /= i
+###
+### Now notice that l_i(x_i) = 1 and l_i(x_j) = 0 if j /= i. Then
+###
+### ----
+### p(x) = > l_i(x) y_i
+### ----
+### 0 <= i < t
+###
+### To see this, it suffices to note that (a) l_i(x) (and therefore the sum)
+### is a degree-(t - 1) polynomial, and (b) it agrees with p(x) at t distinct
+### points, namely each of the x_i. So, with t shares, we can recover the
+### original polynomial, and hence p(0) = s. With t - 1 shares, we can add a
+### fake `share' (0, s') for any guessed s' in K and interpolate
+### corresponding values for the remaining shares; we therefore have perfect
+### secrecy.
+###
+### We use K = GF(2^8), as implemented above. Each byte of a long secret is
+### shared independently.
+###
+### All of this machinery is the same as in my Catacomb library and Daniel
+### Silverstone's `gfshare' package.
+
+class SecretSplit (object):
+ """
+ Create shares of a secret.
+
+ Initialize with a secret S and a threshold T; then issue shares with the
+ `issue' method.
+ """
+
+ def __init__(me, s, t):
+ """
+ Initialize secret sharing.
+
+ S is a string containing the secret; T is the threshold, i.e., the number
+ of shares requierd to recover the secret.
+ """
+
+ ## The number of bytes in the secret is a useful thing to store.
+ me._n = len(s)
+
+ ## Build an array of coefficients chosen at random.
+ me._coeffs = [OS.urandom(me._n) for i in xrange(t - 1)] + [s]
+
+ def issue(me, x):
+ """
+ Issue the share with index X, returning it as a string.
+
+ The share will be binary, even if the original secret is plain text. The
+ index must be in the range 1 <= X <= 255.
+ """
+
+ ## Check that the index is in range.
+ if x < 1 or x > 255:
+ raise ValueError, 'share index out of range'
+
+ ## Evaluate the polynomial at the chosen index.
+ o = StringIO()
+ for i in xrange(me._n):
+ y = 0
+ for j in me._coeffs:
+ y = gf28_mul(x, y) ^ ord(j[i])
+ o.write(chr(y))
+ return o.getvalue()
+
+class SecretJoin (object):
+ """
+ Recover a secret given a number of shares.
+ """
+ def __init__(me):
+ me._n = None
+ me._m = {}
+
+ def insert(me, x, p):
+ """
+ Insert a share P with index X.
+
+ All the shares must have the same length. It doesn't matter what the
+ length of the first share is, but the others have to match it.
+ """
+
+ ## Check that the share index is in range.
+ if x < 1 or x > 255:
+ raise ValueError, 'share index out of range'
+
+ ## Make sure that we haven't been given this one already.
+ if x in me._m:
+ raise ValueError, 'duplicate share index'
+
+ ## Check the length of the share. Store the length if this is the first
+ ## share.
+ if me._n is None:
+ me._n = len(p)
+ elif len(p) != me._n:
+ raise ValueError, 'bad share length'
+
+ ## Store the share.
+ me._m[x] = p
+
+ def recover(me):
+ """
+ Recover the secret from the shares provided, and return it as a string.
+
+ It's assumed that the caller provided the correct number of shares.
+ """
+
+ ## Iniitialize a map of l_i(0) values. These depend only on the share
+ ## indices provided, and are therefore independent of the secret length.
+ ll = {}
+ kk = me._m.keys()
+ for xi in kk:
+ l = 1
+ for xj in kk:
+ if xi != xj:
+ l = gf28_mul(l, gf28_div(xj, xi ^ xj))
+ ll[xi] = l
+
+ ## Now do the interpolation.
+ o = StringIO()
+ for i in xrange(me._n):
+ y = 0
+ for xi in kk:
+ y = y ^ gf28_mul(ll[xi], ord(me._m[xi][i]))
+ o.write(chr(y))
+ return o.getvalue()
+
+###--------------------------------------------------------------------------
+### Key/value encoding.
+###
+### We use a simple encoding for the data structures we handle. The encoding
+### looks like this:
+###
+### LABEL:KEY=VALUE;KEY=VALUE;...
+###
+### The LABEL just says what kind of structure this is meant to be. The KEYs
+### are short strings which identify the structure slots. We're doing this
+### on the cheap, so order is significant, and there are no creature comforts
+### like optional slots. The VALUEs are encodings of the slot values; the
+### details of the encoding depend on the VALUE type, which is statically
+### determined by the structure.
+
+class StructureSlot (object):
+ """
+ Base class for structure slot types.
+
+ Subclasses must implement `encode' and `decode' methods.
+ """
+ def __init__(me, name):
+ """Initialize a structure slot, remembering its name."""
+ me._name = name
+
+class IntegerSlot (StructureSlot):
+ """
+ An integer slot.
+ """
+ TYPE = 'integer'
+ def encode(me, value):
+ return '%d' % value
+ def decode(me, string):
+ return int(string)
+
+class StringSlot (StructureSlot):
+ """
+ A string slot, unencoded. Be careful.
+ """
+ TYPE = 'string'
+ def encode(me, value):
+ return value
+ def decode(me, string):
+ return string
+
+class BinarySlot (StructureSlot):
+ """
+ A binary slot, encoded as Base64.
+ """
+ TYPE = 'base64'
+ def encode(me, value):
+ return B.b64encode(value)
+ def decode(me, string):
+ return B.b64decode(string)
+
+class StructureType (object):
+ """
+ Base class for classes which can encode and decode their slots.
+ """
+
+ def __init__(me, *args, **kw):
+ """
+ Initialize a structure object.
+
+ The arguments correspond to slots. Positional arguments are read first,
+ and stored in the appropriate attributes. Keywords arguments are used to
+ set arbitrary attributes, but it is an error to set an attribute which
+ already has a value.
+
+ The `decoded' method is called after argument processing.
+ """
+
+ _magic = False
+
+ ## Decode the arguments.
+ if len(args) > len(me.SLOTS):
+ raise ValueError, 'too many positional arguments'
+ for i in xrange(len(args)):
+ slotdef, attr = me.SLOTS[i]
+ setattr(me, attr, args[i])
+ for k, v in kw.iteritems():
+ if k == '_magic':
+ _magic = v
+ continue
+ if hasattr(me, k):
+ raise ValueError, 'already set attribute'
+ setattr(me, k, v)
+
+ ## Initialize the object. (There's a hack here for the `decode' method.)
+ if not _magic:
+ me.decoded()
+
+ def encode(me):
+ """
+ Encode an object as a string.
+ """
+ o = StringIO()
+ o.write(me.LABEL)
+ o.write(':')
+ sep = ''
+ for slotdef, attr in me.SLOTS:
+ o.write(sep)
+ o.write('%s=%s' % (slotdef._name, slotdef.encode(getattr(me, attr))))
+ sep = ';'
+ return o.getvalue()
+
+ def save(me, path):
+ """
+ Write an encoded description of the object to PATH.
+ """
+ with open(path + '.new', 'w') as f:
+ f.write(me.encode())
+ f.write('\n')
+ OS.rename(path + '.new', path)
+
+ @classmethod
+ def decode(cls, string):
+ """
+ Decode a STRING, returning a new object.
+
+ The `decoded' method is called on the new object.
+ """
+ if not string.startswith(cls.LABEL + ':'):
+ raise SyntaxError, 'incorrect label'
+ slots = string[len(cls.LABEL) + 1:].split(';')
+ if len(slots) != len(cls.SLOTS):
+ raise SyntaxError, 'wrong number of slots'
+ obj = cls(_magic = True)
+ for i in xrange(len(slots)):
+ slot = slots[i]
+ slotdef, attr = cls.SLOTS[i]
+ if not slot.startswith(slotdef._name + '='):
+ raise SyntaxError, 'incorrect slot name'
+ try:
+ val = slotdef.decode(slot[len(slotdef._name) + 1:])
+ except (ValueError, SyntaxError):
+ raise SyntaxError, 'invalid %s value' % slotdef.TYPE
+ setattr(obj, attr, val)
+ obj.decoded()
+ return obj
+
+ @classmethod
+ def load(cls, path):
+ """
+ Read an encoded description of a structure and return the decoded object.
+ """
+ with open(path, 'r') as f:
+ cont = f.read()
+ if cont and cont[-1] == '\n':
+ cont = cont[:-1]
+ if '\n' in cont:
+ raise SyntaxError, 'encoding must be a single line'
+ return cls.decode(cont)
+
+ def decoded(me):
+ """
+ Hook for object initialization.
+
+ This is called by `__init__' and `decode'.
+ """
+ pass
+
+###--------------------------------------------------------------------------
+### Higher-level share management.
+###
+### We store shares together with a bunch of metadata about the sharing
+### parameters, and a hash of all of that together with the final secret.
+### Theoretically, storing a hash weakens the whole scheme from providing
+### unconditional security to merely providing computational security (based
+### on the assupmption that the hash function is one-way). In practice, the
+### secret will be used as a symmetric encryption key or similar, so it's
+### already only secure against computationally bounded adversaries.
+
+class Secret (StructureType):
+ """
+ Represents a secret, either about to be shared or recently recovered.
+ """
+ LABEL = 'shamir-secret'
+ SLOTS = [(IntegerSlot('n'), 'count'),
+ (IntegerSlot('t'), 'thresh'),
+ (BinarySlot('s'), 'secret')]
+
+ def hash(me, hashfn):
+ """
+ Hash the secret and its parameters using the hash function HASHFN.
+
+ The hash is returned as a raw binary string. The HASHFN must be one of
+ the hash functions known to Python's `hashlib' module (essentially, hash
+ functions known to OpenSSL).
+ """
+ h = H.new(hashfn)
+ h.update(me.encode())
+ return h.digest()
+
+class Params (StructureType):
+ """
+ Represents secret sharing parameters.
+ """
+ LABEL = 'shamir-params'
+ SLOTS = [(IntegerSlot('n'), 'count'),
+ (IntegerSlot('t'), 'thresh'),
+ (StringSlot('f'), 'hashfn'),
+ (BinarySlot('h'), 'hash')]
+
+class Share (StructureType):
+ """
+ Represents a share of a secret.
+ """
+ LABEL = 'shamir-share'
+ SLOTS = [(IntegerSlot('i'), 'index'),
+ (BinarySlot('y'), 'share')]
+
+###--------------------------------------------------------------------------
+### Utilities.
+
+QUIS = OS.path.basename(SYS.argv[0])
+
+def moan(message):
+ SYS.stderr.write('%s: %s\n' % (QUIS, message))
+
+def die(message, rc = 1):
+ moan(message)
+ SYS.exit(rc)
+
+class struct (object):
+ def __init__(me, **kw):
+ me.__dict__.update(kw)
+
+class Subcommand (struct):
+ pass
+
+class SubcommandOptionParser (OPT.OptionParser, object):
+
+ def __init__(me, usage = '%prog [-OPTIONS] COMMAND [ARGS ...]',
+ *args, **kw):
+ super(SubcommandOptionParser, me).__init__(usage = usage, *args, **kw)
+ me.subcommands = [
+ Subcommand(name = 'help', usage = '[COMMAND ...]', opts = [],
+ func = me.cmd_help,
+ desc = 'Show help for %prog, or for the COMMANDs.')
+ ]
+ me.disable_interspersed_args()
+
+ def add_subcommand(me, name, func, usage, desc = None, opts = []):
+ subcmd = Subcommand(name = name, func = func, usage = usage,
+ desc = desc, opts = opts)
+ me.subcommands.append(subcmd)
+
+ def lookup_subcommand(me, name):
+ match = []
+ for sub in me.subcommands:
+ if sub.name == name:
+ return sub
+ elif sub.name.startswith(name):
+ match.append(sub)
+ if len(match) == 1:
+ return match[0]
+ elif len(match) == 0:
+ me.error("unknown command `%s'"% name)
+ else:
+ me.error("ambiguous command `%s': could be any of %s"
+ % (name, ', '.join(["`%s'" % sub.name for sub in match])))
+
+ def subcmd_usage(me, sub):
+ if sub.usage:
+ return '%s %s' % (sub.name, sub.usage)
+ else:
+ return sub.name
+
+ def print_help(me):
+ super(SubcommandOptionParser, me).print_help()
+ print
+ print 'Commands:'
+ for sub in me.subcommands:
+ if sub.usage is None:
+ continue
+ print ' ' + me.subcmd_usage(sub)
+
+ def make_subcommand_optparser(me, sub):
+ op = OPT.OptionParser(usage = 'usage: %%prog %s' % me.subcmd_usage(sub),
+ description = sub.desc)
+ for opt in sub.opts:
+ op.add_option(opt)
+ return op
+
+ def cmd_help(me, gopts, opts, args):
+ if not args:
+ me.print_help()
+ else:
+ for name in args:
+ sub = me.lookup_subcommand(name)
+ op = me.make_subcommand_optparser(sub)
+ op.print_help()
+
+ def dispatch(me, args = None):
+ if args is None:
+ args = SYS.argv[1:]
+ gopts, args = me.parse_args(args)
+ if not args:
+ me.error('missing command')
+ sub = me.lookup_subcommand(args[0])
+ op = me.make_subcommand_optparser(sub)
+ opts, args = op.parse_args(args[1:])
+ sub.func(gopts, opts, args)
+
+OPTPARSE = SubcommandOptionParser(description = """\
+Split and recombine secrets using Shamir's secret sharing system.
+""")
+
+###--------------------------------------------------------------------------
+### Issue shares given a secret.
+
+def parse_sharing(string):
+ slash = string.find('/')
+ if slash == -1:
+ raise ValueError, "no `/'"
+ return int(string[slash + 1:]), int(string[:slash])
+
+def cmd_issue(gopts, opts, args):
+
+ if len(args) < 1 or len(args) > 2:
+ OPTPARSE.error('bad arguments')
+
+ try:
+ count, thresh = parse_sharing(args[0])
+ except ValueError, err:
+ OPTPARSE.error("bad sharing parameters `%s': %s"
+ % (args[0], err.message))
+
+ if len(args) < 2 or args[1] == '-':
+ sec = SYS.stdin.read()
+ else:
+ with open(args[1], 'rb') as f:
+ sec = f.read()
+
+ secret = Secret(count, thresh, sec)
+ h = secret.hash(opts.hashfn)
+ params = Params(count, thresh, opts.hashfn, h)
+ print params.encode()
+
+ ss = SecretSplit(sec, thresh)
+ for i in xrange(count):
+ share = Share(i, ss.issue(i + 1))
+ print share.encode()
+
+OPTPARSE.add_subcommand(
+ 'issue', cmd_issue,
+ '[-H HASHFN] THRESH/COUNT [SECRET-FILE]',
+ """\
+Issue shares of a secret. The secret (as a binary lump) is read from
+SECRET-FILE, or standard input if SECRET-FILE is omitted. COUNT + 1 lines
+are written to standard output: the first line contains the sharing
+parameters, and does not need to be kept especially secret (though it
+contains a hash of the secret, so it compromises the unconditional security
+of the secret sharing scheme); the remaining lines are the shares, one per
+line. All of the lines are plain text.""",
+ [OPT.make_option('-H', '--hash-function', type = 'string',
+ action = 'store', dest = 'hashfn', default = 'sha256',
+ help = 'Hash function for verifying the share.')])
+
+###--------------------------------------------------------------------------
+### Recover a secret from shares.
+
+def cmd_recover(gopts, opts, args):
+
+ ## Keep track of how well we've done so far. Report all of the things
+ ## which go wrong.
+ lose = False
+ lineno = 1
+
+ ## Read the system parameters.
+ line = SYS.stdin.readline()
+ if line.endswith('\n'):
+ line = line[:-1]
+ try:
+ params = Params.decode(line)
+ except ValueError, err:
+ moan("parameters (line %d) invalid: %s" % (lineno, err.message))
+ lose = True
+
+ ## Now read the shares. Pay attention to syntax errors, but not to much
+ ## else. Build the maps for the sharing parameters.
+ sj = SecretJoin()
+ shmap = {}
+ for line in SYS.stdin:
+ lineno += 1
+ if line.endswith('\n'):
+ line = line[:-1]
+ try:
+ share = Share.decode(line)
+ except ValueError, err:
+ moan("share invalid (line %d): %s" % (lineno, err.message))
+ lose = True
+ continue
+ share.lineno = lineno
+ if share.index in shmap:
+ moan("duplicate share index "
+ "(line %d, index %d previously on line %d)" %
+ (lineno, share.index, shmap[share.index].lineno))
+ lose = True
+ elif share.index < 0 or share.index >= params.count:
+ moan("share index %d out of range (line %d)" % (share.index, lineno))
+ lose = True
+ elif len(shmap) >= params.thresh:
+ moan("enough shares already (line %d)" % lineno)
+ lose = True
+ else:
+ sj.insert(share.index + 1, share.share)
+ shmap[share.index] = share
+
+ if len(shmap) < params.thresh:
+ moan("not enough shares")
+ lose = True
+
+ if lose:
+ SYS.exit(1)
+
+ ## Reassemble the secret.
+ secret = Secret(params.count, params.thresh, sj.recover())
+
+ if params.hash != secret.hash(params.hashfn):
+ die('secret doesn\'t match hash')
+
+ if opts.file == '-':
+ SYS.stdout.write(secret.secret)
+ else:
+ with open(opts.file, 'wb') as f:
+ f.write(secret.secret)
+
+OPTPARSE.add_subcommand(
+ 'recover', cmd_recover,
+ '',
+ """\
+Standard input should contain a number of lines. The first line should
+contain the secret sharing parameters (the first line output by `issue');
+the remaining lines should contain shares. The shares may be supplied in
+any order. The secret is written to the OUTPUT file, or standard output.""",
+ [OPT.make_option('-o', '--output', action = 'store', type = 'string',
+ dest = 'file', default = '-',
+ help = 'Write the secret to FILE.')])
+
+###----- That's all, folks --------------------------------------------------
+
+if __name__ == '__main__':
+ OPTPARSE.dispatch()
~mdw / distorted-keys / commitdiff