基于分支定界技术的分组密码新型积分区分器搜索
Exploring New Integral Distinguishers on Block Ciphers with Branch-and-Bound
曾凡洋 1田甜1
作者信息
摘要
积分攻击是一种针对分组密码的重要攻击技术.传统上,积分区分器是在一组给定明文下的平衡比特,即零和积分区分器.然而,一些带密钥的区分器往往被忽略,实际上对积分攻击也有一定帮助.本文提出一种新型分组密码积分区分器,称为基于密钥的积分区分器,以及关于该区分器的搜索技术.本文的主要想法是首先恢复某个输出比特关于轮子密钥的超多项式作为积分区分器,然后猜测最后几轮的部分轮子密钥,通过密钥调度算法来简化超多项式.如果超多项式关于密钥变量是平衡的,则可以恢复1比特轮子密钥信息,一般情况下,可以转换为1比特的主密钥信息.为了有效搜索基于密钥的积分区分器,本文提出一种结合可分性和分支定界的方法,并将其应用到SIMON和Simeck算法中.针对15轮SIMON32、18轮SIMON64和15轮Simeck32,分别恢复了 12、8和9个密钥超多项式,并且利用其中一个超多项式,给出了一个25轮SIMON32的密钥恢复攻击.此外,利用新的搜索技术,给出了 18轮SIMON64的两个新的平衡比特.据我们所知,这是第一次使用与密钥相关的积分区分器对分组密码实施密钥恢复攻击.
Abstract
The integral attack is an important cryptanalysis technique on block ciphers.Tradi-tionally,an integral distinguisher is a balanced output bit corresponding to a set of chosen plaintexts which is called a zero-sum distinguisher.However,some other useful distinguishers with round keys for integral attacks are ignored.This paper proposes a new type of integral distinguishers on block ciphers called key-based integral distinguishers.The main idea is to recover the superpoly of a certain output bit on independent round keys,which is used as a key-based integral distinguisher,and then guess some bits of round keys of last several rounds to simplify the superpoly with the help of the key-schedule.If the superpoly on round key variables is balanced,one bit of information can be recov-ered for the involved round keys,which in general can be transformed into one bit information of the encryption key.As illustrations,combining bit-based division property and branch-and-bound,a new method is presented to search key-based integral distinguishers,which is shown to be very effective for some block ciphers.The method is applied to SIMON and Simeck.As a result,12,8 and 9 superpolies on round keys can be recovered on 15-round SIMON32,18-round SIMON64 and 15-round Simeck32,respectively.Based on one of these superpolies,a key recovery attack is given on 25-round SIMON64.Furthermore,two new balanced bits on 18-round SIMON64 are found.
关键词
积分攻击/可分性质/分支定界/MILPKey words
integral attack/division property/branch-and-bound/MILP引用本文复制引用
出版年
2024
国家科技期刊平台
NSTL
万方数据