poly1305.nx

poly1305.nx -- Bernstein's Poly1305 MAC (RFC 8439 variant). One-time authenticator over prime p = 2^130 - 5. Takes a 256-bit one-time key (128-bit r clamped + 128-bit s), a message of any length, and produces a 16-byte tag that is unforgeable under a unique-per-message key assumption. Why Poly1305: - Proven secure in the one-time-key model (Bernstein 2005). - Pairs with ChaCha20 to form the RFC 8439 AEAD construction (ChaCha20-Poly1305), the primary TLS 1.3 cipher suite that avoids AES cache-side-channel concerns. - Naturally constant-time on this design: only modular multiplication and addition, no branches on key/message bits. (Some implementations use table lookups for performance -- we avoid those for side-channel reasons.) - Under Grover's algorithm a 128-bit MAC has 64-bit effective security against quantum second-preimage -- that's marginal, but second-preimage on a MAC isn't a practical attack; the one-time-key property is what matters. Arithmetic representation: r and acc live as 5 x 26-bit limbs (total ~130 bits). Each limb fits in i64 with headroom; partial products during multiplication sum to at most ~5 * 2^52 = 2^54.3, still in i64 range. After multiplication we carry-propagate and reduce modulo p = 2^130 - 5 via the standard Bernstein trick (multiply high bits by 5, add back to low). Invariants: P1 No branch depends on secret data (key or message bytes). P2 The message is processed exactly once per block; padding of the final short block is explicit (append 0x01, zero- extend), no early exit. P3 The r-clamp (RFC 8439 §2.5) is applied once at key setup; never reapplied mid-stream so no key material leaks. P4 Caller guarantees a *fresh* 256-bit key per message. Poly1305 is not secure if the same r+s pair authenticates two distinct messages. In ChaCha20-Poly1305 this is enforced by deriving (r, s) from ChaCha20(key, nonce, 0).