基于神经区分器的KATAN48算法条件差分分析方法.pdf

2023 08 10计算机应用,Journal of Computer Applications2023,43(8):2462-2470ISSN 10019081CODEN JYIIDUhttp：/基于神经区分器的KATAN48算法条件差分分析方法林东东1，2，李曼曼1，2*，陈少真1，2（1.信息工程大学 网络空间安全学院，郑州 450001；2.密码科学技术全国重点实验室（国家密码管理局），北京 100878）（通信作者电子邮箱）摘要：针对KATAN48算法的安全性分析问题，提出了一种基于神经区分器的KATAN48算法条件差分分析方法。首先，研究了多输出差分神经区分器的基本原理，并将它应用于KATAN48算法，根据KATAN48算法的数据格式调整了深度残差神经网络的输入格式和超参数；其次，建立了KATAN48算法的混合整数线性规划（MILP）模型，并用该模型搜索了前加差分路径及相应的约束条件；最后，利用多输出差分神经区分器，至多给出了80轮KATAN48算法的实际密钥恢复攻击结果。实验结果表明，在单密钥下，KATAN48算法的实际攻击的轮数提高了10轮，可恢复的密钥比特数增加了22比特，数据复杂度和时间复杂度分别由234和234降至216.39和219.68。可见，相较于前人单密钥下的实际攻击，所提方法能够有效增加攻击轮数和可恢复的密钥比特数，同时降低攻击的计算复杂度。关键词：分组密码；混合整数线性规划；KATAN算法；条件差分分析；神经区分器中图分类号：TN918.1 文献标志码：AConditional differential cryptanalysis method of KATAN48 algorithm based on neural distinguishersLIN Dongdong1，2，LI Manman1，2*，CHEN Shaozhen1，2（1.School of Cyber Security，Information Engineering University，Zhengzhou Henan 450001，China；2.State Key Laboratory of Cryptography（State Cryptography Administration），Beijing 100878，China）Abstract:Aiming at the security analysis problem of KATAN48 algorithm，a conditional differential cryptanalysis method of KATAN48 algorithm based on neural distinguishers was proposed.First，the basic principle of multiple output differences neural distinguishers was studied and applied to KATAN48 algorithm.According to the data format of KATAN48 algorithm，the input format and hyperparameters of the deep residual neural network were adjusted.Then，the Mixed-Integer Linear Programming（MILP）model of KATAN48 algorithm was established to search the prepended differential paths and the corresponding constraint conditions.At last，using the multiple output differences neural distinguishers，at most 80-round of the practical key recovery attack results of KATAN48 algorithm were given.Experimental results show that in the single key setting，the number of practical attack rounds of KATAN48 algorithm is increased by 10 rounds，the number of recoverable key bits of KATAN48 algorithm is increased by 22 bit and the data complexity and time complexity of KATAN48 algorithm are reduced from 234 and 234 to 216.39 and 219.68 respectively.Compared to the previous practical attack at the single-key setting，the proposed method can effectively increase the number of attack rounds and recoverable key bits，and reduces the computational complexity of attack.Key words:block cipher;Mixed-Integer Linear Programming(MILP);KATAN algorithm;conditional differential cryptanalysis;neural distinguisher0 引言 当今，人工智能技术飞速发展，生活中的各个领域都有它活跃的身影。深度学习作为人工智能的重要组成部分，解决了一系列人工智能领域内的困难问题，并被广泛地应用于图像识别、自然语言处理、机器翻译等领域1。深度学习的概念由 Hinton 等2提出，利用神经网络自动化提取数据特征，使得特征工程（Feature Engineering）变得高效简洁。卷积神经网络（Convolutional Neural Network，CNN）3和循环神经网络（Recurrent Neural Network，RNN）4等神经网络模型的提出使得神经网络的学习能力大幅增强。随着深度学习的广泛应用，不断有学者提出将深度学习与密码分析结合的可能性。Rivest5从理论上说明了密码学和机器学习是相关联的领域。在随后的几十年里，利用深度学习技术进行密码分析的工作层出不穷。Greydanus6利用单层长短时记忆（Long Short-Term Memory，LSTM）网络模拟了Enigma密码的解密函数。在2018年的国际学习表征会议（International Conference on Learning Representations，ICLR）中，Gomez等7提出使用生成对抗网络完成对维吉尼亚密码等多表代替密码进行破译的方法。在 2019 年的美密会（International Cryptology Conference，CRYPTO）上，首次将深度学习技术应用到分组密码算法分析中，Gohr8利用深度学文章编号：1001-9081（2023）08-2462-09DOI：10.11772/j.issn.1001-9081.2022060886收稿日期：20220620；修回日期：20220830；录用日期：20220901。基金项目：河南省自然科学基金资助项目（232300421394）。作者简介：林东东（1998），男，河南邓州人，硕士研究生，主要研究方向：深度学习、智能化分组密码分析；李曼曼（1986），女，河南开封人，讲师，博士，主要研究方向：分组密码分析、中间相遇攻击；陈少真（1967），女，江苏无锡人，教授，博士，主要研究方向：分组密码分析、密码体制识别。第 8 期林东东等：基于神经区分器的KATAN48算法条件差分分析方法习技术生成了强大的密码区分器，通过实验证明新的区分器优于传统区分器，并利用该区分器改进了Speck32/64算法的密钥恢复攻击。Bao 等9将广义的中性比特技术引入 Gohr的密钥恢复框架，首次提出了 Speck32/64 算法的 13 轮实际密钥恢复攻击，并利用该技术完成了 Simon32/64 算法的 16轮实际密钥恢复攻击，降低了密钥恢复的数据复杂度。在2021年欧密会（European Cryptology Conference，EUROCRYPT）上，Benamira等10给出了一种神经区分器内部工作原理的解释，表明神经区分器不仅依赖密文对的差分分布，也依赖倒数第2轮和倒数第3轮的差分分布。在后续的研究中，更多的学者考虑了神经网络输入数据的格式对神经区分器的影响。Hou等11提出了一种使用多个输出差分的新神经区分器，通过将输出差分拼接成一个矩阵作为样本，同时利用更多衍生特征提高神经区分器的准确率。Chen等12提出了一种同时考虑多个密文对的新神经区分器，并在Speck32/64、Chaskey等5种算法上验证了新的数据格式的有效性，其中多个密文对由不同的密钥构成。KATAN系列密码算法是以非线性反馈移位寄存器为基础的轻量级分组密码算法，最初由de Cannire等13设计并发表在 2009 年加密硬件和嵌入式系统会议（Cryptographic Hardware and Embedded Systems，CHES）上。KATAN 系列算法面向硬件的轻量级分组密码，在实现算法分组长度足够小的同时，保证了足够的安全性。在 2010 年亚密会（Annual International Conference on the Theory and Application of Cryptology and Information Security，ASIACRYPT）上，Knellwolf等14首次提出KATAN系列算法的条件差分分析方法。在单密钥下，对70轮KATAN48算法进行了实际密钥恢复攻击，成功恢复了2比特密钥。Knellwolf等15在相关密钥条件下，实现了对 103 轮 KATAN48 算法的实际密钥恢复攻击。除此之外，还有一些其他的理论攻击结果16-19，详见表1。其中，刘爱森等16改进了文献 15 中的工作，给出了140轮 KATAN48 算法的理论分析结果。文献 17-19 中采用了中间相遇攻击的扩展方法。文献 16-19 中的工作理论上增加了 KATAN48算法的攻击轮数，受限于理论攻击庞大的计算复杂度，因而无法进行实际攻击。神经区分器已经应用到了 Feistel 型和代换-置换网络（Substitution-Permutation Network，SPN）型轻量级分组密码上，改进了诸多算法的实际密钥恢复攻击结果。本文尝试将文献 11 中的多输出差分神经区分器应用到基于NLFSR的KATAN48算法上，并结合条件差分分析的思想，改进实际密钥恢复攻击结果。由表1不难看出，在单密钥下，本文的研究是目前为止KATAN48算法最好的可进行实际攻击的分析结果。本文的主要工作如下：1）深入研究多输出差分神经区分器的基本原理，并将它应用于KATAN48算法。根据KATAN48算法的数据格式，修改了深度残差神经网络的输入格式和部分网络超参数；并通过实验筛选了合适的多输出差分神经区分器的差分堆叠个数和输入差分。2）建立 KATAN48 算法的混合整数线性规划（Mixed-Integer Linear Programming，MILP）模型，搜索前加差分路径及约束条件。将多输出差分神经区分器与约束条件结合，增加了 KATAN48算法区分器的轮数。在筛选明文阶段，利用消息修改等技巧降低了筛选满足约束条件明文时的计算复杂度。3）利用基于神经区分器条件差分分析方法，在单密钥下，提出了 78、79、80 轮 KATAN48 算法的实际密钥恢复攻击，其中80轮KATAN48算法的攻击恢复了连续24比特子密钥。在密钥恢复阶段，结合差分分析方法，扩展了条件差分分析可恢复的密钥轮数。相较于文献 14，攻击轮数增加了10轮，增加了可恢复的密钥比特数，且密钥恢复攻击的时间复杂度为219.68，数据复杂度为216.39。以80轮KATAN48算法密钥恢复攻击为例，展示文章各个部分之间的关系，具体如图1所示。1 基础知识 1.1符号说明文中用到的符号如表2所示。1.2KATAN系列密码算法简介KATAN 系 列 分 组 密 码 算 法 有 3 个 版 本：KATAN32、KATAN48 和 KATAN64。这 3 个算法版本分组长度分别为32、48、64比特，其密钥生成算法、密钥长度和加密轮数均相同，并且共用相同的非线性函数。在KATAN系列算法中，密钥生成算法是采用80级的线性反馈移位寄存器，将80比特密钥置入移位寄存器，每轮寄存器运动2比特，获得每轮对应的2比特子密钥。本文主要对KATAN48算法展开分析研究，下面详细介绍KATAN48算法的结构。KATAN48 算法的主密钥为 80 比特，记为K=表1KATAN48算法的攻击结果Tab.1Attack results of KATAN48 algorithm攻击类型条件差分分析MIMT ASRMatch Box MIMT多维MIMT基于神经区分器的条件差分分析攻击条件单密钥相关密钥相关密钥单密钥单密钥单密钥单密钥攻击轮数7010314010512914880时间复杂度234225277.4279.1278.5279219.68数据复杂度234CP225CP227CP144CP32CP2KP216.39CP参考文献文献 14文献 15文献 16文献 17文献 18文献 19本文 注：MIMT表示中间相遇攻击；ASR表示AllSubkeys Recovery；CP表示选择明文；KP表示已知明文。图180轮KATAN48算法密钥恢复攻击Fig.1Key recovery attack of 80-round KATAN48 algorithm2463第 43 卷计算机应用(k0，k1，k79)。子密钥由密钥生成算法生成：ki+80=ki+ki+19+ki+30+ki+67；0 i 427（1）KATAN48 算法的分组规模是 48 比特，寄存器L和R的长 度 分 别 为 19 比 特 和 29 比 特，48 比 特 明 文P=(p47，p46，p0)按以下方式置入寄存器：(p47，p46，p29)(l0，l1，l18)(p28，p17，p0)(r0，r1，r28)（2）将轮函数定义如图2所示。将上述轮函数写为如下形式：li+19=ri+ri+9+ri+7ri+15+ri+13ri+22+k2t+1ri+29=li+li+6+li+3li+11+li+12ct+k2t；t=i 2，0 i 507（3）其中ct是轮常数，初始值为(1，1，1，1，1，1，1，0)，按照ct+8=ct+ct+1+ct+3+ct+5(t 8)进行更新。经过 254 轮迭代之后，将寄存器L和R中的比特，按置入寄存器时的顺序输出作为密文。1.3基于神经区分器的差分分析在CRYPTO 2019上，Gohr首次系统地提出了基于神经区分器的差分分析框架。基于神经网络构造了神经区分器模型，使用明文差分和密文对数据训练了减轮Speck32/64算法的神经区分器。在密钥恢复阶段，结合贝叶斯优化算法20使用神经区分器攻击了11和12轮Speck32/64算法。首先介绍神经区分器的构造方法。Gohr在文献 8 中给出了Speck32/64的神经区分器模型。具体构造过程如下：固定明文的输入差分为=(0 x40，0)和明文对(P，P)，部分加密得到减轮的密文对(C，C)。其中密文对作为神经网络的输入数据，并随机生成0-1数据Y作为密文对的标签。当Y=1时，明文P=P；当Y=0时，P是随机生成的。将上述密文对数据(C，C)及其对应的标签Y输入神经区分器，若在充分的训练后，区分器能以大于50%的准确率正确区分标签，则得到一个神经区分器。神经区分器的准确率分为训练准确率和测试准确率，测试准确率是衡量区分器是否有效的关键指标。本文默认将测试准确率简记为准确率。Gohr 使用深度残差神经网络21训练了 58 轮Speck32/64算法的神经区分器，准确率随着轮数增高而下降。Gohr利用r轮神经区分器对r+1轮Speck32/64算法进行密钥恢复攻击。使用猜测密钥Kr将r+1轮Speck32/64算法的密文解密一轮，并用r轮神经区分器对当前猜测密钥Kr进行评分并排序，当猜测密钥Kr的得分超过阈值c1时，则返回当前猜测密钥。为了提高密钥恢复的效率，Gohr使用贝叶斯优化算法优化了密钥搜索策略，并且利用了错误密钥对输出响应值分布的不均匀性生成了错误密钥响应分布，在密钥搜索的迭代中生成新的候选密钥。为了增强区分器的响应，Gohr使用了s个中性比特22生成了2s明文组成的明文结构，明文结构中的每一对明文都能通过区分器的初始两轮差分路径。将明文结构加密得到对应的密文结构，密文结构整体的区分器响应值作为当前猜测密钥区分器响应值。将上述算法总结为算法1。算法1 R+1轮贝叶斯密钥搜索策略。输入 密文结构Cstructure=C0，C1，C2s-1，R轮神经网络多差分区分器NDR，需要生成的候选密钥数n，迭代次数l。输出 密钥集合T。1）S k0，k1，kn-1在候选子密钥集的所有子密钥中 随机选择，并且不作替换。2）T 3）for j 0，1，l-1：do4）Pi，k Decrypt(Ci，k)；Ci Cstructure，i 0，1，2s-15）vi，k NDR(Pi，k，k)；i 0，1，2s-1，k S6）wi，k lb(vi，k/(1-vi，k)；i 0，1，2s-1，k S7）wki=02s-1wi，k；k S8）T T|(k，wk)；k S9）mki=02s-1wi，k 2s；k S10）ki=0n-1(mi-kki)22kki；k 0，1，216-111）S argsortk()0：n-112）end for13）return T2 KATAN48算法多输出差分神经区分器 一个轮数足够高的神经区分器能够有效提升密钥恢复攻击的轮数，并且神经区分器在相同轮数下的准确率越高，密钥恢复攻击的计算复杂度就越低。Hou等11提出了针对Simon和Speck算法的多输出差分神经 区 分 器（Multiple Output Differences Neural Distinguisher，MODND），使神经网络不仅学习到每一个输出差分中的特征，也学习到不同输出差分之间的联系，提高了Simon和Speck算法的神经区分器的准确率。本章将多输出差分神经区分器的思想应用到KATAN48算法上，介绍KATAN48算法多输出差分神经区分器的神经网络结构，通过实验验证多输出差分神经区分器在KATAN48算法上的有效性，并为区分器找到合适的输入差分。表2符号说明Tab.2Symbol description符号PCpiciKkiLtRt含义48比特明文数据48比特密文数据第i个明文比特第i个密文比特80比特主密钥第i个密钥比特第t轮的19比特寄存器状态第t轮的29比特寄存器状态符号lt+irt+ilt+irt+iPblockPstructureCstructure含义第t轮的19比特寄存器状态的第i个明文比特第t轮的29比特寄存器状态的第i个明文比特lt+i的差分rt+i的差分明文组明文结构密文结构图2KATAN48算法的轮函数Fig.2Round function of KATAN48 algorithm2464第 8 期林东东等：基于神经区分器的KATAN48算法条件差分分析方法2.1神经网络结构Gohr 利用深度残差神经网络得到了减轮的 Speck32/64算法的神经区分器。本节沿用了 Gohr的基本网络架构，并根据KATAN48算法的数据格式修改了神经网络的输入格式和部分网络参数。具体结构如图 3所示，图中 BN表示批归一化（Batch Normalization）。神经网络主要包括输入层、循环层和输出层3个部分。输入层接收KATAN48算法训练数据，Reshape层将数据堆叠成矩 阵 形 式，并 通 过 一 维 卷 积（1-Dimensional Convolution，Conv1D）层对数据进行简单特征提取。在循环层中，网络使用了5个残差块。在每个残差块中，由两个Conv1D层组成的，并且每一个 Conv1D 层后都有一个 BN 层（batch normalization layer）和一个激活层（activation layer）。在残差块操作之后，将输出进行Add操作，并作为下一个残差块的输入。输出层由全连接层（fully connected layer）和输出单元组成。下面给出网络部分具体参数，输入层 Conv1D 层的卷积核数设为 1，迭代层中卷积核数设为 3。每个卷积层的滤波器数设为n，其中n为差分数据堆叠个数，正则化方法选择L2权值正则化。其余超参数详见表3。2.2KATAN48算法多输出差分神经区分器的训练深度学习技术是数据驱动的，训练数据的质量对模型的优劣起着重要的作用。对于神经区分器来说，训练数据的构造方式直接影响了区分的准确率。深度残差网络最初应用在图像识别领域，对识别矩阵形式的数据有着得天独厚的优势。多输出差分神经区分器将多个输出差分拼接到一个矩阵当中，利用了矩阵中更多的输出差分，使得神经网络学习到了更多的特征。多输出差分数据的构造方式如图4所示。如图 4 所示，设输入差分为（=PP），随机生成n个明文对(P，P)，通过算法加密生成的n个密文对(C，C)，进而得到n个密文差分C。其中密文差分作为神经网络的输入数据，并随机生成0-1数据Y作为密文对的标签。下面通过实验验证多输出差分神经区分器针对KATAN48算法的有效性。神经网络的输入层维度为(n n，1)，超参数设置见表3。实验验证了MODND针对KATAN48算法的有效性，并选择了合适的多差分堆叠个数。实验结果见表4。针对 KATAN48 算法的 40 轮 MODND，当多差分堆叠数n=1时，准确率是61.7%。此时，MODND的准确率已经大于50%，说明了改变数据格式的有效性。当多差分堆叠个数增加后，MODND 的准确率和n是正相关的。当n=48时，MODND 的 准 确 率 比n=1提 升 了 37 个 百 分 点。针 对KATAN48 算法的 50 轮 MODND，当n=1时，准确率仅有50.1%，此时 MODND 训练失败。当n=48时，准确率达到54.0%，MODND具备区分能力。综合上述实验结果，选择多差分堆叠个数n=48的MODND进行输入差分筛选的实验。针对 KATAN48算法，为了得到轮数更高的神经网络多差分区分器，需要选择合适的输入差分。由实验经验可知，汉明重量较低的输入差分的区分器准确率会明显更高，所以本节针对n=48的40轮KATAN48算法MODND遍历了汉明重量为1的所有输入差分。表5中i表示输入差分的第i比特位为1的位置，明文比特的顺序为P=(p47，p46，p0)。实验结 果 如 表 5 所 示，保 留 表 中 准 确 率 大 于 90%的 40 轮KATAN48算法MODND，即当输入差分i=46，45，44，43，42，此时，KATAN48 算法 MODND 的轮数与前人的工作相差过多。因此，结合条件差分分析的思想，通过约束条件控制 KATAN48算法的差分传播，达到改进密钥恢复攻击结果的目的。MODND将选择前加差分路径与区分器轮数之和尽可能大的输入差分。在下一章中，为了得到约束条件和差分路径，建立了KATAN48算法的MILP模型。图3神经网络结构Fig.3Structure of neural network表3神经网络超参数设置Tab.3Hyperparameter setting of neural network超参数训练集规模测试集规模批处理规模迭代周期参数取值1071061 000200超参数优化器学习率损失函数参数取值Adam10-4MSE图4多输出差分数据的构造Fig.4Construction of multiple output differences data表4不同差分堆叠个数下KATAN48算法的MODND准确率Tab.4MODND accuracy of KATAN48 algorithm with different numbers of stacked differences区分器轮数404040405050多差分堆叠数n141648148准确率/%61.774.290.998.750.154.02465第 43 卷计算机应用3 KATAN48算法约束条件的求解 在 KATAN48算法中，每轮新生成比特的差分是由前一轮的部分比特和差分所决定的。通过求解约束条件，对前轮部分比特进行约束，进而来控制差分的值，达到控制差分传播的目的。在实际应用中，约束条件一般用于控制前几轮的差分路径。约束条件可以分为以下3类：1）约束条件中仅包含明文比特pi。2）约束条件中包含明文比特pi和密钥比特ki。3）约束条件中仅包含密钥比特ki。本章基于Xing等23所提出的KATAN32的MILP模型，设计KATAN48算法的MILP模型并对它进行优化。3.1MILP模型建立由于KATAN32和KATAN48算法共用轮函数，本节直接使用文献 23 中的不等式组刻画 KATAN48算法的轮函数。两 者 区 别 在 于 KATAN32 算 法 每 轮 应 用 一 次 轮 函 数，KATAN48 算 法 使 用 相 同 密 钥 应 用 两 次 轮 函 数。由 于MODND对输入差分的选择是敏感的，并且要求输入数据均满足同一输入差分，所以在MILP模型搜索前加差分路径的约束条件时，应加入对差分路径输出差分的约束，搜索在此条件下轮数最长的概率为1差分路径。利用48个等式作为约束条件对差分路径输出差分进行约束：j=0，j i1，j=i；0 j 47（4）利用KATAN48算法的MILP模型搜索前加差分路径及相应 约 束 条 件，固 定 差 分 路 径 输 出 差 分 为i=42，43，44，45，46。实验结果如表 6 所示。选择差分路径输出差分i=42，即=0 x040000000000。求得一条概率为1的23轮差分路径，其约束条件数为15。此时，前加差分路径与区分器轮数之和不一定是最大值。由于密钥恢复攻击时需要使用消息修改技术对约束条件进行化简和变型，以降低明文筛选的复杂度。当约束条件过多时，会导致无法使用消息修改技术。因此，优先选择高准确率的MODND，其次搜索尽可能长的前加差分路径并保证约束条件数尽量少。3.2约束条件求解根据表 6 中 MILP 模型的搜索结果，选择差分路径输出差分为=0 x040000000000，得到了一条 23轮的差分路径，约束条件数为15，详细差分路径如表7所示。表5中部分约束条件的完整形式如下，其中l53=0约束条件完整形式过长，在此不进行详细描述：r23r32=p5(p44p38p41p33p32k2)=1（5）r35=p41p35p38p30p29k12=0（6）r31=p45p39p42p34p33k2=0（7）l34l41=p35p29p32(p24p15p11p9p11p2k5)(p23p14p16p8p10p1k5)k12=0（8）r40=p36p30p33(p25p16p18p10p12p3k3)(p24p15p17p9p11p2k5)k10=0（9）l37=p10p1p3(p43p37p40p32k4)k19=0（10）l43=p4(p43p37p40p32p31k4)k25=0（11）在 上 述 15 个 约 束 条 件 约 束 下 的 明 文 差 分P=0 x100000804024可 以 概 率 1 传 播 到 输 出 差 分=0 x040000000000，差分路径的长度为23轮。为了降低筛选符合约束条件明文时的计算复杂度，本文将约束条件化简和变形。将每个随机生成的明文通过约束条件进行消息修改，使得明文最终满足所有的约束条件。例如，将式（5）进行化简与变形：p5=p44p38p41p33p32k21（12）依次将上述15个约束条件进行化简和变形可以大幅降低明文筛选的计算复杂度。由于已化简的约束条件中的明文比特不能在后续化简过程中被修改，所以为了使得所有的约束条件均满足被化简和变形的条件，在上述15个约束条件的基础上，附加了以下4个约束条件：p30=1（13）r20=p27p18p20p12k11=0（14）r37=p39p33(p37p18p20p12k1)k8=1（15）r33=p43p37p40p32p31k4=0（16）应用上述19个约束条件，明文差分P可以概率1传播到输出差分，差分路径的长度为23轮。一般情况下，在利用神经区分器进行密钥恢复时，区分器对于错误密钥的响应会比较微弱。为了增强区分器的响应，Gohr利用s个中性比特生成了2s明文组成的明文结构并加密得到对应的密文结构，但是中性比特的个数有限，具体到KATAN48算法，需要保证利用中性比特生成的明文以概率1通过23轮的差分路径。因该差分路径的19个约束条件包含表6不同输出差分下MILP模型的约束条件个数和差分路径轮数Tab.6Number of constraint conditions and rounds of differential paths of MILP model with different output differences输出差分424344约束条件数151216差分路径轮数231717输出差分4546约束条件数1218差分路径轮数1620表5不同输入差分下40轮KATAN48算法MODND准确率Tab.5MODND accuracy of 40-round KATAN48 algorithm with different input differencesi474645444342414039383736准确率/%84.991.893.197.297.498.777.583.772.972.573.378.5i353433323130292827262524准确率/%61.664.166.766.965.573.778.377.576.776.988.587.1i232221201918171615141312准确率/%75.686.585.486.460.558.962.966.758.654.057.958.1i11109876543210准确率/%59.862.366.365.472.669.776.474.776.975.077.979.52466第 8 期林东东等：基于神经区分器的KATAN48算法条件差分分析方法了所有明文比特，所以不存在中性比特。文献 9 中提出了对中性比特的泛化，本节利用文献 9 提出的同时中性比特集合（Simultaneous-neutral bit-sets）思想生成明文结构。为了增强MODND的响应，并保证其以概率1通过23轮的 差 分 路 径，使 用 同 时 中 性 比 特 集 合 生 成 明 文 结 构。KATAN48 算 法 的 19 个 约 束 条 件 存 在 5 个 比 特47，46，26，21，7只在最后一个约束条件中出现，所以47，22 ，46，22 ，26，22 ，21，22 ，7，22 是5个同时中性比特集合（p22是最后一个条件改变的明文比特）。与同时中性比特集合不同，本文使用的中性比特集合是概率的，使得明文结构中至少有1/2的概率存在由中性比特生成的明文，进而更好地保证了明文结构的质量。随机生成48个明文对组成一个明文组Pblock，利用s个同时中性比特集合可以生成2s个明文组Pblock，并组成一个明文结构Pstructure。4 KATAN48算法的密钥恢复攻击条件差分分析通过控制非线性反馈移位寄存器的内部状态变量来控制差分的传播。条件差分分析的基本思想如下：首先选择输入差分，研究具体密码算法的差分传播规律，并确定密码算法内部状态比特的约束条件，尽可能地控制差分传播。通过选择合适的约束条件，并通过约束条件筛选符合条件的明文作为输入，可检测到某些更新比特差分存在偏差。表7KATAN48算法的差分路径及对应的约束条件Tab.7Differential paths and corresponding constraint conditions of KATAN48 algorithm轮数01234567891011121314151617181920212223差分状态00010000000000000000000010000000010000000010010000100000000000000000000100000000100000000100100001000000000000000000001000000001000000001001000010000000000000000000010000000010000000010010000000000000000000000000100000000100000000100100000100000000000000000000000000001000000001001000001000000000000000000000000000010000000010010000010000000000000000000000000000100000000100100000100000000000000000000000000001000000001001000001000000000000000000000000000010000000010010000010000000000000000000000000000100000000100100000100000000000000000000000000001000000001001000001000000000000000000000000000010000000010010000010000000000000000000000000000100000000100100000100000000000000000000000000001000000001001000001000000000000000000000000000000000000010010000010000000000000000000000000000000000000100100000100000000000000000000000000000000000001001000001000000000000000000000000000000000000010010000010000000000000000000000000000000000000100100000100000000000000000000000000000000000001001000001000000000000000000000000000000000000010010000010000000000000000000000000000000000000100100000100000000000000000000000000000000000001001000001000000000000000000000000000000000000000010000010000000000000000000000000000000000000000100000100000000000000000