Poly1305 is a cryptographic Message Authentication Code (MAC). That is, it takes a secret key and a message and produces a short "tag" that is extremely difficult to forge unless you know the secret key. It therefore can be used to authenticate a message and ensure it hasn't been tampered with. Compared to the more widely known HMAC, Poly1305 is extremely fast. (Or rather, has the potential to be - I make no claims about the speed of the implementation on this page).
The downside is that if an attacker sees two raw Poly1305 tags from the same key but for different messages, then they can recover the key using straightforward arithmetic. For this reason, modes that use Poly1305 either encrypt the tag with a separate key or derive a fresh Poly1305 key for each message. It is most often used in combination with the ChaCha20 stream cipher (e.g., in TLS), where the combined authenticated encryption scheme is known as ChaCha20-Poly1305, or "ChaPoly" for short.
The name derives from it being a polynomial evaluation MAC (i.e., it treats the message as a large polynomial with secret coefficients), based on the prime number 2^130-5.
The following code provides a very naive implementation, using Tcl's native bigint support. This version is unsafe against timing side-channel attacks and so should only be used in offline/batch applications where timing cannot be observed. I am working on a version that uses more specialised arithmetic to avoid these timing issues.
# poly1305.tcl --
#
# Implementation of the Poly1305 authenticator.
#
# Copyright (c) 2018 Neil Madden.
# License: Tcl-style
package require Tcl 8.6
package provide poly1305 1.0.0
# poly1305 compute key message
# poly1305 verify key message tag
#
# Computes or verifies a Poly-1305 message authentication code (MAC).
# Poly1305 is a fast, cryptographically secure polynomial MAC. It is
# information theoretically secure, although only if the key is only used
# to authenticate a single message. The key can be recovered if more than
# one message tag is computed with the same key. Therefore either a per-message
# fresh key should be computed, or else the tag should be encrypted under
# a separate key.
#
namespace eval ::poly1305 {
namespace export compute verify
namespace ensemble create
#proc debug {msg args} { puts [format $msg {*}$args] }
proc debug args {}
proc clamp r {
expr {$r & 0x0ffffffc0ffffffc0ffffffc0fffffff}
}
proc verify {key data tag} {
set expected [compute $key $data]
equals $expected $tag
}
# constant time equality check
proc equals {a b} {
if {[string length $a] != [string length $b]} {
return 0
}
set ret 0
binary scan $a c* as
binary scan $b c* bs
foreach x $as y $bs {
set ret [expr {$ret | ($x ^ $y)}]
}
expr {$ret == 0}
}
proc compute {key data} {
binary scan $key wu2wu2 r s
set r [expr {([lindex $r 1] << 64) | [lindex $r 0]}]
set s [expr {([lindex $s 1] << 64) | [lindex $s 0]}]
set r [clamp $r]
debug "r = %32llx" $r
debug "s = %32llx" $s
set a 0
set p [expr {(1 << 130) - 5}]
for {set i 1} {$i <= ([string length $data] + 15) / 16} {incr i} {
set start [expr {($i - 1) * 16}]
set end [expr {min($start + 15, [string length $data])}]
debug "Block %d - start: %d, end: %d" $i $start $end
set bytes [string range $data $start $end]\x01
debug "Length = %d" [string length $bytes]
append bytes [string repeat \x00 [expr {17 - [string length $bytes]}]]
binary scan $bytes wu2c1 n c
set n [expr {(($c & 1) << 128) | ([lindex $n 1] << 64) | [lindex $n 0]}]
debug "a = %032llx, n = %032llx" $a $n
incr a $n
set a [expr {($r * $a) % $p}]
debug "(a+n)*r mod p = %032llx" $a
}
incr a $s
set s1 [expr {($a >> 64) & 0xFFFFFFFFFFFFFFFF}]
set s2 [expr {$a & 0xFFFFFFFFFFFFFFFF}]
binary format ww $s2 $s1
}
}
##### TESTS #####
if {![info exists argv0] || [file tail [info script]] ne [file tail $argv0]} {
# Not running as main script so return to avoid running tests below
return
}
proc fromHex hex {
regsub -all {\s+} $hex {} hex
regsub -all {:} $hex {} hex
regsub -all {..} $hex {\x\0} hex
subst $hex
}
proc assertEqual {a b {msg ""}} {
if {$a ne $b} {
puts "FAIL - assertion failed: expecting '[binary encode hex $a]' to equal '[binary encode hex $b]' $msg"
} else {
puts "PASS - $msg"
}
}
set key [fromHex {85:d6:be:78:57:55:6d:33:7f:44:52:fe:42:d5:06:a8:01:0
3:80:8a:fb:0d:b2:fd:4a:bf:f6:af:41:49:f5:1b}]
set msg "Cryptographic Forum Research Group"
set tag [fromHex {a8:06:1d:c1:30:51:36:c6:c2:2b:8b:af:0c:01:27:a9}]
assertEqual [poly1305 compute $key $msg] $tag "poly1305 compute"
assertEqual 1 [poly1305 verify $key $msg $tag] "poly1305 verify"
assertEqual 0 [poly1305 verify $key $msg [string range $tag 1 end]] "poly1305 verify - wrong length"
assertEqual 0 [poly1305 verify $key $msg [string reverse $tag]] "poly1305 verify - wrong tag"
# vim: ft=tcl