改进的SMBA 算法不可能差分分析*

李艳俊, 李寅霜, 汪 振, 刘 健

1.中国电子科技集团公司第十五研究所, 北京100191

2.桂林电子科技大学 广西密码学与信息安全重点实验室, 桂林541004

3.北京电子科技学院, 北京100070

1 引言

2018 年中国密码学会举办全国密码设计竞赛, 分组密码方向收到30 余项参赛算法, 经过两轮评估,2020 年1 月公布了最终入选算法1https://www.cacrnet.org.cn/site/content/854.html.SMBA[1]成为胜出的10 个算法之一, 设计者给出了较为清晰的安全界, 有效评估了算法抵抗差分攻击、线性攻击、不可能差分攻击、积分攻击等已知攻击的强度, 其中根据基于字的自动化搜索工具给出了SMBA-128 的5 轮不可能差分路径和SMBA-256 的1 条8 轮不可能差分路径.目前自动化搜索工具与理论推导方法相比速度快且效率高[2–4], 但是初始建模阶段非常重要, 建立模型不完善或者不正确都会导致最终搜索结果出错或者不充分.此外, 基于比特进行自动化搜索时, 若分组长度较大或者非线性部件规模较大(如8×8 的S 盒), 则搜索的效率会急速降低.所以自动化搜索工具有其自身的局限性, 需要结合理论证明相互补充.

不可能差分分析方法[5]自1999 年Biham 于欧密会上提出之后, 被广泛运用于各种结构分组密码算法的安全性评估中[6–10], 分析效果较为突出.寻找不可能差分区分器是不可能差分分析的关键步骤, 一般采用的是中间相遇产生矛盾的方法, 即采用相反方向概率为1 的两条截断差分路径, 使之无法相遇, 由此构建概率为0 的差分区分器.对于轮函数F为随机置换的Feistel 结构算法, 1998 年Knudsen 证明至少存在5 轮不可能差分区分器[11], 但是实际中F函数无法做到真随机, 所以基于Feistel 结构设计的算法往往存在大于5 轮的不可能差分区分器, 如2007 年Shirai 等对CLEFIA 首次提出的9 轮不可能差分区分器[12], 2007 年Wu 等人对Camellia 提出的8 轮不可能差分区分器[13]等.同样, 对于SMBA 算法,其轮函数F不满足随机函数所有性质, 所以可能存在大于5 轮的不可能差分区分器.

本文对SMBA-128 算法进行了6 轮不可能差分区分器的推导和证明, 基于此区分器结合提前抛弃技术, 首次给出了9 轮密钥恢复攻击, 攻击的数据复杂度和时间复杂度分别为2104.2和2121; 同理, 对SMBA-256 找到8 轮不可能差分区分器, 12 轮密钥恢复攻击过程类似于SMBA-12, 攻击的数据复杂度和时间复杂度分别为2248.2和2227.6.与设计者提出的结果相比, 如表1 所示.

表1 SMBA 不可能差分分析攻击结果比较Table 1 Comparison of SMBA impossible differential analysis attack results

2 SMBA 算法简介

SMBA 算法基于广义Feistel 结构设计, 创新性在于融合了SP、Feistel 和MISTY 三种结构, 分组长度支持128 比特和256 比特, 密钥长度支持128 比特和256 比特, 算法分组长度和密钥长度对应的迭代轮数如表2 所示.

表2 SMBA 算法的三个版本和迭代轮数Table 2 Three versions of SMBA algorithm and number of iteration rounds

2.1 符号说明

2.2 加密变换

SMBA 算法的轮函数F采用Li −S −Pi结构,i=64,128, 即先进行拉线变换Pi, 再按字节查询S盒, 最后进行线性变换Li.SMBA-128 使用拉线变换P64和线性变换L64(如图1 所示), SMBA-256 使用拉线变换P128和线性变换L128(如图2 所示).

图1 SMBA-128 的轮函数Figure 1 Round function of SMBA-128

图2 SMBA-256 的轮函数Figure 2 Round function of SMBA-256

图3 SMBA-128 的密钥扩展过程Figure 3 SMBA-128 key expansion process

P64是一个64 比特到64 比特的变换, 具体是将64 比特数划分为8 个字节, 即x=x0‖x1‖···‖x7,令yi=xτ(i), 其中当0≤i ≤7 时,τ(i) 依次是: 3,4,5,6,0,1,2,7.P128是一个128 比特到128 比特的变换, 具体是将128 比特数划分为16 个字节, 即x=x0‖x1‖···‖x15, 令yi=xπ(i), 其中当0≤i ≤15时,τ(i) 依次是: 3,4,5,6,10,11,12,13,8,9,14,15,0,1,2,7.

L32是32 比特到32 比特的线性变换, 具体为是将32 比特输入X分为4 个字节, 即X=x0‖x1‖x2‖x3, 令

