3.4密码攻击方法 3.42差分密码分析法 ■差分密码分析是采用选择明文统计分析 来攻击迭代分组密码的。 ■它主要分析明文差分和密文差分之间的 统计相关性
3.4 密码攻击方法 3.4.2差分密码分析法 差分密码分析是采用选择明文统计分析 来攻击迭代分组密码的。 它主要分析明文差分和密文差分之间的 统计相关性
■对于给定的r轮迭代密码,对已知分组长为n 的明文对B和B‘,其差分△B=B⑧B-1,其中⑧ 是所有n-bi构成的集合中所定义的群运算, B4-1是B在群中的逆元。 在密钥k控制下,各轮迭代所产生的中间密文 差分为: △X(i)=x(i)(x(i)10≤i≤r 当i=0时,X(0)=B,X(O=B',△X(0)=△B,而 最终的密文差分△X=△X(r) 由于明文对B≠B',故△X(i)≠e(群的单位元), 即△X(i)∈{0,1}n-{e}o 每轮迭代所用子密钥k与明文统计独立,并认 为是服从均匀分布的
对于给定的 r轮迭代密码，对已知分组长为 n 的明文对 B 和B‘，其差分 B=B B’-1，其中 是所有n-bit构成的集合中所定义的群运算， B‘-1 是B’在群中的逆元。 在密钥 k控制下，各轮迭代所产生的中间密文 差分为： X(i)=X(i) (X'(i))-1 0 ≤ i ≤ r 当i=0时，X(0)=B，X'(0)=B'，X(0)= B，而 最终的密文差分 X= X(r) 。 由于明文对 B B'，故 X(i) e(群的单位元 )， 即 X(i) {0,1} n-{e} 。 每轮迭代所用子密钥 k i与明文统计独立，并认 为是服从均匀分布的
■定义31:设a是两个不同明文B和B'的差分,b 是密码第轮输出X(i)和X()之间的差分,称 (a,b)为第轮差分。在给定明文的差分=△B条 件下,第轮出现一对输出的差分是b的概率称 为第论轮差分概率,记为P(b=△X(i)a=△B) ■以DES加密1轮为例了解差分分析攻击的过程
定义3.1：设 a是两个不同明文 B 和B'的差分， b 是密码第 i轮输出X(i) 和X'(i)之间的差分，称 (a,b)为第 i轮差分。在给定明文的差分a= B 条 件下，第 i轮出现一对输出的差分是 b的概率称 为第 i轮差分概率，记为P(b= X(i)|a= B) 。 以DES加密 1轮为例了解差分分析攻击的过程
DES的关键是S盒,设S是一个特定的S盒(is8 (B;B是一对长度为6b的串。B④B*作为S的输 入异或,S(BBS(B则为S的输出异或。 首先考虑对给定的a1∈Z26,把所有异或值为1的 (B,B“)拿来构成集合,即△(a)=(B,B1)B田B:*=a}。 △(a1)=2=64, 因为BB1=a;,所以B=Ba;,即 △(a)={(B,Ba)B1∈Z2} 对△(a)中的每一对,计算出S;的一个输出异或 共可计算出64个输出异或, S盒输出是4bit,只有24=16个可能的输出值 即64个输出异或分布在16个可能值上, 将这些分布列成表,分布的不均匀性就是差分攻击 的基础
DES的关键是 S盒，设 S j是一个特定的S- 盒(1 j 8)， (B j, B j*)是一对长度为6bit的串。 B j B j *作为 S j的输 入异或， S j(B j ) S j(B j*)则为 S j的输出异或。 首先考虑对给定的 a j Z 2 6，把所有异或值为 aj 的 (B j,B j*)拿来构成集合，即 (a j)={(B j,B j*)|B j B j*=a j } 。 |(a j)|=2 6=64， 因为 B j B j*=a j，所以 B j*=B j a j，即 (a j)={(B j,B j aj)|B j Z 2 6 } 。 对 (a j )中的每一对，计算出 Sj 的一个输出异或， 共可计算出64个输出异或， S j盒输出是4bit，只有 2 4=16个可能的输出值， 即64个输出异或分布在16个可能值上， 将这些分布列成表，分布的不均匀性就是差分攻击 的基础
■例3.1:S0的一个输入异或为110100,则 △(110100)={(0000010100),(000001, l10101),,(1111,001011}。 对△(110100)中的所有元素计算输出异或,并由 此统计各输出的分布,得表 00000001001000110100010101100111 8 16 0 12 10001001101010111100110111101111 0 8 0 6 16个可能的输出异或中实际仅出现了8个。实验表明,所 有可能的输出异或中实际上出现约75%~80%
例3.1：S0的一个输入异或为110100，则 (110100)={(000000,110100),(000001, 110101),, (111111,001011)}。 对(110100)中的所有元素计算输出异或，并由 此统计各输出的分布，得表： 0000 0001 0010 0011 0100 0101 0110 0111 0 8 16 6 2 0 0 12 1000 1001 1010 1011 1100 1101 1110 1111 60 0 0 0 8 0 6 16个可能的输出异或中实际仅出现了8个。实验表明，所 有可能的输出异或中实际上出现约75%～80%
对1≤8,长度为6bi的串a和长度为4bi的串b可和b 为给定的差分,分别是输入差分和输出差分) 定义3.2:IN(aj,bj)={Bj∈Z2Sj(Bj)由SjBj曲aj)=bj}, Nj(aj,bj)=INj(aj, bj) N(ajb)是S盒S具有输入异或a和输出异或b的明文 对数量。书上给出的是IN(110100,b)(bj∈Z24) 对8个S盒中的每一个,都有64个可能的输入异或,所 以共需计算512个分布,这可通过利用计算机得到。 在DES中,第谛轮S盒的输入可表示为B=E⊕J,其中 E=E(R1)是R1的扩展,J=K为第轮的工作密钥。输入 异或BAB=EAJ(E*J=EE*。输入异或与工作密 钥无关。但输出异或则与工作密钥有关。 B=B1B2B3B4B5BB2B3(48bi每个B为6bi
对 1 j 8，长度为6bit的串aj和长度为4bit的串bj(aj 和bj 为给定的差分，分别是输入差分和输出差分 ) 定义3.2：INj(aj,bj)={Bj Z 2 6|Sj(Bj) Sj(Bj aj)=bj}， Nj(aj,bj)=|INj(aj,bj)| Nj(aj,bj) 是S- 盒Sj具有输入异或aj和输出异或bj的明文 对数量。书上给出的是IN1(110100,bj)(bj Z 2 4 ) 对 8 个 S盒中的每一个，都有64个可能的输入异或，所 以共需计算512个分布，这可通过利用计算机得到。 在DES中，第 i 轮S-盒的输入可表示为B=E J，其中 E=E(Ri-1 ) 是 Ri-1的扩展，J=Ki为第 i轮的工作密钥。输入 异或 B B*=(E J) (E* J)=E E*。输入异或与工作密 钥无关。但输出异或则与工作密钥有关。 B=B 1 B 2 B 3 B 4 B 5 B 6 B 7 B 8(48bit,每个 Bi 为6bit)
E三E1E2E3E4E5E6E8 102304506708 B,E*也类似表示 攻击的目的是获得工作密钥,由此导出主密 钥。 假定对某个j(18)知道E和E的值,以及 S的输出异或b=S(BjS(B)Bj*= Bjeaj) INEi,b)={Pj∈Z2°Sj(Pj)⊕Sj(Pj⊕Ei)=bj}, 这里Ej=EjE。则正确的加密结果 EjJj∈INj(E'j,bj)
E=E 1 E 2 E 3 E 4 E 5 E 6 E 7 E 8 J=J 1 J 2 J 3 J 4 J 5 J 6 J 7 J 8 B *,E *也类似表示 攻击的目的是获得工作密钥，由此导出主密 钥。 假定对某个j(1 j 8)知道Ej 和Ej*的值，以及 Sj的输出异或bj=Sj(Bj) Sj(Bj*)(Bj*=Bj aj) 。 INj(E'j,bj)={Pj Z 2 6|Sj(Pj) Sj(Pj E'j)=bj} ， 这里E'j= Ej Ej*。则正确的加密结果 Ej Jj INj(E'j,bj)
tes(Ej,Ej,bj)={Bj⊕EjBj∈INj(Ej}。该集合是所有 j(Eib)中元素与E异或的值全体,故元素个数为 IINjCEj, bJNI(Ej,bj) 由于EJ∈INE,b,所以(EJ)E∈test(E,E,b), 即J;∈test(E;,E,b) 因此test(EiEj,b)中必有正确的工作密钥。 例3:设E1=00000,E1*=110101,b1=1101。故EI E1E1*=110100。 因为N(E1,b1)=8,故test(E"1,E1*,b1)有8个元素。从表中 可知IN(110100,1101 ={000110,010000,010110,011100,100010,100100,101000,11001 0},所以可以求得 testI(E'1,E1x,b1)={000111,010001,01011,011101,100011,100 101,101001,110011
testj(Ej,Ej*,bj)={Bj Ej|Bj INj(E'j,bj)}。该集合是所有 INj(E'j,bj)中元素与Ej异或的值全体，故元素个数为 |INj(E'j,bj)|=N1(E'j,bj) 。 由于 Ej Jj INj(E‘j,bj),所以(Ej Jj ) Ej testj(Ej,Ej *,bj )， 即 Jj testj(Ej,Ej*,bj ) 。 因此testj(E'j,Ej*,bj)中必有正确的工作密钥。 例3.2：设E1=000001,E1*=110101, b1=1101。故E1'= E1 E1*=110100 。 因为N1(E1',b1)=8，故test1(E'1,E1*,b1) 有 8个元素。从表中 可知IN1(110100,1101) ={000110,010000,010110,011100,100010,100100,101000,11001 0},所以可以求得 test1(E'1,E1*,b1)={000111,010001,010111,011101,100011,100 101,101001,110011}
如果还有第2组这样的三元组(E1,E1,b1 就可获得包含工作密钥J的第2个 test1,自 然』是这两个集合的交的元素。 ■如果拥有一系列三元组,就可确定J1。最直 接的方法是:建立一个有64个计数器的矩阵 记录工作密钥J1的64种可能情况。每计算 次test1,如果某些元素6bi在test中,则这 些元素所对应的计数器加1,否则不变。给 定个三元组(E1,E1,b1),希望能找到唯 的计数器,使得其值为t,则该计数器所对应 的6bit就是工作密钥J1
如果还有第 2组这样的三元组(E‘1,E1*,b1) ， 就可获得包含工作密钥J1的第 2 个test1，自 然J1是这两个集合的交的元素。 如果拥有一系列三元组，就可确定J1。最直 接的方法是：建立一个有64个计数器的矩阵， 记录工作密钥J1 的64种可能情况。每计算一 次test1，如果某些元素(6bit) 在test1中，则这 些元素所对应的计数器加 1，否则不变。给 定 t个三元组(E'1,E1*,b1)，希望能找到唯一 的计数器，使得其值为 t，则该计数器所对应 的6bit就是工作密钥J1
■对一个r轮迭代密码的差分分析攻击基本步骤是 (1)寻找第r-1轮差分(a,b)使概率 P(b=△X(r-1)a=△B)的值尽可能为最大。 (2)随机选择明文B,求另一明文B',使得B与B的差 分为a。 ◆(3)在密钥k下对B和B进行加密得到X(r)和X'(r), 并求出能使△X(r-1)=b的所有可能的第r轮密钥kr 并对各子密钥k(计数, 若选定的△B=a,明文对(B,B)在k(下产生的(X,X) 满足△X(r-1)=b,就将相应的k(的计数加1 (4)重复(2)、(3)步,直到计数的某个或几个字符串的 值,明显大于其他字符串的计数值,这一字符串或 几个子密钥就可作为对实际子密钥k的分析结果
对一个 r轮迭代密码的差分分析攻击基本步骤是： (1)寻找第r-1轮差分(a,b)使概率 P(b= X(r-1)|a= B)的值尽可能为最大。 (2)随机选择明文 B，求另一明文B'，使得 B 与B'的差 分为 a 。 (3)在密钥 k下对 B 和B'进行加密得到X(r) 和X'(r)， 并求出能使 X(r-1)=b的所有可能的第 r轮密钥 k(r)， 并对各子密钥 k i(r)计数， 若选定的 B=a，明文对(B,B') 在 k i(r)下产生的(X,X') 满足 X(r-1)=b，就将相应的 k i(r)的计数加 1 。 (4)重复(2) 、(3)步，直到计数的某个或几个字符串的 值，明显大于其他字符串的计数值，这一字符串或 几个子密钥就可作为对实际子密钥 k r的分析结果