Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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)$?

share|improve this question
    
$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
add comment

2 Answers

$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.

share|improve this answer
1  
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
add comment

$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.

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.