The thought began, as many good things begin, in #trilema.

Users of the WOT, of V, and other systems where your cryptographic identity is wholly in your own hands¹ live with a certain risk of "cryptographic death" - i.e. the compromise of one's signing key. A conscientious user of public key crypto might keep the thought of this calamity somewhere in the back of his head, filed right next to "piano falling on my head" and other misfortunes from which there can be no return.

A correctly-generated RSA key is unlikely to be broken via cryptoanalytic means within the owner's lifetime. But "never say never!" And there is always the possibility of a mass slaughter of keys, a "cryptocalypse", where the public key cryptosystem of your choice is broken (or, via whatever mathematical advances, weakens, and the cost of deriving your private key from your public key becomes tractably low.)

The popular notion of key revocation is a questionable business because it attempts to impose a political structure onto an uncooperative mathematical reality -- in the jargon of #trilema, it is "promisetronic, not protocolic." Someone who takes possession of your signing key can walk around and befoul your reputation, 'Who steals my purse steals trash; 'tis something, nothing; 'Twas mine, 'tis his, and has been slave to thousands; But he that filches from me my good name...' without regard to time or space - he can sign whatever he likes and attribute it to you. And those who have not received your revocation signal will accept the forgeries as the genuine article. Nothing whatsoever can be done to rescue a compromised signing key. But might it be possible to rescue its owner from WOT death by establishing an unforgeable continuity of identity ?

The answer is: "possibly." The Bitcoin blockchain² gives us a very strong mechanism for cryptographic timestamping³ - i.e. the act of certifying, to a skeptical observer, that some particular string of bits had indeed been in existence at a particular point in time. The current state-of-the-art implementation of this concept is called Deedbot, and the reader is invited to become familiar with it. If you make an arrangement with your associates in advance that a certain public key Deedbotted at a certain time is to be regarded as your emergency fallback, you have a kind of "parachute" on which you may conceivably float safely to the ground in the event of your plane's wings, if you will, breaking off -- i.e. a signing key compromise.⁴

However, the obvious caveat is that the "parachute" keypair must exist at the time of the Deedbotting, and its public key must be, well, public. This can be a problem in the scenario where the cryptosystem itself- e.g., RSA - is publicly broken. The enemy can now do as he pleases with your primary and fallback keys, and you - the cryptographic you - have died a permanent death. And all known public key signature schemes rely on unproven⁵ number-theoretic conjectures, and may conceivably fall this very night. All except for one...

L. Lamport's 1979 "one time signature" algorithm rests on no number-theoretic conjecture, but merely on the strength of a collision-resistant hash of the operator's choosing. On account of certain disadvantages which will soon become apparent to the reader, it is used virtually nowhere. But it so happens that it is entirely perfect for our "parachute" scenario.

A complete and usable implementation of this "Lamport parachute" is presented in this article. It is written in 68 69 lines of Bash and makes use strictly of commonplace userland utilities, such as may be met with on a typical Linux box. This somewhat strange choice of implementation language (it certainly does not shine, for instance, speedwise) is deliberate: the user is expected to understand each individual part, so that the function of the whole becomes unambiguously apparent, like 2+2. As the field of cryptography is slowly reconquered from the Schneiers and other scumbags presently maggoting on top of it, expect this type of didactic presentation to become ordinary practice.

A Lamport public key consists of two lists, let's call them A and B, of randomly-generated bitstrings that have been hashed with a collision-resistant hash and thereafter published. To make use of such a key, the owner hashes the payload being signed, and for each bit that is equal to 0 in the resulting hash, reveals the original pre-hash string from column A, whereas if it is equal to 1 he reveals a pre-hash string from column B. For reasons which I hope are quite obvious to the alert reader, a Lamport public key is to be made use of only once. And such a key is quite bulky, as is the signature resulting from its use.⁶

But enough words! It is time for the deeds!

We shall generate⁷ our Lamport Parachute like this:

lamport_mkpriv.sh

#!/bin/bash
 
