[tahoe-dev] Hash based Signatures for Tahoe LAFS

[Samuel Neves]

I've been meaning to reply to this message for a while now. Haven't had
time to look at the actual signature scheme yet, so I'll comment on
performance for now.

Ideally, one wants to use vector units to compute several hashes in
parallel whenever possible. Threefish is a 64-bit-oriented cipher, which
means one can only run 2 copies in parallel in a vector register. AES
and Camellia are on the other end of the spectrum; bit/byte-sliced
implementations allow one to run 8 or 16 blocks at a time. However, even
the best implementations of bitsliced AES only manage to achieve ~7 cpb,
which is not that great.

In x86/amd64, the most successful ciphers to run in parallel (usually
CTR mode) are 32-bit based. Salsa20/ChaCha20 SSE2 implementations run 4
blocks at a time, and this makes them some of the fastest ciphers
around. Brute-forcing MD5 and SHA1 hashed passwords, both hashes also
32-bit based, is really fast on vector units. Since ARM has 128-bit
vector units too these days (NEON), I believe this is an option worth
checking out.

For what it's worth, here's an SSE2 implementation of 256-bit Threefish
I had lying around: http://eden.dei.uc.pt/~sneves/threefish256.c

Best regards,
Samuel Neves

On 30-03-2011 04:48, Julian Wälde wrote:
> On 18.02.2011 08:58, Zooko O'Whielacronx wrote:
>> 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.)
> Wooo finally got me self some time to do fun stuff ... I started out
> with implementing a prototype for a merkle scheme that has a static
> private key that can do infinite number of signatures [1].
>
> This implementation has received zero review and the scheme it hopefully
> implements can't be reduced to any computational hard problem ...
> collision resistance aside (DONT USE THIS!).
>
> Basicly this is gmss with 16 layers of height 8 (256 leafs per layer)
> the message (128bit 16 * 8 bit) is used to find a path through these
> layers (so the same 128bit message value will allways result in the same
> signature beeing computed). I choose winternitz parameter 16 (4bit).
>
> I think you can test signing/verification speed on your Arm box with
> this (use time(1) for measuring).
>
> On my box I have about 4 sigs/sec and 1700 verifications/sec for 11kb
> signature size. It's possible to get about 8 times faster signing at the
> cost of 50% verification speed and 22kb signature size.
>
> -Julian
>
> [1] http://www.cdc.informatik.tu-darmstadt.de/~jwaelde/smss.tar.xz
>
> PS: using threefish as oneway function is great on 64bit computers ...
> however aes/camellia might be faster on 32bit systems.
>
>
>
> _______________________________________________
> tahoe-dev mailing list
> tahoe-dev at tahoe-lafs.org
> http://tahoe-lafs.org/cgi-bin/mailman/listinfo/tahoe-dev

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://tahoe-lafs.org/pipermail/tahoe-dev/attachments/20110411/a36a0943/attachment.html>