7
$\begingroup$

So I am looking for the most secure method of symmetric key cryptography for long term messaging use between two users. I have heard that most symmetric key algorithms are not absolutely compromised by quantum computers, but rather weakened.

I have read that AES 256 is in fact the weakest, followed by AES 128, and AES 192 being the strongest.

Let us imagine that today quantum computers exist with "good" capacity to break cryptography.

Is AES still the best symmetric key solution as of right now? If not which is? If so then which AES key space is the strongest?

These are many questions which remain unanswered or lack good discussion as there isn't much in regards to post quantum security concerns.

Improve this question
$\endgroup$
6
  • 3
    $\begingroup$ Do you have a link to where you read that AES-256 is the weakest? $\endgroup$
    – Ella Rose
    Commented Jan 7, 2017 at 23:13
  • $\begingroup$ @EllaRose I think that is a reference to the related key attacks where AES-256 does worst. $\endgroup$
    – SEJPM
    Commented Jan 7, 2017 at 23:27
  • 2
    $\begingroup$ @SEJPM you are indeed correct. Ella here is a resource on that: crypto.stackexchange.com/questions/1549/… $\endgroup$
    – Nick
    Commented Jan 7, 2017 at 23:36
  • 3
    $\begingroup$ I'm not sure that "AES-256 is in fact the weakest" is an appropriate conclusion to draw from that, especially if the context/threat landscape in question is quantum computing. The requirements for that attack are arguably less realistic then the requirements for performing a quantum attack - what point is there to protecting the key if an attacker can encrypt/decrypt arbitrary blocks? They can decrypt your ciphertexts and make new ciphertexts, which is what the key was supposed to prevent them from doing. Since your threat model is QC, the largest key size is not the least secure. $\endgroup$
    – Ella Rose
    Commented Jan 8, 2017 at 0:35
  • 5
    $\begingroup$ AES256 is the strongest AES unless you horribly abuse AES. If you do that, you should fix the way you use AES instead of concluding AES256 is weaker that AES192 or AES128. $\endgroup$
    – CodesInChaos
    Commented Jan 8, 2017 at 10:10

3 Answers 3

Reset to default
14
$\begingroup$

AES-256 is still considered the strongest (and is considered secure) as related key attacks are not particular to analysis with quantum computers.

Related key attacks could happen when AES is used within a construction such as a hash function, where the output of one round is used as a key for the next round.

As far as we know now, quantum computing won't have as much as an impact on most symmetric algorithms as it does on asymmetric cryptography (that usually relies on specific mathematical problems that can be solved using quantum computers).

As mentioned, the best generic attack on symmetric ciphers, Grover's attack, about halves the key strength. But you need a lot of qbits to create the attack. Of course, there may be new attacks found that are particular to a specific block cipher, but as far as we can see now, most constructs seems pretty secure against quantum computers. That means that a 256 bit key will still deliver 128 bits of security against analysis using quantum crypt-analysis.

That means that there seems little reason to double the 256 bit key strength, as 128 bits of security are considered plenty against any attack that require such kind of order of operations.

If you require 256 bits security with quantum computers (why?) you could consider Threefish-512 - an algorithm actually designed to deliver that kind of security.

