2022, Vol. 33
2. 密码科学技术国家重点实验室, 北京 100878
2. State Key Laboratory of Cryptology, Beijing 100878, China
得益于互联网及计算机硬件的发展, 人工智能技术广泛应用于生活的各个场景之中. 作为人工智能得以迅速发展的一个重要原因, 深度学习技术作为人工智能的重点研究领域之一, 推动了人工智能从幕后到台前. 目前应用于生活的人脸识别、智慧农业等的人工智能均离不开深度学习技术的推动. 随着深度学习算法的不断发展, 深度学习在人工智能领域一些最困难的问题上取得了重大突破, 并且被应用于图像识别、自动驾驶、自然语言处理等各大领域[1].
深度学习技术是神经网络发展到一定时期的产物. 1943年, McCulloch和Pitts[2]提出了MP神经元模型, 即一个按照生物神经元的结构和工作原理构造出来的抽象和简化了的模型, 实际上就是对单个神经元的一种建模. 其大致模仿了自然神经元的工作原理, 开启了模拟神经网络的先河, 但是其权重设置及调整大量依赖于手工, 十分不利于研究. 1958年, Rosenblatt[3]在MP神经元模型的基础上提出了第一代神经网络单层感知器, 其能够区分三角形、正方形等基本形状. 1986年, Rumelhart等人[4]提出了第二代神经网络, 将第一代神经网络中单一固定的特征层改为多个隐藏层, 使用Sigmoid函数作为激活函数, 并利用反向传播算法(back propagation, BP)逆向传播的思想对网络参数进行学习, 这有效地解决了第一代神经网络只能处理线性分类问题的困难. 卷积神经网络(convolutional neural networks, CNN)[5]和循环神经网络(recurrent neural networks, RNN)[6]等神经网络模型也得到了一定的发展. 步入21世纪, 伴随着计算芯片等硬件设备的提升, 神经网络的研究也得以快速发展. 2006年, Hinton等人[7]首次提出了深度学习的概念, 并指出: 可以通过逐层初始化的方法抑制梯度消失, 从而解决深度神经网络在训练上的难题. 2011年, Glorot等人[8]提出了ReLU激活函数, 能有效地抑制梯度消失问题.
伴随着深度学习基础理论的发展和各型神经网络模型的提出, 以及专用计算芯片的研发与大量部署使用, 深度学习广泛应用于生活的各个领域. 2016年, AlphaGo击败围棋冠军李世石就离不开深度学习技术的助力. 受深度学习技术蓬勃发展的影响, 密码分析领域也逐步使用深度学习技术以帮助减少密码算法分析的复杂度. 在2019年美密会(Crypto2019)上, Gohr[9]提出了使用深度学习技术对轻量级分组密码算法SPECK[10]的密钥恢复攻击. 在文献[9]中, Gohr描述了可以通过深度学习得到区分器, 并且说明了通过深度学习技术得到的区分器要优于通过传统分析方法得到的区分器. 同时, Gohr也刻画了针对SPECK算法的密钥恢复攻击, 其通过将贝叶斯搜索方法与深度学习区分器结合对SPECK32算法的两轮子密钥进行了恢复, 并说明了使用深度学习技术的密钥恢复攻击的复杂度要远远低于传统密钥恢复攻击的复杂度. 但是, Gohr并未说明其选择所用神经网络模型的原因. 深度学习技术领域的专家为应对多种数据的处理难题提出了多种神经网络模型, 针对不同的数据类型, 应该选择不同的模型才能保证模型的精度. 因此, 研究不同网络模型对轻量级分组密码算法的差分区分器的影响是有必要的. 同时, Gohr构造的神经网络区分器的训练时间开销是巨大的, 这不利于后续的密码分析研究, 不利于快速找到适合不同分组算法的神经网络模型. 因此, 在保证模型精度不影响后续差分分析的前提下, 研究神经网络模型中超参数的设置以降低训练开销是有重要意义的.
本文第1节描述本文研究的两个轻量级分组密码算法SIMON[10]与SPECK[10]. 在第2节描述基于深度学习的差分区分器的构造方法, 使用两种典型的神经网络模型构造差分区分器, 并对这两种神经网络模型构造的差分区分器进行对比. 结合第2节的内容, 我们在第3节说明通过深度学习构造差分区分器的超参数的选择. 最后一节, 我们对目前的研究工作进行总结.
1 SIMON与SPECK算法简介SIMON与SPECK算法是由NSA (national security agency)提出的轻量级分组密码算法[10], 两种算法按照分组长度及密钥长度均有多个版本. 虽然两种算法的运算结构是轻量级的, 但是其仍然可以在多个平台上提供良好的安全性. 两种加密算法可满足多平台的要求, 其在多平台上部署是足够灵活的. 其中, SIMON算法在硬件上表现优异, 而SPECK算法在软件上表现优异. 由于SIMON算法与SPECK算法在运算上有诸多相似性, 因此我们将两种算法的运算符一并介绍. SIMON算法与SPECK算法的运算过程主要涉及以下的4个运算操作.
• ⊕: 比特异或操作XOR;
• &: 比特与操作AND;
• +: 模2n加操作;
• Sj: 比特循环左移位j比特.
1.1 SIMON算法为应对不同平台对通信安全性的不同需求, SIMON算法设计者给出了多个版本的SIMON算法以供不同平台的选择. 每个版本的具体参数见表1.
|
表 1 SIMON算法参数 |
针对不同版本的SIMON算法, 其对应的参数如表1所示. 表1给出了不同版本的SIMON算法的参数, 其中, 固定参数序列zi用于密钥扩展中. 对于特定版本的SIMON算法, 通常使用SIMON2n/mn指定. 比如说, 对于分组长度为32比特、密钥长度为64比特的SIMON算法, 通常用SIMON32/64指定. 在不考虑分组长度时, 一般也直接用SIMON2n指定.
设GF(2)代表二元有限域, GF(2)n代表GF(2)上的n维向量空间, 那么对于ki∈GF(2)n, SIMON2n的轮函数可以定义为Feistel映射
| $ {R_{k_i}}({x_{i + 1}},{x_i}) = ({x_i} \oplus f({x_{i + 1}}) \oplus {k_i},{x_{i + 1}}), $ |
其中, f(xi+1)=(S1xi+1&S8xi+1)⊕S2xi+1, ki是轮子密钥. 轮函数的逆为
|
图 1 SIMON算法的轮函数 |
1.2 SPECK算法
同样的, SPECK为应对不同平台对通信安全性的不同需求, 其算法设计者也给出了多个版本的SPECK算法以供用户选择. 每个版本的具体参数见表2.
|
|
表 2 SPECK算法参数 |
针对不同版本的SPECK算法, 其对应的参数如表2所示. 表2给出了不同版本的SPECK算法的参数, 其中, 循环参数α与β用于轮函数运算中. 对于特定版本的SPECK算法, 通常使用SPECK2n/mn指定. 比如说, 对于分组长度为32比特、密钥长度为64比特的SPECK算法, 通常用SPECK32/64指定. 在不考虑分组长度时, 一般也直接用SPECK2n指定.
对于ki∈GF(2)n, SPECK2n的轮函数可以定义为映射
| $ {R_{{k_i}}}({x_{2i + 1}},{x_{2i}}) = (({S^{ - \alpha }}{x_{2i + 1}} + {x_{2i}}) \oplus {k_i},{S^\beta }{x_{2i}} \oplus ({S^{ - \alpha }}{x_{2i + 1}} + {x_{2i}}) \oplus {k_i}), $ |
其中, α与β为循环参数, ki是轮子密钥. 轮函数的逆为:
| $ R_{k_i}^{ - 1}({x_{2i + 3}},{x_{2i + 2}}) = ({S^\alpha }(({x_{2i + 3}} \oplus {k_i}) - {S^{ - \beta }}({x_{2i + 3}} \oplus {x_{2i + 2}})),{S^{ - \beta }}({x_{2i + 3}} \oplus {x_{2i + 2}})). $ |
这通常被用作解密操作. 其加密流程如图2所示.
|
图 2 SPECK算法的轮函数 |
2 神经网络差分区分器的构造及选择
作为一种有效的方法, 差分分析[11]被广泛用于分组密码分析之中. 在差分分析中, 差分区分器是必不可少的, 其经常用于对明文或者密文的区分, 从而辅助密码分析. 在传统的差分分析中, 首要的是找到一条高概率差分特征, 而后通过该高概率差分特征构造差分区分器. 一条高概率差分特征需要输入差分、输出差分以及该输入差分和输出差分构成的差分对的概率. 其中, 输入差分是指输入对的差分值, 输出差分是指输入对经过多轮加密后的输出对的差分值. 差分对的概率也即差分概率, 是指给定一对差分对(α,β), 当输入对的差分为α时, 其对应的输出对的输出差分为β的概率. 一个良好的可以区分更长轮数的区分器, 对于分组密码的分析具有极佳的辅助作用. 在传统差分分析中, 构造差分区分器更多地依赖于算法本身结构可能存在的缺陷, 而且构造过程中大量依赖手工推导, 大大迟缓了密码分析的过程. 近几年, 依赖自动化搜索技术[12]寻找差分区分器, 已经逐步成为差分区分器构造的主流方法.
差分区分器对明文或者密文的区分, 从本质上说就是对明文数据集或者密文数据集的分类. 而深度学习技术在图像、语音识别等领域被广泛应用于分类问题, 这与差分区分器的功能是相似的. 因此, 深度学习技术在理论上也可用于辅助差分区分器的构造或者直接用于构造差分区分器. 目前, 已经有多名学者针对基于深度学习技术构造区分器进行了研究. Gohr最早提出了将深度学习技术应用于差分区分器的构造及密钥恢复攻击之中, 在文献[9]中, Gohr对比了传统的差分区分器和基于深度学习技术的差分区分器, 无论是在区分的准确率或者应用于密钥恢复攻击上的复杂度, 基于深度学习的差分区分器都明显优于传统的差分区分器. 同样的, 在文献[13]中, Anubhab等人构造了基于深度学习的GIMLI算法的差分区分器, 相比于传统的差分区分器,其所需要的数据量更低. 相比于只使用一条或多条差分路径的传统的差分区分器, 基于深度学习的差分区分器可以通过对已知的密文数据进行学习, 完成对未知密文数据的判别. 从基于深度学习技术的差分区分器的构造方法上看, 基于深度学习技术的差分区分器可以通过已知密文数据学到密文对的输入差分的特征, 也就是说, 通过深度学习技术可以学到更多的差分路径的特征, 这也就是基于深度学习技术的差分区分器在区分效果上优于传统的差分区分器的一个原因.
在本节中, 我们探究了SPECK32和SIMON32的基于深度学习技术的差分区分器的构造, 以及两种典型神经网络模型CNN和残差神经网络(residual neural network, ResNet)[14]对基于深度学习构造的差分区分器的精度的影响.
2.1 数据集的构造在深度学习中, 数据集的选取影响着神经网络模型对未知数据判断的准确率. 因此, 我们在构造神经网络差分区分器时, 选取的数据集应尽可能随机并覆盖所有可能的情况. 在使用传统的差分分析方法对SIMON32与SPECK32进行密钥恢复研究时, 首要的步骤是寻找到一个轮数尽可能长、概率尽可能大的差分区分器, 这离不开找到一个良好的输入差分[15]. 与传统的差分区分器相同, 神经网络差分区分器也需要给定输入差分. 我们选择固定的输入差分作为神经网络差分区分器的输入差分.
我们将给定是输入差分记为diff, 下面给出构造数据集的方法.
(1) 随机生成3个包含元素个数为n的集合分别为X1, X2和Y. 其中, X1与X2中的元素为长度不超过32比特的非负整数, Y中元素为0或者1. 将这3个集合中的元素一一对应;
(2) 若Y中某一元素为1, 则将X2中的对应位置的元素的值替换为X1中对应元素与输入差分diff异或后的值, 将进行变换后的X2序列记为X3;
(3) 随机生成包含元素个数为n的集合KEY, 与X1, X3和Y中的元素一一对应, 其中, KEY中的元素为长度不超过64比特的非负整数;
(4) 将X1与X3中的元素看作明文, 使用对应位置的KEY中的元素作为密钥进行加密, 得到的密文序列记为X4与X5;
(5) 将X4与X5中对应位置的元素拼接为新的长度不超过的64比特的新元素, 并将其作为数据, Y中对应位置的元素作为该数据的标签.
图3给出了详细的构造流程.
|
图 3 数据集构造流程 |
作为深度学习技术的一个重要的分支——有监督学习, 其训练的数据集中的每一个实例均对应着一个标签, 该标签作为深度学习技术的一个期望输出, 被用于对神经网络参数的调整. 如图3所示, 我们将X4与X5拼接而成的64比特元素作为一个实例, 与其对应的标签共同构成一个集合, 并作为进行后续深度学习训练的数据集.
深度学习技术是对已知数据集的特征进行提取, 并利用这些提取的特征对未知数据进行计算, 从而得出分类的结果. 在构造不同算法的基于深度学习技术的差分区分器时, 通过不同加密算法随机生成的数据集对于神经网络模型是一致的, 因此对于SIMON32和SPECK32的区分器构造来说, 其数据集的构造方法是相同的, 仅仅在输入差分的选择中有所不同.
2.2 基于CNN的差分区分器的构造与训练CNN[5]是一类包含卷积计算且具有深度结构的前馈神经网络(feedforward neural networks), 是深度学习的代表算法之一. CNN的基本运算包含卷积运算和池化运算等运算, 其中, 卷积运算用于提取输入的不同特征, 而池化运算可以将卷积运算提取到的特征个数以提取主要特征的形式进一步缩减. 而且卷积运算对数据的不同位置使用相同的卷积核以及池化运算每次仅仅在局部进行运算, 也就是CNN采用了局部连接和权值共享的方式, 这减少了权值的数量使得网络易于优化, 同时也降低了模型的复杂度, 也就是减小了过拟合的风险. 卷积神经网络的隐藏层中一般包含卷积层、全连接层和池化层. 为便于研究, 我们构造较为简单的卷积神经网络模型, 其隐藏层仅由卷积层和全连接层构造所得. 由于卷积神经网络中输出层的上游通常是全连接层, 因此其结构和工作原理与传统前馈神经网络中的输出层相同. 使用全连接层作为输出层, 使用逻辑函数(Sigmoid)输出模型结果. 为便于理解, 我们绘制所构造的模型中的卷积层.
在图4中, 我们描述了我们构造的卷积神经网络中的所有卷积操作. 输入层将原始数据进行格式化后传递给第一个卷积层Conv1D. 在经过第一个卷积层的卷积计算后, 数据被传递给5个相同的卷积层, 被这5个相同的卷积层依次计算, 并使用BatchNormalization进行数据的归一化. 在数据经过5轮相同的卷积操作后, 被传输到全连接层和输出层输出最后的结果. 我们使用构造的卷积神经网络模型做SPECK32和SIMON32的神经网络差分区分器的训练. 运算在配置为i7-8750H和GTX1080的电脑上完成, 深度学习训练过程中的运算主要在显卡上进行以提高训练的效率.
|
图 4 卷积层 |
2.2.1 基于CNN的SIMON32的神经网络区分器
选择文献[15]附录中所展示的SIMON32的差分路径的输入差分(0x0, 0x200)作为SIMON32的神经网络区分器的差分. 在训练过程中的训练数据集的数量为107, 验证集的大小为105. 在训练7轮神经网络区分器时, 数据集为加密7轮所得到的密文对集; 而对于8轮神经网络区分器, 则加密8轮. 为了可以更好地研究训练过程中模型在验证集上的精度和损失等因素的变化情况, 对数据集进行200次迭代. 将训练过程中验证集的准确率与损失变化情况绘制图像. 如图5所示, 其中, 横坐标表示训练过程中的迭代次数, 纵坐标表示精度及损失. 图中的4条折线表示模型训练过程中验证集的精度与损失. 从图5中我们可以看到: 使用CNN训练的SIMON32的7轮区分器模型的验证集精度在94%左右, 8轮区分器模型的验证集精度在75%左右.
|
图 5 SIMON32的CNN训练 |
通过图4所示的神经网络结构以及图5所示的训练, 我们可以得到训练后的神经网络模型. 对于使用7轮加密数据进行训练得到的模型, 我们称这个网络模型为SIMON32的基于CNN的7轮差分区分器. 通过这个区分器, 我们可以对一个经过7轮加密的密文对进行分析, 并以一定概率判断该密文对是否由输入差分为(0x0,0x200)的明文对加密生成. 同样的, 对于由8轮加密数据训练得到的模型, 我们也可使用其对经过8轮加密的密文对进行判别. 通过此种方式, 我们便可以将减轮的加密算法与随机置换进行区分.
为了衡量模型的精度, 我们使用函数
同时, 研究训练过程中精度与损失的变化, 我们发现在训练过程中曲线会出现波动, 这是由于优化器设置导致的. 在本文中, 我们选择Keras中的Adam作为优化器, 且使用默认的学习率进行训练, 这就使得学习率无法变化, 从而导致图像出现轻微波动. 学习率是深度学习中的一个重要的超参数, 如何调整学习率, 是训练出好模型的关键要素之一. 在通过随机梯度下降求解问题的极小值时, 梯度不能太大, 也不能太小: 梯度太大容易出现超调现象, 即在极值点两端不断发散, 或是剧烈震荡; 太小会导致无法快速找到好的下降方向, 随着迭代次数增大损失基本不变. 学习率越小, 损失梯度下降的速度越慢, 收敛的时间更长. 在设置学习率时, 可在训练初期设置较大的学习率, 而后在训练过程中学习率逐渐降低, 这样可有效地避免出现波动. 在深度学习领域, 调节超参数是没有成文规则的, 只能通过有限的工具[17]来调节超参数来优化模型. 由于我们关注的是模型对通过固定输入差分得到的密文对的判断的准确率, 在模型训练过程中, 我们保存了模型对验证集准确率最高时的模型参数, 以便后续的研究与使用. 因此, 由于学习率导致的准确率和损失的轻微波动并不影响我们对模型的使用. 但若模型训练过程中准确率和损失波动过大, 则需要对学习率进行调整, 以求模型尽可能训练到最佳位置. 最后, 从验证集精度的变化曲线可以看出: 在进行模型训练过程中, 可能并不需要多代训练, 通过前几代训练便可以得到一个较好的差分区分器模型. 这有助于降低训练的时间开销, 以实现快速的对分组算法的分析.
2.2.2 基于CNN的SPECK32的神经网络区分器与SIMON32的神经网络差分区分器的训练过程相似, 选择差分(0x40,0x0)作为SPECK32的神经网络区分器的差分. 在训练过程中, 数据集的数量为107, 验证集的大小为105. 训练SPECK32的6轮与7轮神经网络区分器时, 数据集均通过2.1节的方法构造. 与在SIMON32上的训练相同, 我们对数据集进行200次迭代. 我们将SPECK32的6轮与7轮区分器的训练过程验证集的精度及损失绘制如图6所示, 其中, 横坐标表示训练过程中的迭代次数, 纵坐标表示精度及损失. 从图6中我们可以看到: 使用CNN训练的SPECK32的6轮区分器模型的验证集精度在78%左右, 7轮区分器模型的验证集精度在61%左右. 对模型进行评估, 模型的精度与模型在验证集上的精度相当. 我们可以看到: 使用CNN模型对SPECK32进行6轮与7轮区分器训练时, 其损失与精度在经过最初的几次的迭代后便趋于平缓. 这对于我们构造与训练神经网络差分区分器是有所启示的, 我们对于模型的训练可能并不需要经过多次迭代也可取得一个良好的模型.
2.3 基于ResNet的差分区分器的构造与训练作为卷积神经网络的一种优化版本, ResNet[14]在2015年一经提出便被应用到ImageNet比赛中, 并取得了第一名的成绩. 由于神经网络训练过程中的反向传播, 很容易出现梯度消失的问题. 这使得随着网络层级的不断增加, 模型的精度会不断得到提升. 而当网络层级增加到一定的数目后, 训练精度和测试精度会迅速下降, 从而导致当网络变得很深以后, 深度网络就变得更加难以训练. 也就是说, 随着网络深度的增加, 准确率达到饱和然后迅速退化. ResNet引入了残差网络结构, 也就是在卷积神经网络中叠加了恒等映射, 这可以让网络随着深度增加而不退化, 这也从侧面反映了多层非线性网络无法逼近恒等映射网络. 通过这种残差网络结构可以增加网络层数, 同时使用了较少的池化层, 大量使用降采样, 提高了传播效率, 最终的分类效果会表现得非常好. 为便于直观了解我们所构造的模型, 我们将所构造的残差神经网络中的残差块绘制如图7所示.
我们构造的残差模型的隐藏层中共包含5个图7所示的残差块. 为保证硬件的统一, 我们选用与CNN训练过程中相同的硬件设备进行训练. 与CNN中对原始密文数据集的处理方式相同, 我们将原始数据进行格式处理, 并通过Conv1D卷积层对数据进行计算和通过BatchNormalization对数据进行归一化, 而后传输到图7所示的残差块中进行计算, 最后通过输出层输出最终的结果.
|
图 6 SPECK32的CNN训练 |
|
图 7 残差块 |
2.3.1 基于ResNet的SIMON32的神经网络区分器
与CNN训练中选择的参数相同, 选择输入差分为(0x0, 0x200)作为SIMON32的神经网络区分器的差分. 在训练过程中, 训练数据集的数量为107, 验证集的大小为105, 且在训练中进行200次迭代. 在训练7轮与8轮神经网络区分器时, 其数据集的获得方式与基于CNN的SIMON32神经网络区分器训练时的数据集获取方式一致. 我们将训练过程中验证集的准确率与损失变化情况绘制图像, 如图8所示, 其中, 横坐标表示训练过程中的迭代次数, 纵坐标表示精度及损失. 从图8可以看到: 使用ResNet训练的SIMON32的7轮区分器模型的验证集精度在97%左右, 8轮区分器模型的验证集精度在75%左右. 对模型进行评估, 其在新的数据集上的精度与验证集上的精度相当.
|
图 8 SIMON32的ResNet训练 |
2.3.2 基于ResNet的SPECK32的神经网络区分器
与SPECK32的基于CNN模型的神经网络差分区分器的训练过程相似, 我们选择差分(0x40, 0x0)作为SPECK32的基于ResNet的神经网络区分器的差分. 在训练过程中, 数据集的数量为107, 验证集的大小为105, 且在训练中进行200次迭代. 通过第2.1节可知, 在训练6轮和7轮神经网络区分器时, 其数据集分别通过7轮与8轮SPECK32加密得到. 我们将训练过程中验证集的准确率与损失变化情况绘制图像, 如图9所示, 其中, 横坐标代表训练过程中的迭代次数, 纵坐标表示精度及损失. 从图9中我们可以看到: 使用ResNet训练的SPECK32的6轮区分器模型的验证集精度在78%左右, 7轮区分器模型的验证集精度在61%左右. 对模型进行评估, 模型的精度与验证集的精度相当, 在6轮和7轮上的精度分别是78. 3%和61%.
|
图 9 SPECK32的ResNet训练 |
2.4 两种区分器的对比 2.4.1 传统区分器与神经网络区分器对比
差分分析属于选择明文的攻击方法, 其探究选择的明文对差分在加密过程中的概率传播特性, 将分组密码与随机置换进行区分, 并依赖于此进行密钥恢复攻击. 在传统的差分区分器构造过程中, 其依赖一对或几对差分对, 而这离不开对差分路径的寻找. 目前, 主流的寻找差分路径的方式为自动化搜索, 包括基于SAT的自动化搜索和基于MILP的自动化搜索. 为更好地利用差分对, 目前常用的技术是固定输入差分和输出差分, 使用自动化搜索技术差分路径, 而后统计并计算差分对的概率[18]. 而对于基于深度学习的差分区分器, 其利用一个给定的输入差分, 将密文对作为训练集进行模型的训练构造区分器. 而由于这些密文对的差分并不固定, 因此, 通过深度学习训练的差分区分器可以视为一个多合一的区分器[13]. 从这一角度来看, 基于深度学习的差分区分器可以更有效地利用输入差分.
在Crypto2019中, Gohr已经对SPECK32算法的神经网络区分器强于传统的差分区分器进行了对比说明, 但目前仍未有文献对SIMON32的神经网络区分器和传统区分器进行对比说明. 因此, 我们着重对SIMON32算法的传统差分区分器和基于深度学习的差分区分器进行对比说明. 在第2.2节与第2.3节中, 我们构造了SIMON32的7轮和8轮的神经网络区分器. 为进行对比, 我们构造7轮和8轮SIMON32的传统差分区分器, 即基于差分路径的差分区分器. 基于文献[18]中的SIMON算法的SAT模型, 使用Z3求解器[19]搜索得到了SIMON32算法的8轮差分路径.
如表3所示, 基于SAT对SIMON32的差分路径进行了自动化搜索, 其在8轮中最佳的差分路径的概率为2−25. 也就是说, 使用传统的差分区分器至少需要225对明文对[20]才具有区分效果. 而在第2.2节和第2.3节中, 构造基于深度学习的差分区分器只需要107对密文对即可完成对神经网络模型的训练.
|
|
表 3 SIMON32的8轮差分路径 |
但是传统的差分区分器在轮数较低时, 其传播概率较大, 所需要的选择明文量也更少. 我们使用Z3求解器搜索得到了SIMON32算法的最佳7轮差分路径, 其概率为2−20.
通过表4发现: 对于SIMON32的7轮区分器, 其依赖于传统的差分区分器所需要的选择明文量要低于基于深度学习技术构造差分区分器所需要的明文量. 我们可以发现, 传统的差分区分器所需要的选择明文量与其轮数有关: 当轮数增加时, 即使选择固定轮数, 其传播概率也会降低, 从而使得选择明文量增加; 而对于基于深度学习的差分区分器, 其由于需要对差分特征进行学习, 因此其选择的明文量越大, 其准确率一般也会增大.
|
|
表 4 SIMON32的7轮差分路径 |
对于相同的密码算法, 由于算法的扩散性和混淆性, 当轮数增加时, 密文的伪随机性也在增加, 这导致了对于基于深度学习得到的差分区分器其识别效果将会下降. 而对于通过差分路径构造的差分区分器, 其轮数的增加会导致其差分路径的概率下降, 从而使得其区分效果也是下降的. 从这一点来看, 两种方法得到的差分区分器是相同的. 同时, 在构造基于深度学习的差分区分器时, 其需要给定输入差分, 当该输入差分对应的输出差分分布较为均匀时, 神经网络区分器的区分效果是较差的. 而对于传统的差分区分器, 当输入差分对应的输出差分分布较为均匀时, 其差分路径的概率接近
我们对两种模型进行对比, 以便选择更佳的模型进行分组密码的分析. 表5给出了其中的对比.
在表5中, 训练时间是指在配置为i7-8750H和GTX1080的PC上进行一代(epoch)运算的时间, 精度是指使用新数据集对模型进行评估的精度. 正如表5所展示的: 对于SIMON32的差分区分器来说, ResNet模型在单考虑精度的前提下是要优于CNN模型. 因此, 在进行SIMON32的差分区分器训练过程中, 在硬件设备可以满足及时间可以允许的前提下, 选择ResNet作为神经网络区分器模型对于区分器的精度的提升是有效的. 而对于SPECK32的差分区分器, CNN模型在考虑时间与模型精度上均胜于ResNet, 也即对于SPECK32的差分区分器来说, 首要应该选择CNN模型. 同时, 根据第2.2节与第2.3节中差分区分器的训练过程中验证集的精度的变化, 我们发现CNN模型与ResNet模型并未出现过拟合的现象, 而且精度在最初30次迭代中已经达到最高点. 这也启示我们, 可通过减少迭代来降低训练的时间花销.
|
|
表 5 CNN与ResNet的对比 |
3 神经网络差分区分器的参数选择建议
不同的神经网络模型针对相同的数据集训练出的模型的精度会有所不同, 而在相同的神经网络模型中,由于网络超参数的设置, 也会导致训练出的模型精度有所不同. 在卷积神经网络模型及其各种优化版本中, 卷积层的数量会直接影响模型的精度. 一般认为: 在没有过拟合现象出现时, 对数据集进行越多的运算, 数据集的特征被模型学到的越多, 也就意味着模型的精度越高. 在深度学习中, 有时会通过增加卷积层等运算层的个数提高模型的精度.
为了研究神经网络在构造差分区分器中超参数选取对模型精度的影响, 我们分别增加了CNN模型与ResNet模型的卷积层数与残差块数. 将图4中相同卷积层的层数增加到10层, 将图7 所示的残差块的个数增加到10个, 并对7轮SPECK32差分区分器和8轮SIMON32差分区分器进行训练.
3.1 改变网络结构对区分器精度的影响首先针对SPECK32的7轮差分区分器进行研究. 通过改变CNN和ResNet模型中卷积层和残差块的个数训练差分区分器, 将训练过程中模型对验证集判断的精度变化绘制如图10. 其中, 横坐标依然代表着训练过程的迭代次数, 纵坐标表示精度. 图例中, CNN5, CNN10分别代表只有5层相同卷积层的CNN模型与10层相同卷积层的CNN模型, 而ResNet5, ResNet10分别代表5个残差块的ResNet模型与10个残差块的ResNet模型. 我们从图10中可以看出: 对于SPECK32的7轮差分区分器, 虽然增加了模型的深度对数据进行了更多的计算去提取特征, 但是模型在验证集上的精度并没有因此而上升, 反而有所下降. 当我们使用Keras中的evaluate函数评估模型的精度时, 当使用5层卷积层时, 其精度大约为60.8%; 但是当使用10层卷积层时, 其精度只能保持在50%左右. 而构造区分器的问题本质上是二分类问题, 因此, 使用10层卷积层构造的CNN模型所训练得到的区分器在分类问题上是失败的, 其无法有效地对数据进行区分. 同时, 考虑ResNet5与ResNet10的精度, 我们发现相较于ResNet5的精度, ResNet10的精度也有所下降.
同样基于CNN5, CNN10, ResNet5和ResNet10这4种模型训练了8轮的SIMON32的差分区分器, 发现: 类似于这4种模型对SPECK32的差分区分器的影响, 增加卷积层层数和残差块个数都会使得区分器的精度有所下降.
如图11, 横坐标依然代表着训练过程的迭代次数, 纵坐标表示模型对于验证集判断的精度. 图例中CNN5, CNN10, ResNet5, ResNet10分别代表只有5层相同卷积层的CNN模型与10层相同卷积层的CNN模型以及有5个残差块的ResNet模型与10个残差块的ResNet模型. 从图11中可以看出, CNN5与ResNet5面对验证集的精度都远远高于CNN10和ResNet10. 使用Keras的evaluate函数对模型进行评估, 我们发现对于未知数据, 选择CNN5和ResNet5进行判别的精度大约为74%, 而ResNet10的精度大约为73%, CNN10的精度不足70%.
|
图 10 SPECK32不同参数的训练 |
|
图 11 SIMON32不同参数的训练 |
同时, 在深度学习训练过程中, 增加卷积层的个数会增加训练的时间花销. 我们在GTX1080的显卡上进行差分区分器的训练时, 在CNN模型中, CNN5的时间花销大约为CNN10的一半; 在ResNet模型中也有相似的结论, ResNet5的时间开销大约为ResNet10的一半. 这也就意味着: 增加卷积层数或者残差块数加大了训练过程的时间开销, 而精度却没有上升反而有所下降.
3.2 分析与建议在密码分析中, 时间复杂度与存储复杂度都是需要考虑的内容. 有时需要使用时空折中技术, 通过以时间换空间或者以空间换时间完成对密码的分析. 在通过深度学习技术构造差分区分器时, 我们需要考虑的内容是模型的精度与训练时间开销的折中. 根据不同的研究目标, 我们通常会选择增加运算内容, 加大时间开销, 从而提高模型的精度. 或者在精度要求较低时, 通过减少训练中的计算从而降低时间开销. 在基于CNN模型或ResNet模型构造差分区分器时, 我们已经发现: 增加卷积层数和残差块数虽然增加了时间开销, 但是对于精度的提升是无效的. 我们在通过深度学习技术构造差分区分器时, 需要考虑训练的花销及模型精度对后续密码分析的影响. 通过CNN5模型构造的SIMON32的区分器与SPECK32的区分器与ResNet5构造的区分器的精度相差在4%以内, CNN5时间开销在GTX1080上仅需要68 s, 而ResNet5的时间花销却大约为110 s.
针对SIMON32和SPECK32两种轻量级分组算法, 通过CNN就可构造得到模型精度符合密码分析要求的区分器, 而无须再通过ResNet模型构造差分区分器. 但是ResNet模型由于其独特的残差块设计, 可使模型的深度增加而不会使得梯度消失. 因此, ResNet在训练深度较深的区分器时是有优势的.
综合考虑, 面对轻量级分组密码算法的差分区分器, 可预先通过CNN模型进行快速地训练, 若CNN模型训练得到的区分器的精度已经满足后续密码分析的要求, 便可快速对密码进行分析. 而若CNN模型并不能满足密码分析的要求, 可通过尝试ResNet等神经网络模型训练神经网络区分器. 在设备与时间受限的情况下, CNN模型应是进行基于深度学习技术构造差分区分器的首要选择. 同时, 我们也发现: 由于基于深度学习技术构造差分区分器所使用的数据集较为简单, 不像图像或者语音中使用的数据那样复杂, 构造差分区分器的网络模型无须太多的层数已可得到一个较好的结果. 因此, 在使用深度学习技术构造差分区分器时, 应以少层数的模型为主, 这样也可以降低训练的时间花销.
4 总结与未来工作本文深入研究了基于深度学习的差分区分器的构造及网络模型参数对其的影响. 首先描述了基于深度学习的差分区分器的构造方法, 而后, 基于CNN模型与ResNet模型训练了神经网络差分区分器, 并对两种方法训练的差分区分器进行了比较. 最后, 给出了训练神经网络差分区分器的参数选择建议. 我们在实验过程中发现, 不同的网络模型对密码算法的差分区分器的训练效果是不一样的. 在我们构造的CNN模型与ResNet模型中, CNN模型的训练时间开销更少而精度与ResNet模型的精度相当. 由于差分区分器的构造过程在密码分析中属于预计算过程, 其一旦训练完成, 在之后的密码分析中将可以一直使用. 因此, 即使在前期花费大量的时间训练神经网络差分区分器去提高区分器的精度, 对密码分析也是有效的. 但是预训练时间过长,依然不利于对分组密码算法的研究. 同时我们发现: 增加网络模型中的卷积运算, 并不能有效提高模型的精度. 我们在实验中发现: 增加卷积层数和残差块数会导致差分区分器模型的精度下降, 从而无法对数据进行有效的区分, 最终导致实验失败. 因此, 若精度的提升不足以大幅度降低密码分析的复杂度, 通过适当地减少卷积操作从而减少训练的时间, 也将提高密码分析的效率. 我们在实验过程中也发现, 输入差分的选择将会影响神经网络差分区分器的精度. 目前, 我们正在研究输入差分对神经网络差分区分器精度的影响, 从传统的差分分析方法角度分析差分对神经网络差分区分器的影响.
| [1] |
Zhang ZK, Pang WG, Xie WJ, Lü MS, Wang Y. Deep learning for real-time applications: A survey. Ruan Jian Xue Bao/Journal of Software, 2020, 31(9): 2654−2677 (in Chinese with English abstract). http://www.jos.org.cn/1000-9825/5946.htm
|
| [2] |
McCulloch WS, Pitts W. A logical calculus of the ideas immanent in nervous activity. The Bulletin of Mathematical Biophysics, 1943, 52(1−2): 115−133.
|
| [3] |
Rosenblatt F. The perceptron: A probabilistic model for information storage and organization in the brain. Psychological Review, 1958, 65(6): 386-408.
[doi:10.1037/h0042519] |
| [4] |
Rumelhart DE, Hinton GE, Williams RJ. Learning representations by back-propagating errors. Nature, 1986, 323(6088): 533-536.
[doi:10.1038/323533a0] |
| [5] |
Lawrence S, Giles CL, Tsoi AC, Back AD. Face recognition: A convolutional neural-network approach. IEEE Trans. on Neural Networks, 1997, 8(1): 98-113.
[doi:10.1109/72.554195] |
| [6] |
Williams RJ, Zipser D. A learning algorithm for continually running fully recurrent neural networks. Neural Computation, 1989, 1(2): 270-280.
[doi:10.1162/neco.1989.1.2.270] |
| [7] |
Hinton GE, Osindero S, Teh YW. A fast learning algorithm for deep belief nets. Neural Computation, 2006, 18(7): 1527-1554.
[doi:10.1162/neco.2006.18.7.1527] |
| [8] |
Glorot X, Bordes A, Bengio Y. Deep sparse rectifier neural networks. Journal of Machine Learning Research, 2011, 15: 315-323.
|
| [9] |
Gohr A. Improving attacks on round-reduced speck32/64 using deep learning. In: Boldyreva A, Micciancio D, eds. Advances in Cryptology. Cham: Springer, 2019. 150−179.
|
| [10] |
Beaulieu R, Treatman-Clark S, Shors D, Weeks B, Smith J, Wingers L. The SIMON and SPECK lightweight block ciphers. In: Proc. of the 52nd ACM/EDAC/IEEE Design Automation Conf. San Francisco: IEEE, 2015. 1−6.
|
| [11] |
Biham E, Shamir A. Differential cryptanalysis of DES-like cryptosystems. Journal of Cryptology, 1991, 4(1): 3-72.
[doi:10.1007/BF00630563] |
| [12] |
Sun SW, Hu L, Wang P, Qiao KX, Ma XS, Song L. Automatic security evaluation and (related-key) differential characteristic search: Application to SIMON, PRESENT, LBlock, DES(L) and other bit-oriented block ciphers. In: Sarkar P, Iwata T, eds. Advances in Cryptology. Berlin: Springer, 2014. 158−178.
|
| [13] |
Baksi A, Breier J, Chen Y, Dong XY. Machine learning assisted differential distinguishers for lightweight ciphers. In: Proc. of the 2021 Design, Automation & Test in Europe Conf. & Exhibition (DATE). Grenoble: IEEE, 2021. 176−181.
|
| [14] |
He KM, Zhang XY, Ren SQ, Sun J. Deep residual learning for image recognition. In: Proc. of the IEEE Conf. on Computer Vision and Pattern Recognition. Las Vegas: IEEE, 2016. 770−778.
|
| [15] |
Abed F, List E, Lucks S, Wenzel J. Differential cryptanalysis of round-reduced simon and speck. In: Proc. of the 21st Int’l Workshop on Fast Software Encryption. London: Springer, 2015. 525−545.
|
| [16] |
Ramasubramanian K, Singh A. Deep learning using keras and TensorFlow. In: Ramasubramanian K, Singh A, eds. Machine Learning Using R. Berkeley: Apress, 2019. 667−688.
|
| [17] |
Bergstra J, Komer B, Eliasmith C, Yamins D, Cox DD. Hyperopt: A python library for model selection and hyperparameter optimization. Computational Science & Discovery, 2015, 8(1): 014008.
[doi:10.1088/1749-4699/8/1/014008] |
| [18] |
Kölbl S, Leander G, Tiessen T. Observations on the SIMON block cipher family. In: Gennaro R, Robshaw M, eds. Advances in Cryptology. Berlin: Springer, 2015. 161−185.
|
| [19] |
De Moura L, Bjørner N. Z3: An efficient SMT solver. In: Ramakrishnan CR, Rehof J, eds. Tools and Algorithms for the Construction and Analysis of Systems. Berlin: Springer, 2008. 337−340.
|
| [20] |
Li C, Sun B, Li RL. Attack Method and Case Analysis of Block Cipher. Beijing: Science China Press, 2010. 64−72 (in Chinese).
|
| [1] |
张政馗, 庞为光, 谢文静, 吕鸣松, 王义. 面向实时应用的深度学习研究综述. 软件学报, 2020, 31(9): 2654−2677. http://www.jos.org.cn/1000-9825/5946.htm
|
| [20] |
李超, 孙兵, 李瑞林. 分组密码的攻击方法与实例分析. 北京: 科学出版社, 2010. 64−72.
|