Dividing an encrypted file is secure against classical or quantum

gq flag

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?

in flag

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

hajalev896 avatar
gq flag
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)
kelalaka avatar
in flag
@hajalev896 all clear now?
preferred_anon avatar
tg flag
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?
kelalaka avatar
in flag
@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.
benrg avatar
cn flag
"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.
kelalaka avatar
in flag
@benrg Grover's algorithm is asymptotically optimal for searching on non-structured data. Grover's algorithm can brute-force any block cipher with $\mathcal{O}(\sqrt n) $-time. Are you saying that someone will come to an idea to use Grover's algorithm other than brute-forcing the key to breaking a block cipher? All Grover's algorithm does, is an effective search $n$ non-structured data.
benrg avatar
cn flag
What I mean is it sounds like you're saying that provably no quantum attack on AES can outperform Grover's algorithm.
kelalaka avatar
in flag
@benrg ok, added on key search there. Thanks.
I sit in a Tesla and translated this thread with Ai:


Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.