Mickey-128的错误攻击
2011-04-23胡予濮
张 鹏,胡予濮,张 涛
(1.西安电子科技大学通信工程学院,陕西西安 710071;2.中国人民解放军69220部队司令部,新疆阿克苏 842000)
旁道攻击[1]不同于传统的密码分析,它是利用密码体制在具体实现过程中所表现出来的物理特性来分析密码参数的。威胁最大的旁道攻击手段有错误插入攻击(Fault Induction Attack),能量攻击(Power Attack),时间攻击(Timeing Attack)。本文介绍了一种Mickey流密码的错误引入攻击方法。
错误引入攻击是假设攻击者控制了密码设备,正确使用密码设备加密,同时在加密过程中可以引入错误,使加密过程受到影响,输出错误的加密结果。攻击者不知道密码设备中的信息,其目的是通过把引入错误后的输出结果与没有错误的结果进行对比,从而得到密码设备中的信息。
向设备中引入错误的类型可以分为以下几类。按照错误影响的时间可以分为永久错误与暂时错误。按照错误发生位置的不同,有的精确到某一比特引入错误,有的对一定的范围内引入错误。按照错误发生的时间不同,有的精确到某一时刻引入错误,有的在一定时间范围内引入错误。不同的错误类型在实现时会有不同的难易程度。
1 Mickey算法
Mickey[2]流密码是一种基于硬件的流密码,由Steve Babbage和 Matthew Dodd设计,后发展为Mickey2.0[3]和 Mickey - 128[4], 本 文 主 要 研 究Mickey-128。Mickey是在ECRYPT(European Network of Excellence for Cryptology)[5]计划中最终的胜出密钥之一,它具有设计简单、硬件容易实现等优势。
密码算法包括一个128位的密钥种子K以及一个初始化变量iv,iv的长度是0~128中的任意值,iv的长度记做ivlength,2个160位的寄存器记做R和S。
1.1 R寄存器
PRAPS={0,4,5,8,10,11,14,16,20,25,30,32,35,36,38,42,43,46,50,51,55,56,57,60,61,62,63,65,66,69,73,74,76,79,80,81,82,85,86,90,91,92,95,97, 100, 101, 105, 106, 107, 108, 109,111,112,113,115,116,117,127,128,129,130,131,133,135,136,137,140,142,148,150,152,153,154,156,157}
函数定义 CLOCK_R(R,INPUT_BIT_R,CONTROL_BIT_R)
r0,r1,…,r159表示前一时刻寄存器中的状态。r0',r1',…,r159'表示后一时刻寄存器中的状态。式中,“⊕”表示异或运算,“·”表示与运算。
1.2 S寄存器
先定义 4个序列:COMP01,…,COMP0158、COMP11,…,COMP1158、FB00,…,FB0159、FB10,…,FB1159。
COMP0i={0,1,1,1,1,0,1,0,0,1,0,0,1,1,1,1,0,1,1,0,1,0,1,1,1,0,1,1,1,0,1,0,1,0,1,0,1,0,1,0,1,0,0,1,0,0,0,0,0,1,1,0,0,1,0,0,1,0,0,1,1,1,1,0,0,1,0,0,0,1,1,0,0,0,0,0,1,1,1,0,0,0,0,0,0,0,0,0,1,0,0,1,1,1,1,0,1,0,0,0,1,1,0,0,1,0,0,1,1,0,1,1,1,1,1,1,0,1,0,1,1,1,1,0,1,1,0,0,0,1,1,1,1,1,0,1,0,1,1,0,0,0,0,0,0,1,1,1,1,1,0,1,1,1,1,1,0,0,0,0};
1≤i≤158
COMP1i={0,0,0,0,1,1,0,0,1,1,1,1,1,0,0,0,1,0,0,1,1,0,0,0,1,0,1,1,1,1,1,0,0,0,0,1,1,0,0,1,0,0,1,1,1,1,0,0,0,1,1,0,1,1,0,1,0,1,1,1,1,1,1,1,0,0,0,0,0,1,1,1,1,1,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,0,1,0,1,0,0,0,1,0,1,1,0,0,0,1,1,1,0,0,0,0,0,1,1,0,0,1,1,0,0,1,1,0,1,0,1,0,1,1,0,1,1,1,0,1,1,0,1,0,0,0,1,0,1,1,1,1,1,1,1,1,1,1,1,0};
1≤i≤158
FB0i={1,1,1,1,0,1,0,1,1,1,1,1,1,0,0,0,0,0,1,1,1,1,0,0,0,0,1,0,0,0,1,1,0,1,0,0,0,1,0,0,1,1,0,0,0,1,0,1,1,1,1,1,0,1,0,0,0,1,1,1,0,0,0,0,1,0,0,0,0,0,0,1,1,0,1,1,0,0,1,0,1,0,1,0,0,1,1,1,0,1,1,0,0,1,1,0,1,0,0,0,1,0,0,1,1,1,0,1,0,0,1,0,0,0,1,0,1,0,1,0,0,0,1,0,1,0,1,1,1,0,0,0,0,0,1,1,1,1,0,1,0,0,0,0,1,1,0,0,0,1,1,0,1,1,0,0,0,0,0,1};
0≤i≤159
FB1i={1,1,0,1,0,1,0,1,1,1,1,0,1,1,1,0,0,0,1,0,1,1,1,1,1,1,0,1,1,0,0,1,0,0,0,0,1,0,0,1,0,0,1,1,0,0,0,1,1,0,0,1,1,1,1,0,0,0,0,0,1,1,1,0,0,1,1,0,1,1,0,1,0,0,0,1,1,0,0,0,0,1,0,1,1,0,0,1,1,1,1,1,0,1,1,0,1,1,1,0,0,1,1,1,0,1,1,1,1,1,1,0,1,1,0,1,0,0,1,0,0,0,1,1,0,1,1,0,1,1,1,1,0,1,1,1,0,0,0,0,0,0,0,1,1,1,1,0,0,1,0,1,1,0,0,0,1,0,0,0};
0≤i≤159
函数定义 CLOCK_S(R,INPUT_BIT_S,CONTROL_BIT_S)
s0,s1,…,s159表示前一时刻寄存器中的状态。,…,159表示寄存器的中间状态。s0',s1',…,s159'表示后一时刻寄if存器中的状态。
1.3 寄存器的混合
混合函数定义为 CLOCK_KG(R,S,INPUT_BIT)
CONTROL_BIT_R=s54⊕r106
CONTROL_BIT_S=s106⊕r53
If MIXING=TRUE,
CLOCK_R(R,INPUT_BIT_R=INPUT_BIT⊕s80,CONTROL_BIT_R=CONTROL_BIT)
CLOCK_S(S,INPUT_BIT_S=INPUT_BIT,CONTROL_BIT_S=CONTROL_BIT)
If MIXING=FALSE,
CLOCK_R(R,INPUT_BIT_R=INPUT_BIT,CONTROL_BIT_R=CONTROL_BIT)
CLOCK_S(S,INPUT_BIT_S=INPUT_BIT,CONTROL_BIT_S=CONTROL_BIT)
1.4 R密钥种子的输入及初始化
先将寄存器R和S置全0。输入iv
For 0≤i≤ivlength -1
CLOCK_KG(R,S,MIXING=TRUE,INPUT_BIT=ivi)
输入k
For 0≤i≤127
CLOCK_KG(R,S,MIXING=TRUE,INPUT_BIT=ki)
输入全0
For 0≤i≤159
CLOCK_KG(R,S,MIXING=TRUE',INPUT_BIT=0)
1.5 获得密钥流
For 0≤i≤L -1
zi=r0⊕s0
CLOCK_KG(R,S,MIXING=FALSE,INPUT_BIT=0)
2 攻击方法
2.1 攻击模型
根据文献[6]提出的错误攻击模型,假设攻击者能在生成密钥流阶段和初始化阶段中在特定的时刻向某些特定位置上引入一个到两个错误。此外,攻击者可以多次重启密钥生成机,其目的是通过比较错误引入前后密钥流的变化,从而确定寄存器内部初始状态的信息。
2.1 攻击步骤
第1步 在产生密钥流的过程引入错误。从而求解出初始化完成之后寄存器R和S的状态。
z0,z1,…表示第0,1,…时刻的输出密钥。
用同样的方法,反复多次,解出每一时刻的r159,cr,s158,s159,cs。从而计算出初始化完成之后寄存器R和S的所有准确的状态。
第2步 在已知初始化结束后寄存器R和S的所有准确状态的情况下。在初始化过程中向寄存器R和S引入错误求解出密钥种子。
在初始化过程中,有3个阶段,输入iv,输入K,输入全0。
在输入全0的过程中,如果已知后一时刻的全部状态和前一时刻的控制位 CONTROL_BIT_R、CONTROL_BIT_S就能计算出前一时刻的状态。已知初始化结束后的寄存器状态,现在可以假设控制位,即CONTROL_BIT_R和CONTROL_BIT_S分别为00、01、10、11,从而计算出前一时刻的状态,再来验证之前假设的控制位是否正确。在验证过程中,有两种情况:一种是只有一个假设成立;另一种是有两个或多个假设成立。如果是第一种情况,就直接计算出前一时刻状态。若是第二种情况,在该时刻向寄存器R和S同时引入错误,然后记录其输出结果。另外计算出多种假设成立时的前一时刻状态,在同样的位置引入错误,计算其输出密钥流,与实际引入错误后的输出密钥流比较,排除不同的。从而得到正确的前一时刻状态。通过160轮计算可以计算出在输入密钥种子之后的寄存器状态。
用同样的方法作用于输入K的过程,在这个过程中不只要假设控制位,还要假设ki,再用排除法计算出ki和前一时刻状态。在这个过程中,只有一种假设成立的情况很少,所以每轮都要引入错误。再通过128轮计算,解得密钥种子和输入密钥种子之前寄存器的状态。
计算iv方法不变,只是计算完成1轮后要监测计算出的寄存器状态,直到检测到状态为全0。计算的轮数为ivlength。同时解出iv。
3 引入错误攻击的软件模拟
用C++语言编写程序,模拟实现了攻击算法。并且每次随机选取密钥种子,都能准确地计算出密钥种子。在密钥流生成阶段插入640次错误,需要960个密钥就可以计算出寄存器R和S在密钥流生成阶段的初始状态,恢复整个密钥流。在得出寄存器R和S在密钥流生成阶段的初始状态的前提下,在初始化阶段最坏的情况下插入416次错误,需要12480个密钥就可以计算出密钥种子K和初始值iv。
4 结束语
给出了一种对Mickey流密码的引入错误攻击方法,要求攻击者能够在任意时刻向寄存器的任意位置引入错误,实验证明了其可行性。
[1] QUISOUATER J J,RIZK M.Side channel attacks[EB/OL].(2008-9-12)[2010-11-2]http://www.ipa.go.jp/se-curity/enc.
[2] BABBAGE S,DODD M W.The stream cipher MICKEY IST-2002-507932,[EB/OL].(2007-09-11)[2010-12 -28]http//www.ecrypt.eu.org/stream.
[3] BABBAGE S,DODD M W.The stream cipher MICKEY 2.0,revised ECRYPT stream cipher submission[EB/OL].(2009-03-12)[2010-12-28]www.ecrypt.com.
[4] BABBAGE S,DODD M W.The stream cipher MICKEY-128 2.0,revised ECRYPT stream cipher submission[EB/OL].(2009-05-03)[2010-12-28]www.ecrypt.com.
[5] Ecrypt.eSTREAM:ECRYPT stream cipher project,IST -2002-507932[EB/OL].(2010-07-18)[2011-01-12]http://www.ecrypt.eu.org/stream.
[6] HOCH J J,SHAMIR A.Fault analysis of stream ciphers[C].Heidelberg:CHES 2004,LNCS,Springer,2004,3156:240-253.