[tahoe-dev] Hash based Signatures for Tahoe LAFS

[Samuel Neves]

One positive point about hash-based signatures is that there's plenty of
parallelism to go around. And parallelism is what processors are getting
good at lately.

The performance of SHA-256** for signatures can be improved. Firstly,
any modern desktop processor has 128-bit vector instructions, which
allow us to run 4 SHA-256 compressions by (essentially) the price of
one. Further, one is hashing small (1 block) byte sequences, which
simplifies padding and reduces the complexity of SHA-256 to the
complexity of one compression call. In [1], Wei Dai showed that the
SHA-256 compression function could be computed using 2698 instructions.
This means that, worst-case, we can compute 4 compression calls in 2698
cycles, or 10.54 cycles/byte; best-case scenario, we can do it in 2698/3
or 3.513 cycles/byte.

Upcoming processors make things interesting. AVX doubles the vector size
to 256 bits or 8 parallel compression calls##. Current GPUs do much
better, but it is unclear whether the latency penalty involved in
sending and receiving memory through PCIe speeds anything up (even 466
Mcycles is just 1/5 of a second in a typical desktop CPU).

Another thought, raised by Zooko, relates to using second-preimage-based
hash signatures. Dahmen [2] shows how to achieve signatures out of
second-preimage resistance, which greatly increases the strength of the
signature in function of the underlying function's output length. For a
128-bit level of security, then, we don't really need the full 256-bit
output size of SHA-256.

Currently, there seems to be no trusted (and fast) 128-bit hash. Trying
to repurpose an existing 256-bit hash to 128 bits can certainly be done
simply by truncating. But it is no faster. We can look at [3, Section
5.2] for specific constructions designed for this purpose. They use AES
in MMO mode, truncated to 80 bits for a 2^80 security level. Our problem
becomes, then, to find a trusted fast AXR block cipher with only a
128-bit block size. Or we can use AES and enjoy Westmere's fast AES
instructions (or very fast bit-sliced implementations).

[1] Wei Dai, "Re: SHA-2 timings??", NIST hash-forum mailing list,
2009-07-03.
[2] Erik Dahmen et al., "Digital Signatures Out of Second-Preimage
Resistant Hash Functions",
http://www.springerlink.com/content/g7454567t750k065/
[3] Erik Dahmen and Christoph Krauß, "Short Hash-Based Signatures for
Wireless Sensor Networks",
http://www.springerlink.com/content/c4w61v2n3h621q23/

**: I am using SHA-256 as reference. This is applicable to essentially
any AXR hash on 32-bit words.
##: Currently (Sandy Bridge) AVX does not support 256-bit *integer*
instructions. I'm told, however, that this is temporary and those will
be added.

On 18-02-2011 07:58, Zooko O'Whielacronx wrote:
> Hello Julian:
>
> Thank you for your letter. I have time tonight to respond to only one bit of it:
>
> 2011/2/16 Julian Wälde <jwaelde at cdc.informatik.tu-darmstadt.de>:
>> There is no way in hell that these stateless merkle schemes can compete
>> with ecdsa or rsa in terms of speed/signature size ... the fastest
>> stateless scheme (meaning that the privatekey does not change with every
>> signature) was still 5 times slower than rsa4k and had ~40kb per signature.
> Hm, I guess "competitive with ECDSA or RSA" is the wrong measure. How
> about "efficient enough for all practical purposes" instead?
>
> Let's see, there are basically three places where we might need to do
> digital signatures:
>
> 1. A Tahoe-LAFS gateway running locally to a user, e.g. on their
> workstation, laptop, or handheld.
>
> 2. A Tahoe-LAFS gateway running remotely, and possibly serving many
> users at once.
>
> 3. A Tahoe-LAFS storage server (if, in the future, storage servers
> verify digital signatures on shares, which I hope they do in order to
> provide simple and strong resistance against denial-of-service by
> scribbling attacks).
>
> In particular, I want to be able to do verifications on a cheap little
> low-power 32-bit ARM storage servers. Let's say as a
> shooting-from-the-hip goal that I would like to do 50 verifications
> per second. I come up with that number by the following sequence of
> rough estimates. (The roughness of some of the numbers is indicated
> with *'s.)
>
> The number of disk seeks that the storage server would have to do to
> accept a share would be 4 **, and one seek-and-read or seek-and-write
> takes about 20 ms * [1], so a single spinning disk can't really accept
> upload of more than 12.5 shares per second. One cheap ARM server can
> manage 4 * spinning disks, so one cheap ARM server might be able to
> accept upload of 50 shares per second.
>
> A cheap ARM server might have a 1.2 GHz * CPU, so that gives us a
> budget of 60 million instructions per upload, if we could spend 100%
> of the CPU time doing verifications. Let's guess that we need 50% ***
> of the CPU time for other tasks, so now we have only 30 million
> instructions left to do signature verification on each share as it is
> uploaded. Is that achievable with hash-based digital signatures?
>
> For what it is worth, I suspect that the other two deployment
> situations will have even looser constraints on the speed of the
> digital signature algorithm. The personal-to-one-user gateway doesn't
> have that high of a load of requests -- its constraint is more about
> not imposing a time penalty that is noticeable on a human scale (tens
> of milliseconds) and not wasting the user's battery life. The
> many-users gateway can perhaps have more specialized hardware such as
> a high-powered 64-bit CPU or a GPU. Or alternately the many-users
> gateway can be horizontally load-balanced into many small, cheap
> gateways, thus making it have similar performance needs as the cheap
> storage servers.
>
> The size of the signature in a hash-based signature system maybe be a
> worse problem than the CPU time to verify it.
>
> Regards,
>
> Zooko
>
> [1] http://www.storagereview.com/western_digital_caviar_green_3tb_review_wd30ezrsdtl
>
> P.S. Apologies if there are glaring errors or omissions in the above.
> It is late! I've now satisfied my goal of at least one reply to
> tahoe-dev per night. :-)
> _______________________________________________
> tahoe-dev mailing list
> tahoe-dev at tahoe-lafs.org
> http://tahoe-lafs.org/cgi-bin/mailman/listinfo/tahoe-dev