则得到输出L32(X)=y0‖y1‖y2‖y3.L64含2 个L32, 是64 比特到64 比特的变换, 具体是将64 比特数分为2 个32 比特数, 即X=XH‖XL, 令

则L64(X0‖X1)=Y0‖Y1.L128含2 个L64, 是一个128 比特到128 比特的变换, 具体是将128 比特数分为2 个64 比特数, 经过两次L64后合并得到128 比特输出.

2.3 密钥扩展

密钥扩展算法基于广义Feistel 结构设计, 由主密钥Key 生成N个大小为BL/2 的加密子密钥RKi,其中0≤i ≤N −1,N为加密轮数, BL 为分组长度.下面以算法1 SMBA-128 子密钥生成算法为例介绍子密钥生成.

算法1 SMBA-128 子密钥生成算法1 U0 = MSB64(Key), V0 = LSB64(Key), 其中MSBt(x) 由x 的最左(即最高) t 比特组成的t 比特数; LSBt(x)由x 的最右(即最低) t 比特组成的t 比特数.2 D = N‖BlockLen‖KeyLen‖040, BlockLen = BL/8 为分组长度, KeyLen = BL/8 为密钥长度, N、BlockLen、KeyLen 都用8 比特表示.3 C0 = MSB64(C)⊕D;4 进行N 个密钥扩展轮变换(如图3 所示), 即for i = 0 到N −1 do 5 Xi = Ui ⊕Ci;6 Yi = α64(Xi);7 Zi = γ64(Yi);8 EKi = DKN−i−1 = Zi;9 Ui+1 = Zi ⊕Vi;10 Vi+1 = β64(Ui);11 Ci+1 = Ci ≪23;12 end

常数C为自然对数的底e的小数部分的前 128 比特, 用 16 进制表示为C= 0xb7e15162,0x8aed2a6a, 0xbf715880, 0x9cf4f3c7.

变换α、β、γ对SMBA-128 来说, 使用α64、β64、γ64.α64、β64、γ64都是64 比特到64 比特的变换, 分别如下:

(1)α64是换位变换.把64 比特数x分为8 个8 比特数xi, 其中0≤i ≤7, 即x=x0‖x1‖···‖x7.令α64(x)=xψ(i), 其中当0≤i ≤7 时,ψ(i) 依次是: 2,7,1,4,6,3,5,0.

(2)β64是循环左移16 比特, 即β64(x)=x≪16.

(3)γ64是S 盒变换.把64 比特数x分为8 个8 比特数xi, 其中0≤i ≤7, 即x=x0‖x1‖···‖x7.γ64(x)=Simod2(xi).

SMBA-256 的密钥生成与SMBA-128 类似, 有兴趣者可以参考算法设计文档[1].

2.4 等价结构

在SMBA-128 算法结构中, 函数F=P64◦S ◦L64, 进一步我们将整体结构进行了等价变换, 即图4(a) 和图4(b) 等价.

图4 等价结构Figure 4 Equivalent structure

这是因为图4(a) 中

而图4(b) 中

所以二者等价.

将函数F中拉线操作P64和线性变换L64的复合表示为P, 即P=L64◦P64, 函数F就是一个SP结构.不失一般性, 在之后的不可能差分区分器构建和密钥恢复攻击中我们忽略结构两端的置换操作P64和.

3 SMBA-128 的不可能差分分析

本节通过分析SMBA-128 算法整体和轮函数结构, 推导并证明了SMBA-128 至少存在6 轮不可能差分区分器, 最后进行了9 轮密钥恢复攻击, 数据复杂度和时间复杂度分别为2104.2和2121.

3.1 SMBA-128 的6 轮不可能差分区分器

证明: 此处采用反证法, 即如果不存在6 轮不可能差分区分器, 那么如图5 所示, 在第4 轮和第5 轮之间的⋆处将有ΔY ⊕P{S{P[S(ΔY)]}}=P[S(ΔX)] 成立, 我们对等式两边进行P−1变换之后为:

P−1ΔY=S(ΔX)⊕S{P[S(ΔY)]}.

第一步, 取ΔY= 0000 000b, 那么P[S(ΔY)] =P(0000 000a) =P64[L64(0000 000a)], 其中字节a=S1(b)̸=0, 此处a和b都指的是差分值.

L64(0000 000a) = [(L32(0000)⊕L32(000a) ≪9)⊕L32(0000)]‖[(L32(0000)⊕L32(000a) ≪9)⊕L32(000a)].

由L32的性质知,L32(0000) = (0000),L32(000a) = (aa0a), 故L64(0000 000a) = [((aa0a) ≪9)]‖[((aa0a) ≪9)⊕(aa0a)].设非零差分字节a= (x1x2···x8), 得(aa0a) ≪9 = (x2x3···x80;0000 000x1;x2x3···x8x1;x2x3···x8x1), 然后得

