Quantum algorithms can accelerate cryptanalysis and reduce the security strength of symmetric ciphers. Increasing the key length is a common approach to enhance the security of symmetric ciphers. Triple DES (3DES), a block cipher derived from DES, achieves this by applying triple encryption with extended key lengths. A quantum meet-in-the-middle (MITM) attack is specifically proposed for two-key 3DES. This attack utilizes Grover’s quantum algorithm to accelerate the key-recovery process and, through a classical preprocessing process, reduces the complexity of the online quantum computation to \(\text{O}({2}^{28})\) , which is significantly lower than the optimal classical attack complexity \(\text{O}({2}^{56})\) . Since the quantum security strength of DES is \(\text{O}({2}^{28})\) , this attack demonstrates that two-key 3DES cannot provide more security than DES in quantum setting. The attack is only feasible in the Q2 model and requires \(\text{O}({2}^{56})\) quantum random access memory (QRAM). Based on this attack, a time-QRAM tradeoff variant is also proposed, which balances the time complexity and QRAM. This results in an attack complexity and QRAM size both at \(\text{O}({2}^{42})\) , which is still better than optimal classical attack.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Quantum Meet-in-the-Middle Attacks on Two-Key 3DES

  • Ruihao Gao,
  • Jiali Wu,
  • Min Liang

摘要

Quantum algorithms can accelerate cryptanalysis and reduce the security strength of symmetric ciphers. Increasing the key length is a common approach to enhance the security of symmetric ciphers. Triple DES (3DES), a block cipher derived from DES, achieves this by applying triple encryption with extended key lengths. A quantum meet-in-the-middle (MITM) attack is specifically proposed for two-key 3DES. This attack utilizes Grover’s quantum algorithm to accelerate the key-recovery process and, through a classical preprocessing process, reduces the complexity of the online quantum computation to \(\text{O}({2}^{28})\) , which is significantly lower than the optimal classical attack complexity \(\text{O}({2}^{56})\) . Since the quantum security strength of DES is \(\text{O}({2}^{28})\) , this attack demonstrates that two-key 3DES cannot provide more security than DES in quantum setting. The attack is only feasible in the Q2 model and requires \(\text{O}({2}^{56})\) quantum random access memory (QRAM). Based on this attack, a time-QRAM tradeoff variant is also proposed, which balances the time complexity and QRAM. This results in an attack complexity and QRAM size both at \(\text{O}({2}^{42})\) , which is still better than optimal classical attack.