implement Poly1305 or VMAC

[zooko]

Poly1305 is a very fast and strong MAC designed by Prof. Dan Bernstein. You pair it with a cipher, and its security is proven on the assumption that the cipher is secure. I have a lot more confidence in the long-term security of Poly1305-XSalsa20 (or even in Poly1305-AES) than I do in HMAC-SHA256.

Unfortunately Poly1305 isn't implemented in Crypto++. Wei Dai, the author of Crypto++, is also the author of VMAC, which is a competitor to Poly1305. VMAC is faster than Poly1305 per-byte on long messages, but it has a higher setup cost than Poly1305 has, so for short messages it is slower.

On my old Pentium-M 1.86 GHz laptop Poly1305 took about 15,000 CPU cycles to setup and then MAC the first 64 bytes and VMAC took about 60,000 CPU cycles to do the same:

​http://osdir.com/ml/encryption.cryptopp/2008-02/msg00013.html

Our current need for a MAC is solely for use in a KDF e.g. HKDF-Poly1305 where the inputs will be only a few tens of bytes, so the performance on short messages is more important. Also potential future uses of MACs would also probably most often be used on short messages.

Also Poly1305 has more marketing power -- DJB pushes it (e.g. ​http://rdist.root.org/2009/07/14/nacl-djbs-new-crypto-library/ ). This means that over time Poly1305 is likely to get more peer-review and more independent re-implementation than VMAC.

I asked Wei Dai if he would please implement Poly1305 in Crypto++, and his final answer was: ​http://www.mail-archive.com/cryptopp-users@googlegroups.com/msg04168.html , which I interpret as basically that he'd be willing to accept it and support it, but he doesn't want to spend the time to implement it himself.

Now, it turns out that there doesn't exist a portable implementation of Poly1305! Here is the list of implementations, none of which we can just add into the pycryptopp source tree and have it automatically build on all of the platforms we support: ​http://cr.yp.to/mac.html

The most portable one is the one built on OpenSSL and GMP: ​http://cr.yp.to/mac/test.html . It looks like it might be fairly straightforward to adapt this implementation by replacing OpenSSL and GMP with Crypto++. Replacing OpenSSL's AES with Crypto++'s AES should be trivial, but replacing GMP's math functions with Crypto++'s might be trickier. That "test.html" page that I referenced says "The system must have GMP 3 or later (for the mpz_tdiv_q_ui return value)". The source code -- ​http://cr.yp.to/mac/poly1305_gmp.c -- looks like mpz_tdiv_q_ui() plus a few simpler functions is all we need. Here is the GMP API doc for mpz_tdiv_q_ui(): ​http://gmplib.org/manual/Integer-Division.html#Integer-Division and here is the GMP API doc for the other functions: ​http://gmplib.org/manual/Integer-Arithmetic.html#Integer-Arithmetic . Here is the API doc for Crypto++'s integers: ​http://www.cryptopp.com/docs/ref/class_integer.html

To close this ticket, either benchmark VMAC-XSalsa20 and Poly1305-XSalsa20 on a 32-bit ARM and convince us that the performance of VMAC-XSalsa20 is good enough or else port the ​http://cr.yp.to/mac/test.html implementation of Poly1305 to Crypto++'s integers from GMP and convince Wei Dai to accept your port into Crypto++.

(Why 32-bit ARM? Because among the architectures that we care about, that's the one where performance matters most -- wasting CPU cycles on ARM is much more likely to noticeably reduce battery life than wasting wasting CPU cycles on amd64, and it is also more likely to force a human to wait.)

[davidsarah]

Replying to zooko:

Poly1305 is a very fast and strong MAC designed by Prof. Dan Bernstein. You pair it with a cipher, and its security is proven on the assumption that the cipher is secure. I have a lot more confidence in the long-term security of Poly1305-XSalsa20 (or even in Poly1305-AES) than I do in HMAC-SHA256.

...

Our current need for a MAC is solely for use in a KDF e.g. HKDF-Poly1305 ...

Poly1305 is a Wegman-Carter-Shoup MAC. It's intended for use under the assumption that its nonce is unique, and its key is uniformly random and uncorrelated with other keys. A hash-based KDF, on the other hand, is intended to produce a suitable key even from a key that is not uniformly random, as long as it has sufficient entropy.

So, a Wegman-Carter-Shoup MAC might be subject to related-key attack. In fact, because AES is subject to related-key attack, there's no strong reason to believe that Poly1305-AES isn't. Also note that the Salsa20 papers specifically decline to consider security against related-key attack. (I quite agree with Bernstein that this isn't necessary for a cipher, and that the proper way to design protocols is to ensure that keys are uncorrelated. However, in the case of protocols like Tahoe's that derive keys originally from structured and possibly attacker-controlled plaintext, at some point you need to rely on a conventional hash function. Therefore, using Poly1305 is adding one extra algorithm to the protocol that you didn't really need.)

If you like Bernstein's algorithms (as I do) and want to use HKDF with one of them, then HKDF(HSalsa20) might be a better and simpler choice than HKDF(Poly1305-XSalsa20), because HSalsa20 is designed as a collision-resistant hash, and HKDF is designed to be constructed from a collision-resistant hash.

[davidsarah]

Replying to davidsarah:

If you like Bernstein's algorithms (as I do) and want to use HKDF with one of them, then HKDF(HSalsa20) might be a better and simpler choice than HKDF(Poly1305-XSalsa20), because HSalsa20 is designed as a collision-resistant hash, and HKDF is designed to be constructed from a collision-resistant hash.

OTOH,

• SHA-256 has had much more analysis than HSalsa20. (The analysis done on Salsa20 doesn't really carry over to the security of HSalsa20 as a hash function, and its ​security proof applies only to its use in XSalsa20.)
• SHA-256, unlike AES, doesn't have any data-dependent table lookups in an obvious implementation, so there's no reason to switch to HSalsa20 to protect against side-channel attacks.

But, I must apologize for drifting off-topic for this bug. Poly1305 would be a very useful MAC for Crypto++, and don't let my reservations about using it in a KDF discourage anyone from implementing it.

[davidsarah]

Gahh, HSalsa20 is not claimed to be collision-resistant. Rumba20 is. (Still off-topic, but I just wanted to correct this mistake.)

[zooko]

I think you're on the right track. We don't need to use Poly1305 here. But are you wrong to say that Tahoe-LAFS generates key material from structured and possibly attacker-controlled input? I guess that is true for things such as the convergent encryption key. But what I was thinking about was generating the ECDSA private key from a short secret input. In that case the input is a nice high-entropy, secret, evenly-distributed byte string.

So for some uses in Tahoe-LAFS we could use something fast and simple like subkey = XSalsa20(key=masterkey, plaintext=tag+salt), but for others we need something with collision resistance. So maybe I should stop thinking about a "good KDF" to be used in various ways and instead start thinking about the specific problem at hand. The first problem at hand is to finish ECDSA in pycryptopp by changing the way it generates a private exponent (private key) from a seed. There is currently an implementation in pycryptopp -- ​http://allmydata.org/trac/pycryptopp/browser/pycryptopp/publickey/ecdsamodule.cpp?rev=672#L269 -- but I don't want to commit to supporting it long-term because it uses the Tiger-192 hash function and an ad-hoc key-expansion mode.

Maybe all I need to do is replace that with a simple XSalsa20 invocation and be happy! :-)

[weidai]

A couple of clarifications:

I'm not "the" author of VMAC, I'm one of the two authors, but the main author is Ted Krovetz. He came up with the overall design and I just made some suggestions for improvement after reading his original paper, which Ted was kind enough to accept and share credit with me on the subsequent paper and specifications.

The reason I went looking for an alternative to Poly1305 in the first place was that it's hard to implement in a portable way that's also reasonably fast, and I didn't want to integrate and maintain the many versions of fast assembly code that DJB has written in his own qhasm language. I like DJB's designs in general and would have no problem putting Poly1305 in Crypto++ if the cost wasn't so high. The implication that I kept it out because I'm the (co)inventor of a competitor seems rather unfair.

[zooko]

I apologize for impugning your motives.

[zooko]

Okay once again my crypto designs have changed so that once again I no longer see a need for a MAC. So I'm closing this as wontfix until such a time as I once again want a MAC. (At which time we'll actually measure VMAC and Poly1305 doing what we need it to do on a platform that we care about.)