遍历a=(x1x2···x8), 得到P[S(ΔY)] 全部取值, 进而得到S{P[S(ΔY)]}全部取值:

(1) 当x1=0 时,x2x3···x8不可能同时为0, 此时S{P[S(ΔY)]}=(*****0**);

(2) 当x1=x2=···=x8=1,S{P[S(ΔY)]}=(*******0);

(3) 当x1=1,x2=x3=···=x8=0,S{P[S(ΔY)]}=(****0***);

(4) 其他情况, 易知S{P[S(ΔY)]}=(********).

仅考虑b的最高位比特y1是0 的情形, 容易得到L−164[P−164(0000 000b)] = (***0 ****).我们发现P−1(ΔY) 出现差分为0 的位置是第4 字节, 而在这个位置处S{P[S(ΔY)]}⊕S(ΔX) 的差分不可能为0, 故出现矛盾, 即P−1(ΔY)̸=S{P[S(ΔY)]}⊕S(ΔX), 也即(ΔY)⊕P{S{P[S(ΔY)]}}̸=P[S(ΔX)].

综上所述, SMBA-128 存在6 轮不可能差分区分器, 输入输出为[0000**0*0000 0000]→[0000 000b0000 0000], 其中“*” 为非0 字节,b为最高比特为1 的非0 字节.同理可证[0000 000b0000 0000]→[0000**0*0000 0000] 也为6 轮不可能差分区分器, 符号“*” 与b满足的条件同上.

3.2 SMBA-128 的9 轮密钥恢复攻击

选取6 轮不可能差分区分器的输入差分为[0000 **0* 0000 0000], “*” 表示任意非零字节, “?” 表示任意字节, 输出差分为[0000 000b0000 0000],b的最高比特为0 其余7 比特任意非零.在区分器之前加1 轮, 之后加2 轮, 如图6 所示, 可以进行9 轮恢复密钥攻击.

图6 SMBA-128 的9 轮密钥恢复攻击Figure 6 Attack on SMBA-128

攻击步骤如下:

(1) 选择2n个明文结构, 每个差分的结构形式: ΔX0=P(0000 **0*), ΔX1= (0000 **0*), 每个“*” 位可选择28−1 个值, 共组成约2n+95个明文对, 对这些明文进行9 轮加密, 得到相应的2n+95密文对.

(2) 在得到的2n+95个密文对中, 选择满足差分结构形式为ΔX9=P(0000 000*), ΔX10= (????????), 筛选后剩下密文对2n+95−56=2n+39.

(3) 根据P[S(X9⊕RK9)]⊕X10=X8, 有S(X9⊕RK9)⊕P−1[X10] =P−1[X8], 先猜测16 比特RK9, 再分步猜RK9剩余的每个密钥字节, 解密计算密文对是否符合P−1[X8] 对应的差分, 筛选后剩下2n+39−57=2n−18密文对.

(4) 猜测RK8的1 个字节值, 计算P[S(X8⊕RK8)]⊕X9⊕P[S(X′8⊕RK8)]⊕X′9, 判断是否符合ΔX7, 筛选后剩下2n−18−8=2n−26密文对.

(5) 分步猜测RK1的3 个字节值, 计算P[S(X1⊕RK1)]⊕P[S(X′1⊕RK1)] 是否符合差分P(0000**0*), 若符合, 则抛弃对应密钥.

(6) 重复上述(1)–(5) 步骤, 直到剩下唯一正确的密钥.

上述攻击中错误密钥被留下的概率为(1−2−24)2n−26, 上述一共猜测了96 比特的密钥值, 故留下(296−1)×(1−2−24)2n−26个错误密钥.取n=56.2 时, (296−1)×(1−2−24)2n−26＜2−4, 可认为错误密钥全部被淘汰.此时攻击的数据复杂度为248×256.2= 2104.2个选择明文; 假设每进行8 次S 盒查询的时间与加密一轮SMBA-128 算法等价, 整个9 轮密钥恢复攻击过程采用了提前抛弃技术[14], 时间复杂度是(216×(296.2+28×(288.2+28×(280.2+28×(272.2+28×(264.2+28×(256.2+28×(248.2+28×(239.2+224×231.2)))))))))÷72≈2121次9 轮加密.

4 SMBA-256 的不可能差分分析

