Further Security Evaluation for Piccolo Structure against Differential and Linear Cryptanalysis

YIN Qing1, WANG Nianping2,†

1. Space Engineering University, Beijing 101416; 2. School of Cryptography Engineering, The PLA Information Engineering University, Zhengzhou 450001; † Corresponding author, E-mail: wwnnpp@126.com

Abstract To evaluate the security of Piccolo structure, the security against differential and linear cryptanalysis is investigated. A new lower bound on number of active round function and active S-boxes for arbitrary round differential characteristics is given. Using the duality between differential characteristics and linear approximations of Piccolo structure, the new lower bound on number of active round function and active S-boxes for arbitrary round linear approximations is also given. The authors prove that these lower bounds cannot be improved. Key words Piccolo structure; differential cryptanalysis; linear cryptanalysis

对分组密码而言, 差分密码分析[1]和线性密码分析[2]是两种最重要的攻击方法, 评估分组密码抵抗这两种攻击的能力一直是密码学研究的热点。如果分组密码的最大差分特征概率(最大线性逼近概率)足够小, 就可以认为该密码对差分密码分析(线性密码分析)是安全的, 而差分特征概率(线性逼近概率)的上界通常可以用差分特征(线性逼近)中活动轮函数或活动 S 盒个数的下界来估计, 所以, 估计分组密码抵抗差分密码分析能力的关键在于求出活动轮函数或活动 S 盒个数的下界[3]。在研究差分特征中活动轮函数或活动 S 盒个数的下界时, 通

常不考虑轮函数和 S 盒的具体结构, 而只假定轮函数和 S 盒是双射, 文献[4–7]就是按照此思路对不同的结构进行研究。

对于从 Piccolo 算法[8]中归纳出来的 Piccolo 结构[9], Shibutani 等[8]利用计算机模拟的方法, 给出若

[9]干轮差分特征中活动轮函数个数的下界;殷勍等利用推导证明的方法, 给出任意轮差分特征中活动轮函数个数的下界, 但没有证明此下界不可改进。

本文将推导证明与计算机模拟相结合, 在相同条件下, 改进了殷勍等[9]的结果, 并证明所得结果是不可改进的。

1 预备知识1.1 基本概念定义 1[10] 设( X , ) 和 ( Y , )都是有限交换群, f : X → Y ,  X ,   Y ,令1 pf (  → )= #{ x  X : f ( x +  )  f (x )   },

