3
$\begingroup$

I like the idea behind Gimli and libhydrogen but in my benchmarks Gimli permutation function is considerably slower than ChaCha20 one. By considerably I mean four times slower using SIMD builtins. This is a big difference. Moreover, ChaCha20 is more mature and a more conservative choice.

Can ChaCha20 be repurposed as a general purpose permutation function as Gimli? What are the security risks to consider?

EDIT

My objective is to patch libhydrogen to use ChaCha20 instead of Gimli. I do not have the knowledge on this field nor the intention to do anything else.

$\endgroup$
  • $\begingroup$ Are you familiar with the Blake hash function? $\endgroup$ – Ella Rose Jul 3 '18 at 16:45
  • $\begingroup$ @EllaRose Yes. It's quite similar to ChaCha20, but not exactly the same (it adds message contents on each quarter round too). My knowledge on the subject is not enough to discern how much it affects its security. My idea is to patch libhydrogen to work with ChaCha20 instead of Gimli. I don't trust me to do anything fancier. $\endgroup$ – user3368561 Jul 3 '18 at 16:54
  • 3
    $\begingroup$ ChaCha core is no general purpose cryptographic permutation, and Blake2's core is no general purpose block-cipher. $\endgroup$ – CodesInChaos Jul 3 '18 at 22:17
4
$\begingroup$

There is a library called Monocypher* that heavily utilizes derivatives of ChaCha and Salsa. (Plus Poly1305, X25519, and Ed25519.) The algorithms it uses, XChaCha20, Blake2b, and Argon2 all use different permutations but those permutations are all extremely similar.

I don't know if any Salsa variant's permutation can be used as is. It certainly would be risky to decrease the round count by much. I'm not aware of published analysis of any variant used as a stand-alone permutation.

If ChaCha's permutation function (with 20 rounds) is a secure public permutation, then we know the algorithm ChaCha20 is secure. But if we know ChaCha20 is secure, that doesn't mean we know the permutation is secure. One reason why ChaCha20 is so robust (and therefore why it can get away with few enough operations to make it fast) is because of the algorithm as a whole, not just the permutation. The only thing you can qualify as attacker controlled inputs in ChaCha20 is the IV. Message bits (plain- or ciphertext) have zero influence in ChaCha20's permutation function. This is a smaller attack surface than what's possible with block ciphers, hash functions, and public permutations. All of which have security properties that ChaCha20 doesn't need to have. The permutation it uses wasn't designed to be one-size-fits all, so we don't have much evidence yet to say it's safe for general-purpose permutation use.

One property of the ChaCha permutation is that it does not use round constants. It's also an ARX (add rotate xor) construct. It has a trivial fixed point $P(0) = 0$. Which results from

  • Addition: $0 + 0 = 0$
  • XOR: $0 \oplus 0 = 0$
  • Rotation: $0 \text{ rotate-by } k = 0, \forall \space k$

The presence of a fixed point in a randomly chosen permutation function is to be expected. Finding one a permutation on a large block size is a harder problem if it requires brute force. This known fixed point might be a problem for some (but not all) applications. For Salsa, Chacha, Blake 1 and 2, their respective permutations are used with a portion of their input bits fixed to a non-zero constant so it isn't a problem there.

In the Gimli paper I found (ctrl-f) a reference to round constants, so I'm pretty sure it doesn't have a zero fixed point.

The number of rounds you use of a ChaCha-like permutation function obviously has an effect on security. It seems like even the algorithms that use less than 20 rounds probably are still safe. But that likely has a lot to do with how the permutations are used in addition to the robustness of the permutation itself. I can't tell you if 20 rounds are safe enough for all or most general purpose permutation uses, if you can safely decrease them, if you need to increase them, or if increase the number of rounds will help.

The safe answer to your question is no.

And although it doesn't seem like it, this is a sort of "Should I implement my own crypto?" question. I've considered the same idea. Breaking two secure constructs into pieces and recombining pieces Frankenstein's monster style doesn't make the end result secure.

* I'm aware of the project but haven't looked into it. It's probably safest to use NACL, but I can't and shouldn't endorse any option.

$\endgroup$
  • 1
    $\begingroup$ The ChaCha permutation is not a pseudorandom permutation. Security properties aside, it doesn't have the right syntax for that. It's a single fixed permutation, not a keyed family of permutations. $\endgroup$ – Squeamish Ossifrage Jul 4 '18 at 1:20
  • $\begingroup$ @SqueamishOssifrage I didn't mean a family of permutations. Were you referring to a greater content error or just a vocabulary error? $\endgroup$ – Future Security Jul 4 '18 at 3:24
  • $\begingroup$ Vocabulary—‘pseudorandom permutation’ or PRP is a specific technical term with a widely agreed-upon definition in cryptography, and neither ChaCha nor Keccak is (even conjectured to be) one. AES is (conjectured to be) an example of one. $\endgroup$ – Squeamish Ossifrage Jul 4 '18 at 4:40
  • 1
    $\begingroup$ @FutureSecurity Note that it's really easy to find a fixed point $x$ for ChaCha when you define it as $ChaCha(x) = P(x) + x$ so $ChaCha(x) = x$ leads to $x = P^{-1}(0)$. Note that $x$ would probably not be usually possible since it likely contains invalid constants. $\endgroup$ – VincBreaker Jul 4 '18 at 18:56

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.