CryptoDB
Bing Sun
Publications
Year
Venue
Title
2018
ASIACRYPT
Programming the Demirci-Selçuk Meet-in-the-Middle Attack with Constraints
Abstract
Cryptanalysis with SAT/SMT, MILP and CP has increased in popularity among symmetric-key cryptanalysts and designers due to its high degree of automation. So far, this approach covers differential, linear, impossible differential, zero-correlation, and integral cryptanalysis. However, the Demirci-Selçuk meet-in-the-middle ($$\mathcal {DS}$$-$$\mathsf {MITM}$$) attack is one of the most sophisticated techniques that has not been automated with this approach. By an in-depth study of Derbez and Fouque’s work on $$\mathcal {DS}$$-$$\mathsf {MITM}$$ analysis with dedicated search algorithms, we identify the crux of the problem and present a method for automatic $$\mathcal {DS}$$-$$\mathsf {MITM}$$ attack based on general constraint programming, which allows the cryptanalysts to state the problem at a high level without having to say how it should be solved. Our method is not only able to enumerate distinguishers but can also partly automate the key-recovery process. This approach makes the $$\mathcal {DS}$$-$$\mathsf {MITM}$$ cryptanalysis more straightforward and easier to follow, since the resolution of the problem is delegated to off-the-shelf constraint solvers and therefore decoupled from its formulation. We apply the method to SKINNY, TWINE, and LBlock, and we get the currently known best $$\mathcal {DS}$$-$$\mathsf {MITM}$$ attacks on these ciphers. Moreover, to demonstrate the usefulness of our tool for the block cipher designers, we exhaustively evaluate the security of $$8! = 40320$$ versions of LBlock instantiated with different words permutations in the F functions. It turns out that the permutation used in the original LBlock is one of the 64 permutations showing the strongest resistance against the $$\mathcal {DS}$$-$$\mathsf {MITM}$$ attack. The whole process is accomplished on a PC in less than 2 h. The same process is applied to TWINE, and similar results are obtained.
2016
EUROCRYPT
Program Committees
- Asiacrypt 2023
- FSE 2018
Coauthors
- Hoda AlKhzaimi (1)
- Lei Cheng (1)
- Patrick Derbez (1)
- Jian Guo (2)
- Lei Hu (1)
- Ruilin Li (3)
- Chao Li (3)
- Heng Li (1)
- Meicheng Liu (2)
- Zhiqiang Liu (1)
- Longjiang Qu (2)
- Vincent Rijmen (3)
- Danping Shi (1)
- Siwei Sun (1)
- Yosuke Todo (1)
- Qingju Wang (1)