8
$\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$
2
  • 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, 2020 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, 2020 at 16:24

3 Answers 3

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

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

$\endgroup$
2
  • 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, 2020 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$
    – Aravind A
    Feb 15, 2020 at 17:28
0
$\begingroup$

The chacha20 is not vulnerable to known plaintext attacks.

https://datatracker.ietf.org/doc/html/rfc7539#section-2.3.2

This is the process of chacha20. 1st row is constant "expand 32bytes k" as little indian in hex. 2nd row and 3rd row you encryption key. 4th row block number and nonce. you have the initial matrix:

 ChaCha state with the key setup. Matrix X

       61707865  3320646e  79622d32  6b206574
       03020100  07060504  0b0a0908  0f0e0d0c
       13121110  17161514  1b1a1918  1f1e1d1c
       00000001  09000000  4a000000  00000000

then perform 20 rounds of chacha operations

ChaCha state after 20 rounds - Matrix X^20

   837778ab  e238d763  a67ae21e  5950bb2f
   c4f2d0c7  fc62bb2f  8fa018fc  3f5ec7b7
   335271c2  f29489f3  eabda8fc  82e46ebd
   d19c12b4  b04e16de  9e83d0cb  4e3c50a2

Then you sum X+X^20 to get the XOR_MATRIX.

ChaCha state at the end of the ChaCha20 operation - XOR_MATRIX

   e4e7f110  15593bd1  1fdd0f50  c47120a3
   c7f4d1c7  0368c033  9aaa2204  4e6cd4c3
   466482d2  09aa9f07  05d7c214  a2028bd9
   d19c12b5  b94e16de  e883d0cb  4e3c50a2

the encryption operation is XOR between XOR_MATRIX and your PLAINTEXT.

Even if you have the XOR_MATRIX, you can't get the KEY and NONCE,because of the sum operation (X+X^20 = XOR_MATRIX). 1 known variable(XOR_MATRIX and 2 unknown(X and X^20)

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