Can Poly1305-AES be used with AES-256?

Question

I'm reading through Bernstein's The Poly1305-AES message-authentication code.

The MAC is predicated on 16-byte block ciphers like AES and produces 16-byte authentication tags. However, Bernstein does not really discuss the block cipher's key sizes, other than to state its a 32-byte key comprised of a 16-byte key and a second 16-byte string r.

I presume Bernstein selected AES-128 because it met security requirements with the most efficiency (i.e., AES-128 is faster than AES-256 because it uses fewer rounds, among other stated criteria). (Bernstein talks about the selection of other parameters, like r, in the section Design Decisions).

If one desired, could Poly1305-AES be used with AES-256? In this case, a 48-byte key would be used.

Answer 1

Yes, Poly1305-AES can safely be modified to use AES-256 rather than AES-128; but if AES is implemented in software beware of not introducing a timing vulnerability in the implementation.

Change of the cipher in Poly1305-AES is explicitly endorsed; quoting D. J. Bernstein's The Poly1305-AES message-authentication code

There is nothing special about AES here. One can replace AES with an arbitrary keyed function from an arbitrary set of nonces to 16-byte strings. (..)
Perhaps AES will be broken someday. If that happens, users should switch to Poly1305-AnotherFunction. Poly1305-AnotherFunction provides the same security guarantee relative to the security of AnotherFunction.

The reference implementation of Poly1305-AES in software has AES carefully optimized to reduce cache-induced timing dependencies; beware that whatever AES-256 implementation is used is at least as good from this standpoint. If AES is implemented using AES-NI, in hardware, or otherwise in constant time (e.g. on a CPU without cache), that's a non-issue.

More generally, in any system using AES-128, if we can double the key size, we can safely use AES-256 instead from a theoretical standpoint; and if we can tolerate the slightly slower operation, and do not introduce a vulnerability (in particular by timing of cache misses), that's fine from a practical standpoint.