Score:1

Poly1305 variants with bigger output?

br flag

This is a rather simple question, but answers are nowhere to be found. Are there any variants of Poly-n hashing algorithms which provide bigger outputs (like 32 instead of 16 bytes)? Or, is there any research which discusses the variability of the constant $2^{130}-5$, why this number is special or whether there are other good alternatives? I understand that it would be better if it was a prime number, but are all primes good (ignoring the cost of modular arithmetic)? Or, could I use the Poly1305 two times with two differenst pairs of $(r,s)$ and concatenate to produce a 32-byte hash?

samuel-lucas6 avatar
bs flag
You could do something like [Daence](https://eprint.iacr.org/2020/067).
Score:1
tr flag

$\newcommand{FP}{\mathbb F_p}$ The authenticator built on Poly1305 follows a generic construction to build MAC from a universal hash and a pseudo-random function. So, increasing the field size and hence output size (assumedly for security) is possible, in theory at least. Poly1305 precisely refers to the universal hash part of the construction. Which itself is a polynomial evaluation hash that can be generically defined over any field $\FP$. The actual details of Poly1305 are somewhat more complicated. But the point is that this construction yields an excellent Difference-Unpredictable Hash.

The “issue” comes from turning such a hash into a MAC, especially when $p$ is a prime. In the purest version of the MAC scheme, we would simply have a PRF generating values in $\FP$. However, the most practical and efficient PRFs, including AES that is commonly used with Poly1305, produce $n$-bit strings instead. Leaving us with two options for how big $p$ should be: 1) either slightly larger than $2^n$ or 2) slightly smaller. Poly1305 makes the first choice, which offers one big advantage: The message can be broken up and processed in $n$-bit blocks. With the second option, we would need to process inputs as field elements. Which is inconvenient if $p$ is prime. Again, the actual implementation details are likely to be more involved than this.

Finally, increasing the field size would require adjusting the PRF size accordingly. Otherwise, there might not be significant security gains. Which means that we would also need a performant PRF with bigger output space.

Score:1
ru flag

To add to Marc Ilunga's excellent answer, I would point out that that the efficiency of Poly1305 is platform dependent. It covers the very important software space where chip instructions can be relied on to include highly optimised integer/float multiplication and addition operations. I believe that the choices in Poly1305 are highly tuned to the capabilities of current chip sets.

In more constrained environment, it can be better to base the polynomial evaluation hash over a binary field $\mathbb F_{2^w}$. This is done in the GHASH function that is used in Galois Counter Mode and although usually described over $\mathbb F_{2^{128}}$, the 2004 GHASH paper describes GHASH for any even $w$. This also gives an exact match between blocks and field elements and hence provable universality.

There have been a few other polynomial evaluation hashes over prime fields tested for performance in the literature these include $p=2^{127}-1$ and $p=2^{64}-59$.

I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.