SLIM算法的9轮不可能差分分析_郑会超.pdf

第 30 卷 第 4 期北京电子科技学院学报2022 年 12 月Vol.30 No.4Journal of Beijing Electronic Science and Technology InstituteDec.2022SLIM 算法的 9 轮不可能差分分析郑会超 魏锦鹏北京电子科技学院,北京市 100070摘 要:近年来,随着射频识别(RFID)技术和无线传感器网络(WSN)的迅速发展,低功耗设备在生活中有了广泛的应用。轻量级分组密码具有效率高、功耗低、资源需求少等优点,便于在硬件和软件上实现。因此,它可以为物联网和资源受限环境提供安全保障。SLIM 算法是 Aboushosha等人在 2020 年提出的一种新的轻量级分组密码。本文采用不可能差分攻击对 SLIM 算法的安全性进行分析。首先,根据 SLIM 算法的结构特征,构造一条 6 轮不可能差分路径。然后,在不可能差分路径的基础上添加 1 轮前置路径和 2 轮后置路径,对 9 轮 SLIM 算法进行不可能差分攻击。研究结果表明:攻击 9 轮 SLIM 算法所需的数据复杂度约为 229选择明文数据量,所需的时间复杂度约为 255.83次 9 轮 SLIM 加密。关键词:SLIM;不可能差分;区分器中图分类号:TP309 文献标识码:A文章编号:1672-464X(2022)4-48-53 作者简介:郑会超(1995-),男,硕士研究生,研究方向:分组密码的不可能差分分析。E-mail:3499394988 魏锦鹏(1995-),男,硕士研究生,研究方向:分组密码的安全性研究。引言 分组密码是最成熟的密码分支之一,具有速度快、易于标准化和便于软硬件实现等特点,是一种非常重要的加密方案。分组密码作为信息与网络安全中实现数据加密、消息鉴别及密钥管理的核心密码算法,在计算机通信和信息系统安全领域有着广泛的应用。近年来,随着物联网的发展,无线传感器网络(WSN)和无线射频技术(RFID)的应用越来越广泛,它们具有硬件制造、维护成本低,网络健壮性、自组织性强,适用性广泛的特点,已成为物联网应用的关键组成部分。WSN 和 RFID 基于无线网络传输信息,攻击者更加容易获得、干扰甚至破坏信息传输。由于物联网上使用的微型计算设备计算能力有限,人们开始越来越关注轻量级分组密码算法的研究来保证信息的安全1。轻量级分组密码算法作为一种特殊的分组密码算法,它们在硬件实现、加密速度、运行功耗等方面与 AES 等传统分密码相比有明显的优势,更适合物联网微型计算设备使用。在这种情况下,大量轻量级分组密码算法被研究出来,其中比较典型的有 Lblock2,LED3,PRESENT4,SIMON5,Midori6,SKINNY7,HIGHT8,SIMECK9等。一个密码算法能够被广泛应用不仅应具有较高的实现效率,更重要的是保证算法的安全性。然而,密码设计者在设计密码算法过程中,有时会追求高效性导致安全性降低,因此,采用多种密码分析方法去分析算法的安全性是很有必要的。目前轻量级分组密码分析方法主要包第 30 卷SLIM 算法的 9 轮不可能差分分析 括线 性 分 析10、差 分 分 析11、截 断 差 分 分析12、不可能差分分析13、积分分析14、相关密钥分析15、Biclique 分析16等。2020 年,Aboushosha 等人提出了一个新的轻量级分组密码 SLIM17。Aboushosha 等人表明,SLIM 算法能有效抵抗差分分析和线性分析,并给出了 7 轮差分路径和 11 轮线性路径。目前还没有文献对 SLIM 算法进行不可能差分分析,本文试图对 SLIM 算法进行不可能差分分析,以进一步评估其安全性。本文充分利用了 SLIM算法轮函数的具体细节,特别是挖掘非线性组件S 盒的差分性质,并结合 P 置换设计,利用差分方程求解的方法构造出 SLIM 算法的 6 轮不可能差分区分器。进一步,本文利用构造的区分器攻击了 9 轮 SLIM 算法,攻击的数据复杂度为 229个选择明文,时间复杂度为 255.83次 9 轮加密。1 SLIM 算法简介1.1 SLIM 算法的整体框架SLIM 算法整体采用 Feistel 结构,轮函数采用类似于 PRESENT 算法的 SP 结构,其中 S 盒为 4 比特,P 置换采用 16 比特的比特拉线设计。SLIM 算法的分组长度为32 比特,密钥长度为80比特,算法总轮数为 32 轮。该算法的整体加密流程如图 1 所示。在加密时,将 32 比特的分组数据分为左右各 16 比特,即左支 Li和右支 Ri均为 16 比特。若一轮迭代的输入为(Li,Ri),输出为(Li+1,Ri+1),则有:Li+1=Ri;Ri+1=LiF(Ri,Ki),其中,Ki表示第 i 轮的轮密钥,F 表示轮函数。1.2 SLIM 算法的轮函数SLIM 算法轮函数 F 的加密流程由轮密钥加、S 层和 P 置换 3 部分组成,如图 2 所示。轮密钥加:分组加密数据的右支 Ri与第 i轮的轮密钥 Ki进行逐比特异或。S 层:由 4 个相同的 4 比特 S 盒并行加密,SLIM 算 法 中 的 4 比 特 S 盒 与 国 际 标 准图 1 SLIM 算法的加密流程图 2 SLIM 算法轮函数 F 的加密流程PRESENT 算法的 S 盒相同,如表 1 所列。表 1 SLIM 算法的 S 盒x0123456789ABCDEFSC56B90AD3EF84712P 置换:按照比特拉线设计,即 16 比特数据按照表 2 的规律进行比特置换。在表 2 中,输入的第 i 比特经过 P 置换后变为第 P(i)比特。表 2 SLIM 算法的 P 置换x0123456789ABCDEFP7D18BE254AF0369C在研究不可能差分区分器的构造时,由于轮密钥不影响差分的传播,因此本文不详细介绍SLIM 的密钥扩展算法,具体细节见文献17。94北京电子科技学院学报2022 年2 SLIM 算法的 6 轮不可能差分区分器 构造尽可能长的不可能差分区分器是不可能差分分析的核心。本节首先挖掘 SLIM 算法 S盒的具体细节,给出一个关于 S 盒的差分性质;然后利用该性质,结合 P 置换的加密流程,构造出 SLIM 算法的一条 6 轮不可能差分区分器。根据表 1 给出的 SLIM 算法的 S 盒,利用 python编程搜索 S 盒的差分分布表,如表 3 所示。表 3 SLIM 算法 S 盒的差分分布表0123456789ABCDEF0&000000000000000100040004040004002000204200020222030202204200220000400000422022020205020020000222420060020002020042004704200020200020048000200020204020490020402020002040A0022040020200220B0200200042220200C0020040222200020D0242200200220000E0022002222002200F0400400000000044 注:&表示数字 16在表 3 中,第 1 列为 S 盒的输入差分,第 1行为 S 盒的输出差分,输入与输出差分均用 16进制表示,中间的值为该输入输出差分方程对应的解的个数。例如,当 S 盒的输入差分为 0 x2时,输出差分为 0 x3 时,满足该差分方程的解的个数为 2。注意当解的个数为 0 时,说明该输入差分和输出差分不匹配,即该输入差分经过 S 盒后不能传播到该输出差分。通过观察 SLIM 算法 S 盒的差分分布表,容易得到如下性质。性质 1对于 SLIM 算法的 S 盒,当输入差分分别为 0 x1,0 x8,0 x9 时,经过 S 盒后输出差分分别为 1,1 和 0,以概率 1 成立。其中表示该比特差分可能为 0 也可能为 1。证明 以 0 x8 1 为例进行分析。根据表 3,当输入差分为 0 x8 时,输出差分可能为0 x3,0 x7,0 x9,0 xB,0 xD,0 xF,则输出差分前 3 比特 0 或 1 均能够出现,但是最低比特差分一定为1,即输出差分的形式为 1。因此,0 x8 1 以概率 1 成立。类似地,可以说明 0 x1 1和 0 x9 0 以概率 1 成立。下面利用性质1 并结合 P 置换的特点,给出定理 1。定理 1在 SLIM 算法中,当输入差分为(X,016),输出差分为(016,Y)时,(X,016)(016,Y)是 SLIM 算法的一条 6 轮不可能差分区分器,如图 3 所示。其中 X 满足(12|1000),Y 满足(012|1000),i表示连续 i 个,0i表示连续 i 个 0。“”表示比特串之间的连接。证明 首先从正向加密开始计算,正向输入差分为(X,016),经过 1 轮加密后输出差分为(016,X),经过 2 轮加密后输出差分为(X,F(X),经过 3 轮加密后输出差分的左分支为F(X),计算结果如表 4 所示。表 4 输入差分 X 的加密X ,1000F(X),1 然后从逆向进行运算,逆向的输出差分为(016,Y),由于 SLIM 算法结构为 Feistel 型,加解密运算是相同的,所以逆向解密运算的轮函数与正向加密的轮函数相同。输出差分经过 1 轮解密后,输出差分仍为(016,Y),经过 2 轮解密后输出差分为(Y,F(Y),经过 3 轮解密后输出差分右分支为 F2(Y)Y。计算结果如表 5 所示。表 5 输出差分 Y 的解密Y0000,0000,0000,1000F(Y)000,000,000,1000F2(Y),1 F2(Y)Y ,0 05第 30 卷SLIM 算法的 9 轮不可能差分分析 由图 3 可知,需要对比正向加密 3 轮的输出差分左分支与逆向解密 3 轮的输出差分的右分支,即需要对比 F(X)与 F2(Y)Y 的值,由表4 和表 5 容易看出二者之间存在矛盾,故(X,016)(016,Y)是 SLIM 算法的一条 6 轮不可能差分区分器,定理 1 成立。图 3 SLIM 算法 6 轮不可能差分区分器3 SLIM 算法的 9 轮密钥恢复攻击 本节在上节构造的 6 轮不可能差分区分器的基础上,添加 1 轮前置路径和 2 轮后置路径,对 SLIM 算法进行9 轮不可能差分攻击。图4 为攻击 9 轮 SLIM 算法的示意图。步骤 1 选取一个结构,在该结构内任意选择两个明文进行异或,它们的差分需要满足如下形 式:(,1 ,1000)。该结构能够提供 227个明文和 253组明文对。步骤 2 选择 2n个上述结构,则这些结构总共能提供2n+27个明文和2n+53组明文对。选择密文差分满足以下形式的密文对留下:(000,00图 4 SLIM 算法 9 轮不可能差分攻击0,000,1000,0 ),保留下来的明密文对数目约为 2n+53 2-14=2n+39。步骤 3 对于保留下来的明密文对,猜测最后一轮的轮密钥 K9的全部 16 比特密钥,即 K915 K90,使得关于 4 个 S 盒的差分方程都成立。在平均意义下,每 4 个比特通过 S 盒使差分方程成立的概率约为 2-4,则 4 个差分方程同时成立的概率为 2-44。因此,经过步骤 3 后剩余明密文对的数目约为 2n+39 2-16=2n+23。步骤 4 对于剩余的明密文对,猜测第 8 轮的轮密钥 K8的低 4 比特密钥,即 K83 K80,使得关于最右边 S 盒的差分方程成立,差分方程成立的概率约为 2-4。因此,经过步骤 4 后剩余明密文对的数目约为 2n+23 2-4=2n+19。步骤 5对于经过上述步骤处理的剩余明密文对,猜测第 1 轮的轮密钥 K1的全部 16 比特密钥,即 K115 K10,若关于 4 个 S 盒的差分方程都成立,则筛除步骤 3 到步骤 5 中猜测的 36 比特密钥。15北京电子科技学院学报2022 年当猜测的 3