[tahoe-dev] note about hash-based digital signatures

[Zooko O'Whielacronx]

Folks:

Per the earlier discussion about hash-based digital signatures [1],
I've updated some wiki pages [2], [3].

I chatted with Brian in person about this and we realized that the
standard construction, e.g. the one in [4] is stateful in a way that
causes much problems for Tahoe-LAFS. In those constructions there is a
sequence of one-time keys and if you ever use a one-time-key more than
once then unauthorized people can forge signatures after that! This
means that we would have to be extremely careful about dealing with
crash-and-recovery of clients. Furthermore, it means we would have to
invent a completely new solution for distributed multiple writers
which somehow prevented writers from *ever* using the same one-time
key that another writer had used! This would be hard, and would also
necessitate a big trade-off of reduced availability (meaning that
there would be more situations where you couldn't write due to network
problems or other synchronization issues).

So, I was about to give up on the idea of hash-based signatures, but
then I thought that you could instead have a giant space of one-time
keys, say 2²⁵⁶ one-time keys, and pick one at random to use for each
signature! (This sounds crazy, but it turns out that you don't have to
actually pre-generate all of the one-time keys in these sorts of
schemes, so the giant space of 2²⁵⁶ one-time keys is actually "a
virtual space of one-time keys" where every key has a unique sequence
number assigned to it but not every key has actually been generated
yet.)

Then Brian pointed out that the only security problem with re-using a
one-time key is if you re-use the same one-time key with a *different*
plaintext that you are signing. That suggests an easy way out of the
statefulness mess: uses the one-time key whose index is determined by
the message representative that you are about to sign.

Now *that* suggested, to me, another optimization, which is if you are
going to use a one-time key out of a giant virtual space of one-time
keys (say 2²⁵⁶ in size) then you don't need to actually *perform* the
one-time signature with that key! You can just reveal the secret key.
:-)

However, Brian then did some back-of-the-envelope calculations and
figure it that it would take many tens of thousands of hashes to
generate a public key. Or maybe that was to sign a message. I was too
sleepy by this point to follow his arithmetic. He ended by saying that
we ought to write down the equations which determine these various
tradeoffs and trying solving them for various preferences and see how
efficient we can make it. (See also [4] which does exactly that except
they choose trade-offs that we would never choose. See also my
comments on [4] below.)

Note that "tens of thousands of hashes" is not necessarily a
show-stopper! Depending on a large number of details, we might be able
to compute a secure hash in as little as 1000 CPU cycles. So to do
10,000 of them would take (with ideal CPU utilization) 10,000,000
cycles. On a 1 GHz machine, this would take 10 milliseconds. (WARNING:
all of these numbers are *very* rough estimates for the purposes of
deciding if it is worth figuring out more accurate numbers.)

By comparison RSA 4096 signatures might take around 70,000,000 cycles
(depending on a lot of factors) and ECDSA 256 might take around
5,000,000 cycles. (Warning: also very rough, but derived from real
data: http://bench.cr.yp.to/results-sign.html .)

Oh, one more detail: the "giant virtual space of one-time keys" might
not need to be as large as 2²⁵⁶. That's because an attacker can't
"brute force attack" this space. The resistance against brute force
attack is provided by other parts of the system. This space needs to
be large only in order to avoid accidental collision. It could be
perhaps as small as 2¹⁶⁰, which if I calculate correctly would let you
write 10¹⁶ times to your file while still incurring less than a 10⁻¹⁵
chance of an accidental collision which would let people forge new
writes to your file.

Regards,

Zooko

Here is what I just added to the Bibliography page:

[http://www.cdc.informatik.tu-darmstadt.de/~dahmen/papers/hashbasedcrypto.pdf
Hash-based Digital Signature Schemes] by Buchmann, Dahmen, and Szydlo;
A survey of why it might be a good idea.

[http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=8AC81C407AA3CBF35093032BD01F3085?doi=10.1.1.95.1374&rep=rep1&type=pdf
Merkle Signatures with Virtually Unlimited Signature Capacity] by
Buchmann, Dahmen, Klintsevich, Okeya, and Vuillaume; includes treating
the parameters as an optimization problem and solving it with various
weights or constraints to find various good settings for the
parameters. Unfortunately their weights and constraints are different
from hours: they thought it was fine to let key generation time take
tens of hours! We want key generation time to be as few milliseconds
as possible. A good rule of thumb for us would probably be try to
reduce the time of whichever of the three operations is the slowest:
key-generation, signing, and verification.

[https://www.minicrypt.cdc.informatik.tu-darmstadt.de/reports/reports/REDBP08.pdf
Fast Hash-Based Signatures on Constrained Devices] by Rohde,
Eisenbarth, Dahmen, Buchmann, and Paar; a case study of implementing
hash-based digital signatures for a 8-bit microcontroller. Their
implementation had some trade-offs that we wouldn't want: it is a
"key-evolving" design (the signer has to maintain state in order to
avoid a security failure), it can only handle a limited number of
signatures, and they spent a lot of time in key generation. Hm, they
don't say how long key-generation took in this paper—only that it took
so long that they had to run it on a PC instead of on their
microcontroller. In "Merkle Signatures with Virtually Unlimited
Signature Capacity", the key-generation took tens of hours on a PC!!!
On the other hand, they do show a digital signature scheme which is
faster at signing and verifying and is also arguably safer than RSA or
ECDSA on their 8-bit microcontroller.

[1] http://tahoe-lafs.org/pipermail/tahoe-dev/2010-June/004439.html
[2] http://tahoe-lafs.org/trac/tahoe-lafs/wiki/Bibliography
[3] http://tahoe-lafs.org/trac/tahoe-lafs/wiki/OneHundredYearCryptography
[4] http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=8AC81C407AA3CBF35093032BD01F3085?doi=10.1.1.95.1374&rep=rep1&type=pdf