Page 411 - 《软件学报》2024年第4期

黄明 等: 分组密码复杂线性层可分性传播的 MILP 刻画方法 1989

图 1 中 S 盒是一个 4 比特到 4 比特的双射, <<<b 表示将输入字分成 32 比特的子块, 并在每一个子块上循
32
环左移 b 比特, PL n 、 PR n 是基于字节的位置置换, 具体置换见表 2, 有关算法的详细描述请参考文献 [14].

表 2 位置置换 PL n 、PR n 选择

置换选择
PL n /PR n
{4, 0, 5, 1, 2, 7, 3, 6}
PL 128
PR 128 {3, 4, 0, 7, 6, 2, 5, 1}
{15, 8, 0, 4, 9, 14, 5, 1, 2, 6, 11, 13, 7, 3, 12, 10}
PL 256
PR 256 {9, 2, 6, 13, 5, 15, 0, 8, 14, 4, 11, 1, 3, 10, 12, 7}

在 uBlock 算法轮结构中, S 盒的输出到 PL n 、 PR n 的输入的操作 <<<b 中 b 的取值为 4 的倍数, 所以一系列
32
<<<b 和 ⊕ 操作等价于 n/16 个相同的矩阵 M ∈ F 16×16 .
2
32
 
 A B 
    ,

M =   
 
B C
F 8×8 的循环矩阵.

其中, A, B, C 均为
2
     
 0 0 1 1 1 0 1 1   1 1 0 1 0 1 1 1   1 0 1 1 0 0 1 1 
     
     
     
     
     
 1 0 0 1 1 1 0   1 1 1 0 1 0 1   1 1 0 1 1 0 0 



 1    1    1  
     
     
     
           
 1 1 0 0 1 1 1   1 1 1 1 0 1 0   1 1 1 0 1 1 0 



 0    1    0  
     
     
     
     
     
 0 1 1 0 0 1 1   1 1 1 1 1 0 1   0 1 1 1 0 1 1 



 1    0    0  
          .


A =   , B =   , C =   


     
 1 0 1 1 0 0 1   0 1 1 1 1 1 0   0 0 1 1 1 0 1 



 1    1    1  
     
     
     
     
 1 1 0 1 1 0 0 1    1 0 1 1 1 1 1 0    1 0 0 1 1 1 0 1  
     



     
     
     
     
     
 1 1 1 0 1 1 0    0 1 0 1 1 1 1    1 1 0 0 1 1 1 

 0    1    0  
     
     
     
     
     
0 1 1 1 0 1 1 0 1 0 1 0 1 1 1 1 0 1 1 0 0 1 1 1
对于 S 盒可分性传播的 MILP 建模采用文献 [8] 的方法; 对于复杂线性层矩阵 M ∈ F 16×16 可分性传播的刻画,
2
采用动态选取策略, 即通过算法 1 的框架构建 MILP 模型, 具体来说, 线性层输入可分性汉明重量分类情况为:

{0,16}, Θ ZR = {1,2,14,15}, Θ HZ = {3,4,...,13}, 并将 Θ ZR 继续分为 Θ ZR 0 = {1}, Θ ZR 1 = {2}, Θ ZR 2 = {14}, Θ ZR 3 = {15}

这 4 种情况.
根据上述思想, 本文构建了搜索 uBlock128 算法积分区分器的 MILP 模型, 选择与文献 [15] 相同的初始可分
性进行搜索得到多 32 个平衡比特的 8 轮积分区分器如下:
( ) 8轮 ( 2 32 )
4
C A 124 → (BUB ) .
事实上, 我们尝试过只使用 ZR 方法对 uBlock128 算法 8 轮积分区分器进行搜索以求得是否存在更多的平衡
65535×8×8 = 4194304 个, 即使 MILP 模型在内存为 256 GB 的工作站中
比特, 但其线性层需要的不等式数量为
运行也会发生内存溢出, 进而无法求解. 而使用我们的模型在个人笔记本 16 GB 内存就能在有限时间内求解. 另
外, 本文搜索到比之前最优区分器多一轮的 9 轮积分区分器.
( ) 9轮 ( 32 )
3
ACA 126 → (U B) .
文献 [15] 中作者搜索到 uBlock256 算法的 9 轮积分区分器, 然而利用本文的模型, 则可以搜索到 uBlock256
算法的 10 轮积分区分器.
( ) 10轮 ( 64 )
3
3
C A 253 → (U B) ,
( ) 10轮 ( )
ACA 254 → B 256 .
3.2 Saturnin 算法积分区分器的搜索
Saturnin 算法是一种类 AES 结构算法, 分组长度和密钥长度均为 256 比特, 记为 Saturnin256/256, 默认迭代轮