I\'m reading through Bernstein\'s The Poly1305-AES message-authentication code.
ID: 651750 • Letter: I
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.
Explanation / Answer
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.
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.