MICKEY的错误攻击研究
摘要
Mickey (Mutual Irregular clocking KEY)是E-STREAM工程最终胜选的流密码算法之一。该算法基于硬件实现,是由Steve Babbage和Matthew Dodd设计的,后发展为Mickey2.O和Mickey-128。由于算法设计简单,易于实现,Mickey受到了密码学界的广泛关注。
本文通过分析Mickey,密码体系的设计弱点,结合错误攻击方法,提出了一种对Mickey-128的攻击方案。主要工作如下:
(1)分析Mickey-128密码体系,找出在错误攻击下暴露出的弱点:寄器S的CONTROL比特对改变寄存器下一时刻的状态起了决定性作用,但对下一时刻输出的密钥流没有影响,这降低了输出函数的安全性;寄存器内部状态转化的布尔函数在一些情况下是可逆的,这降低了内部状念转化的复杂度。
(2)对提出的错误攻击方案进行了仿真,证明了方案的可行性和高效性。得出如下结论:当插入640次错误时,需要960个密钥流,可以计算出寄存器的初始状态,恢复密钥流;在此的基础上再捅入416此错误时,最坏的情况下需要12480个密钥流,可以计算出密钥种子K和仞始化变量IV。
Mickey (Mutual Irregular Clocking KEY) is one of the final winner algorithms in the project of E-STREAM which was designed by Steve Babbage and Matthew Dodd, and was developed to Mickey2.0 and Mickey-128. As the algorithm is designed to be simple and easy hardware implementation, Mickey has been widely concerned in cryptography.
This paper analysis the weakness of Mickey, use the fault attacks, proposes a new scheme of fault attack to Mickey-128. the main contributions are as follows.
(l)With analyzing Mickey-128 we find out te weakness when it attacked with fault attack: CONTROL bit of the register R is an instrument in changing state, but it do not affect the stream key, so security of the putout-function is reduced; the boolean-function that can change the internal state meybe reversible, so complexity of changeing the internal state is reduced.
(2)We imitate the scheme of fault attack with sofeware, and prove its probability, and efficiency.
We have conclusion as follow: When we induct 640 fault and have 960 stream key, we can find the initial state of register R and S, and find the all stream key. When we induct 416 fault and have 12480 stream key, we can find the key-seed K and the initialization variable IV.
本文通过分析Mickey,密码体系的设计弱点,结合错误攻击方法,提出了一种对Mickey-128的攻击方案。主要工作如下:
(1)分析Mickey-128密码体系,找出在错误攻击下暴露出的弱点:寄器S的CONTROL比特对改变寄存器下一时刻的状态起了决定性作用,但对下一时刻输出的密钥流没有影响,这降低了输出函数的安全性;寄存器内部状态转化的布尔函数在一些情况下是可逆的,这降低了内部状念转化的复杂度。
(2)对提出的错误攻击方案进行了仿真,证明了方案的可行性和高效性。得出如下结论:当插入640次错误时,需要960个密钥流,可以计算出寄存器的初始状态,恢复密钥流;在此的基础上再捅入416此错误时,最坏的情况下需要12480个密钥流,可以计算出密钥种子K和仞始化变量IV。
Mickey (Mutual Irregular Clocking KEY) is one of the final winner algorithms in the project of E-STREAM which was designed by Steve Babbage and Matthew Dodd, and was developed to Mickey2.0 and Mickey-128. As the algorithm is designed to be simple and easy hardware implementation, Mickey has been widely concerned in cryptography.
This paper analysis the weakness of Mickey, use the fault attacks, proposes a new scheme of fault attack to Mickey-128. the main contributions are as follows.
(l)With analyzing Mickey-128 we find out te weakness when it attacked with fault attack: CONTROL bit of the register R is an instrument in changing state, but it do not affect the stream key, so security of the putout-function is reduced; the boolean-function that can change the internal state meybe reversible, so complexity of changeing the internal state is reduced.
(2)We imitate the scheme of fault attack with sofeware, and prove its probability, and efficiency.
We have conclusion as follow: When we induct 640 fault and have 960 stream key, we can find the initial state of register R and S, and find the all stream key. When we induct 416 fault and have 12480 stream key, we can find the key-seed K and the initialization variable IV.
引文
[1] C.E.Shannon. A Mathematical Theory of Communication, Bell SystemTechnical Journal,27(1948),Part 1,479-523.
[2] C.E.Shannon. Communication Theory of Systems,BellSystem TechnologyJoural,1949,Vol.28,pp.656-715.
[3] W.Difie, M.E.Hellman. New Direction in Cryptography, IEEE Transaction onInformation Thery,1976,Vol.IT22,No.6,pp.644-654.
[4] National Institute of Standards and Technology (NIST), USA, AdvancedEncryption Standards (AES), FIPS-197, 2001.
[5] NESSIE: New European Schemes for Signatures, Integrity,and Encryption.Available at http//www.cryptonessie.org,1999.
[6]丁存生，肖国镇.流密码学及其应用。北京：国防工业出版社，1994。
[7]五勇.一次一密的安全性与新保密体制。信息网络安全，2004，43(7)：41-43。
[8]杨义先，林须瑞.编码密码学。北京：人民邮电出版社，1996。
[9]张木想，肖国镇.流密码中非线性组合函数的分析和设计。通信学报，1996，24(1)：48-52。
[10] T.Siegenthaler.“Correlation Immunity of Nonlinear Combining function forcryptographic application,”IEEE Transaction on information Theory. IT 30: 776 780.1984
[11] W. Meier, and O. Staffelbach, "Fast correlation attacks on certain streamciphers", Advances in Cryptology–EUROCRYPT'88, Lecture Notes in ComputerScience, vol 330, Springer-Verlag, pp. 301-314. 1988.
[12] T.Johansson and F.J.nsson, "Fast correlation attacks through reconstruction oflinear polynomials," appear in Advances in Cryptology-CRYPTO'2000, Lecture Notesin Computer Science, Springer-Verlag, 2000.
[13] N.Courtois, W.Meier. Algebraic Attacks on Stream Ciphers with LinearFeedback. Advance in Cryptology Eurocrypt 2003, LNCS 2656. Berlin:Springer-Verlag,2003:345-359.
[14] A.Mohammad, R.Mirghadri. A Distinguish attack on COSvd Cipher, WorldAcademy of Science, Engineering and Technology,11,2005.
[15] Biham,E.shamir,A.Differential Cryptanalyeie of the Dada EncryptionStandard,Spring-Verlag,1993.
[16] H.Ahmadi and T.Eghlidos, Advanced Guess and Determine Attacks onStream Ciphers, IST 2005, pp. 87-91, 2005.
[17] Jin Hong and Palash Sarkar, Rediscovery of the Time Memory Tradeoff,Cryptology ePrint Archive, Report 2005/090, 2005.
[18] Rechberger, Oswald. Stream Ciphers and Side-Channel Analysis. In:SASC2004-The State of the Art of Stream Ciphers, Workshop Record, pp 320-326(2004),http//www.ecrypt.eu.org/stream.
[19] ECRYPT. http://www.ecrypt.eu.org/stream/.
[20] eSTREAM: ECRYPT Stream Cipher Project, IST-2002-507932. Available athttp//www.ecrypt.eu.org/stream.
[21] S.Babbage, M.W.Dodd, The stream cipher MICKEY IST-2002-507932.Available at http//www.ecrypt.eu.org/stream.
[22] S.Babbage, M.W.Dodd, The stream cipher MICKEY 2.0, revised ECRYPTstream cipher submission, expected to become available via the ECRYPT web site.
[23] S.Babbage, M.W.Dodd, The stream cipher MICKEY-128 2.0, revisedECRYPT stream cipher submission, expected to become available via the ECRYPTweb site.
[24]臧玉亮，曾光. MICKEY流密码算法的能量攻击。解放军理工大学学报。2009，10-4.
[25] QUISOUATER J J, RIZK M. Side channel attacks [EB/OL]. [2008-9-12].http://www.ipa.go.jp/se-curity/enc/CRYPTREC/fy15/doc/1047Side.Channel.report.pdf.
[26] KOCHER P , JAE J , JUN B , et al. Differential power analysis [C].Berlin:Springer-Verlag,1999.
[27] ZHOU Yong-bin, FENG Deng-guo. Side-Channel attacks:ten years after itspublication and the impacts on cryptographic module security testing [EB/OL].[2008-4-22]. http://eprint.iacr.org/2005/388.pdf.
[28] Anderson,Security engineering,New York，John Wiley&Sons Inc．2001
[29] Boneh,DeMiilo,and Lipton．On the Importanc．of CheckingCryptographicProtocols for Faults,Advances in Cryptology,proceedings ofEUROCRYPT’97，Locturc Notes in Computer Science,1997，v01．1294,PP．37-51
[30]E．Biham and A．Shamir,Differential Fault Analysis of SecretKeyCryptosystems．Loclurc Notes in Computer Science, 1997, v01．1a94,PP．513-525
[31] Marc Joye，Arjen K．Lenstra and Jean-Jacques Ouisquater,ChineseRemaindering Based Cryptosystems in the Presence of Faults,Journal ofCryptology,1999,vol。12,no．4,pp241-245
[32] I．Biehl，B．Meyer and V．Muller,Differential Fault Attacks 011 elliptic eulvecryptosystems，I．,ecture Notes in Computer Science，2000,v01．1880,ppl31
[33] Johannes BlOmer,Martin Otto and Jean-Pierre Seifert,Sign Change FaultAttacks on elliptic cnlNe cryptosystems，Cryptology ePrint Archive，Report 2004/227.
[34] Mitsuru Matsui，Linear crypmnalysis method for DES cipher,Workshop Onthe theory and application of cryptographic techniques on Advances in cryptology,1994,pp386-397
[35] David Naccache and Claire Whlelan,Experimenting with Faults,Lattices andthe DSA,Cryptology ePrint Archive，Report 2004/277，http：//eprint．iacr．org/
[36] D．Page and F．Vercauteren，Fault and Side-Channel Attacks on Pairing basedcryptography,Report 2004/283
[37]高军涛，胡予濮，李雪莲。对自缩序列生成器的错误攻击.西安电子科技大学学报2006,33-5.
[38] Kocher P C. Timing Attacks on Implementations of Diffie-Hellman, RSA,DSS, and Other Systems[C]. 16th Annual International Cryptology Conference, SantaBarbara, USA, 1996; Berlin: Springer, 1996: 104-113.
[39] Ferguson N, Schneier B. Practical Cryptography[M]. 1st edition, New York:John Wiley & Sons, 2003.
[40] P.Kocher，Time attacks on implementations on Diffie-Hellmen，RSA，DSSand other systems，In Advances in Cryptology，CRYPTO96，1996. Springer LNCSl109．404一113．
[41] Quisquater J J，Samyde D．Electromagnetic analysis(EMA)：measures andcountermeasures for smart cards[c] //Proceedings of Smart Card Programming andSecurity(E-smart 2001)．U、IcS 2140．Berlin/Heidelberg：Springer-Verlag，2001：200-210
[2] C.E.Shannon. Communication Theory of Systems,BellSystem TechnologyJoural,1949,Vol.28,pp.656-715.
[3] W.Difie, M.E.Hellman. New Direction in Cryptography, IEEE Transaction onInformation Thery,1976,Vol.IT22,No.6,pp.644-654.
[4] National Institute of Standards and Technology (NIST), USA, AdvancedEncryption Standards (AES), FIPS-197, 2001.
[5] NESSIE: New European Schemes for Signatures, Integrity,and Encryption.Available at http//www.cryptonessie.org,1999.
[6]丁存生，肖国镇.流密码学及其应用。北京：国防工业出版社，1994。
[7]五勇.一次一密的安全性与新保密体制。信息网络安全，2004，43(7)：41-43。
[8]杨义先，林须瑞.编码密码学。北京：人民邮电出版社，1996。
[9]张木想，肖国镇.流密码中非线性组合函数的分析和设计。通信学报，1996，24(1)：48-52。
[10] T.Siegenthaler.“Correlation Immunity of Nonlinear Combining function forcryptographic application,”IEEE Transaction on information Theory. IT 30: 776 780.1984
[11] W. Meier, and O. Staffelbach, "Fast correlation attacks on certain streamciphers", Advances in Cryptology–EUROCRYPT'88, Lecture Notes in ComputerScience, vol 330, Springer-Verlag, pp. 301-314. 1988.
[12] T.Johansson and F.J.nsson, "Fast correlation attacks through reconstruction oflinear polynomials," appear in Advances in Cryptology-CRYPTO'2000, Lecture Notesin Computer Science, Springer-Verlag, 2000.
[13] N.Courtois, W.Meier. Algebraic Attacks on Stream Ciphers with LinearFeedback. Advance in Cryptology Eurocrypt 2003, LNCS 2656. Berlin:Springer-Verlag,2003:345-359.
[14] A.Mohammad, R.Mirghadri. A Distinguish attack on COSvd Cipher, WorldAcademy of Science, Engineering and Technology,11,2005.
[15] Biham,E.shamir,A.Differential Cryptanalyeie of the Dada EncryptionStandard,Spring-Verlag,1993.
[16] H.Ahmadi and T.Eghlidos, Advanced Guess and Determine Attacks onStream Ciphers, IST 2005, pp. 87-91, 2005.
[17] Jin Hong and Palash Sarkar, Rediscovery of the Time Memory Tradeoff,Cryptology ePrint Archive, Report 2005/090, 2005.
[18] Rechberger, Oswald. Stream Ciphers and Side-Channel Analysis. In:SASC2004-The State of the Art of Stream Ciphers, Workshop Record, pp 320-326(2004),http//www.ecrypt.eu.org/stream.
[19] ECRYPT. http://www.ecrypt.eu.org/stream/.
[20] eSTREAM: ECRYPT Stream Cipher Project, IST-2002-507932. Available athttp//www.ecrypt.eu.org/stream.
[21] S.Babbage, M.W.Dodd, The stream cipher MICKEY IST-2002-507932.Available at http//www.ecrypt.eu.org/stream.
[22] S.Babbage, M.W.Dodd, The stream cipher MICKEY 2.0, revised ECRYPTstream cipher submission, expected to become available via the ECRYPT web site.
[23] S.Babbage, M.W.Dodd, The stream cipher MICKEY-128 2.0, revisedECRYPT stream cipher submission, expected to become available via the ECRYPTweb site.
[24]臧玉亮，曾光. MICKEY流密码算法的能量攻击。解放军理工大学学报。2009，10-4.
[25] QUISOUATER J J, RIZK M. Side channel attacks [EB/OL]. [2008-9-12].http://www.ipa.go.jp/se-curity/enc/CRYPTREC/fy15/doc/1047Side.Channel.report.pdf.
[26] KOCHER P , JAE J , JUN B , et al. Differential power analysis [C].Berlin:Springer-Verlag,1999.
[27] ZHOU Yong-bin, FENG Deng-guo. Side-Channel attacks:ten years after itspublication and the impacts on cryptographic module security testing [EB/OL].[2008-4-22]. http://eprint.iacr.org/2005/388.pdf.
[28] Anderson,Security engineering,New York，John Wiley&Sons Inc．2001
[29] Boneh,DeMiilo,and Lipton．On the Importanc．of CheckingCryptographicProtocols for Faults,Advances in Cryptology,proceedings ofEUROCRYPT’97，Locturc Notes in Computer Science,1997，v01．1294,PP．37-51
[30]E．Biham and A．Shamir,Differential Fault Analysis of SecretKeyCryptosystems．Loclurc Notes in Computer Science, 1997, v01．1a94,PP．513-525
[31] Marc Joye，Arjen K．Lenstra and Jean-Jacques Ouisquater,ChineseRemaindering Based Cryptosystems in the Presence of Faults,Journal ofCryptology,1999,vol。12,no．4,pp241-245
[32] I．Biehl，B．Meyer and V．Muller,Differential Fault Attacks 011 elliptic eulvecryptosystems，I．,ecture Notes in Computer Science，2000,v01．1880,ppl31
[33] Johannes BlOmer,Martin Otto and Jean-Pierre Seifert,Sign Change FaultAttacks on elliptic cnlNe cryptosystems，Cryptology ePrint Archive，Report 2004/227.
[34] Mitsuru Matsui，Linear crypmnalysis method for DES cipher,Workshop Onthe theory and application of cryptographic techniques on Advances in cryptology,1994,pp386-397
[35] David Naccache and Claire Whlelan,Experimenting with Faults,Lattices andthe DSA,Cryptology ePrint Archive，Report 2004/277，http：//eprint．iacr．org/
[36] D．Page and F．Vercauteren，Fault and Side-Channel Attacks on Pairing basedcryptography,Report 2004/283
[37]高军涛，胡予濮，李雪莲。对自缩序列生成器的错误攻击.西安电子科技大学学报2006,33-5.
[38] Kocher P C. Timing Attacks on Implementations of Diffie-Hellman, RSA,DSS, and Other Systems[C]. 16th Annual International Cryptology Conference, SantaBarbara, USA, 1996; Berlin: Springer, 1996: 104-113.
[39] Ferguson N, Schneier B. Practical Cryptography[M]. 1st edition, New York:John Wiley & Sons, 2003.
[40] P.Kocher，Time attacks on implementations on Diffie-Hellmen，RSA，DSSand other systems，In Advances in Cryptology，CRYPTO96，1996. Springer LNCSl109．404一113．
[41] Quisquater J J，Samyde D．Electromagnetic analysis(EMA)：measures andcountermeasures for smart cards[c] //Proceedings of Smart Card Programming andSecurity(E-smart 2001)．U、IcS 2140．Berlin/Heidelberg：Springer-Verlag，2001：200-210