# What is the function of the secret key “r” in Poly1305?

Poly1305-AES uses two per-connection keys $k$ (for AES) and $r$ (for Poly1305's compression function) and a per-message nonce n to execute. I've read the original paper on the implementation, and I think I understand what it does, but not how it works. In particular, if the security of the MAC is dominated by the security of $AES_k(n)$, why must $r$ be kept secret?

In other words: what are the security properties of $Poly1305_r(m)$ by itself, before adding $AES_k(n)$?

-
$r$ being secret is essential. The only point of $s$ is to prevent an attacker from learning $r$. –  CodesInChaos Dec 2 '13 at 8:50

$Poly1305_{{r,s}}(m)$ is a one-time authenticator - it can be used to authenticate only a single message with any given key $(r,s)$ without violating the security guarantees (the violation is immediate - only two authenticated messages with the same key are required to create a forgery according to the nacl docs).

There are two 128 bit key values to this function (commonly combined into a single 256 bit key):

• $r$ is the basis for the polynomial evaluation (in a specific format with some bits cleared)
• $s$ is a key value that is added at the end to the result of the polynomial evaluation

Both of these values are part of the key - the specification requires that the key (including $r$) is unpredictable, and the size of the set $R$ from which $r$ is sampled does factor in the security proofs, so I would presume that exposing $r$ would compromise the security guarantee to some degree. Given the $2^{106}$ bound on that security, I would treat all parts of they key as secret.

$Poly1305{-}AES_{(r,k,n)}(m)$ extends $Poly1305$ into a general purpose MAC function - i.e. it can be used to authenticate many messages with a single key $(r,k)$ as long as the nonce $n$ is not repeated.
The extension is achieved by replacing the $s$ value in the one-time authenticator with the result of $AES_k(n)$, which produces an unpredictable value for each unique nonce.

The $AES$ part of the calculation can be replaced by another secure cipher - e.g. the nacl library uses $xsalsa20$ to encrypt the nonce, but other block ciphers like Serpent/Twofish etc. will work just as well.

-
These things are all true, but it doesn't really answer the question. How is the security of the MAC affected by publishing either r or s, but not both? In detail, how is the hash's resistance to forgery based on the secrecy of both r and s? –  Jonathan Dec 2 '13 at 4:36

$Poly1305_{k,r}(N,M)$ is a Carter-Wegman nonce-based MAC, whose security crucially depends on the uniqueness of nonce $N$ for every message $M$. It is defined as $$Poly1305_{k,r}(N,M) = f(M,r) + AES_k(N),$$ where $f(M,r)$ is a polynomial of $r$ with coefficients derived from the binary representation of $M$, and $AES_k(N)$ is the encryption of nonce $N$ on key $k$.

The function $f(M,r)$ alone does not have provide any security. Given $f(M_1,r)$ and $f(M_2,r)$ for two distinct $M_1,M_2$, it is easy to recover $r$ and generate a forgery. This is even easier if $r$ is known.

Therefore, it is a uniqueness of nonce $N$ (and hence its ciphertext) that randomizes the MAC value and makes it unpredictable. The importance of $f$ comes from its speed, which is larger than that of AES, whereas the call of AES is independent of the message and its length.

-
I think you missed the point of the question ... which is "why must $r$ stay secret", not "why do we have a nonce?" –  Paŭlo Ebermann Dec 2 '13 at 21:21
$r$ must stay secret, because it is easy to construct collisions for $f$ if you know $r$. These collisions are forgeries for the MAC. –  Dmitry Khovratovich Dec 2 '13 at 21:41