2
$\begingroup$

Why not use chacha derivatives (BLAKE, rumba) to make an [H]MAC for use with chacha? Why use poly1305?

This question is especially interesting considering...

"The security of Poly1305[...] is very close to the underlying [...] block cipher algorithm." -Wikipedia


So... why not reconfigure chacha as a Merkle–Damgård like construction. (Or a HAIFA construct, as is done with BLAKE.) Then do a standard H(key || H(key || message)) for effective HMAC? Then, from here, you have CHF, MAC, and AEAD, all from one cipher.

$\endgroup$
  • $\begingroup$ Notice BLAKE is not using Merkle–Damgård but a simplified HAIFA construct instead. $\endgroup$ – Lery Nov 15 at 13:27
5
$\begingroup$

OK, so the core ChaCha primitive (for any fixed number of rounds) is a function $\operatorname{ChaCha}: \{0,1\}^{256}\times \{0,1\}^{64}\times\{0,1\}^{64}\to \{0,1\}^{512}$ which is believed to be a secure PRF when the first input is the key.

So now that we know what ChaCha is, for the three desired functionalities:

MAC. Of course a PRF is also immediately a secure MAC, but ChaCha only accepts 128 bits of input. So you could only MAC messages that are exactly 128-bit long, which isn't practically useful in itself. So this would mean you'd have to build a secure MAC around ChaCha which is certainly possible but needs to be standardized so everyone is doing the same and can talk to each other.
Possible variants include running ChaCha in CBC-MAC mode, in OMAC-mode, with Poly1305, or using a using a cascade-style construction where a subset of the output is the next iteration's input.
One could also build a Merkle-Damgard HMAC out of ChaCha but there you face the significant problems, that

  • each iteration only consumes 128-bit of data,
  • the HMAC security proof requires a PRF that can use either input as the key which doesn't immediately follow from our above model, and
  • ChaCha only takes 384-bit of input but produces 512-bit, how do you map this for the iteration?

As for why it's paired with Poly-1305 that mostly due to the fact that this construction is even faster than any of the above other options because the evaluation of Poly1305 is one polynomial multiplication per 128-bit of data, much less work than 20 ChaCha rounds. The speed estimate is 125 cycles / byte on 8-bit low-end platforms and much faster on wider platforms.

For Collision-Resistant Hashing, see my other answer.

AEAD. Again, using a mode like CCM or EAX you can build an AEAD scheme from any PRF like ChaCha. Or alternatively you can use the more efficient ChaCha-Poly construction, but there's no "immediately obvious way" to build AEAD from a PRF short of making use of predefined modes like the above.

$\endgroup$
  • $\begingroup$ The 8-bit case is interesting, and relevant to what I'm actually doing. The thing that sparked my question was my evaluation of the speed of these two things on 8-bit hardware. I currently have chacha20 running on an 8-bit PIC18 at around 205 cycles/byte. My first glance over poly1305 made me think it was going to take in the 10k cycle range for one loop though. Clearly, I must have missed something. $\endgroup$ – Charlie Nov 15 at 18:42
  • 2
    $\begingroup$ @Charlie If you're looking for a really small primitive out of which to build lots of symmetric cryptography on a tiny device, you might want to consider libhydrogen, which uses the 384-bit permutation Gimli for everything. $\endgroup$ – Squeamish Ossifrage Nov 15 at 19:42
  • $\begingroup$ Thanks, I'll definitely take a look. +1 $\endgroup$ – Charlie Nov 15 at 19:45
3
$\begingroup$

Why not use chacha derivatives (BLAKE, rumba) to make an [H]MAC for use with chacha? Why use poly1305?

Performance. Poly1305 is extremely cheap to compute, and the computation can be essentially arbitrarily parallelized, because it's just evaluating a polynomial modulo $2^{130} - 5$.

In contrast, functions like BLAKE2 and Rumba20 can't be parallelized without changing what it is they compute: the parallel BLAKE2bp is a different function from BLAKE2b, so you can't speed up an implementation of a protocol involving BLAKE2b by dropping in BLAKE2bp, because it will be incompatible.

(More details.)

