2
$\begingroup$

Encrypting with AES-256 is widely claimed to be post-quantum secure.

But let's take a case where you use an initial key that has less than 256 bits of real entropy. In this example, let's work with a 128-bit key that has 128 bits of real entropy. We stretch it with something commonly used, like PBKDF2 with 120,000 iterations. We use the 256-bit result as the encryption key for AES-256 to encrypt some secret.

Is the the secret still secure against brute force attacks by a quantum computer, the kind can halve (or worse) the effective security of a symmetric cipher using Grover's algorithm? (Edited to add:) We assume the attacker knows the specifics of the above scheme, but not they length of the entropy or the initial key.

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ Grovers algorithm square-roots the amount of keys needed to be tested, not halfed (2^128 is the square-root of 2^256 for AES256 for example; 2^255 is half of 2^256) $\endgroup$
    – SamG101
    Dec 10, 2019 at 13:32
  • $\begingroup$ @SamG101 I'm aware of that, and that's why I wrote "effective security", not key space. Am I using these terms incorrectly? $\endgroup$
    – Sutarbi Dudek
    Dec 11, 2019 at 1:54

1 Answer 1

Reset to default
4
$\begingroup$

Currently, the quantum attacks work on the block cipher itself. The Grover's search algorithm reduces the complexity of 256-bit key into 128-bit since it has complexity $\mathcal{O}(\sqrt{n})$ and in the case of 256-bit $\mathcal{O}(\sqrt{2^{256}}) = \mathcal{O}(2^{128})$

Since you have started with 128-bit entropy, theoretically, the quantum attacker to block cipher itself with a 256-bit key will not benefit from Grover's algorithm since Grover's algorithm will search 256-bit. Keep in mind that 256-bit space is infeasible for the quantum.

What if in an unforeseeable future, someone builds a quantum circuit for the PBKDF2 + AES combination that is the search for the 128-bit input to PBKDF2 and uses the output for the AES-256 key and perform Grover's kind of attack?

This can be done by extending the AES-256 Grover Search with a 128-Q-bit PBKDF2 Quantum circuit. Since the input is 128-bit, the search will be $\mathcal{O}(2^{64})$ to find the ciphertext.

The attacker, always, will use the weakest point!.

Improve this answer
$\endgroup$
6
  • 4
    $\begingroup$ Given that we know how quantum computers can simulate classical ones efficiently , it should be straightforward to implement the functionality starting at the "weakest" point (ie where the least options are possible) and then search from there to the target ciphertext. $\endgroup$
    – SEJPM
    Dec 10, 2019 at 17:45
  • 1
    $\begingroup$ @SEJPM yes, The weakest point is always the key. $\endgroup$
    – kelalaka
    Dec 10, 2019 at 18:53
  • $\begingroup$ @kelalaka "Since you have started with 128-bit entropy, theoretically, the quantum attacker to block cipher itself will not benefit from Grover's algorithm." Why is that? Isn't it the case that absent quantum computing, 128 bits would be "impossible" to break, and 256 bits are needed only because of the quantum threat? "The attacker, always, will use the weakest point!." Maybe I should have clarified, the attacker doesn't know how much entropy I used for the KDF. They only know the specifics of the derivation. $\endgroup$
    – Sutarbi Dudek
    Dec 11, 2019 at 2:20
  • $\begingroup$ If you consider only attacking the block cipher, without considering the PBKF2, then classically searching 128 is almost the same for QC. If you don't consider QC then why we are talking about QC-attacks? Breaking a 128-bit key is possible if you have multiple targets, like billions, If we live in Kerckhoff principles we assume attacker knows everything but the key(passwords). Can you guarantee that every user has a passoword with at least 192-bit entropy? $\endgroup$
    – kelalaka
    Dec 12, 2019 at 7:47
  • 1
    $\begingroup$ @SutarbiDudek Multiple-target means, you have more than one target to attack, If you have a billion targets finding the first one reduces to around $2^{70}$ 192. Not It is not clear yet how a quantum will run $2^{64}$ AES evaluations. $\endgroup$
    – kelalaka
    Feb 17, 2020 at 13:47

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.