相较于SMBA-128, SMBA-256 拉线变换更复杂, 并且线性部分使用了L128, 但是二者整体结构类似, 按照相似的方法可以证明SMBA-256 至少存在8 轮不可能差分区分器.选取8 轮不可能差分区分器的输入差分[0000 0000 0000 *000 0000 0000 0000 0000], 输出差分为[0000 0000 0000 0000 0000 0000 0000 0*00] (其中“*” 为任意非零字节); 基于此不可能差分区分器向前加两轮、向后加两轮, 如图7 所示, 进行12 轮密钥恢复攻击.其中X11,[13]表示X11的第13 个字节, RK12,[4,5,6,7,8,9,10,11]表示RK12的第4,5,6,7,8,9,10,11 个字节.

图7 SMBA-256 的12 轮密钥恢复攻击Figure 7 Attack on SMBA-256

攻击步骤如下:

(1) 选择2n个明文结构, 每个差分的结构形式: ΔX0=P(0000 ???? ???? ?000), ΔX1=P(0000 0000 0000 *000), 每个“*” 位可选择28−1 个值, 每个“?” 位可选择28个值, 共组成约2n+159个明文对, 对这些明文进行12 轮加密, 得到相应的2n+159密文对.

(2) 在得到的2n+159个密文对中, 选择满足差分结构形式为ΔX12=P(0000 0000 0000 0*00),ΔX13=P(0000 ???? ???? 0000)⊕(0000 0000 0000 0*00), 筛选后剩下密文对2n+159−8×22=2n−17.

(3) 猜测RK12,[4,5,6,7,8,9,10,11]8 个字节, 根据P[S(X12⊕RK12)]⊕X13=X11, 有S(X12⊕RK12)⊕P−1[X12] =P−1[X11], 先猜测16 比特RK12, 再分步猜RK12剩余的密钥字节, 计算是否符合P−1[X11] 对应的差分, 筛选后剩下2n−17−8×8=2n−81密文对.

(4) 猜测RK12,[0,1,2,3]4 个字节值, 计算P[S(X12⊕RK12)] 的[13] 字节位置对应值, 与X13,[13]异或得X11,[13], 同理可得X′11,[13], 猜测RK11的1 个字节值, 计算P[S(X11⊕RK11)]⊕X12⊕P[S(X′11⊕RK11)]⊕X′12是否等于ΔX10, 筛选后剩下2n−81−8=2n−89密文对.

(5) 猜测RK1,[4,5,6,7,8,9,10,11]8 个字节值,计算S(X1⊕RK1)⊕S(X′1⊕RK1)的[4,5,6,7,8,9,10,11]字节位置处输出差分是否等于P−1(X0) 中的8 个“?” 字节, 若符合, 则留下密文对, 筛选后剩下2n−89−64 =2n−153个密文对.

(6) 猜测RK1,[0,1,2,3]4 个字节值, 计算P[S(X1⊕RK1)] 的[12] 字节位置对应值, 与X0,[12]异或得X2,[12], 同理可得X′2,[12], 猜测RK2的1 个字节值, 计算其输出差分是否等于P−1(X1) 中的“*” 字节, 若符合, 则抛弃对应的密钥.

(7) 重复上述(1)–(6) 步骤, 直到剩下唯一正确的密钥.

上述攻击中错误密钥被留下的概率为(1−2−8)2n−153, 上述一共猜测了26×8=208 比特的密钥值,故留下(2208−1)×(1−2−8)2n−153个错误密钥.取n=168.2 时, (2208−1)×(1−2−8)2n−153＜2−4, 可认为错误密钥全部被淘汰.此时攻击的数据复杂度为280×2168.2=2248.2个选择明文; 假设每进行16 次S 盒查询的时间与加密一轮SMBA-256 算法一致, 整个12 轮密钥恢复攻击过程采用了提前抛弃技术[14],时间复杂度是(216×(2151.2+28×(2143.2+28×(2135.2+28×(2127.2+28×(2119.2+28×(2111.2+28×(2103.2+232×(287.2+28×(287.2+216×(279.2+28×(271.2+28×(263.2+28×(255.2+28×(247.2+28×(239.2+28×(231.2+232×(215.2+28×215.2))))))))))))))))))÷(12×16)≈2227.6次12 轮加密.

5 结论

本文对SMBA 算法进行了不可能差分分析, 针对SMBA-128 算法, 相比于设计者提出的5 轮不可能差分区分器, 本文给出了6 轮并给出了理论证明, 进一步, 基于其中一条不可能差分区分器并结合提前抛弃技术给出了9 轮密钥恢复攻击, 数据复杂度和时间复杂度分别为2104.2和2121; 对于SMBA-256 算法,给出了12 轮密钥恢复攻击, 数据复杂度和时间复杂度分别为2248.2和2227.6.

对于Feistel 结构算法, 由于轮函数F无法设计为随机函数, 所以存在长于5 轮的不可能差分区分器,轮函数F的扩散性越差则区分器长度越长, SMBA-256 与SMBA-128 相比, 扩散性更弱, 是否存在9 轮不可能差分区分器是我们下一步的工作.