Security goals. Poly1305 has very different security goals from ChaCha, BLAKE, Rumba20, etc.

  • Poly1305 is a universal hash family. The important property for Poly1305 as a building block in a MAC is that, from the perspective of an adversary who doesn't know the secret key $r$ or the values of the Poly1305 function, $\operatorname{Poly1305}_r$ has bounded difference probability: for any distinct messages $x \ne y$ of length up to $L$ bytes and any 128-bit string $\delta$,

    \begin{equation*} \Pr[\operatorname{Poly1305}_r(x) - \operatorname{Poly1305}_r(y) = \delta] \leq 8\lceil L/16\rceil/2^{106}. \end{equation*}

    Bounded difference probability is cheap and easy to prove. However, an adversary who can see a Poly1305 output can quickly recover the secret key $r$ (or at least narrow it down to $8\lceil L/16\rceil$ possibilities). So to use Poly1305 as a message authentication code, we usually encrypt its output with a one-time pad, $\operatorname{Poly1305}_r(m) + s$, and then to make that practical we derive $s$ pseudorandomly under a secret key from a unique message number.

    For example, in Poly1305-AES, we derive $s = \operatorname{AES}_k(m)$ under the secret key $k$. NaCl crypto_secretbox_xsalsa20poly1305 uses XSalsa20 to derive both $r$ and $s$ pseudorandomly under a secret key from a unique message number for each message.

  • ChaCha is designed to be a pseudorandom function family: if you pick a secret key $k$ uniformly at random, then an adversary confronted with a black box that either (a) computes $\operatorname{ChaCha}_k(x)$ or (b) picks a 512-bit string independently and uniformly at random and returns it (and caches it), given any number of adversary-chosen inputs $x$, can't tell which kind of black box it is. Here, unlike Poly1305, the adversary gets to see the outputs.

    Pseudorandomness is generally much more expensive than bounded difference probability, and requires years of hard cryptanalysis to get confidence in it.

  • BLAKE and Rumba20 are designed to be collision-resistant: the adversary wins if they can simply find two strings $x$ and $y$ such that $\operatorname{Rumba20}(x) = \operatorname{Rumba20}(y)$, and there's no secret key at all.

    Collision resistance is generally much more expensive than pseudorandomness and much much more expensive than bounded difference probability, and also requires years of hard cryptanalysis to get confidence in it.

This question is especially interesting considering...

"The security of Poly1305[...] is very close to the underlying [...] block cipher algorithm." -Wikipedia

‘Security’ here means security as a message authentication code. You and your partner share a secret key $(r, k)$; the authenticator for the $n^{\mathit{th}}$ message $m$ is $a := \operatorname{Poly1305}_r(m) + \operatorname{AES}_k(n)$, and your partner will reject the putative $n^{\mathit{th}}$ message $(m', a')$ unless $a' = \operatorname{Poly1305}_r(m') + \operatorname{AES}_k(n)$. Of course, if $m' = m$ and $a' = a$, your partner will always accept it, but if an adversary who doesn't know $r$ or $k$ tries to find any distinct message $m' \ne m$ with any authenticator $a'$, your partner will reject it with high probability (unless the adversary can break AES).

Again, it is crucial that you and your partner share a secret key. No secret key, no security.

So... why not reconfigure chacha as a Merkle–Damgård like construction. (Or a HAIFA construct, as is done with BLAKE.) Then do a standard H(key || H(key || message)) for effective HMAC? Then, from here, you have CHF, MAC, and AEAD, all from one cipher.

You can build lots of things out of a single primitive—though maybe not ChaCha because it was designed only for PRF security, not for collision resistance. See, for example, Mike Hamburg's STROBE, which is built mostly out of the Keccak permutation (plus Curve25519 for public-key cryptography), or Frank Denis's libhydrogen, which is built mostly out of the Gimli permutation (plus Curve25519 for public-key cryptography).

But it won't beat any speed records.

$\endgroup$
  • $\begingroup$ A couple more notes to point out. Performance notions are based on 3 assumptions. 1: parallelization 2: unbiased execution time for math primitives 3: time-memory trade off favors using more memory. Though I concede these are fair assumptions, I would like to make a point that it's not always the case. 1: Many architectures are (sub)scalar, and cannot improve speed through parallelization. 2: Many architectures take substantially longer to execute some math primitives vs. others. 3: Keeping a single cryptographic primitive in cache can be faster than having several that don't all fit. $\endgroup$ – Charlie Nov 16 at 7:39
  • $\begingroup$ @Charlie Not just based on assumptions—also based on published measurements (paywall-free) from μNaCl which reported appreciably higher throughput for Poly1305 than for Salsa20 on an 8-bit AVR microcontroller (and that's for Salsa20 to do key expansion; the Salsa20 throughput would be substantially lower, probably (1/4)x, for message compression). But you are right about space, which is what makes Gimli attractive. $\endgroup$ – Squeamish Ossifrage Nov 16 at 14:43
  • $\begingroup$ ATmega2560 has a single cycle hardware multiplier. $\endgroup$ – Charlie Nov 16 at 17:00
  • 1
    $\begingroup$ Also, there QR() is 16 cycles slower than mine. :sips tea: $\endgroup$ – Charlie Nov 16 at 17:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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