8
$\begingroup$

Having looked at the paper "Breaking Symmetric Cryptosystems using Quantum Period Finding", I'm unsure as to whether the AES-Keywrap as defined by NIST SP 800-38F is safe against the described attack or not.

I also came up empty handed on google.

Does anyone have any information on this?

$\endgroup$
  • $\begingroup$ Additional info: The paper linked to contains attacks against MAC constructions and authenticated ciphers. The key wrapping mechanisms defined in the NIST draft also allow for authenticity / integrity protection. $\endgroup$ – Maarten Bodewes Mar 21 '18 at 16:27
  • $\begingroup$ AES' small block size certainly doesn't help with regarding quantum or largely parallel traditional adversaries. If you're after post-quantum, you'll want to look at larger block sizes too. $\endgroup$ – cypherfox Mar 22 '18 at 13:56
  • $\begingroup$ @cypherfox I thought only the key sizes mattered. How do block sizes factor into the equation? $\endgroup$ – forest Mar 25 '18 at 22:00
  • $\begingroup$ @forest I cannot recall my sources. Hmm. $\endgroup$ – cypherfox Mar 26 '18 at 5:15
3
+50
$\begingroup$

The Kuwakado-Morii attack (the attack of Kaplan et al. is a nice adaptation of this) relies crucially on Simon's algorithm, which essentially says that on the group $(\mathbb{Z}/2)^n$, the hidden shift problem is easy. That is, from quantum access to $H(\cdot)$ and $H(\cdot\oplus s)$, it is possible to recover $s$ efficiently.

On the other hand, the Key-wrap algorithm of NIST SP 800-38F does not use group structure. Well, at least not much: while some constants are XORed during the execution of the algorithm, no adversarially-controllable data are ever XORed during the computation: the whole process is mostly built using shuffling and blockcipher evaluation.

Of course, we cannot really know whether it would be secure until we prove the security, but some constructions not relying on group structures (not even XOR) are known to be quantum-secure: for example, Zhandry proved that the GGM construction is a secure PRF, and, it happens that GGM uses only function composition, not group structure.

At the least, I think this suggests that Kuwakado-Morii is not really applicable here.

|improve this answer|||||
$\endgroup$
1
$\begingroup$

These attacks are theoretical amusements that are completely irrelevant in the real world, even if quantum computers were as cheap as classical computers.

The attack model posits that the adversary can evaluate quantum superpositions of the secret function. They just can't get the key.

The way to thwart these attacks is simply to not evaluate your secret functions on quantum superpositions of inputs—e.g., don't engineer your system to evaluate $\operatorname{AES}_k$ for secret $k$ on a quantum computer. Instead, evaluate it on a classical computer. Since there are no sufficiently capable quantum computers today, is actually rather difficult not to thwart these attacks.

|improve this answer|||||
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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