密码学报 ISSN 2095-7025 CN 10-1195/TN
Journal of Cryptologic Rearch , 2021, 8(1): 124-131
小学美术老师©《密码学报》编辑部版权所有.C H A M 算法的安全性分析#
陈少真' 李航\付志新\任炯烟1
笛子曲谱1. 战略支援部队信息工程大学，郑州450001
2. 密码科学技术国家重点实验室，北京100878中国神话故事
通信作者：付志新，E-mail: fz x _m a t h @163.c o m
摘要：本文主要研究基于A R X 结构的轻量级分组密码C H A M 算法，利用不可能差分分析、零相关线 性分析对其进行安全性分析.首先，利用线性不等式组对算法的每个组件进行等价刻画，描述了差分特征 和线性掩码的传播规律，建立了基于MILP (混合整数规划问题）的不可能差分和零相关线性自动化搜索 模型.其次，根据C H A M 算法四分支广义F e i s t e l 结构的特点，得到C H A M 算法特定形式（输入或者输 出差分（掩码）仅含有一个非零块）下的最长不可能羡分路径和零相关线性路径具有的性质，优化了搜索 策略.缩小了搜索空间.最后，利用搜索算法，遍历特定的输入输出集合，共得到C H A M -64的5
条19轮 不可能差分区分器，C H A M -128的1条18轮不可能差分区分器和15条19轮零相关线性区分器，均为 目前公开发表的最长同类型区分器.
关键词：轻量级分组密码；C H A M 算法；自动化搜索
中图分类号：T N 918.1 文献标识码：A DOI : 10.13868/j .c n k i .j c r .000425
中文引用格式：陈少真，李航，付志新，任炯炯.C H A M 算法的安全性分析丨J ].密码学报，2021, 8(1): 124-_131.
[DOI : 10.13868/j .c n k i .j c r .000425]
英文引用格式：CHEN S Z , L I H , FU Z X , REN J J . S e c u r i t y a n a l y s i s o f C H A M c i p h e r [J ]. J o u r n a l o f C r y p t o l o g i c R e s e a r c h , 2021, 8(1): 124 131. [DOI : 10.13868/j .c n k i .j c r .000425]
E -m a i l : j c r @c a c r n e t .o r g .c n h t t p : / / w w w .j c r .c a c r n e t .o r g .c n T e l /Fax : +86-10-82789618S e c u rity A n a ly sis o f C H A M C ip h e r
C H E N Shao -Zhen 1'2, L I Hang 1, FU Z h i -Xin 1, REN J i o n g -.J i o n g 1
1. P L A Strategic Support Force Information Engineering University, Zhengzhou 450001, China
2. State K e y Laboratory of Cryptology, Beijing 100878, China
Corresponding author: F U Zhi-Xin,E-mail:*****************
Abstract : T h i s p a p e r a n a l y z e s t h e s e c u r i t y o f A R X s t r u c t u r e c i p h e r C H A M b y i m p o s s i b l e d i f f e r e n c e a n a l y s i s and z e r o -c o r r e l a t i o n l i n e a r a n a l y s i s . F i r s t l y , e a c h component o f t h e c i p h e r i s c h a r a c t e r i z e d e q u i v a l e n t l y b y u s i n g a s e t o f l i n e a r i n e q u a l i t i e s . The p r o p a g a t i o n c h a r a c t e r i s t i c s o f t h e d i f f e r e n t i a l f e a t u r e s and l i n e a r masks a r e d e s c r i b e d , t h e n a n MILP (M i x e d I n t e g e r L i n e a r Programming ) i m p o s s i b l e d i f f e r e n t i a l and z e r o -c o r r e l a t i o n l i n e a r auto ma te d s e a r c h mo del a r e e s t a b l i s h e d . S e c o n d l y , a c c o r d i n g t o t h e c h a r a c t e r i s t i c s o f t h e f o u r -b r a n c h g e n e r a l i z e d F e i s t e l s t r u c t u r e o f C H A M , t h e p r o p e r t i e s o f t h e **基金项目：数学工程与先进计算国家重点实验室开放课题（2018A03)；国家密码发展基金（MMJJ20180203)；信息保障技 术重点实验室幵放课题（KJ-17-002)
Foundation: Ope n Fund of State Key Laboratory of Mathematical Engineering and Advanced Comp
uting (2018A03); National Cryptography Development Fund of China (MMJJ20180203) ; Open Fund of Science and Technology on Information Assurance Laboratory (KJ-17-002)
本兮死因收稿 n 期• 2020-03-18 定稿日期：2020-05-28
陈少真等：CH AM算法的安全性分析125
最迟开始时间
l o n g e s t i m p o s s i b l e d i f f e r e n t i a l p a t h and z e r o-c o r r e l a t e d l i n e a r p a t h i n t h e s p e c i f i c fo rm(t h e i n p u t o r o u t p u t d i f f e r e n t i a l c o n t a i n s o n l y o n e n o n-z e r o b l o c k)o f C H A M a r e o b t a i n e d,t h e s e a r c h s t r a t e g y i s o p t i m i z e d,and t h e s e a r c h s p a c e i s r e d u c e d.F i n a l l y,by u s i n g t h e s e a r c h a l g o r i t h m,t r a v e r s i n g a s p e c i f i c s e t o f i n p u t s and o u t p u t s,f i v e 19-r o u n d i m p o s s i b l e d i f f e r e n t i a l d i s t i n g u i s h e r s o f C H A M-64, o n e 18-r o u n d i m p o s s i b l e d i f f e r e n t i a l d i s t i n g u i s h e r o f C H A M-128 and f i f t e e n 19-r o u n d z e r o-c o r r e l a t i o n l i n e a r d i s t i n g u i s h e r s o f C H A M-128 a r e f o u n d,t h e y a r e t h e l o n g e s t p u b l i c l y a v a i l a b l e d i s t i n g u i s h e r s o f t h e same t y p e known s o f a r.
Key words:l i g h t w e i g h t b l o c k c i p h e r;C H A M;automated s e a r c h
i引言
轻量级密码算法具有资源占用量较少的优点，特别适用于RFID(R a d i o F r e q u e n c y I d e n t i f i c a t i o n)、无线传感器网络CWSN)等资源和计算能力有限的设备和环境.近年来，关于轻量级分组密码的研宄越来 越受到人们的关注，很多轻量级算法陆续被提出，比如PRESENT W,MIBS LEA W等算法.为了更 好地实现安全性和效率的折中，涌现出了一批基于A R X结构的轻量级分组密码.A R X型密码算法采用 模加运算、循环移位和异或运算三种运算，其中只有模加运算为非线性运算.为了便于软硬件的快速实现，A R X型密码算法的非线性组件规模一般较小，但是由于模加运算的迭代次数较高，其仍然具有较强的安 全性.为了提高L E A算法对资源受限环境的适应性，在ICISC 2017, Koo B等W提出了一个新的分组 密码家族C H A M算法.
在基于统计学方法的攻击如差分类、线性类、积分类等密码攻击过程中，需要寻找有效的区分器，区分器的好坏，直接关系到密码攻击的效果，找到更长轮数的区分器，往往意味着在密码分析中能取得更好 的攻击结果.自动化搜索算法充分考虑了密码算法特点，结合其线性和非线性组件性质，通过计算机，可 在有效时间内给出特定条件下的所有区分器，在具体应用中往往能比传统方法搜索到效果更好、条数更多 的区分器.目前常用的自动化搜索算法主要包括基于SAT(布尔可满足性问题）的自动化搜索算法和基于 MILP(混合整数规划问题）的自动化搜索算法.
M I L P问题是运筹学中的一类优化问题，旨在线性约束条件下求解目标函数的最值.最近几年，为了 获取分组密码中活跃S盒数量的下界，进而评估分组密码抵抗差分和线性攻击的能力，很多密码学者
将该 问题转换为M I L P问题，取得了非常好的结果15'61.后来模加运算差分概率的计算也转化为了 M I L P问题，用于搜索A R X型分组密码算法的区分器I7#.基于M I L P自动化搜索技术发展越来越成熟，显示出 强大的密码分析能力，借助M I L P的求解工具Gu ro bi，可以在一定的时间内搜索得到相应的区分器.
本文旨在利用不可能差分分析、零相关线性分析对C H A M算法进行安全性分析.首先利用不等式组 对算法的每个组件进行等价刻画，描述了差分特征和线性掩码的传播规律，其次针对C H A M算法四分支 广义F e i s t e l结构的特点，优化了不可能差分区分器和零相关线性区分器的搜索策略，缩小了搜索空间，进 而基于M I L P工具设计了有效的搜索算法.依靠搜索算法，共得到C H A M-64的5条19轮不可能差分区 分器，C H A M-128的1条18轮不可能差分区分器和15条19轮零相关线性区分器，这是C H A M算法目 前找到的最长零相关特征和最长不可能差分特征.与己有结果的对比如表1所示.
2 C H A M算法
C H A M是一个四分支广义F e i s t e l结构的分组密码族，每个密码由C H A M-n/m表示，分组长度为n 比特，密钥长度为m比特.表2显示了该家族的密码及其参数列表，在这里，！•、w和k w分别表示迭代的 轮数、一个分支（字）的长度以及密钥的字数.
2.1 C H A M算法的轮函数
明文P=(X0[0]，X0[l j，X0[2]，X0[3])作为加密函数的输入，利用轮函数加密t■轮可以得到密文 C = (X r[0]，X r[l]，X r[2],X r[3]).值得注意的是，C H A M算法的奇数轮和偶数轮对应轮函数的参数不同，
126Jemma丨 〇/C V ypfoZo仍c Hearc/i 密码学报 Vol.8, No.1,Feb.2021
表1C H A M算法区分器比较
T able 1 Comparison of distinguishers about C H A M family
攻击方法算法区分器轮数来源
不可能差分
C H A M-64
18
19
讲神话故事[4]
河虾炒韭菜
本文C H A M-128
15
18
[4]
本文C H A M-6421[4]
零相关线性
C H A M-128
18
19
[4]本文
表 2 C H A M系列算法参数表
T a b l e 2 Parameters table of C H A M family
n m r xv k w CHA M-64/1286412880168
CHAM-128/12812812880324
CHAM-128/25612825696328
当轮数r(0 <i <r)为偶数时，轮函数为:
Xi+i[3]=((Xi[0]㊉i)田（(^[1]《C1)㊉rk[i m o d2kw])) 8，
X i+1[j] =Xi[j), 0^j^2
当轮数r*为奇数时，轮函数为：
_Xi+i[3] = ((Xi[0] ®i)田（(^[1]《8) 0r k[i m o d2k w]))贫 1,
X i^[j} =X l[ji0^j^2
以上符号“田”表示模y加，“®”表示按位进行异或，“《<”表示循环左移.图1给出了 C H A M算法2轮 加密函数，其中，山）表示第i轮的输入.
2.2 C H A M算法的密钥生成算法
C H A M-n/A：的密钥扩展算法是利用主密钥K =(尺[0]，尺[1]，...，K[kW— 1])生成2 .k w个忉比特的轮子密钥（r k[0],r k[l],... ,r k[2.k w- 1])，生成轮子密钥的过程如下所示：
r k[i] =®(K[i]《1)©(尺⑷後8)，
r k[i+kw] =K[i]㊉（K[i]《8)㊉（/C[i]《11)
其中0 <i <kw.加密过程则循环使用这些轮子密钥—加密2 •k w轮循环使用一次全部轮子密钥.
3 C H A M算法不可能差分区分器搜索
不可能差分分析由B i h a m M和K n u d s e n l M分别提出，其原理可以简单概括为：利用概率为零的不 可能差分区分器来排除错误的候选密钥，从而恢复正确密钥.
本节我们给出一个基于M I L P自动化搜索C H A M算法的不可能差分路径的模型，并利用该模型搜
陈少真等：CH AM算法的安全性分析127
索得到19轮C H A M-64和18轮C H A M-128的不可能差分路径.对于给定的输入和输出差分，我们首先 把C H A M算法的每个组件用线性不等式组等价刻画并进行组合，然后将目标函数设定为任意的常值一 我们只关心不等式组是否有解而不关心目标函数的取值.若不等式组无解，当前的输入差分和输出差分导 致一条不可能差分路径；反之，则对应的差分路径存在.
3.1差分特征传播规律
轻量级分组密码C H A M算法的加密函数较为简单，仅仅包含分支运算、循环移位运算、常数异或运 算以及模加运算，其中模加运算是唯一的非线性运算，其余均为线性运算.我们知道，与常数进行异或不影 响差分的传播，分支运算同样不改变差分，因此仅需用不等式组刻画循环移位操作和模加操作.
对于循环移位操作，由于它仅仅是将输入的比特位置进行置换，因而我们很容易构建线性等式组对其 进行刻画.
对于模加操作，文献[11]进行了刻画，长度为71比特的差分特征（a，/3,7)满足a田0=7当且仅当
a[0]+/3[0]+7[〇]-2d=0,
-a[i] -0[i]—7[*] +a[*+1] +/3[i+1]+7[* +1]^ -2,
a[i]+/3[i]+7[i]—a[j+ 1] —/3[i+1] —"f[i + 1]^ —2,
a[i] +/3[i]+7[i]+a[i+ 1] +/3[i+1] —7[i + 1]^ 0,
a[i]+P[i]+7[i]+a[i+ 1] -0[i+1] +-y[i + 1]^ 0,
a[i] +P[i)+7[j]-a[i+ 1] +/3[i+1] +i[i + 1]> 0,
-a[i]-P[i]—7[i]+a[i+1]—P[i+1]—l[i+1]>—4,
—a[i] ——7[i]—a[i+1] +0[i+1] —7[i +1]^—4,
-a[i] -P[i]-7[i]-a[i+ 1] -P[i+1]+7[* + 1]^ -4
其中c；是二元变量，0 <i <n.
3.2搜索策略
在上一小节中，C H A M算法加密函数的每个运算的差分特征传播都用一组线性不等式进行了刻画. 通过组合所有的不等式，整个不等式体系能够完美刻画差分特征在C H A M算法中的传播规律，其给出的 每个解就是一条可能的差分路径.而对于给定的输入差分和输出差分，如果不等式组无解，那么当前的输
128Jemma/ 〇/CVypk/o仍'c Z?e5earc/i 密码学报 Vol.8，No.1,Feb.2021
入输出差分将导致一条不可能差分路径.由于时间的约束，我们很难遍历整个输入差分和输出差分空间, 而仅仅搜索特定形式输入输出差分的集合，通过遍历输入差分和输出差分的特定集合，我们可以确定该集 合中是否存在不可能差分路径.
蓬莱阁风景区
因为C H A M算法是四分支广义F e i s t e l结构，所以我们不难得出C H A M算法的最长不可能差分路 径具有性质1.这里“最长”仅仅指的是在输入或输出差分仅含有一个非零比特块的情况下，并非针对所有 的不可能差分区分器.
性质1对于C H A M算法的最长不可能差分路径，若输入差分只有一个非零块，则一定形如(a，0,0,0)或（0,0,0,/3)，其中w t(a) > 0，wt⑷> 0；若输出差分只有一个非零块，则一定形如（7,〇,〇,〇) 或（0,77,0,0)，其中 w t(7) >〇,w t(77)> 0.
证明：以输入差分的形式的证明为例，假设r■轮不可能差分路径为（ai，a2，a3，Q4)二1^
(m馬).
若非零块位于第二个字，即形如（0，a2,0,0).根据差分的传播规律，输入差分可以自然的向上传播- 轮，得到差分（0,0,a2,0).因此，存在（r+ 1)轮的不可能差分路径（0,0，a2,0) — (0，a2,0,0)
与r轮不可能差分路径最长矛盾.
若非零块位于第三个字，即形如（〇,〇，a3,〇).根据差分的传播规律，输入差分可以自然的向上传播一 轮，得到差分（0,0,0，a3).因此，存在（r+ 1)轮的不可能差分路径（0,0,0，a3)(0,0，a3,0) -r'r〇u n d-> d f t，A,A)，与r轮不可能差分路径最长矛盾.
因此，对于C H A M算法的最长不可能差分路径，若输入差分只有一个非零字，则一定形如（a，0,0,0) 或（0,0,0，外
同理可证，对于C H A M算法的最长不可能差分路径，若输出差分只有一个非零字，则一定形如
(7, 〇,〇,〇)或（〇,”，〇,〇).
综上所述，命题得证. 口
在搜索输入（输出）差分仅有1个非零块的最长不可能差分路径时，我们首先对路径的轮数预估一个 上界，然后递减轮数进行搜索，直至找到不可能差分路径为止.根据性质1，我们可以排除掉最长不可能差 分路径的输入（输出）差分所不具有的形式，而不需要遍历全部的输入（输出）差分.
3.3 C H A M算法的不可能差分区分器
C H A M算法的分组长度是64比特或128比特，遍历所有可能的输入输出差分对复杂度太高，所以我 们只考虑三种特殊的情况：输入、输出差分的重量均为1比特（称为一进一出)；输入、输出差分的重量分 别为1比特、2比特（称为一进二出)；输入、输出差分的重量均为2比特、1比特（称为二进一出).在搜 索时，我们利用性质1来降低时间复杂度.
对于C H A M-64算法，搜索得到5条-进二出的19轮不可能差分区分器，结果如表3所示.
表3C H A M-64不可能差分路径
T a b l e 3 Impossible differential path of C H A M-64
(0, 0, 0, ei4)〜（0, e2,7,〇,〇)(〇,〇,〇,614) — (0, e2,6, 〇,〇)
(0, 0, 0, e i4)(0, e2,5, 〇, 〇) (〇,〇,〇, e14) 〜（〇, e2,4, 〇, 〇)
(0,0,0,e14)(0,e2.3,〇,〇)
对于C H A M-128算法，搜索得到1条一进二出的18轮不可能差分区分器（0,0,0，e3O)#
(e23,〇, 〇, e〇).
4 C H A M算法零相关线性区分器搜索
零相关分析方法由Bogdanov和Rijmen l12i于2012年提出，该方法首先要构造一条零相关路径，通常让线性掩码在非零偏差下从两头向中间传播并相遇，若任何一个位置产生矛盾，则找到一条零相关路 径[131.构造完零相关路径后，就可以利用区分器对密钥进行恢复.
