id	summary	reporter	owner	description	type	status	priority	milestone	version	resolution	keywords	cc	launchpad_bug
33	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.)"	defect	closed	major		0.5.17	wontfix