DI Management Home > Cryptography > Poly1305 authenticator

Poly1305 authenticator

The Poly1305 authenticator is a high-speed message authentication code designed by Daniel J. Bernstein [POLY1305]. It takes a 256-bit one-time key and a message and outputs a 128-bit tag.

Poly1305 is currently being incorporated along with the ChaCha stream cipher as an alternative algorithm for TLS [CHACHA-TLS] and as part of a proposed "standby" algorithm for IETF protocols [CHACHA20-IETF] which uses it both as a simple authenticator and as part of an Authenticated Encryption with Additional Data (AEAD) algorithm.

We show here how you can use the latest version of bdcalc to reproduce the example test vector for poly1305 in section 2.5 of ChaCha20 and Poly1305 for IETF protocols [CHACHA-TLS].

To help with this, we added some byte manipulation functions to version 2.1 of bdcalc. These byte manipulation functions treat large integers as arrays of bytes (octet strings) in "big-endian" order. Reversing the bytes will give the integer in "little-endian" order. You can do some fancy tricks with masks to break up the input into the required 16-byte blocks. The actual big integer arithmetic to compute the MAC is easy.

BTW we're not saying this is a good example of an efficient or fast implementation of poly1305. It's just an explanation of the big digit computations involved.

The Code

The script poly1305.bdscr (source) shows how to reproduce the example test vector (output).

Setting P is easy 
   P = (1<<130) - 5
Given a one-time 256-bit key in network order we can separate out r and s as 128-bit little-endian numbers 
# 256-bit key in network order
k = 0x85d6be7857556d337f4452fe42d506a80103808afb0db2fd4abff6af4149f51b
s = k band mask128
s = revbytes(s, 128/8)
printf("s as 128-bit number: 0x%x\n", s)
r = (k >> 128) band mask128
r = revbytes(r, 128/8)
# clamp r
 r = r band 0x0ffffffc0ffffffc0ffffffc0fffffff
printf("r after clamping   : 0x%x\n", r)
We set the message as a large integer in network order and then reverse the bytes 
msg = 0x43727970746f6772617068696320466f72756d2052657365617263682047726f7570
mbytes = bytelen(msg)  # Careful if have leading zero bytes
nblocks = (mbytes + 15) / 16
msg = revbytes(msg, bytelen(msg))
We can then use a 128-bit mask of 1's [mask128 = ((1<<128)-1)] to work through the message in blocks of 16 bytes 
for i in (1..nblocks) do
  block = msg & mask128;
  # ...
  msg = msg >> 128;
done
Adding the 0x01 byte can be done by a shift and an XOR (this can be improved: see below) 
   block = (0x01 << (bytelen(block))*8) | block;
The actual core calculation is simple 
   acc = ((acc+block)*r) mod P;
At the end, we simply add s to the accumulator and reverse the order of bytes back to network order. 
tag = acc + s
tag = revbytes(tag, 16)
printf("Serialize to get the tag as a 16-byte octet string:\nComputed: [%032x]\n", tag)

An improvement

There is one issue with the bytelen() function in bdcalc where we have leading zero bytes at a boundary.

As an example, the 5-byte octet string 00:de:ad:be:ef is different from the 4-byte octet string de:ad:be:ef, but both are represented in bdcalc as the integer 0xdeadbeef (3735928559). Both bytelen(0x00deadbeef) and bytelen(0xdeadbeef) return 4, the number of significant bytes, which may not be what we want.

In particular, using the bytelen() function to prepend a 0x01 byte to the octet string 00:de:ad:be:ef will fail (expected result 01:00:de:ad:be:ef, represented by the integer 0x100deadbeef) 

# leading zeros are ignored for the 5-byte octet string 00:de:ad:be:ef...
> !block = 0x00deadbeef
0xdeadbeef
# so using bytelen() will not work as we expect...
> bytelen(block)
4
# and our attempt to prepend a 0x01 byte using `bytelen(block)` will fail..
> !(0x01 << (bytelen(block))*8) | block;
0x1deadbeef
# But if we know the correct length, we get what we want...
> blklen = 5
5
> !(0x01 << (blklen)*8) | block;
0x100deadbeef

The above poly1305 code can be improved by carefully counting bytes and avoiding bytelen() where there might be a leading zero byte: see improved source and differences with original.

References

Contact

For more information, or to comment on this page, please send us a message.

This page first published 28 January 2015. Last updated 11 July 2018.