if [ $# -lt 2 ]
then
  echo "Usage: ./`basename $0` PAYLOADBITS STRENGTHBITS"
  exit 1
fi
 
for i in $(seq 1 $(($1 * 2))) ; do
    echo `od -N $(($2 / 8)) -An -t x1 -v /dev/random | tr -d " n"` ;
done | xargs -n 2

All this does is to give us two columns of STRENGTHBITS-sized random integers, times PAYLOADBITS rows.

Specifically:

$ ./lamport_mkpriv.sh 256 512 > privkey.txt

This will create a parachute private key suitable for use with sha256 - i.e. it is able to sign a 256-bit payload. The strength - or length of the random strings - in this example is 512 bits. It is pointlessly suicidal to use a strength value below the output length of your chosen hash algorithm, but otherwise the choice is unconstrained, so long as it byte-aligns.⁸

Now we would like to generate the corresponding public key:

lamport_priv2pub.sh

#!/bin/bash
 
if [ $# -lt 1 ]
then
  echo "Usage: ./`basename $0` HASHUTIL < PRIVKEY.TXT > PUBKEY.TXT"
  exit 1
fi
 
for x in $(cat) ; do
    echo -n $x | xxd -r -p | $1 | cut -d ' ' -f1 ;
done | xargs -n 2

We simply apply the HASHUTIL of choice to the bitstrings produced by lamport_mkpriv.sh.

And it is done like this:

$ ./lamport_priv2pub.sh sha256sum < privkey.txt > pubkey.txt

Now we have the public key.

If you are generating a "battlefield"⁹ key, it is now time to consider its intended usage scenario. If the payload of the signature is known in advance - e.g., a "warrant canary", or some other such thing - you will generate its signature immediately, and the private key may then be destroyed immediately.¹⁰

Otherwise the private key is to be retained, shielded stegatronically from prying eyes, and hidden safely far away from your usual places of business or habitation, or other locations liable to be searched by the enemy.

Let's make a second public/private keypair of the same type:

$ ./lamport_mkpriv.sh 256 512 > another_privkey.txt
$ ./lamport_priv2pub.sh sha256sum < another_privkey.txt > another_pubkey.txt

And now we should like to make use of our Lamport Parachute.

Let's sign a message:

lamport_encode.sh

#!/bin/bash
 
if [ $# -lt 1 ]
then
  echo "Usage: ./`basename $0` PRIVKEY.TXT < HEXPAYLOAD > ENCODED.TXT"
  exit 1
fi
 
payload=$(cat | tr '[:lower:]' '[:upper:]')
len=$((${#payload} * 4))
bits=$(printf "%*s" $len $(echo "ibase=16;obase=2;$payload" | bc | tr -d 'n') | tr ' ' 0)
 
while IFS= read -r p; do
    bit=${bits:0:1};
    bits=${bits:1};
    echo $p | cut -d ' ' -f$(($bit + 1));
done < "$1"

Here we simply iterate over the bits of the payload, choosing the unhashed original private strings from column A or B as discussed earlier.

Remember, we generated a private key that can carry a 256-bit payload. It does not necessarily have to be a hash, but in this example we will take one, e.g.:

$ echo "Attack at dawn." | sha256sum | cut -d ' ' -f1
 
1d6c270d7cc7e82a816ffb7bc3797d213b24d9d17af48f4b3b8d01fb43ed15c3
 
echo "Attack at dawn." | sha256sum | cut -d ' ' -f1 | ./lamport_encode.sh privkey.txt > encoded.txt

And we get a signature.

NOW YOU MUST DESTROY THE PRIVATE KEY! IT SHALL NEVER BE USED AGAIN!

Quite analogously to a Vernam "One Time Pad" -- the re-use of a Lamport private key is cryptographically suicidal.

And now some counterparty, with whom you have taken care to share your parachute's public key, wishes to verify the signature. It happens like this:

lamport_decode.sh

#!/bin/bash
 
if [ $# -lt 2 ]
then
  echo "Usage: ./`basename $0` HASHUTIL PUBKEY.TXT < ENCODED.TXT > HEXPAYLOAD"
  exit 1
fi
 
bits=""
while read -u 3 pkl; do
    if ! read el
    then
        break
    fi
    bits="$bits$(
        case $(echo -n $el | xxd -r -p | $1 | cut -d ' ' -f1) in
            $(echo $pkl | cut -d ' ' -f1)) echo "0" ;;
            $(echo $pkl | cut -d ' ' -f2)) echo "1" ;;
            *) exit 1; break ;;
            esac)"
    if [[ $? == 1 ]]
    then
        echo False >&2;
        exit 1
    fi
done 3< $2
 
padlen=$(od -N 1 /dev/zero | $1 | cut -d ' ' -f1 | tr -d " n" | wc -c)
printf "%*sn" $padlen $(echo "ibase=2;obase=10000;$bits" | bc  | tr -d 'n' | tr '[:upper:]' '[:lower:]') | tr ' ' 0

Here we simply take each bitstring from an encoded parachute message (the signature) -- hash it with the pre-agreed hashing algo; and determine which column of each respective row of the public key the result is found in. (If the answer is "neither", the decoder terminates and warns us.)

So, for instance:

$ ./lamport_decode.sh sha256sum pubkey.txt < encoded.txt
 
1d6c270d7cc7e82a816ffb7bc3797d213b24d9d17af48f4b3b8d01fb43ed15c3

We have decoded a payload. If we had agreed, in advance, that this payload is the sha256 hash of a document, e.g.:

$ diff < (./lamport_decode.sh sha256sum pubkey.txt < encoded.txt) <(echo "Attack at dawn." | sha256sum | cut -d ' ' -f1)

We are able to verify it.

Now let's try the same, but with the wrong public key:

$ diff < (./lamport_decode.sh sha256sum another_pubkey.txt < encoded.txt) <(echo "Attack at dawn." | sha256sum | cut -d ' ' -f1)
 
False
0a1
> 1d6c270d7cc7e82a816ffb7bc3797d213b24d9d17af48f4b3b8d01fb43ed15c3

Observe that it is possible to make use of any hashing algorithm¹¹ you may happen to like, so long as you have it available as a command-line program.

Epilogue.

A V-genesis for these didactic examples is available¹² here; Seal - here..

Edit (Nov. 2020) :

Do you, reader, have one of your own? Please write in!