题目：Programming the Demirci-Selcuk Meet-in-the-Middle Attack with Constraints

报告人：孙思维，中国科学院信息工程研究所 副研究员

报告时间：2017年10月28日20:30-21:30

报告地点：知新楼B1201

摘要：In recent years, 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 linear, and integral cryptanalysis. However, the Demirci-Sel¸cuk meet-in-the-middle (DS-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 DS-MITM analysis with dedicated search algorithms, we identify the crux of the problem and present a method for automatic DS-MITM attack based on general constraint programming (CP), 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 DS-MITM cryptanalysis more straightforward and efficient, 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 DS-MITM attacks on these ciphers without using any dedicated optimization techniques. 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. Interestingly, it turns out that the permutation used in the original LBlock is one of the 0.74% permutations showing the strongest resistance against the DS-MITM attack. In addition, a set of 200 permutations which are potentially more secure with respect to the DS-MITM attack is identified. The whole process is accomplished on a PC in less than 2 hours. The same process is applied to TWINE, and similar results are obtained.

报告人简介：孙思维，中国科学院信息工程研究所副研究员，主要研究兴趣是对称密码算法的自动化分析，开发了一个自动化密码分析框架，在国家多个相关部门的密码算法设计与分析任务中得到了应用。