Winternitz-OTS+ with Poly1305

Would it be safe to implement Winternitz OTS+ using Poly1305 as a parameterized MAC? It's very fast and apparently very secure but with the caveat that keys cannot be used more than once, which is fine for this application. Does anyone know if Poly1305 has any features that differ from a normal HMAC that would make it unsafe for this application?

The requirement of the function in Winternitz OTS+ is a pseudorandom function family, or PRF: a family of functions $F_K\colon \{0,1\}^n \to \{0,1\}^m$ such that if $K$ is uniformly distributed in all $k$-bit strings, then $F_K$ is indistinguishable from a uniform random choice of function $U\colon \{0,1\}^n \to \{0,1\}^m$. Specifically, the best known random algorithm $A(G)$ taking a function $G\colon \{0,1\}^n \to \{0,1\}^m$ to a true/false value and having a plausible computational cost has a negligible PRF advantage, $$\operatorname{Adv}^F_{\mathrm{PRF}}(A) = |\Pr[A(F_K) = 1] - \Pr[A(G) = 1]|,$$ which compares the probability that $A$ returns true for $F_K$ under uniform random distribution on $K$ to the probability that $A$ returns true for a uniform random function $U$.

Poly1305 is a one-time message authentication code, or one-time authenticator/MAC: a family of functions $H_K\colon \{0,1\}^n \to \{0,1\}^t$ such that if $K$ is uniform random, then given up to a single message $M$ and its authentication tag $T = H_K(M)$, an adversary has no hope of finding another message $M'$ and authentication tag $T'$ such that $T' = H_K(M')$—it resists forgery after a single message. That is, the forgery probability for a random algorithm $A(M, T)$ giving $(M', T')$, namely $\Pr[M' \ne M, H_K(M') = T']$, is negligible.

A PRF makes a passable MAC, even a one-time MAC, although as you note Poly1305 is a much more efficient one-time MAC than a PRF. However, a one-time MAC does not make a passable PRF. Why not? The adversary's algorithm $A$ in the notion of PRF advantage is allowed to call the function more than once.

To make this concrete, consider the secure one-time MAC $H_K(M)$ for $K = (K_0, K_1) \in \operatorname{GF}(2^{128}) \times \operatorname{GF}(2^{128})$ and $M \in \operatorname{GF}(2^{128})$ defined by $$H_{K_0, K_1}(M) = K_0 M + K_1.$$ (This is essentially GHASH, of AES-GCM, limited to one message block, which is a polynomial evaluation MAC much like Poly1305. We can naturally interpret any 128-bit string as an element of $\operatorname{GF}(2^{128})$ given a choice of irreducible degree-128 binary polynomial like the standard GHASH one.)

How do we define the algorithm $A$ to distinguish $H_K$ from $U$? We can first compute $T = K_0 M + K_1$ and $T' = K_0 M' + K_1$ by evaluating the putative $H_K$ on two different inputs, and then solve for $K_0$ and $K_1$ using secondary school algebra. Then we can immediately distinguish $H_K$ from a uniform random function $U$ with high probability by computing the candidate function on $M''$ and checking whether we get $K_0 M'' + K_1$: with high probability, a uniform random function will give something else.

Actually, Winternitz OTS+ requires a slightly weaker notion than pseudorandom function family, namely key one-wayness: for uniform random key $K$ and input $X$, letting $Y = F_K(X)$, the success probability of the best known algorithm $A(X, Y)$ for recovering the key (or an equivalent), $$\operatorname{Adv}^F_{\mathrm{KOW}}(A) = \Pr[Y = F_{A(X, Y)}(X)]$$ is negligible, as long as it has a plausible computational cost, where $Y = F_K(X)$. I leave it as an exercise to the reader to define such an algorithm $A$ for a polynomial evaluation MAC like the above example.

• Now that I think about it, I'm actually not sure the KOW condition gives $A$ access to $F_K$ on more than one message, in which case maybe a one-time MAC is sufficient. Feb 5 '18 at 18:36

WOTS+ requires a family of second-preimage resistant, undetectable one-way functions. Any MAC does most likely not fulfill this requirement and the definition of MAC definitely does not suffice.

There exists a WOTS version (later) called WOTS-PRF which uses a PRF instead. However, it recently turned out that there is a flaw in the WOTS-PRF paper (see this paper). Currently it is not known how to fix the proof. While this does not allow for an attack, instantiating WOTS with a PRF is not suggested until someone figures out a fix. Note that this flaw is limited to the proof for WOTS-PRF and does not concern any other variants like WOTS+.

• Sounds like it's unwise then to implement Winternitz in any form without using a strong truly cryptographic hash function like SHA, BLAKE, etc. Feb 8 '18 at 18:17
• Well, you need second-preimage resistance, undetectability and one-wayness... collision-resistance is not required (if you use the WOTS+ construction). Only the WOTS-PRF proof has a flaw. The others are fine. Feb 9 '18 at 21:06