X则称 pf ( → ) 为 f 在输入差为 的条件下, 输出差为 的差分概率。此外, 也称→ 为 f 的一个差分对应, 并称 pf ( → ) 为该差分对应的概率。其中, “| |”和“#{ }”表示集合的元素个数。定义 2[10] 设( X , ) 是有限交换群, f  ( k ,...,k ) 1 n   n 1  X , 则称  1 →  2 → ... →  n→ fkn ... fk2 fk1 , 1,...,  为f的一个起点为1 , 终点为的差分n 1 (k ,...,k ) n 1 1 n传递链, 并称 pk 1( 2(  →  )  pk  →  )... p ( → f 1 2 f 2 3 f n kn 1)  为该差分传递链的概率。n 本文也称差分传递链 →  → ... →  → 为1 2 n n 1 n轮差分特征。定义 3[10]设 f : Zm →Zn是多输出布尔函数, 2 2  (  1,  2,..., m )  Z2 m ,  (  ,  ,...,  )  Zn , 记1 2 n 2 1

 (  → )  W )()    ( 1 )  f ( x ) x , f (  f 2m

xz m 2则称  (  → ) 为 f 在输入线性组合为 的条件下, f输出线性组合为 的相关系数, 称→ 为 f 的一个线性逼近。其中,“”表示逐位异或,“  f (x)” 和“  x”都表示点积。定义 4[10]设 f  fkn ... fk fk1 , 则称 →2 ( k 1,..., kn ) 1 2 → ... →  → 为 f 的一个起点为1, 终点为n n 1 ( k 1,..., kn )  的组合传递链, 并称 2  2(  →  ) 2 n 1 f fk1 1 2 fk2 ( k 1,..., kn) (  →  )...  2kn (  → )为该组合传递链的概率。2 3 f n n 1本文也称组合传递链 →  → ... →  → 为1 2 n n 1 n轮线性逼近。显然, 差分对应(线性逼近)0 →0的概率恒为 1,因此, 称 0 →0为平凡差分对应(平凡线性逼近), 否则, 称为非平凡差分对应(非平凡线性逼近)。以下考虑的都是非平凡的情形。1.2 Piccolo 结构描述图1 为 1 轮 Piccolo 结构, 其中X 0, X 1, X 2, X  3 Z2 t 表示输入, f0和 f 表示轮函数, k , k  Zt 表示1 0 1 2子密钥, 块移位变换 RP 表示将 4 个分块Y 0, Y 1, Y2, Y3平均分成 8 个子分块后, 再对 8 个子分块进行移位变换。为了分析方便, 将 Xi ( i  0, 1, 2, 3) 视为由左右规模相等的两部分 x2i 和 x 连接而成, 表示为 X  2 i 1 0 x || x 1, X 1= x || x 3, X 2= x || x 5, X 3= x || x7, 则 Piccolo 0 2 4 6结构的输入可表示为( x || x 1, x || x 3, x || x 5, x || x7) 0 2 4 6 ( Zt 2)8 , 故 1 轮 Piccolo 结构(略去子密钥)可表示为2 Q ( x || x 1, x || x 3, x || x 5, x || x7) 0 2 4 6  RP( x || x 1, f 0( x || x 1)  x || x3, 0 0 2 x || x 5, f 1( x || x 5)  x || x7 )。4 4 6 1) 轮函数 f 和 f 。如图 2 所示, 轮函数 f0 和0 1 f1 都采用 SPS 结构, 其中, S 表示 n 个 m 比特双射S 盒的并置(n 为偶数, nm=t, t 表示输入块 X (i i 0, 1, 2, 3) 的比特位数), P 表示线性变换 P :( Zm )n→ 2 ( Zm ) n , x → M  x , x 是列向量, M 是有限域GF(2 m) 2上的 n 阶 MDS 矩阵。显然, P 变换的差分分支数[10]和线性分支数[10]都为 n+1, 且轮函数 f0 和 f1 都为双射。2) 块移位变换RP。如图3所示, 设块移位变换RP的输入为y  ( Y 0, Y 1, Y 2, Y 3)  ( y 0, y 1, y 2, y 3, y 4, y5, y , y )  ( Zt 2)8, 则块移位变换 RP 可表示为 RP( y) 6 7 2  RP( y 0, y 1, y 2, y 3, y 4, y 5, y 6, y 7)  ( y 2, y 7, y 4, y 1, y 6, y3, y 0, y5) 。[11] 设→ 是轮函数(S 盒)的一个差分定义5对应, 若  0, 则称该轮函数(S 盒)为差分活动轮函数(S 盒)。

性质 1[9] 对于 Piccolo 结构的轮函数 fj ( j  0, 1) ,设 →  →  → 是轮函数 fj ( j  0,1) 的差分对应,  0,  ,...,n , 0, 0, 0, 1,   ,...,  ,   ,..., 和  1 1 1 n1 1 n 1 ..., n 依次为 ,  , 和的n 个分块, 且 → 或1 j j  → (  j ,0  j  n 1) 表示 S 变换的第 j个 S 盒的j j差分对应, (  0,  ,...,  1) → (  0, 1 , ..., n1) 是 P 变换1 n 的差分对应。对于  (  0, 1 ,...,  )  ( Zm )n , 将n 1 2  看成 Z2 mn 2 上的 2 维列向量, 即  (  ,  ) 0 1 ( Z mn 2)2 , 并将 0, 1中非零元的个数记为W (  ) , 则2对于 f :( Zmn 2)2 → ( Z mn 2)2 的差分对应 → , 有j 2 2

min { W (  )  W (  )}  3。

0  a  ( Z mn 2 )2 2 2轮函数和活动S盒个数下界2.1差分活动轮函数和活动S盒个数下界设 (  ||  1,  ||  3,  ||  5,  ||  7) 是 Piccolo 结0 2 4 6构的输入差分, “1”代表非零差分块i , “0”代表零差分块i ( i  0, 1, 2, ... , 7) , 则 Piccolo 结构非零输入差分有且仅有 28–1=255 种表示, 即   (10000000) 1 def def def =1,  = (01000000) = 2, ... ,  = (11111111) = 255

