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.
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.
P = (1<<130) - 5Given 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; doneAdding 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)
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
but both are represented in bdcalc as the integer
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
fail (expected result
01:00:de:ad:be:ef, represented by the integer
# 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
- [POLY1305] Bernstein, D., The Poly1305-AES message-authentication code, March 2005. <http://cr.yp.to/mac/poly1305-20050329.pdf>.
- [CHACHA-TLS] Langley, et al, The ChaCha Stream Cipher for Transport Layer Security, September 2014. <https://tools.ietf.org/html/draft-mavrogiannopoulos-chacha-tls-03>.
- [CHACHA20-IETF] Nir, D. and A. Langley, ChaCha20 and Poly1305 for IETF protocols, January 2015. <http://tools.ietf.org/html/draft-irtf-cfrg-chacha20-poly1305-08>.
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.