Poly1305-AES: a state-of-the-art message-authentication code D. J. Bernstein
Authenticators and signatures

A state-of-the-art message-authentication code

Why is Poly1305-AES better than other message-authentication codes?
How do I use Poly1305-AES in my own software?
How does the Poly1305-AES implementation work?
Where can I learn more about Poly1305-AES?
Poly1305-AES speed tables
AES timing variability at a glance
AES timing variability graphs
Poly1305-AES for the Athlon
Poly1305-AES for the Pentium Pro/II/III/M
Poly1305-AES for the PowerPC under AIX
Poly1305-AES for the PowerPC under MacOS X
Poly1305-AES for the UltraSPARC
Poly1305-AES for generic computers with IEEE floating point
Poly1305-AES for the 8051
Poly1305-AES using GMP and OpenSSL
Poly1305-AES is a state-of-the-art secret-key message-authentication code suitable for a wide variety of applications.

Poly1305-AES computes a 16-byte authenticator of a message of any length, using a 16-byte nonce (unique message number) and a 32-byte secret key. Attackers can't modify or forge messages if the message sender transmits an authenticator along with each message and the message receiver checks each authenticator.

There's a mailing list for Poly1305-AES discussions. To subscribe, send an empty message to poly1305-subscribe@list.cr.yp.to.

Why is Poly1305-AES better than other message-authentication codes?

Poly1305-AES has several useful features:

Guaranteed security, cipher replaceability, and parallelizability are provided by the standard polynomial-evaluation-Wegman-Carter-MAC framework. Within that framework, hash127-AES achieved extremely high speed at the expense of a large table for each key. The big advantage of Poly1305-AES is key agility: extremely high speed without any key expansion.

Other standard MACs are slower and less secure than Poly1305-AES. Specifically, HMAC-MD5 is slower and doesn't have a comparable security guarantee; CBC-MAC-AES is much slower and has a weaker security guarantee. Both HMAC-MD5 and CBC-MAC-AES are breakable within 2^64 messages. I'm not saying that anyone is going to carry out this attack; I'm saying that everyone satisfied with the standard CBC security level should be satisfied with the even higher security level of Poly1305-AES.

How do I use Poly1305-AES in my own software?

My fast poly1305aes library is in the public domain. You can and should include it in your own programs, rather than going to the effort of linking to a shared library; the compiled code is between 6 and 10 kilobytes, depending on the CPU.

To get started, download and unpack the poly1305aes library:

     wget http://cr.yp.to/mac/poly1305aes-20050218.tar.gz
     gunzip < poly1305aes-20050218.tar.gz | tar -xf -
Compile the library (making sure to use appropriate compiler options for your platform, such as -m64 for the UltraSPARC) to get an idea of how it's structured:
     cd poly1305aes-20050218
     env CC='gcc -O2' make
Copy the library files into your project:
     cp `cat FILES.lib` yourproject/
     cat Makefile.lib >> yourproject/Makefile
For any C program that will use Poly1305-AES, modify the program to include poly1305aes.h; also modify your Makefile to link the program with poly1305aes.a and to declare that the program depends on poly1305aes.a and poly1305aes.h.

Inside the program, to generate a 32-byte Poly1305-AES key, start by generating 32 secret random bytes from a cryptographically safe source: kr[0], kr[1], ..., kr[31]. Then call

to create a 32-byte Poly1305-AES secret key kr[0], kr[1], ..., kr[31].

Later, to send a message m[0], m[1], ..., m[len-1] with a 16-byte nonce n[0], n[1], ..., n[15] (which must be different for every message!), call

to compute a 16-byte authenticator a[0], a[1], ..., a[15].

After receiving an authenticated message a[0], a[1], ..., a[15], n[0], n[1], ..., n[15], m[0], m[1], ..., m[len-1], call

to verify the authenticator. Accept the message if poly1305aes_verify returns nonzero; otherwise throw it away.

Do not generate or accept messages longer than a gigabyte. If you need to send large amounts of data, you are undoubtedly breaking the data into small packets anyway; security requires a separate authenticator for every packet.

Please make sure to set up a Googleable web page identifying your program and saying that it is ``powered by Poly1305-AES.''

How does the Poly1305-AES implementation work?

Interested in writing your own Poly1305-AES implementation? Seeing whether Poly1305-AES can benefit from, say, AltiVec? Using Poly1305-AES in a language without C linkage? Checking Poly1305-AES test vectors? Building Poly1305-AES circuits? Adapting the Poly1305-AES computational techniques to other functions?

The simplest C implementation of Poly1305-AES is poly1305aes_test, which relies on GMP and OpenSSL. I suggest starting from the top: read poly1305aes_test_verify.c and work your way down.

Test implementations in other languages:

You can then move on to the serious implementations:

If you're trying to achieve better speed, make sure you understand all the different situations covered by my speed tables. You might want to start with my essay on the difference between best-case benchmarks and the real world. I designed the Poly1305-AES software, and the underlying Poly1305-AES function, to provide consistent high speed in a broad range of applications. A slight speedup in some situations often means a big slowdown in others; a Poly1305-AES implementation making that tradeoff might be useful for some applications, but it will be at best an alternative, not a replacement.

Where can I learn more about Poly1305-AES?

There are four papers: I'm also giving three talks on Poly1305-AES: 2005.02.15, emphasizing the structure of message-authentication codes; 2005.02.21, emphasizing the difference between best-case benchmarks and the real world; 2005.05, emphasizing the security-bound proof.