How to Make Your Own Lamport Parachute from Common Household Materials.

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 hands1 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 blockchain2 gives us a very strong mechanism for cryptographic timestamping3 - 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.4

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 unproven5 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.6

But enough words! It is time for the deeds!

We shall generate7 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.8

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"9 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.10

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 algorithm11 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 available12 here; Seal - here..



  1. As opposed to... the other kind. Where your self-appointed masters could impersonate you at their leisure if they so choose. 
  2. There exists, and can exist, precisely one blockchain.
  3. All other cryptographic timestamp schemes currently known rely on a "trusted third party." And a sane user trusts "third parties" no further than he can throw them! 
  4. If it so happens that you learn of your private key having been compromised before the consequences become irreparably grave, you should consider yourself extraordinarily lucky. Just ask, e.g., Admiral Isoroku Yamamoto. 
  5. The "hardness" -- i.e. the amount of computation required to break an RSA key, of whatever length, is unknown. And if your university professor taught you that it is known, or -- more egregiously -- that "it is equivalent to integer-factoring", then he is not merely an ignoramus but a particular kind of liar
  6. There exist certain questionable schemes to somewhat reduce this bulk, but I have deliberately eschewed them in light of the gravity of the task at hand. Good men may well die from your "reasonable" optimizations, your "negligible" losses of strength, loathesome hucksters
  7. Chances are that Lamport key generation, being an entropy-hungry affair, will take an unacceptably long time on your box. The temptation to replace "/dev/random" with "/dev/urandom" will be great. Needless to say that if the key is being generated for battlefield use, such a substitution is impermissible. But if you are following along simply for study, go ahead. Just remember to switch it back before crafting that missile launch key... 
  8. I.e. a multiple of 8. 
  9. I.e. for use in practice. 
  10. Along, if your situation is sufficiently grave to merit this, you will also cremate the very machine used in these operations! 
  11. One interesting tidbit is that public key signatures are only possible if trapdoor functions exist -- see Rompel, 1990. So, today, or 100 years from now, you're stuck choosing a hash algo. 
  12. Strictly under Popescu's License

Edit (Nov. 2020) :

One N. D. Moskopp wrote a supposedly more portable and readable implementation of the Parachute. He also implemented a variant featuring Winternitz's One-Time Signature system.

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

This entry was written by Stanislav , posted on Wednesday September 28 2016 , filed under Bitcoin, Cold Air, Computation, Cryptography, Friends, Idea, Mathematics, NonLoper, Papers, Philosophy, ShouldersGiants, SoftwareArchaeology, SoftwareSucks, VTronics . Bookmark the permalink . Post a comment below or leave a trackback: Trackback URL.

