1
$\begingroup$

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?

$\endgroup$
1
  • 1
    $\begingroup$ You could do something like Daence. $\endgroup$ May 27, 2023 at 17:54

3 Answers 3

1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

This SoK seems to provide variants of Poly1305 with bigger output and also discuss which other primes could be good alternatives.

Regarding concatenating two times Poly1305 with independent keys, this is also another secure option as proven in section 7.5 of this other paper but according to the benchmarks in the SoK (cf. Appendix D), it is less efficient than simply choosing a bigger and good prime.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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