5
$\begingroup$

I've been recently implementing the chacha20 stream cipher with Poly1305. As the core operations which make up the Quarter Round of chacha20 (ARX - Addition Rotation Xor) are indeed reversible, does that make reversing the ChaCha20 possible if an attacker knows the 512 bit key stream generated by the function, by a known plaintext attack on ciphertext that was generated by XORing the former keystream with the known plaintext?

I understand that the design of Chacha20 that uses the processor friendly ARX at its core, makes it very efficient, fast and secure, and hence widely adopted, and I'm also confident about the confusion and diffusion that it offers.

But, Will it be reversible in the face of a Quantum Computer, if not by a classical computer?

Sorry if my concerns are naive!

$\endgroup$
  • 1
    $\begingroup$ The initial state (constants, key, nonce, counter) is arithmetically added after the last round before keystream block is outputted. $\endgroup$ – DannyNiu Feb 15 at 9:41
  • 1
    $\begingroup$ ARX designs are not linear, I think you'll find more information if you look into (pseudo-) linear properties of these ciphers that disallow linear cryptanalysis. $\endgroup$ – Maarten Bodewes Feb 15 at 16:24
3
$\begingroup$

The function which generates keystream blocks is based on a 512-bit permutation function. A permutation is, by definition, bijective.

The inverse of this permutation particular is trivial to implement in software. Just perform the individual operations (add, rotate, XOR) in reverse order, replacing modular addition with modular subtraction and reversing the direction of rotations.

Trying to reverse the entire keystream-block-generating function will fail, though, if the key is not already known. Actual keystream blocks are formed by combining the input bits of the permutation with the output bits.1 Part of those input bits are key bits (which should be uniformly distributed and secret).

Since the permutation function scambles inputs so well, you can basically treat each input and its corresponding permutation-output as being statistically independent.

(Warning: Diliberate over-simplification. This is for illustrative purposes only. I don't want to say that "scrambling well" is sufficient. Or even that ChaCha's internal permutation is good enough to abuse in non-standard ways.)

If you change one input bit other than the key, then the output of the permutation will look completely different. When the secret key gets added back in, it obscures the value of the actual permutation output.

You would have to guess the 128-bit or 256-bit key before you could work backward even if you knew the full value of the keystream block in addition to the non-secret parts of the input vector. (The IV, counter, and constants. Adding these non-secret inputs to the permutation output does nothing to affect security, but it's included in the algorithm specification anyway for software efficiency reasons.)


One could almost make a stronger claim, that the keystream-block-generating function is one-way in the same way that hash functions are one way. Hash function design was actually a source of inspiration for ChaCha20's predecessor.

By one-way I mean there is no efficient algorithm to compute an input which produces an arbitrarily chosen output value. That's probably not possible (or at least is non-trivial) for any non-zero output block value.

The construction $F(x) = x \oplus P(x)$ should make $F$ a one-way function if $x$ has sufficiently many bits and $P$ were a random permutation. (Chosen uniformly from the set of all $(2^n)!$ possible n-bit permutations.)

Such a permutation would be unlikely to have any systemic relationship between input and output values. That thwarts the search for preimages for an ideal $P$. The same would be true if $\oplus$ were replaced with $\boxplus$.

We don't currently know an algorithm to find preimages for ChaCha20's hash-like operation, when we don't have foreknowledge of that preimage, with the exception of the value zero.2

That exception could be really important for some applications. So don't take the risk in adapting ChaCha to roll your own algorithm!


1. Specifically, ChaCha20 uses mod $2^{32}$ addition on the 16-word input/output vectors. It would also have worked if the design called for XORing inputs and outputs bit-for-bit, since both addition and XOR are non-linear with respect to the permutation function and neither operation should produce biased results.

2. ChaCha20 uses a pure ARX permutation. $F(0) = 0$ because $P(0) = 0$ because $0 \oplus 0 = 0, 0 \boxplus 0 = 0, \text{and}\ 0 \>>>> r = 0$.

| improve this answer | |
$\endgroup$
1
$\begingroup$

There are no known attacks as of now.

With a known plaintext you can get the keystream by XORing plaintext with ciphertext.

But as keystream = matrix-before-any-rounds (input state)+ matrix-after-20-rounds (the mixed ARXed state.)

You cannot separate them easily to get the key.

| improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ This answer is not wrong, but I think any answer needs a bit more than a single statement "But as keystream = matrix-before-any-rounds + matrix-after-20-rounds" to show why cryptanalysis would fail. Could you add detail? $\endgroup$ – Maarten Bodewes Feb 15 at 16:25
  • $\begingroup$ @Maarten Bodewes♦: Thankyou, I got it, and I edited the answer by CrytoNerd. The matrix before any rounds referred to the initial state of input to the function, and the matrix after 20 rounds referred to the mixed ARXed initial state after all 80 Quarter rounds. $\endgroup$ – Vivekanand V Feb 15 at 17:28

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.