TWINE-128的中间相遇攻击的自动检测算法  

Automatic Search Algorithm of Meet in the Middle Attack on TWINE-128

作　　者：孔海龙[1] 王薇[1,2] 张国艳[1,2] 

机构地区：[1]山东大学计算机科学与技术学院,济南250101 [2]山东大学密码技术与信息安全教育部重点实验室,济南250100

出　　处：《密码学报》2015年第6期559-569,共11页Journal of Cryptologic Research

基　　金：山东省优秀中青年科学家科研奖励基金(BS2012DX018);国家自然科学基金青年基金项目(61103237)

摘　　要：Biryukov等人在FSE 2015首次将多重集的中间相遇攻击应用于Feistel结构,并给出TWINE-128算法目前最好的分析结果.基于Biryukov等人的工作,本文详细介绍了TWINE算法的中间相遇攻击的自动检测算法.该算法分为三个步骤.(1)区分器的自动检测算法,结合算法结构,搜索出全部区分器.然后,对搜索出的区分器逐个用步骤(2)、(3)进行筛选.(2)在线阶段涉及轮密钥的自动定位算法,在区分器的头部和尾部添加轮数,分别推导出区分器的头部δ集解密到明文,区分器的尾部加密到密文,需要猜测的轮密钥.(3)待求轮密钥向等价主密钥的自动转换算法,选取主密钥或者密钥调度算法生成的某一个128比特的中间变量作为等价主密钥WK[r](r为轮数),猜测WK[r]的部分半字节,并推导相应的轮密钥取值,若步骤(2)中需要的所有轮密钥都可推导出来,攻击成立.程序结果可手动验证,在δ集特性不变的情况下,我们发现,除Biryukov等人采用的区分器外,还存在其他区分器,可对25轮的TWINE-128算法进行中间相遇攻击,复杂度不变.因为运算规则的定义与加密算法的具体细节无关,本文给出的自动检测算法可适用于S盒是一一映射的广义Feistel结构的分组密码算法.Biryukov et al. proposed a new kind of meet-in-the-middle attack(MITM) based on multiset, and applied it to the Feistel network, and achieved so far the best cryptanalysis results on TWINE-128. Inspired by their work, this paper introduces an automatic testing algorithm of MITM attack, taking TWINE-128 as an example. The algorithm is divided into three parts.(1) The distinguishers are detected automatically. Combining with the encryption function of TWINE, all the distinguishers are obtained and sieved in step(2)–(3).(2) The round subkeys involved in the online phase are listed. Several rounds are added to the beginning and the ending of each distinguisher, respectively, and we mark the round subkeys participating in the decryption from δ-set to plaintexts, and the encryption from the end of the distinguisher to ciphertexts.(3) The guessed round subkeys are transferred to equivalent master keys, which means that the 128-bit internal state WK[r](r is the round number) can be achieved in the key schedule. If the round subkeys involved in step(2) can be deduced from partial nibbles of WK[r], then we only need to guess the corresponding nibbles in WK[r] instead of round subkeys, and the attack works. The results achieved from the algorithm can be verified manually. With the same δ-set, we found another distinguisher besides the one proposed by Biryukov et al., and the attack process remains the same, so does the complexity. Moreover, since the definition of the operation has no relation with the details of encryption algorithm, the automatic search algorithm can be applied to generalize Feistel networks with 1-1 S-boxes.

关 键 词：中间相遇攻击 自动搜索算法 广义Feistel结构 TWINE-128 

分 类 号：TN918.4[电子电信—通信与信息系统]