[tahoe-dev] pycryptopp benchmarks

[Zooko Wilcox-O'Hearn]

Folks:

Someone asked me in private email if pycryptopp included ECDSA. The
answer is that it does, but it was never really finished, never used,
and is deprecated.

However, I took the opportunity to do some simple benchmark of
pycryptopp's unused ECDSA-192 vs. its new Ed25519 and its current
RSA-2048. I added a benchmarking script and configured buildbot to run
it automatically. Then I amended it
[e6833d434fbad94d7fff753ea6293e99d67a3f7c] to do 256-bit ECDSA, which
is comparably strong to Ed25519, and 3248-bit RSA, which is comparably
strong to Ed25519 (according to ECRYPT II --
http://www.keylength.com/en/3/ ). Also I added benchmarks for the
ciphers (AES-128, AES-256, and XSalsa20) and SHA-256 and the Python
Standard Library's "hashlib" implementation of SHA-256.

You can browse the buildbot
(https://tahoe-lafs.org/buildbot-pycryptopp/waterfall) for the
results, but here is my summary.

1. The important thing is that the RSA-2048 that we're currently using
for digital signatures takes a lot of CPU to generate a new keypair,
which we do on every mkdir and every creation of a mutable file.
(Every mutable directory and every mutable file comes with its own
keypair, so that you can grant someone write authority to that one by
giving them the private key without thereby granting them write
authority to any other file or directory.)

For example, here's the results on the Atlas buildslave (donated by
Atlas Networks and operated by Brian Warner -- thank you both!)

https://tahoe-lafs.org/buildbot-pycryptopp/builders/atlas1%20natty/builds/96/steps/bench/logs/stdio

It took 394 milliseconds to generate a keypair. Here is the
measurement of the same operation on other machines:

https://tahoe-lafs.org/buildbot-pycryptopp/builders/marcusw%20cygwin/builds/85/steps/bench/logs/stdio

453 milliseconds

https://tahoe-lafs.org/buildbot-pycryptopp/builders/Kyle%20OpenBSD-amd64/builds/99/steps/bench/logs/stdio

114 milliseconds

https://tahoe-lafs.org/buildbot-pycryptopp/builders/francois-ts109-armv5tel%20syslib/builds/95/steps/bench/logs/stdio

5879 milliseconds!

(That's François's little ARM box.)

2. RSA-2048 is not strong enough for long-term security. For our
target security level of 2¹²⁸, we would require RSA-3248. That is even
more ridiculously expensive to generate a key. On the Atlas buildslave
it takes 6000 milliseconds, and on the little ARM box it takes 50,000
milliseconds!

3. Ed25519 is much faster at generating keys -- Atlas server: 0.02
milliseconds, ARM box: 32 milliseconds. By inventing a new mutable
file format which uses Ed25519 (which is ticket #217), we can
noticeably reduce the delay in creating a new mutable file or
directory. It will also simplify the file format since Ed25519 private
keys and public keys are are merely 32 bytes each. This is small
enough that we can stick the whole private key into a write cap and
the whole public key into a read cap. This will be simpler than the
current scheme in which we tie RSA public keys—which are hundreds of
bytes—into the read caps by sticking the hash of the public key into
the read cap, encrypting the public key with said hash, and storing
the ciphertext of the public key to the storage server.

4. Our strategy has always been to choose algorithms that *can* be
implemented with great efficiency in the long run, even if the current
implementation that we are using is merely adequate. This is most
clearly shown by our choice of Ed25519 and the current "reference
implementation" thereof. The current reference implementation is a tad
slower than the current ECDSA implementation, but still adequate for
current needs. There exist more aggressively optimized implementations
of Ed25519 which are up to 100X faster! So if we ever need a more
efficient digital signature, we can get it by upgrading to a more
optimized implementation without losing compatibility with extant
versions of Tahoe-LAFS.

5. Unless there's something wrong with my benchmarks, encryption isn't
quite as fast as I'd like on  François's little low-power ARM box. 340
μs per byte? That almost 1 ms for 3 bytes! That means it would take a
whole second to en-/de-crypt 3000 bytes? If it were really that slow,
I would think that François's little ARM box would be uncomfortable to
actually use. However, I remember using it (he made it publicly
available as a gateway on the Test Grid), so it wasn't totally
unusable. If anybody else has a low-power CPU, please run the
pycryptopp benchmarks and report what you get.

Regards,

Zooko

patches mentioned in this letter:

https://tahoe-lafs.org/trac/pycryptopp/changeset/e6833d434fbad94d7fff753ea6293e99d67a3f7c/git

tickets mentioned in this letter:

https://tahoe-lafs.org/trac/tahoe-lafs/ticket/217# Ed25519-based
mutable files -- fast file creation, possibly smaller URLs