2 255若左起第 1 和 2 位不全为零, 则 f0 为活动轮函数;若第 5 和 6 位不全为零, 则 f1为活动轮函数。首先, 给出输入输出差分块“1”和“0”通过 XOR运算和轮函数需要满足的约束条件。令a , b , c , d  {0, 1} 分别代表 ,  ,  ,   Z2 t 2 , “ ”表示按位与, “ ”表示按位或。条件1 差分经过 XOR 运算时满足以下条件:设 , 则

 a  b, 当a  b  0, c    0或1, 当a  b  1。条件 1 表示, 对于 , 当和 至少有一个为零时, 有 c=a+b; 当 和 都非零时,     的值可能为零, 也可能不为零, 所以 c=0 或1。条件2 差分经过轮函数时满足以下条件: 设

f (  ||  )  ||  , 则

 3, 当a  b  1, a  b  c  d   0,当a  b  0。条件 2 表示, 当轮函数输入差分非零时, 因为输入差分和输出差分满足性质 1, 所以a  b  c d  3; 当轮函数输入差分为零时, 输出差分也为零。

以条件 1 和 2 作为约束, 对于 Piccolo 结构, 当给定输入差分的“0”和“1”表示和迭代轮数时, 通过计算机搜索, 容易给出输出差分的“0”和“1”表示及其所需活动轮函数个数的最小值。利用这两个约束条件可以完成以下３个实验。

实验 1 通过计算机搜索, 给出 6 轮差分特征中活动轮函数个数的最小值。实验结果如图４所示, 其中第 x 行第y列( x 和y都是十六进制)交叉处的数值表示以 为首轮差xy分输入的 6 轮差分特征中活动轮函数个数的最小值。例如, 第 3 行第 e 列交叉处的数值为 7, 就表示以  = 3e =(3 e)=(1100 0111) 为首轮差分输入的xy 6 轮差分特征中活动轮函数个数的最小值为 7。这里, 3=1100= 1  20+1  21+0  22+0  23, e  0111= 0  20 +1  21+1  22+1  23, 且行数和列数都从0开始统计。从图 4可得以下结论。命题1 对于 Piccolo 结构, 任一 6 轮差分特征至少有 6个活动轮函数。

实验2 通过计算机搜索, 筛选出所有恰有 6个活动轮函数的 6 轮差分特征的尾轮输出差分(十六进制), 筛选结果记为集合 A, 表示如下(不计重复值)。3 13 15 17 19 23 26 2a 2b 30 31 32 33 36 39 4a 4b 51 58 59 5b 5e 5f 62 63 67 6a 6b 71 76 77 78 79 7a 7b 7e 7f 85 87 91 93 95 97 9b a2 a4 a6 a7 ad af b2 b4 b5 b6 b7 b9 bb bd bf da db e5 e7 f5 f7 fa fb实验3 对于 k  1, 2, 3, 4, 5, 通过计算机搜索,筛选出所有恰有k 1个活动轮函数的k 轮差分特征的首轮输入差分(十六进制), 筛选结果记为集合B,如下表示(不计重复值)。4 7 8 b c d e f 40 44 45 48 4c 4d 54 70 80 84 88 8a 8c 8e a8 b0 c0 c4 c8 cc d0 d4 e0 e8 f0通过观察发现, 集合A和 B没有公共元素, 故

可得以下结论。命题2 对于 Piccolo 结构, 任一恰有6个活动轮函数的 6 轮差分特征后面不可能“联接”一个恰有k  1( k  1, 2, 3, 4, 5)个活动轮函数的k 轮差分特征。引理 1 对于 Piccolo 结构,设 (0) →  (1) →... →  (6) → ... →  (6 n  6) → ... → (6 n) 为任一恰有 6n 个活动轮函数的6n 轮差分特征, 则最后 6 轮差分特征 (6 n  6) → ... → (6 n) 恰有 6个活动轮函数。证明 根据命题 1 可知, 6 轮差分特征 (6 n6) → ... → (6 n)  (6至少有 6 个活动轮函数。若 n6)→ ... → (6 n)中活动轮函数的个数大于 6, 则6( n 1) 轮差分特征 (0) →  (1) → ... →  (6) → ... → (6 n6) 中活动轮函数的个数必小于6( n 1) , 与命题 1 相矛盾, 故 (6 n  6) → ... → (6 n) 必含有 6 个活动轮函数, 所以本结论成立。

