1
$\begingroup$

I'm very new to cryptography and this may sound so foolish. Often I read quantum computers will brute force keys. Let's assume this is true (does it depend on key length? or on an algorithm? I don't know, let's say they will).

If I have a file encrypted with ChaCha20-Poly1305, or perhaps a LUKS encrypted partition with default options (AES 256?), and I split that file in two. If you have only one of the two, can you brute force anything? Can you recover anything? Is there a header somewhere containing metadata?

$\endgroup$

1 Answer 1

4
$\begingroup$

Let's assume this is true (does it depend on key length? on algorithm? I don't know, let's say they will).

For key search with quantum computers, we have Grover's algorithm. Given key space in $2^n$, Grover's algorithm can find the key in $\mathcal{O}(\sqrt{2^n}) $-time and $\mathcal{O}(\log{2^n})$-space. If we consider key sizes 128 and 256 bits we will have the costs;

\begin{array} {|c|c|}\hline \text{Key Size} & \text{time} & \text{space} \\ \hline 2^{128} & c\sqrt{2^{128}} = c{2^{64}} & d\log{2^{128}} \\ \hline 2^{256} & c'\sqrt{2^{256}} = c'{2^{128}}& d'\log{2^{256}} \\ \hline \end{array}

where $c,c',d,d'$ are some integer constants ( we quantized the $n$ so we need constant).

It is expected that 128-bit ciphers will go, though this is the short story since it is not clear how one can run the ~$2^{64}$ sequential evaluation of Grover's algorithm. And, we can see this from NIST's post-quantum cryptography competition; there is no block cipher section in the competition!

Though, Grovers' algorithm can be parallelizable with $t$ machine, unlike classical we only get $\sqrt{t}$ speed up instead of $t$.

If you have only one of the two, can you brute force anything? Can you recover anything?

AES-256 or any classically secure 256-bit keyed cipher is secure against quantum attack. We already know that Grover's algorithm is optimal for key search by brute-force.

There is no danger on AES-256 or ChaCha20-Poly1305 (uses 256-bit key) with uniformly randomly generated keys * - that is used for the encryption, but there is a danger on the Key-Encryption Key (KEK);

  • While using LUKS, one usually chooses a password to convert into KEK with a Key Derivation Function (KDF) that is selectable from implemented KDFs. While the key derivation function can increase the brute-force timing of password search (time and space), it is your responsibility to have a good password that is not brute-forceable. You are advised to use Dicewire or Bip39-like password generation methods that have to provide equal to 256-bit password strength.

  • for Bip-39 you need 15 words to reach around $\approx 2^{260}$

split that file in two

This can be read in two ways;

  1. The file is encrypted and then split This doesn't matter in the attacker's sense too much since it will only affect the nonce part if they obtain the second part. They can try candidates based on your division algorithm that we may assume is simple and/or known.

  2. The file is split and then encrypted

    This is not different than attacking two files encrypted with different keys. Just the double time.

Is there a header somewhere containing metadata?

Yes, on the head of the container and you are adviced to back it up. See

In short

Use AES-256 or ChaCHa20 with a good password, and done, as long as LUKS is securely implemented, it seem yes.


*Well, that was a short story, too. One should be careful on the IVs since they are CTR mode (AES-GCM and ChaCha20 uses CTR mode) which can cause crib-dragging attack that removes the confidentiality, at least

$\endgroup$
8
  • $\begingroup$ You imply there is no need to divide a file in two. If I did, would it provide any guarantee against brute forcing at all? (I'm curious to know) $\endgroup$
    – hajalev896
    Oct 15, 2022 at 16:53
  • $\begingroup$ @hajalev896 all clear now? $\endgroup$
    – kelalaka
    Oct 15, 2022 at 17:02
  • $\begingroup$ You write "key sapce $2^n$" then "$O(\sqrt{n})$" and then time "$c2^{64}$". Is that meant to be read as $O(\sqrt{2^{n}}$? i.e. should the two uses of $n$ be different? $\endgroup$ Oct 16, 2022 at 12:59
  • 1
    $\begingroup$ @preferred_anon yes, that should be, corrected, thanks, my mistake. That is given $n$ non-structured elements Grover can find in $\mathcal{O}(\sqrt n)$-time. $\endgroup$
    – kelalaka
    Oct 16, 2022 at 14:05
  • $\begingroup$ "AES-256 [...] is secure against quantum attack. We already know that Grover's algorithm is optimal." - this paragraph seems to imply that Grover's algorithm has been proven optimal against AES which of course it hasn't. $\endgroup$
    – benrg
    Oct 16, 2022 at 18:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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