轻量级分组密码PRIDE的线性分析

--1--轻量级分组密码PRIDE的线性分析汇报人：伊文坛信息工程大学河南郑州2015年10月23日上海--2--主要内容一、研究背景和工作动机二、PRIDE密码的设计特点三、PRIDE密码线性分析的具体过程--3--一、研究背景和工作动机--4--PRIDE是Albrecht等在2014美密会上提出的轻量级分组密码算法；PRIDE密码算法采用的是典型的SPN结构，分组长度64比特，密钥长度128比特，共迭代20轮；PRIDE设计特色在于线性层，兼顾了安全和效率。一、研究背景和工作动机明文P轮函数KSP...轮函数KSP轮函数KSK明文M0k18k1920,kk密钥扩展算法64比特128比特64比特20轮--5--一、研究背景和工作动机目前针对PRIDE的分析有如下分析结果：赵静远等：构造出1-3-1型两轮可迭代的概率为2-8的差分路径，进而构造概率为2-58的15轮的差分路径，往前、后各扩展1和2轮，对18轮PRIDE进行分析；杨倩倩等：构造出2-2型一轮可迭代的概率为2-4的差分特征，迭代15轮，往前、后各扩展2轮，结合S盒的差分特点，攻击了19轮的PRIDE算法；戴艺滨等：在一些相关密钥条件下，构造出概率为2-4的两轮可迭代的差分特征，对全轮PRIDE算法做了差分分析。--6--一、研究背景和工作动机目前针对PRIDE的安全性分析仅有在单密钥和相关密钥条件下的差分分析结果。我们第一次考虑评估该密码算法在线性分析下的安全性。分析过程中，我们关注了如下三个问题：高偏差线性路径的构造；PRIDE算法S盒运算的一些线性性质；明文剖分技术的一个应用。--7--一、研究背景和工作动机分析方法轮数数据复杂度时间复杂度工作出处相关密钥差分分析20239CPs260ENCDai,etal.差分分析18260CPs266ENCZhao,etal.差分分析19262CPs263ENCYang,etal.线性分析18260KPs286ENC本文线性分析19262KPs295ENC本文PRIDE密码算法的主要分析结果--8--二、PRIDE密码的设计特点--9--非线性层是由16个相同的规模为4比特的S盒并置而成；线性层包括三部分，置换层（拉线）、矩阵变换层和逆置换层（拉线）；拉线部分可以描述成矩阵层是有4个规模为16比特的矩阵并置，其中第1、4个矩阵是对角和对偶矩阵，分支数为4。二、PRIDE密码的设计特点(){(3)mod4}161.4xypxx--10--二、PRIDE密码的设计特点PRIDE密码算法的轮函数S盒S盒S盒S盒S盒S盒S盒S盒S盒S盒S盒S盒S盒S盒S盒S盒L1L2L3L4fi(k1)IiXiYiZiWiOi--11--PRIDE密码的S盒运算存在一些弱点：存在偏差较大输入输出掩码相同，并且重量为1的线性逼近；S盒运算输出的第2比特可以有输入的第2、3和4比特确定，和输入第1比特无关。PRIDE密码的线性层存在一些弱点：存在局部对偶性；矩阵变换层矩阵分支数为4，相对较小。二、PRIDE密码的设计特点--12--三、PRIDE密码线性分析的具体过程--13--利用偏差较大的线性逼近来区分随机函数和密码算法；主要过程包括线性逼近的构造、数据收集、部分加解密和密钥筛选等；要求是已知明文，数据量和线性逼近的偏差以及成功概率有关。三、PRIDE密码线性分析的具体过程--14--三、PRIDE密码线性分析的具体过程E2E1E31k2k3k明文密文10niiiaxax011(,,,)nxxxx011(,,,)nyyyyStep1对由多轮复合构成的E2进行线性逼近：选择适当a=(a0,…,an-1)和b=(b0,…,bn-1)，使对E2的线性逼近a→b的优势尽可能地大。这里22(,)()EkWab22(,){01}1(1)2nbExkaxnx，22()()EkWaba和b称作为掩码(mask)表达式为0的概率减掉不为0的概率--15--三、PRIDE密码线性分析的具体过程命题对于PRIDE算法采用的S盒运算，线性逼近成立的概率为0.75，偏差为2-2。0x10x1()0,xSx这样，结合线性层的特点，PRIDE算法存在16条2轮迭代并且偏差为2-5线性逼近和8条1轮迭代，偏差为2-3线性逼近11轮轮，1.轮--16--三、PRIDE密码线性分析的具体过程例如：0)00000000000001(00)01000000010001(00)00000000000001(011，，，；，，，；，，，；，，，，，，；，，，；，，，；，，，，，，；，，，；，，，；，，，轮轮偏差为2-5的2轮可迭代线性逼近偏差为2-3的1轮可迭代线性逼近0)00100000001000(00)00100000001000(01，，，；，，，；，，，；，，，，，，；，，，；，，，；，，，轮这里0和1都是十六进制表示。--17--三、PRIDE密码线性分析的具体过程E2E1E31k2k3k明文密文120(,,,)nnmmmm120(,,,)nncccc120(,,,)nnxxxx120(,,,)nnyyyyStep2将a·x写成明文和密钥k1的部分比特的函数：1,(,)partialpartialaxfmk将b·E2(k2,x)写成密文和密钥k3的部分比特的函数：从而得到线性逼近方程:3,(,)partialpartialbygck1,3,(,)(,)0partialpartialpartialpartialfmkgck--18--三、PRIDE密码线性分析的具体过程E2E1E31k2k3k得到的线性逼近方程:E3-13()ktestE1-11()ktestmc1,3,(,)(,)0.partialpartialpartialpartialfmkgck对于错误的密钥,等式成立的概率接近0.5。对于正确的密钥，等式成立的概率为22()11();22EkWab据此可将(k1,partial,k3,partial)的正确假设与错误假设区分开来。--19--三、PRIDE密码线性分析的具体过程在部分加解密的过程中，主要有两个计算方法来减少计算复杂度：部分和技术(Partial-sum)；快速傅里叶变换(FFT)。密钥扩展算法相对简单，轮密钥之间有很多关系，所以我们利用部分和技术；S盒存在一定的扩散性，但是对于某些输出比特而言，只和部分输入比特有关。--20--三、PRIDE密码线性分析的具体过程定理对于一个4×4比特规模的S盒运算，则下面两个条件等价：(a)截断差分特征概率为1。(b)设线性逼近的输出掩码为(0,1,0,0)。若偏差非零，则输入掩码的第1比特必为零，就是只能从集合中取值，其中?表示该比特位置未知。S(1,0,0,0)(,0,,)盒？？？{|(0,?,?,?)},--21--三、PRIDE密码线性分析的具体过程定理仅仅是描述了一个最简单的形式，当然不局限于4比特规模的运算；定理直觉上非常简单明了，证明也很简单；从不同角度反映一个问题，S盒输出某些比特和输入某些比特无关。S盒S盒(a)S盒的差分性质(b)S盒的线性性质1000？0？？0？？？0100输入差分输出差分输入掩码输出掩码P=1Ɛ≠0--22--三、PRIDE密码线性分析的具体过程推论对于PRIDE算法采用的S盒运算，若偏差非零的线性逼近的输出掩码为(0,1,0,0)，则输入掩码具有形式(0,?,?,?)；性质对于PRIDE算法采用的S盒运算，若差分特征的输入差分为(1,0,0,0)，则输出差分具有形式(?,0,?,?)。从上面的定理和性质，可得到关于S的线性性质：--23--三、PRIDE密码线性分析的具体过程I10000????0???00000000????????0000????????000000000???????00000000X10000????0???00000000????????0000????????000000000???????00000000Y10000??0?0?0000000000?0??00?0000000?0?0??000000000?00??0?00000000Z10?000?000?000?000??000000000??0000000??0??0000000?0000?000?00?00W10?0000000?0000000?0000000?0000000?0000000?0000000?0000000?000000I20000????0000000000000000000000000000????000000000000000000000000X20000000100000000000000000000000000000001000000000000000000000000Y20000000000000000000000000000000000000001000000000100000001000000Z20000000000000000000000000000000000000001000000000100000001000000W20000000100000000000000000000000000000001000000000000000000000000I3000000010000000000000000000000000000000100000000000000000000000018轮PRIDE分析中部分加密过程--24--Step3建立统计量()()1,3,[(,)(,)]1,3,1[][](1)iipartialpartialpartialpartialNfmkgckpartialpartialiTkk对于正确密钥(k1,partial,k3,partial)，定义二元随机变量序列:()()1,3,(,)(,)(1)iipartialpartialpartialpartialfmkgcki22()()1111(1),(1)2222kkiipp2()()1(1)(1)(1)kiiiEpp2()222()()[()]1[]kiiiDEE相互独立(1)(1)(2)(2)()()(,),(,),,(,)NNpartialpartialpartialpartialpartialpartialmcmcmc1,3,[][]partialpartialTkk相互独立12,,,N中心极限定理近似服从正态分布期望：Nε(k2)方差：N(1-[ε(k2)]2)期望：方差：因三、PRIDE密码线性分析的具体过程--25--数据复杂性（已知明文量N）阈值d数据量N成功率错误密钥构成的候选密钥数量M2212[1]2rdExNpedx2212(21)[1]2xdmNMedx2()krEN候选密钥数量M2212xdNedxdN成功率rdEN22()()kkrENNNNNd数据复杂性的量级：O()系数由两个通过率决定三、PRIDE密码线性分析的具体过程2()k--26--三、PRIDE密码线性分析的具体过程明文剖分技术的思想是Biham和Carmeli在分析FEAL-8X提出的；就是变相的增大线性逼近的线性偏差，来减少已知明文量；FEAL-8X提供非线性运算的是模加运算，输出比特和相应以及相邻位置的输入比特有较大的关系；对于某些轻量级分组密码算法，S盒规模通常比较小，也存在一定条件下线性偏差增大的情况，比如PRIDE算法的S盒运算。--27--三、PRIDE密码线性分析的具体过程（x1,x2,x3,x4）（y1,y2,y3,y4）线性逼近：440,yx成