定理 1[9] 对于 Piccolo 结构, k ( k  1)轮差分特征至少有 k 1个活动轮函数。定理2 对于 Piccolo 结构, 以下结论成立。1) k (1  k  5)轮差分特征至少有k 1个活动轮函数。2) k ( k  6)轮差分特征至少有k 个活动轮函数。证明 1) 由定理 1, 即知。2) 当k  6 s ( s  1) 时,由命题 1 可知, 本结论成立。当 k  6 s  m ( s  1, 1  m  5) 时, 分以下两种情形进行讨论。

情形 1: 当前 6s轮差分特征至少有6 s  1个活动轮函数时, 由定理 1 可知, 后m轮差分特征至少有m 1个活动轮函数, 所以6s  m轮差分特征至少有(6 s  1)  ( m  1)  6 s  m个活动轮函数。

情形2: 当前 6s 轮差分特征恰有6s 个活动轮函数时,设 (0) → ... →  (6 s ) → ... → (6 s  m) 为任一 6s m轮差分特征, 且 6s轮差分特征 (0) → ... → (6 s) 恰

6s (6 s 6) → → (6 s)有 个活动轮函数。由引理1知,  ...恰有 6个活动轮函数, 再由命题 2 和定理 1 可

 (6 s) → ... →  (6 s  m) m个知, 后m轮差分特征 至少有活动轮函数, 所以 6s  m轮差分特征至少有6s m个活动轮函数。

结合轮函数中 P 变换的差分分支数[10]为(n + 1),由定理 2可得以下结论。推论1 对于 Piccolo 结构, 以下结论成立。1) k (5  k  1)轮差分特征至少有( n  1)(k  1) 个活动 S 盒。

2) k ( k  6) 轮差分特征至少有(n+1)k个活动S盒。2.2 线性活动轮函数和活动S盒个数的下界

定义 6[9]若 满足以下两个条件, 则称密码结构具有差分线性对偶性。

1) 对任一活动轮函数个数为s ( s  0) 的 k 轮差分特征U , 都存在活动轮函数个数为s ( s  0) 的 k轮线性逼近U *。

2) 对任一活动轮函数个数为s ( s  0) 的 k 轮线

*  0) 的k性逼近U , 都存在活动轮函数个数为s ( s轮差分特征U 。定理 3[9] Piccolo 结构具有差分–线性对偶性。定理4对于 Piccolo 结构, 以下结论成立。1) k (1  k  5)轮线性逼近至少有k 1个活动轮函数; 2) k ( k  6)轮线性逼近至少有k 个活动轮函数。证明 由定理 2 和 3易知本结论成立。结合轮函数中 P 变换的线性分支数[10]为(n+1),由定理 4可得到以下推论。推论2 对于 Piccolo 结构, 以下结论成立。1) k (1  k  5)轮线性逼近至少有( n  1)(k  1)个活动 S 盒。2) k ( k  6)轮线性逼近至少有( n  1)k 个活动S盒。定理5 设 S 盒的最大差分概率和最大线性逼近概率分别为p和 q , 则以下结论成立。

1) k (1  k  5)轮 Piccolo 结构的最大差分特征概率 p ( n  1)(k 1) , 最大线性逼近概率 q ( n  1)(k 1) 。2) k ( k  6) 轮 Piccolo 结构的最大差分特征概率 p ( n 1)k , 最大线性逼近概率 q ( n 1) k 。2.3 Piccolo 结构活动轮函数个数下界的不可改进性

本节证明, 定理 2 和 4 给出的活动轮函数个数的下界是不可改进的, 即确实存在一类差分特征和线性逼近, 其活动轮函数的个数恰好达到给出的下界。

