1
$\begingroup$

Would it be possible to use ChaCha20 as a block cipher? With the key, the entire block function can be reversed.

$\endgroup$
5
  • 1
    $\begingroup$ Please clarify what is meant by "With the key, the entire block function can be reversed". Is that the unobjectionable statement of the goal that a block cipher must meet? Or an assertion that it applies to some part of ChaCha20, and then which? I doubt that exists in ChaCha20. $\endgroup$
    – fgrieu
    Feb 21 at 5:49
  • $\begingroup$ @fgrieu ChaCha20's block function contains an ARX permutation (which can be reversed), and adding the key to the output. If you have the key, you can subtract the key from the output and reverse the ARX permutation $\endgroup$
    – SomeHybrid
    Feb 21 at 7:58
  • $\begingroup$ Use ChaCha or any PRF as $f$ function of Fiestel construction, done! Of course, any solution is not good. ChaCha is designed as PRF ( no reverse) with built-in CTR mode where there is no need for a decryption routine. $\endgroup$
    – kelalaka
    Feb 21 at 15:13
  • $\begingroup$ @kelalaka: Yes, using ChaCha as PRF for a Feistel cipher works, and is unobjectionably secure with the appropriate number $r$ of rounds. I wish I knew how many! 4 (asymptotic result), 6 (my rule of thumb), or is it 7 or 10 per Patarin's work? That matters, because we end up about $r$ times less efficient than ChaCha for bulk encryption. $\endgroup$
    – fgrieu
    Feb 22 at 10:49
  • $\begingroup$ @fgrieu I cannot rule out the necessary number of rounds, maybe 2? However, it is not a good idea to use ChaCha in Feistel while we have PRF built-in CTR. $\endgroup$
    – kelalaka
    Feb 22 at 14:21

1 Answer 1

3
$\begingroup$

It's not possible to use any existing part of ChaCha# as a block cipher. In particular, I read this statement as incorrect:

With the key, the entire (ChaCha) block function can be reversed.

Chacha's block is 512-bit wide, organized as 16 × 32-bit words. It's block transformation function applies a fixed public ARX-based pseudo-random permutation of a block, then combines the input and output of that permutation by 16 additions of 32-bit words (with the carry out ignored). That makes this block function a public pseudo-random function from and to the 512-bit blockspace.

Chacha's key is added to the output of the permutation, and also part of the input of the permutation. Same for the rest of the input. It's computationally infeasible to reverse the block function knowing the key, for unknown arbitrary rest of the input. It's even almost certain that for most keys, there are several rests of the input leading to the same output.


We could try to make a 512-bit block cipher with a 512-bit (or 1024-bit) key from the public ARX-based pseudo-random permutation of a block inside ChaCha's block function, using the Even-Mansour construction: XOR with the key, apply the public pseudo-random permutation, XOR with the key (or the other half of the key).

If we used Salsa20's permutation rather than ChaCha's, that would not be secure: Salsa20's permutation has the property that if we toggle the high-order bit of each 32-bit word of it's input, that does the same for the output, and that allows a trivial distinguisher for the block cipher.

ChaCha's permutation does not have this property. It has others (like the all-zero input being stationary, and remarkable things happening when all inputs are identical), but I do not immediately see that they degenerate into an attack in the Even-Mansour construction assuming uniformly random key. Still I'm not comfortable with using this permutation out of it's design context.


# Recall that ChaCha is to Salsa20 what ChaChaR is to Salsa20/R. This answer applies regardless of the number R of rounds.

$\endgroup$
1
  • 2
    $\begingroup$ This paper investigated precisely the security of Even-Mansour with permutations with certain flaws, including those of ChaCha. $\endgroup$ Feb 21 at 11:47

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.