## Lamport Signatures
Lamport's signature scheme constructs a digital signature from a cryptographic
hash function. The scheme is pretty simple but the basic version of it has
serious constraints which can be mitigated through extra cleverness.
### Informal Explanation
A Lamport signature relies on:
* Generating a lot of pieces of random data as the private key
* Publishing hashes of those pieces of random data as the public key
* Using the bits of the hash of the message being signed to decide which
bits of the private key (the original random data) to reveal
This produces a working signature scheme:
* An attacker can't sign a message, because they won't have the private data
they need to reveal to make a signature
* Anyone can verify a signature, by checking that:
1. The revealed private data matches the previously-known public key
2. The revealed private data is the right set for the signed message
With the following cool properties:
* It can be implemented in very little code, and doesn't require any advanced
math
* Its security rests entirely on the security of a cryptographic hash function,
which is a well-studied problem, and therefore...
* Unlike most signature schemes, it is resistant to quantum cryptanalysis
But there are severe drawbacks:
* The private key, the public key, and the signature are all very large compared
to other signature schemes
* Signature verification requires hundreds of hash operations
* A given key pair can be used to sign at most one message, since the act of
signing a message inherently reveals half of the private key; if a second
message is signed, most of the private key will have been revealed, allowing
anyone to likely sign other messages
### Syntax
Let:
R() return a cryptographically random value of sufficient length to
be unguessable
H(m) return a cryptographic hash of m
n be the length of the output of H
### The Lamport Primitive
Lamport signatures work like this:
The signer S chooses a random private key, which is a sequence of n pairs
of random numbers, each itself cryptographically random. So, let the private
key Kp be:
Kp = { Kp[0], Kp[1], ..., Kp[n] }
where each Kp_i is:
Kp[i] = { R(), R() }
Then the public key Ku is the hashes of all these values:
Ku = { Ku[0], Ku[1], ..., Ku[n] }
where each Ku[i] is:
Ku[i] = (H(Kp[i][0]), H(Kp[i][1]))
The signer then signs a message m thus:
let { s[0], s[1], ..., s[n] } = H(m) (s is the bits of the hash of m)
sig = { Kp[0][s[0]], Kp[1][s[1]], ..., Kp[n][s[n]] }
so the signature is a sequence of n of Kp values.
A verifier can validate a signature like so:
let { sig[0], sig[1], ..., sig[n] } be the signature from above
let { s[0], s[1], ..., s[n] } = H(m)
let u[i] = Ku[i][s[i]] for i in 0 to n (i.e. use the i'th bit of s to
choose an element from the pair
Ku[i])
for each u[i]:
check that H(sig[i]) = u[i]
### A C Implementation
Here is a **non-cryptographic** demonstration of the algorithm, in C. It uses
a fake RNG, a fake hash function, a non-constant-time signature verifier (which
opens it to easy timing attacks), and keys that are far too small to be
practical.
To run this example, do:
$ sed -e '1,/^>>>/d' -e '/^<<>>
/* lamport.c */
#include
#include
uint32_t random() {
static uint32_t r = 0;
return r++;
}
uint32_t hashv(uint32_t r) { return r * 2; }
uint32_t hashm(const char *m) {
uint32_t h = 0;
while (*m)
h += *(m++);
return h;
}
#define NBITS(t) (sizeof(t) * 8)
typedef uint32_t randval;
typedef uint32_t hashval;
#define KEYLEN (NBITS(hashval))
typedef randval privkey[KEYLEN][2];
typedef hashval pubkey[KEYLEN][2];
typedef randval sig[KEYLEN];
void genkey(privkey pk, pubkey uk) {
for (int i = 0; i < KEYLEN; i++) {
pk[i][0] = random();
pk[i][1] = random();
}
for (int i = 0; i < KEYLEN; i++) {
uk[i][0] = hashv(pk[i][0]);
uk[i][1] = hashv(pk[i][1]);
}
}
void sign(privkey pk, sig s, const char *m) {
hashval h = hashm(m);
for (int i = 0; i < KEYLEN; i++)
s[i] = pk[i][(h >> i) & 1];
}
int verify(pubkey uk, sig s, const char *m) {
hashval h = hashm(m);
for (int i = 0; i < KEYLEN; i++) {
hashval u = uk[i][(h >> i) & 1];
if (hashv(s[i]) != u)
return 0;
}
return 1;
}
int main(int argc, char *argv[]) {
privkey pk;
pubkey uk;
sig s;
if (argc < 2)
return 0;
genkey(pk, uk);
sign(pk, s, argv[1]);
printf("sig starts: %08x %08x %08x %08x\n", s[0], s[1], s[2], s[3]);
return !verify(uk, s, argv[1]);
}
<<<
### Improvement 1: Smaller Private Keys
The private key can be compacted down by generating it with a CSPRNG or any
other key expansion method. For example, we could compute the private key from
a single random key K and an HMAC function HMAC as:
Kp[i] = HMAC(K, i)
That reduces the size of the private key, but we unfortunately can't do the
same technique for the public key, since it's unlikely we'll be able to find
any f such that:
f(i) = H(HMAC(K, i))
for all i (or indeed any useful set of i).
### Improvement 2: Smaller Public Keys
The "public key" can instead be the hash of all the public key hashes, like so:
Ku = H(Ku[0][0] + Ku[0][1] + Ku[1][0] + Ku[1][1] + ... + Ku[n][1])
Then the signature must include all the "unused" parts of the public key, so
the signature becomes for example:
{ Ku[0][0], Kp[0][1], Kp[1][0], Ku[1][1], Ku[2][0], Kp[2][1], ... }
so that the verifier can compute:
{ Ku[0][0], H(Kp[0][1]), H(Kp[1][0]), Ku[1][1], ... }
to verify that the hash of that sequence is the smaller hash public key.
### Improvement 3: Key Trees
It's possible to use a Merkle tree of keys to allow a single private/public key
pair to sign a fixed (but arbitrarily large) number of messages; I'll write
about how this is done in a subsequent post because it's pretty involved and
Merkle trees deserve their own post :)