4
$\begingroup$

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.

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ The question is not just if it can be replaced, the question becomes if it would be any more secure if you do. It seems the polynomial was chosen to provide $2^{106}$ bits of security. Changing the underlying cipher to 256 bits keys may not provide the same level of security increase ("may" means I'm really not sure either way, but it seems to me that it won't). $\endgroup$ – Maarten Bodewes♦ Mar 29 '15 at 15:12
  • $\begingroup$ @Maarten - agreed. I'm not really looking to improve theoretical security. Rather, I'm trying to nail down an interface to Poly1305 in the Crypto++ library. In effect, the question becomes how much leeway to allow a programmer when constructing one in Crypto++. $\endgroup$ – user10496 Apr 1 '15 at 8:26
  • $\begingroup$ OK, so if you are going to allow this then a bit of a warning to your users would be nice. $\endgroup$ – Maarten Bodewes♦ Apr 1 '15 at 20:42
5
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • 2
    $\begingroup$ After thinking about it some more, I don't think there's an advantage to using AES-192 or AES-256. Unless, of course, the security level of AES-128 drops below the security provided by r, which is 106 bits. And I don't know what would happen if AES-128 lost 20 or 25 bits of security overnight. It would probably be kind of funny to watch (in a morbid sort of way). $\endgroup$ – user10496 Apr 1 '15 at 8:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy