差分密码分析和线性密码分析原理

差分密码分析和线性密码分析原理CONTENTS0102差分密码分析线性密码分析PARTONE差分密码分析差分密码分析是迄今为止已知的攻击迭代分组密码最有效的方法之一，其基本思想是：通过分析明文对的差值对密文对的差值来影响来恢复某些密钥比特当密码分析人员可以进行选择明文分析时，差分密码分析十分有效。已知明文的差分密码分析也是可行的，但是要求已知明密文的量很大差分密码分析简介设计DES的IBM小组知道了差分分析197419911990……Biham和Shamir对多种加密算法和Hash函数进行差分密码分析攻击，结果发表在[BIHA93]中差分密码分析公开发表最早研究是Murphy分析分组密码FEAL【MURP90】差分密码分析的历史6符号定义P表示明文，T表示密文(P,P∗)表示明文对，其异或后得到特定的值：P’,使得P’=P⊕P∗(T,T∗)表示密文对，其异或后得到特定的值T’，使得T’=T⊕T∗带撇的值总是表示差分，P’,T’,a’,A’。例如，a’=a⊕a∗7差分密码分析_DESDES的设计要求之一是确保尽可能的分布均匀例如，明文或密钥的1比特变化，将导致64比特的密文中大约32比特的看起来是不可预测和随机的变化不过对于固定的密钥，DES的差分并不呈现伪随机现象即对于固定明文P和P∗的异或P’T’=T⊕T∗不是均匀分布的8S-Box是非差分均匀的𝑺𝟏𝒙𝟏…𝒙𝟔：𝟔位输入，𝟒位输出对于输入S盒的6比特的(x,x∗)值对，一共有多少种可能？考虑一个S-box的差分现象：输入值对的差分为x’=x⊕x∗差分值可能有多少种？对于其4比特输出值，y=S(x),y∗=S(x∗)，以及y’=y⊕y∗=S(x)⊕S(x∗)输出差分值有多少种可能？642=409626=6424=16S-Box是非差分均匀的𝑺𝟏𝒙𝟏…𝒙𝟔：𝟔位输入，𝟒位输出x0123456789abcdefx⊕f’fedcba9876543210S(x)e4d12fb83a6c5907S(x⊕f’)7095c6a38bf21d4ES(x)⊕S(x⊕f’)9444e91bb19e4449输入差分f’=111110S1的差分分布表０.........６３=26-1出现的次数6比特的差分输入x’有64个值：00-3F(16进制，10进制是0-63)4比特的差分输出y’有16个值：0-F(16进制，10进制是0-15)可以看到：第一行除第一列外全为0，因为当x’=x⊕x∗=0，同样的输入出现了两次，因此其输出y’=y⊕y∗=0后面的行：例如，当x’=01时,6个可能的y’中有5个值:0,1,2,4,8呈现0可能次数，就是说不出现。A出现的概率是12/649和C出现的概率是10/64这就是说，S1呈现出很强的不均匀分布这种差分不均匀性对于所有的S盒S1,S2,...,S8都有体现考虑输入异或值为34时，可能的输出异或是：其中：344有两种可能，这种输入对是成双的，即：(α,β)和(β,α)S1的差分分布表对S1构建差分表，发现当输入是13和27时(只看后面的6位)：12S1的差分分布表12列出S1中输入异或值为34的可能的输入值(16进制)：13确定密钥的原理假设已知S1的两个输入是01和35，其异或的结果是34，经过S1之后输出异或的结果是D。查S1的差分分布表，得到输入异或为34，输出异或为D时，可能的输入：14确定密钥的原理14实际上，输入异或的结果是34，与密钥无关，这是因为：因为所以这样就得到：所以，可能的密钥就是15确定密钥的原理此外，假设已知S1的两个输入是21和15，它们异或后的结果是34，输出异或后的结果是3。查S1的差分分布表，得到输入异或为34，输出异或为3时，可能的输入：。16确定密钥的原理16这样就可以从得到可能的密钥值17确定密钥的原理17而正确的密钥值必定同时出现在两个集合因此可以确定密钥是在中的一个。要确定到底是哪一个，需要知道更多的输入输出异或对。以此类推得到此轮密钥18多轮DES的特征差分输入具有很高的或然性，可以直接追踪到多轮的情况，观察到：E扩展中的异或值是线性的：异或值与密钥是无关的：192轮DES的特征差分密码分析20在第一轮中，输入到函数f的差分结果是a’=60000000经f中的扩展变换后，把这部分放进了每个S盒的中间4个比特，顺序是S1：6=0110S2：0=0000S3,...,S8等等因为所有边缘比特都是0，所以S1是唯一的得到非0差分输入的S盒。S1的差分输入是001100=0C而其他所有Ｓ盒S2,...,S8的差分输入都是０2轮DES的特征差分密码分析21察看S1的差分分布表，发现当输入异或x’=0C时，最可能的差分输出y’是E=1110，出现的概率是14/64；其他Ｓ盒的输入一定是x’=0且y’=0Ｓ盒的输入通过置换Ｐ成为f(R,K)的输出。如前所述，f(R,K)的差分输出是而A’与L’异或后得到00000000，因为2轮DES的特征差分密码分析000000001000000010000010000000101110000000000000000000000000000022所以,在第２轮后，所有Ｓ盒都得到差分输入０，产生的差分输出也是０；f(R,K)的输出在２轮后是０，差分输出则是(00000000,60000000)2轮DES的特征差分密码分析23假定：去掉初始置换IP和最终置换FP。2轮的差分分析共有７个步骤。Step1:产生明文对(P,P∗)，使得办法是，随机产生一个P，将其与下述值进行异或得到P∗2轮DES的特征差分密码分析24Step2:对于产生的明文对(P,P∗)，计算加密后产生密文对(T,T∗)（选择明文攻击）Step3:计算T’=T⊕T∗，检查结果是否等于如果不相等，就说明特征不符，这个明文对就不能用。重返第一步，产生新的明文对；如果相等，则特征相符，进入第四步2轮DES的特征差分密码分析25Step4:因为S2,...,S8的差分输入都为０，所以没有信息可以从S2K,...,S8K得到。在S1的差分分布表中，0C→E有14/64的概率，即只有64分之14可以得到产生2轮DES的特征差分密码分析这14个可能值可以通过把每个可能的S1K与相应的S1E和S1∗E的６比特相异或来确定，计算S1的差分输出S1’，检查其是否等于E,把S1K的这14个值放进表中26Step5:计算这些表的交集因为正确的密钥必定同时出现在每张表中如果有不止一个S1K值，就说明还需要更多的明文和密文差分对才能唯一确定密钥S1K，转到第一步，计算更多的数据需要的明文密文差分对的数量，大致等于使用的特征概率的倒数，本例中需要64/14≈5对如果只得到一个S1K，就是正确的，转到第六步。2轮DES的特征差分密码分析27Step6:这个阶段，要恢复构成S1K的6个比特。采用类似的特征，恢复第一轮中与S2-S8的输入相异或的6比特密钥Step7:这个阶段已经有了构成S1K密钥的48比特，等同于S1K-S8K。其余的８比特密钥，采用穷举方法在64个可能的值中搜寻2轮DES的特征差分密码分析差分密码分析破解DES效率R轮迭代密码的差分攻击步骤r-轮特征Ω=α0α1……α𝑟的概率是指在明文和子密钥𝑘1,𝑘2,......,𝑘𝑟独立,均匀随机时,明文对m和m*的差分为α0的条件下,第i(1≤i≤r)轮输出c(i)和c*(i)的差分为α1的概率(或称为特征Ω的差分扩散率)。若r-轮特征Ω=α0α1……α𝑟满足(1)m与m*的差分为α0；(2)第i轮输出c(i)与c*(i)的差分为α1(1≤i≤r),则称明文对m与m*是一个正确对，否则称其为错误对。定义R轮迭代密码的差分攻击步骤1)找出一个（r−1）轮Ω=α0α1……α𝑟,使它的概率达到最大或几乎最大.2)均匀随机地选择明文m,并计算出m*,使m⊕m*=α0,再找出m和m*在实际密钥加密下所得的密文c(r)和c*(r).3)若最后一轮的子密钥𝑘𝑟（或𝑘𝑟的部分比特）有2𝑚个可能的值𝑘𝑗𝑟(1≤j≤2𝑚),我们就设置2𝑚个相应的计数器δ𝑗(1≤j≤2𝑚),用每一个可能的密钥解密c(r)和c*(r)得到c(r−1)和c*(r-1).若c(r−1)+c*(r-1)=α𝑟−1,则给相应的计数器δ𝑗加1。4)重复第2、3步,直到有一个或几个计数器的值明显高于其它计数器的值,输出它们所对应的子密钥（或部分比特）。攻击成功！对r轮迭代密码的差分攻击的步骤如下:PARTTWO线性密码线性密码分析概述•线性密码分析的基本思想是通过寻找一个给定密码算法有效的线性近似表达式来破译密码系统。由于每个密码系统均为非线性系统，因此只能寻找线性近似表达式。•线性分析的分析者利用了包含明文、密文和子密钥的线性表达式发生的较大可能性。线性密码分析的基本方法线性密码分析的方法是寻找一个给定密码算法的具有下列形式的“有效的”线性表达式这里𝑖1,𝑖2,…,𝑖𝑎；𝑗1,𝑗2,…,𝑗𝑏和𝑘1,𝑘2,…,𝑘𝑐,表示固定的比特位置。随机给定的明文P和相应的密文C上面的等式成立的概率p≠1/2线性密码分析的基本方法——相关定理设𝑋1,𝑋2,…,𝑋𝐾是取值于集合{0,1}的独立随机变量.设𝑝1,𝑝2,….都是实数,且对所有的i,i=1,2,…,k有0≤𝑝𝑖≤1,再设Pr[𝑋𝑖=0]=𝑝𝑖,则Pr[𝑋𝑖=1]=1−𝑝𝑖.对取值于{0,1}的随机变量,用分布偏差来表示它的概率分布.随机变量Xi的偏差定义为ε𝑖=𝑝𝑖−12（堆积引理.Piling-uplemma）设𝑋1,𝑋2,…,𝑋𝐾是取值于集合{0,1}的独立随机变量.ε𝑖1𝑖2……𝑖𝑘表示随机变量𝑋𝑖1⊕𝑋𝑖2…⊕𝑋𝑖𝑘的偏差,则ε𝑖1𝑖2……𝑖𝑘=2𝑘−1ε𝑖𝑗𝑘𝑗−1线性密码分析的基本方法用堆积引理,我们可以将每轮变换中偏差最大的线性逼近式进行组合,组合后的所有轮变换的线性逼近式,也将拥有最佳的偏差,即寻找分组密码的最佳线性逼近式.由上述分析我们知道,分组密码的最佳线性逼近式的寻找,归结为每轮线性逼近式的寻找,而每轮的变换中,除了非线性变换(即S-盒)部分,线性部分是自然的线性关系,也就是说,每轮线性逼近式的寻找,只需寻求S-盒部分的最佳线性逼近式.subkeyK1mixingC1…..ciphertext……C16S11S12S13S14subkeyK2mixingS21S22S23S24subkeyK3mixingS31S32S33S34subkeyK4mixingsubkeyK5mixingS41S42S43S44P1…..plaintext……P16线性密码分析例子——SPN算法的输入为16比特的数据块，并且重复四次相同操作处理数据块。•每一轮包括•1)S-box置换•2）比特变换•3）密钥混合。•S-box置换S-box的最基本的性质是其非线性映射，S-box的输出不能通过输入的线性变换而得到。input0123456789ABCDEFoutputE4D12FB83A6C5907线性密码分析例子——SPNinput12345678910111213141516output15913261014371115481216•P置换（其中的数字表示比特的位置，1表示最左边的比特，16表示最右边的比特）4×4S-boxX1X2X3X4Y1Y2Y3Y4分析加密部件在下图中的S-box中考虑表达式X2X3Y1Y3Y4＝0或等价形式X2X3＝Y1Y3Y4。4×4S-boxX1X2X3X4Y1Y2Y3Y4线性密码分析例子——SPN例子：对于16种可能的输入X和其相应的输出Y，有12种情况可以使得该式成立，因此线性可能性偏移量是12/16－1/2＝1/4。相似的，对于等式X1X4＝Y2其线性可能性偏移量接近于0，而等式X3X4＝Y1Y4的线性可能性偏移量是2/16－