Improve this answer
$\endgroup$
8
  • 5
    $\begingroup$ Grover's algorithm is asymptotically optimal[1], the best possible quantum attack is O(sqrt(n)), IE the effective number of bits of the key gets halved. [1] Bennett C.H.; Bernstein E.; Brassard G.; Vazirani U. (1997). "The strengths and weaknesses of quantum computation". SIAM Journal on Computing. 26(5): 1510–1523. $\endgroup$
    – SAI Peregrinus
    Commented Jan 8, 2017 at 2:08
  • $\begingroup$ According to an article on this website it states that quantum computers would have an impact on symmetrical operations and in fact AES, weakening it. $\endgroup$
    – Nick
    Commented Jan 8, 2017 at 2:53
  • 2
    $\begingroup$ @Nick "weakening it" does not mean breaking it; The weakness is easily compensated for by doubling the key size. $\endgroup$
    – Ella Rose
    Commented Jan 8, 2017 at 3:10
  • 4
    $\begingroup$ @Nick I am looking to build a pragmatic discussion on what actually happens when… This is a Q&A site, not a discussion platform. Fact is, quantum computers with cryptographic or cryptanalytic abilties simply don’t exist at this moment in time. Due to the lack of practical testing options (which may prove QC to be either effective, or not as effective as expected when it comes to crypto), such discussions are purely theoretical and – in the end – primarily opinion-based. Answers like Maarten’s can only reflect the current status-quo. $\endgroup$
    – e-sushi
    Commented Jan 8, 2017 at 9:20
  • 5
    $\begingroup$ Doubling key sizes is more than enough because Grover parallelizes badly (references). To find the first of $t$ target AES-192 keys on a quantum computer parallelized $p$ ways, it would take the time for $2^{96}\!/\sqrt{p \sqrt t}$ sequential steps. Even you had a quintillion (${\approx}2^{50}$) quantum computers to mount a batch attack in parallel on tens of millions of targets (${\approx}2^{25}$), and even if each AES evaluation took a nanosecond, it would take nearly a millennium to return the first answer. $\endgroup$
    – Squeamish Ossifrage
    Commented Oct 5, 2019 at 20:50
-3
$\begingroup$

Given that the link to the Kudelski analysis does not work anymore, please find an updated link here.

Hopefully, that addresses your concerns about the answer's legitimacy. To be more precise, regarding the OP's question, using currently standardized key sizes, AES is most secure with 256-bit keys and the suggested modifications to its key schedule. The suggestion is to use HKDF or CSHAKE as a way to make related key attacks impossible, therefore allowing key sizes >= 256 safely, while keeping backward compatibility with the Rijndael core loop. Squeamish Ossifrage (what a beautiful name by the way!) were themselves slightly mistaken in their reading of the paper. The reference implementation is GPL, by the way.

Improve this answer
$\endgroup$
3
  • 3
    $\begingroup$ Related-key attacks are not relevant to any serious real-world protocols. AES-192 is sufficient—and AES-256 more than enough—to thwart all known quantum attacks on AES; you're more likely to be hurt by timing side channels in software AES implementations even if someone develops a quantum computer large enough to run Grover's algorithm. The quantum encryption oracle attack model alluded to on p. 10 and reference [8] of the alleged Kudelski analysis is so far divorced from reality it's laughable. See, e.g., this answer for references. $\endgroup$
    – Squeamish Ossifrage
    Commented Oct 7, 2019 at 17:17
  • 1
    $\begingroup$ (By the way, I go by ‘them’, not by ‘him’ or ‘her’.) $\endgroup$
    – Squeamish Ossifrage
    Commented Oct 7, 2019 at 17:18
  • $\begingroup$ This doesn't seem to be a separate answer to the one you already provided. However, I don't see how we can merge the two. Could you please merge the answers. If you want you can use this one as the target so you're only at -2 instead of -6 afterwards. Don't forget to delete the other answer afterwards. $\endgroup$
    – Maarten Bodewes ♦
    Commented Oct 9, 2019 at 2:30
-6
$\begingroup$

Regarding using AES in the most secure way possible against quantum computers AND related key attacks (while keeping hardware compatibility with existing CPU cryptographic optimizations), I would suggest you to read https://eprint.iacr.org/2019/553 (Towards post-quantum symmetric cryptography).

At the time of the question we hadn't yet written a formal paper about it, and it is by searching the Internet for our paper that I found this question.

Improve this answer
$\endgroup$
2
  • 2
    $\begingroup$ This doesn't address the question; it only advertises a bespoke AES variant that replaces the key schedule by HMAC-SHA256 or SHAKE128, justified by a misunderstanding of the related-key attack model, of the limitations of Grover's algorithm, and of the nonsensical quantum oracle attack model for Simon's algorithm on symmetric cryptosystems, according to the preprint and to the alleged Kudelski analysis it cites. $\endgroup$
    – Squeamish Ossifrage
    Commented Oct 5, 2019 at 17:40
  • 2
    $\begingroup$ I've removed the fluff from the answer, but now it has become a link only answer. You should include some excerpt in your answer, or possibly remove it as the votes seem to move in one direction only at this time. $\endgroup$
    – Maarten Bodewes ♦
    Commented Oct 5, 2019 at 20:41

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.