设 ,  ,  ,  ,  ,  全不为零。为叙述方便, 用 S1表示 2 轮差分特征 (0||0,  ||0, 0||0, 0||0) → (  || 0, 0||0, 0||0, 0||0) → (  ||0, 0||0, 0||  ,  || 0), 其轮函数差分对应依次为 f 0(1) : 0 → 0, f 1(1) : 0 → 0, f0(2): ||0 →  ||  , f1(2): 0 →0。用 S2 表示 3 轮差分特征 (  ||  ,  ||0,0||0,0|| 0) → (0||0,0||  ,0||0,  ||0) → (0||0,0||0,  ||  ,0||0) → (0||0,  ||0,  ||0,0||  ),其轮函数差分对应依次为f 0(1) :  ||  →  ||0, f 1(1) : 0 → 0, f 0(2) : 0 → 0, f1(2) : 0 → 0, f 0(3) : 0 → 0, f1(3):  ||  →  ||0。用 S3表示 4 轮差分特征(  ||  ,  ||0,0||0,0||0) → (0||0,0||  ,0||0,  ||0) → (0 || 0, 0 || 0,  ||  , 0 || 0)→ (0||0,  ||0,  ||0,0||  ) → (  ||  ,  || 0,  || 0, 0 || 0) , 其轮函数差分对应依次为 f 0(1) : ||  ||0, f1(1) : 0→

0 ， f 0(2) : 0 → 0 ， f 1(2) : 0 → 0 ， f 0(3) : 0 → 0, f1(3):  ||  → || 0, f 0(4) : 0 → 0, f1(4): ||0 →  ||  , 其中 0。用 S4 表示 5 轮差分特征 (  || 0,  || 0 , 0 || 0,  || 0) → (0||0,0||0,  ||  ,  || 0) → (0 || 0,  || 0, 0 || 0, 0 || ) → (  ||  ,0||0,0||0,0||0) → (  || 0, 0 ||  ,0||0,  || 0) → (  ||0,0||0,  ||0,  || 0, ) , 其轮函数差分对应依次为f 0(1) :  ||0 →  || , f 1(1) : 0 → 0, f 0(2) : 0 → 0, f1(2):  || →  ||0, f 0(3) : 0 → 0, f 1(3) : 0 → 0, f 0(4):  ||  →  ||0, f1(4): 0 → 0, f 0(5):  ||0 →  || , f1(5) : 0 → 0。

由 ,  ,  ,  ,  ,  0可知, S1有 1 个活动轮函数, S2 有 2 个活动轮函数, S3 有 3 个活动轮函数, S4有 4 个活动轮函数。这说明, 对k  2, 3, 4, 5, 定理2第1个结论中活动轮函数个数的下界是不可改进的。又因为k  1时, 显然存在恰有 0 个活动轮函数的 1 轮差分特征, 所以定理 2 第 1 个结论中的下界是不可改进的, 再由定理 3 知, 定理 4 第 1 个结论中的下界也是不可改进的。

下面说明定理 2 第 2个结论和定理 4 第 2 个结论中的下界是不可改进的。

S5 表示 3 轮差分特征(0 || 0,  || 0,  ||  ,0|| ) → (  ||  ,  ||0,0||0,0||  ) → (  ||  ,0||  ,0||0,  || 0)→ (0 || 0, 0 ||  ,  ||  ,  || 0) , 其轮函数差分对应依次为f 0(1) : 0 → 0, f 1(1) :  ||  → 0||  , f0(2):  ||  →  || 0, f 1(2) : 0 → 0, f 0(3) :  ||  → 0 ||  , f1(3): 0 → 0, 其中   , 和  都不为零。

S5的每一轮各含有1个活动轮函数。现在将两个 S5 “联接”在一起得到 S → S5 , 其中“联接”处的

5差分特征(0 || 0, 0 ||  ,  ||  ,  ||0) → (0||0,  ||0,  || , 0 ||  )的轮函数差分对应为 f 0(4) : 0 → 0, f0(3): ||  →  || 0 , 其中 0。易知, S  S5 的每一轮

5各含有1个活动轮函数。这样一来, 通过“联接” S5 ,可以得到任意k ( k  1)轮有 k 个活动轮函数的差分特征, 故定理 2 第 2个结论中的下界是不可改进的,再由定理 3 知, 定理 4 第 2 个结论中的下界也是不可改进的。3 结束语

本文给出 Piccolo 结构抵抗差分密码分析和线性密码分析能力的评估结果。具体地, 给出任意轮差分特征中活动轮函数和活动 S盒个数的一个新下界, 并利用差分线性对偶性, 给出任意轮线性逼近中活动轮函数和活动 S盒个数的一个新下界。本研

图 3 块移位变换RP Fig. 3 Block shift transformation RP

图 4 6轮差分特征中活动轮函数个数的最小值Fig. 4 Minimum of number of active round function for 6-round differential characteristics