12 Responses to “How to Make Your Own Lamport Parachute from Common Household Materials.”

  • Adlai Chandrasekhar says:

    I'm not sure this is useful for a warrant canary. Shouldn't a warrant canary be a fresh signature each day/week/etc, saying something like "As of blockheight 432072, Cretans are still liars"? Needing to produce a new signature each time precludes using a one-time scheme.

    This leaves aside the fact that warrant canaries are borderline security theater. When did somebody last tell you they stopped using Apple or Reddit specifically due to the death of their canaries?

    • Stanislav says:

      Dear Adlai,

      I was thinking of a somewhat different kind of "canary".

      A Lamport public key does not necessarily have to be public, in the usual sense: in certain situations it will make sense to share one with a small circle of trusted people. They will be able to receive an authenticated message from you, in confidence -- a Lamport signature is not distinguishable from noise to someone who does not know the corresponding public key.

      Thereby your "canary" is, e.g., a block of RNG turd posted every morning. Generate it using the same Lamportron you will use to fire the actual signal, but with a randomly-produced public key.

      And folks in-the-know apply the Lamport transform to it, and normally, the output is "False", but if one day you have been threatened with torture and murder by your "Western democracy", it will output something else...

      One might obtain a similar result by issuing Vernam pads, but the loss of a pad is catastrophic (whoever finds it, can read and forge messages) whereas the leakage of the Lamport public key is merely dangerous. And to a cryptographer, a transmutation of catastrophe into mere danger is a victory of sorts.

      Yours,
      -Stanislav

  • cat-v.org sectant says:

    I ran scripts through checkbashisms and looks like those scripts shuol work equally well with just POSIX sh, which is preferable, because bash is bad for your karma. Didn't actually try doing so myself yet though.

    sh is still notorious for being bad at clarity and suffering from unexpected behavior though. It's good for portability across POSIX systems, but if fits-in-the-head was main goal, there probably was a better alternative.

    • Stanislav says:

      Dear cat-v.org,

      I was specifically and deliberately uninterested in using for this tutorial any language that is not already present on every reasonable box, or has "library issues" (this means any known pertinent variation in functionality between extant versions. So no perl. no python, no C.) That leaves us with the shell and common utils.

      Yours,
      -Stanislav

      • Chief Fetters says:

        Your "already present" requirement limits your definition of "reasonable Unix box" to... basically linux, and a subset of that to boot. Arguably "linux" isn't an especially acceptable Unix, but let's not bicker about that; this excludes non-linux Unices.

        Moreover, not even all linux distributions actually deliver bash in the default install; dash being an oft-used alternative for /bin/sh, but it could just as well be something else, like busybox. You'd have to add bash, possibly by hand, afterward. Some sort of POSIX shell can be expected unless the Unix at hand is really old, but it likely won't provide bashisms like read -u. Likewise, xxd is not that common, better use od, and seq is a linuxism, elsewhere you can have jot. sha256sum is also a linuxism, elsewhere it's merely sha256. I make no claim of being exhaustive here.

        So we have an "all the world is a VAX" type assumption. To the point that writing in some suitably simple subset of C is probably more portable modulo interfacing with a hash implementation somehow (pipe, library, ship own implementation in C, what have you), since it may well be the case that C compilers are more prevalent on Unix derivates than bash. But again, not even cc is universal in the default install.

        Awk would be a candidate except that its bitwise operators are a gnu (and busybox) extension, not present in awk implementations like the One True original you might find on non-gnu systems.

        Thus this implementation supports mainly your own workstation since it is the only thing that can be reasonably expected to provide everything you expect to be available already. The result is a showpiece that cannot be expected to work anywhere else without operator understanding and possibly quite a bit of tinkering. Which is fine, of course, if put that way.

        • Stanislav says:

          Dear Chief Fetters,

          Did all four of the example scripts bomb in your favourite shell? Consider posting - which shell, what output..?

          Or did you not even bother to try?

          The "sha256sum" is specifically substitutable. If your hasher produces a single string, instead of "HASH filename", remove the "cut -d ' ' -f1" everywhere you find the invocation of hasher | cut -d ' ' -f1 .

          Yours,
          -Stanislav

    • Stanislav says:

      Dear cat-v.org,

      Consider joining us on #trilema ?

      Yours,
      -Stanislav

  • Stanislav says:

    The braindamage of Unix is truly astounding:


    $ od -N 32 -An -t x1 -v /dev/zero | tr -d " \n" | ./lamport_encode.sh privkey.txt | ./lamport_decode.sh sha256sum pubkey.txt

    0

    Turns out, bc truncates zeroes.

    Added padding; article, downloads, V-Genesis updated.

  • GTP says:

    "The "hardness" -- i.e. the amount of computation required to break an RSA key, of whatever length, is unknown. And if your university professor taught you that it is known, or -- more egregiously -- that "it is equivalent to integer-factoring", then he is not merely an ignoramus but a particular kind of liar. "

    Are you saying that there might be some way of recovering the private key from the public key that doesn't involve factoring? Or better, that it has never been proven that factoring is the only way?

    • Stanislav says:

      Dear GTP,

      Correct. AFAIK to this day no proof exists that factoring is required to break RSA. Or for that matter, of a hard lower bound for the cost of factoring.

      Yours,
      -S

Leave a Reply

XHTML: You can use these tags: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong> <pre lang="" line="" escaped="" highlight="">


MANDATORY: Please prove that you are human:

9 xor 119 = ?

What is the serial baud rate of the FG device ?


Answer the riddle correctly before clicking "Submit", or comment will NOT appear! Not in moderation queue, NOWHERE!