分组密码AES分析方法研究
|
摘要
信息系统安全的紧迫性和网络通信安全的重要性使人们越来越对分组密码的相关理论感兴趣，分组密码的设计与分析也一直是密码学中的热点课题。分组密码作为现代密码学中的一个重要研究分支，其诞生和发展有着广泛的实用背景和重要的理论价值。
美国国家标准和技术研究所在经过一系列的评测后，从众多的分组密码中选中Rijndael算法，在2001年11月26日对外公布该算法作为AES算法[1,2,3,4]。AES算法作为美国数据加密标准算法，代表了国际密码界在分组密码设计与攻击领域的最高水平。因此对它的安全性分析是一个具有挑战性的课题，具有重大的密码学意义。围绕着AES算法的安全性分析，本文主要取得了以下研究成果：
1、利用中间相遇攻击方法成功实现了对AES算法的前身Square算法[3]的研究。建立一个四轮分析器，分析出字节之间的组合关系，利用中间相遇攻击的思想，加密五轮，解密一轮后得到的函数值与事先准备的函数集合里的函数值进行比较，进而验证猜测的密钥正确与否；
2、在倒数第四轮输入处植入故障，攻击了完整轮数的AES-128。在第七轮的输入诱导一个有故障差分的字节，进行四轮的运算得到错误密文值，通过正确密文与错误密文的差分值与字节之间的比例关系组成四个等式组，根据四个等式的比例关系猜测相关密钥，理论上需要使用两对明密文对就可以恢复正确的密钥。
The urgency of the information system security and the importance network communicati-ons of safety make people are increasingly interested in theories of block cipher, block cipheranalysis and design also has been a hot topic in cryptography. Block cipher is an importantresearch branch of modern cryptography, its birth and development has a wide range of practicalbackground and important theoretical value.
The USA National Institute of Standard and Technology Institute after a series of evaluation,selected Rijndael algorithm from a large number of block cipher , announced that the algorithmas the AES algorithm[1,2,3,4]in November 26, 2001. The AES algorithm as USA data encryptionstandard algorithm, represent the highest level of international cryptography sector in the field ofblock cipher design and attack. Thus safety analysis is a challenging task, and have a majorcryptography significance. Around the safety analysis of the AES algorithm, some achievementshave been obtained in this paper:
The meet-in-the-middle attack methods successful analysis the AES algorithm predecessorSquare algorithm. First, we constructed a fourth round differentiator, then used the differentiatorto analyze the relations between bytes,used the idea of meet-in-the-middle attack,encryption fiveround，compare the values obtained by this decryption to the values in the precomputed set, thenverify that whether the guessed key correct or not;
Induce a fault at the input of the last fourth round, attack complete AES-128. Induce a faultdifferential bytes in the input of the seventh round, then by four round operations to get the faultciphertext,composed of four equations by the proportional relationship between the differencevalue four equations proportional relationship guess keys, theoretically only required two pairsof plaintext and cipher to recovery the right key .
美国国家标准和技术研究所在经过一系列的评测后，从众多的分组密码中选中Rijndael算法，在2001年11月26日对外公布该算法作为AES算法[1,2,3,4]。AES算法作为美国数据加密标准算法，代表了国际密码界在分组密码设计与攻击领域的最高水平。因此对它的安全性分析是一个具有挑战性的课题，具有重大的密码学意义。围绕着AES算法的安全性分析，本文主要取得了以下研究成果：
1、利用中间相遇攻击方法成功实现了对AES算法的前身Square算法[3]的研究。建立一个四轮分析器，分析出字节之间的组合关系，利用中间相遇攻击的思想，加密五轮，解密一轮后得到的函数值与事先准备的函数集合里的函数值进行比较，进而验证猜测的密钥正确与否；
2、在倒数第四轮输入处植入故障，攻击了完整轮数的AES-128。在第七轮的输入诱导一个有故障差分的字节，进行四轮的运算得到错误密文值，通过正确密文与错误密文的差分值与字节之间的比例关系组成四个等式组，根据四个等式的比例关系猜测相关密钥，理论上需要使用两对明密文对就可以恢复正确的密钥。
The urgency of the information system security and the importance network communicati-ons of safety make people are increasingly interested in theories of block cipher, block cipheranalysis and design also has been a hot topic in cryptography. Block cipher is an importantresearch branch of modern cryptography, its birth and development has a wide range of practicalbackground and important theoretical value.
The USA National Institute of Standard and Technology Institute after a series of evaluation,selected Rijndael algorithm from a large number of block cipher , announced that the algorithmas the AES algorithm[1,2,3,4]in November 26, 2001. The AES algorithm as USA data encryptionstandard algorithm, represent the highest level of international cryptography sector in the field ofblock cipher design and attack. Thus safety analysis is a challenging task, and have a majorcryptography significance. Around the safety analysis of the AES algorithm, some achievementshave been obtained in this paper:
The meet-in-the-middle attack methods successful analysis the AES algorithm predecessorSquare algorithm. First, we constructed a fourth round differentiator, then used the differentiatorto analyze the relations between bytes,used the idea of meet-in-the-middle attack,encryption fiveround，compare the values obtained by this decryption to the values in the precomputed set, thenverify that whether the guessed key correct or not;
Induce a fault at the input of the last fourth round, attack complete AES-128. Induce a faultdifferential bytes in the input of the seventh round, then by four round operations to get the faultciphertext,composed of four equations by the proportional relationship between the differencevalue four equations proportional relationship guess keys, theoretically only required two pairsof plaintext and cipher to recovery the right key .
引文
[1]冯国登，吴文玲．分组密码的分析和设计[M]．清华大学出版社，2009.59.
[2]杨景辉，王丽娜，于戈．AES_Rijndael算法综述[J]．计算机科学，2002.29(4):48-50.
[3]陈杰．分组密码的分析技术[D]．西安：西安电子科技大学，2007.
[4]张闻宇．高级加密标准[D]．山东：山东大学，2007．
[5]杜承航．分组密码算法ARIA的不可能差分分析和中间相遇分析[D]．山东：山东大学，2010．
[6]Biham, E.Shamir. A.Differential Cryptanalysis of the Data Encryption Standard[M]. Springer,Heidelberg,1993.
[7]Bahrak, B. Aref, M.R.Impossible differential attack on seven-round AES-128[M].IET Information Security2008 Journal 2,28-32.
[8]W.Phan. Inpossible Differential Cryptanalysis of 7-round Advanced Encryption Standard (AES)[J].Informa-tion Processing Letters 2004.Volume 91,Issue 1,33-38,
[9]Biryukov,A. Boomerang attack on 5 and 6-round AES[C].In:The Fourth Conference on Advanced Encrypti-on Standard(2004)
[10]J,Daemen,V.Rijnmen. AES Proposal:Rijndael[OL],http://csrc.nist.gov/envryption/aes/rijndael.
[11]韦宝典,刘东苏,王新梅．一种新的Square攻击[J]，西安电子科技大学学报(自然科学版)，2003,30(4)：473-476．
[12]钟名富,胡予濮,陈杰．分组加密算法SMS4的14轮Square攻击[J]．西安电子科技大学学报(自然科学版),2008,35(1):105-109．
[13]董晓丽，胡予濮，陈杰，李顺波，杨旸．改进的7轮AES-192和8轮AES-256的中间相遇攻击，通讯学报[J]．2010.(9A):197-201．
[14]王美一，唐学海，李超，屈龙江．3D密码的Square攻击[J]．电子与信息学报, 2010,V32(1): 157-161．
[15]李清玲，李超．变种Camellia对Square攻击的安全性[J]．应用科学学报, 2006 , V24 (5) : 485-490．
[16]贺也平，吴文玲，卿斯汉．对于5轮Camellia密码的Square攻击[J]．中国科学院研究生院学报，2001.1218(2):177-180．
[17]Biryukov, A., Khovratovich, D., Nikolic, I. Distinguisher and related-key attack on the full AES-256[J].Springer, Heidelberg, 2009.5677: 231-249.
[18]Joan Daemen, Lars Knudsen and Vincent Rijmen,The Block Cipher Square[J], Fast Software Encryption1997，Lecture Notes in Computer Science1997. 1267: 149-165.
[19]Hamid Mala,Bliclique Cryptanalysis of the Block Cpher Square[OL],http://eprint.iace.org/2011/500. pdf.
[20]Yongzhuang Wei,Jiqiang Lu and YupuHu, Meet-in-the-Middle Attack on 8 Rounds of the AES BlockCipher under 192 Key Bits[OL], http://eprint.iacr.org/2010/537.
[21]Huseyin Demirci and Ali Aydin Selcuk,A Meet-in-the-Middle Attack on 8-Round AES[C].In:Fast SoftwareEncryption2008, Lecture Notes in Computer Science2008,vol 5086, 116-126.
[22]Huseyin Demirci,Ihsan Taskm,Mustafa Coban,and Adnan Baysal, Improved Meet-in-the-middle Attackson AES[C].In: Lecture Notes in Computer Science 2009,Volume 599,144-156.
[23]曾游．AES攻击算法分析[D]．解放军信息工程大学信息工程学院硕士论文，2003.3．
[24]万航．AES加密算法的实现[J]．软件导刊，2007,(23):30-32．
[25]Daemen, J., Rijmen, V. The Design of Rijndael[M]. Springer, Heidelberg (2002).
[26]Joan Damen,Vincent Rijmen. The Advanced Encryption Standard[C].version.NewYork:NIST,1997:3-61.
[27]Orr Dunkelman, Nathan Keller and Adi Shamir, Improved Single-Key Attack on 8-round AES[OL].http://eprint.iacr.org/2010/322.
[28]Bonwook Koo,Yongjin Yeom, and Junghwan Song. Related-Key Boomerang Attack on Block CipherSquare[C], IEICE Transaction,2001.94-A(1),3-9.
[29]Yongzhuang Wei, Jiqiang Lu, and Yupu Hu.Meet-in-the-Middle Attack on 8 Rounds of the AES BlockCipher under 192 Key Bits[OL].http://eprint.iacr.org/2010/537.
[30]H.Gilbert and M.Mnier,A collision attack on 7 rounds of Rijndael[C].In The Third AES CadndidateConference.2000.
[31]Subidh Ali and Debdeep Mukhopadhyay and Michael Tunstall. Differential Fault Analysis of AES using asingle Multiple-Byte Fault[OL].http://eprint.iacr.org/2010/636.
[32]Dhiman Saha and Debdeep Mukhopadhyay and Dipanwita RoyChowdhury.A Diagonal Fault Attack on theAdvanced Encryption Standard[OL].http://eprint.iacr.org/2009/581.pdf.
[33]P. Dusart, G. Letourneux and O. Vivolo, Differential Fault Analysis on A.E.S.[C]Cryptology eprint ArchiveReport 2003/010.
[34]C. Giraud. DFA on AES[C]. Cryptology ePrint Archive, Report 2003/008.
[35]杜育松，王大星，沈静．一种对AES-128的差分错误分析原理[J]．计算机工程，2006,12 (23):174-176．
[36]M. Tunstall, D. Mukhopadhyay. Differential fault analysis of the advanced encryption standard using asingle fault[OL]. http://eprint.iacr.org/2009/575.pdf.
[37]Michael Tunstall and Debdeep Mukhopadhyay,Subidh Ali,Differential Fault Analysis of the Advanced En-cryption Standard using a Single Fault[OL]. http://eprint.iacr.org/2009/575.pdf.
[38]J. Takahashi and T. Fukunaga. Differential fault analysis on the AES key schedule[OL]. http://eprint.iacr.org/2007/480.pdf..
[39]D. Peacham and B. Thomas. A DFA attack against the AES key schedule[OL]. In:SiVenture White Paper001, 26 October 2006. http://www. siventure.com/pdfs/AES_Key Schedule_DFA_white paper.pdf.
[40]Piret, G., Quisquater, J.J. A Differential Fault Attack Technique against SPN Structures With Applicationto the AES [C].In: Walter,C.D,Paar,C.(eds.)CHES 2003.LNCS.2779,Springer,Heidelberg 2003:77-88.
[41]D. Saha, D. Mukhopadhyay,D. RoyChowdhury. A diagonal fault attack on the advanced encryptionstandard[OL]. http://eprint.iacr.org/2009/581.pdf?q=diagonal.
[42]J.Takahashi, T.Fukunaga. Differential Fault Analysis on the AES Key Schedule[OL].http://eprint.iacr.org/2007/480.
[43]P. Dusart, G. Letourneux and O. Vivolo. Differential Fault Analysis on A.E.S[OL]. http://eprint.iacr.org/2003/010.
[44]Boneh, D, DeMillo, R.A., Lipton, R.J.: On the Importance of checking cryptographic,Protocols forFaults[C].In: Fumy, W. (ed.) EUROCRYPT 1997. LNCS,vol. 1233:37-51.
[45]Biham, E., Shamir, A.: Differential Fault Analysis of Secret Key Cryptosystem[C] .In: Kaliski Jr., B.S. (ed.)CRYPTO 1997. LNCS, vol. 1294, Springer,Heidelberg 1997:513-525.
[46]Blomer, J., Seifert, J.P. Fault Based Cryptanalysis of the Advanced Encryption Standard (AES). In: Wright,R.N. (ed.) FC 2003. LNCS, vol. 2742.Springer, Heidelberg 2003: 162-181.
[47]J. Takahashi and T. Fukunaga.Differential fault analysis on AES with 192 and 256-Bit keys[OL].http://epr-int.iacr.org/2010/023.pdf.
[48]D. Mukhopadhyay.An Improved Fault Based Attack of the Advanced Encryption Standard[J]. Africacrypt2009,vol.5580 of LNCS,2009:421-434.
[49]An Improved Method of Differential Fault Analysis on the SMS4 Cryptosystem[C],In proceedings of theFirst International Symposium on Data, Privacy, and E-Commerce 2007, IEEE-CS, pp.175-180.
[50]刘祥忠．分组密码AES-128的差分故障攻击[J]，计算机技术与发展，2012(8):12-15．
[2]杨景辉，王丽娜，于戈．AES_Rijndael算法综述[J]．计算机科学，2002.29(4):48-50.
[3]陈杰．分组密码的分析技术[D]．西安：西安电子科技大学，2007.
[4]张闻宇．高级加密标准[D]．山东：山东大学，2007．
[5]杜承航．分组密码算法ARIA的不可能差分分析和中间相遇分析[D]．山东：山东大学，2010．
[6]Biham, E.Shamir. A.Differential Cryptanalysis of the Data Encryption Standard[M]. Springer,Heidelberg,1993.
[7]Bahrak, B. Aref, M.R.Impossible differential attack on seven-round AES-128[M].IET Information Security2008 Journal 2,28-32.
[8]W.Phan. Inpossible Differential Cryptanalysis of 7-round Advanced Encryption Standard (AES)[J].Informa-tion Processing Letters 2004.Volume 91,Issue 1,33-38,
[9]Biryukov,A. Boomerang attack on 5 and 6-round AES[C].In:The Fourth Conference on Advanced Encrypti-on Standard(2004)
[10]J,Daemen,V.Rijnmen. AES Proposal:Rijndael[OL],http://csrc.nist.gov/envryption/aes/rijndael.
[11]韦宝典,刘东苏,王新梅．一种新的Square攻击[J]，西安电子科技大学学报(自然科学版)，2003,30(4)：473-476．
[12]钟名富,胡予濮,陈杰．分组加密算法SMS4的14轮Square攻击[J]．西安电子科技大学学报(自然科学版),2008,35(1):105-109．
[13]董晓丽，胡予濮，陈杰，李顺波，杨旸．改进的7轮AES-192和8轮AES-256的中间相遇攻击，通讯学报[J]．2010.(9A):197-201．
[14]王美一，唐学海，李超，屈龙江．3D密码的Square攻击[J]．电子与信息学报, 2010,V32(1): 157-161．
[15]李清玲，李超．变种Camellia对Square攻击的安全性[J]．应用科学学报, 2006 , V24 (5) : 485-490．
[16]贺也平，吴文玲，卿斯汉．对于5轮Camellia密码的Square攻击[J]．中国科学院研究生院学报，2001.1218(2):177-180．
[17]Biryukov, A., Khovratovich, D., Nikolic, I. Distinguisher and related-key attack on the full AES-256[J].Springer, Heidelberg, 2009.5677: 231-249.
[18]Joan Daemen, Lars Knudsen and Vincent Rijmen,The Block Cipher Square[J], Fast Software Encryption1997，Lecture Notes in Computer Science1997. 1267: 149-165.
[19]Hamid Mala,Bliclique Cryptanalysis of the Block Cpher Square[OL],http://eprint.iace.org/2011/500. pdf.
[20]Yongzhuang Wei,Jiqiang Lu and YupuHu, Meet-in-the-Middle Attack on 8 Rounds of the AES BlockCipher under 192 Key Bits[OL], http://eprint.iacr.org/2010/537.
[21]Huseyin Demirci and Ali Aydin Selcuk,A Meet-in-the-Middle Attack on 8-Round AES[C].In:Fast SoftwareEncryption2008, Lecture Notes in Computer Science2008,vol 5086, 116-126.
[22]Huseyin Demirci,Ihsan Taskm,Mustafa Coban,and Adnan Baysal, Improved Meet-in-the-middle Attackson AES[C].In: Lecture Notes in Computer Science 2009,Volume 599,144-156.
[23]曾游．AES攻击算法分析[D]．解放军信息工程大学信息工程学院硕士论文，2003.3．
[24]万航．AES加密算法的实现[J]．软件导刊，2007,(23):30-32．
[25]Daemen, J., Rijmen, V. The Design of Rijndael[M]. Springer, Heidelberg (2002).
[26]Joan Damen,Vincent Rijmen. The Advanced Encryption Standard[C].version.NewYork:NIST,1997:3-61.
[27]Orr Dunkelman, Nathan Keller and Adi Shamir, Improved Single-Key Attack on 8-round AES[OL].http://eprint.iacr.org/2010/322.
[28]Bonwook Koo,Yongjin Yeom, and Junghwan Song. Related-Key Boomerang Attack on Block CipherSquare[C], IEICE Transaction,2001.94-A(1),3-9.
[29]Yongzhuang Wei, Jiqiang Lu, and Yupu Hu.Meet-in-the-Middle Attack on 8 Rounds of the AES BlockCipher under 192 Key Bits[OL].http://eprint.iacr.org/2010/537.
[30]H.Gilbert and M.Mnier,A collision attack on 7 rounds of Rijndael[C].In The Third AES CadndidateConference.2000.
[31]Subidh Ali and Debdeep Mukhopadhyay and Michael Tunstall. Differential Fault Analysis of AES using asingle Multiple-Byte Fault[OL].http://eprint.iacr.org/2010/636.
[32]Dhiman Saha and Debdeep Mukhopadhyay and Dipanwita RoyChowdhury.A Diagonal Fault Attack on theAdvanced Encryption Standard[OL].http://eprint.iacr.org/2009/581.pdf.
[33]P. Dusart, G. Letourneux and O. Vivolo, Differential Fault Analysis on A.E.S.[C]Cryptology eprint ArchiveReport 2003/010.
[34]C. Giraud. DFA on AES[C]. Cryptology ePrint Archive, Report 2003/008.
[35]杜育松，王大星，沈静．一种对AES-128的差分错误分析原理[J]．计算机工程，2006,12 (23):174-176．
[36]M. Tunstall, D. Mukhopadhyay. Differential fault analysis of the advanced encryption standard using asingle fault[OL]. http://eprint.iacr.org/2009/575.pdf.
[37]Michael Tunstall and Debdeep Mukhopadhyay,Subidh Ali,Differential Fault Analysis of the Advanced En-cryption Standard using a Single Fault[OL]. http://eprint.iacr.org/2009/575.pdf.
[38]J. Takahashi and T. Fukunaga. Differential fault analysis on the AES key schedule[OL]. http://eprint.iacr.org/2007/480.pdf..
[39]D. Peacham and B. Thomas. A DFA attack against the AES key schedule[OL]. In:SiVenture White Paper001, 26 October 2006. http://www. siventure.com/pdfs/AES_Key Schedule_DFA_white paper.pdf.
[40]Piret, G., Quisquater, J.J. A Differential Fault Attack Technique against SPN Structures With Applicationto the AES [C].In: Walter,C.D,Paar,C.(eds.)CHES 2003.LNCS.2779,Springer,Heidelberg 2003:77-88.
[41]D. Saha, D. Mukhopadhyay,D. RoyChowdhury. A diagonal fault attack on the advanced encryptionstandard[OL]. http://eprint.iacr.org/2009/581.pdf?q=diagonal.
[42]J.Takahashi, T.Fukunaga. Differential Fault Analysis on the AES Key Schedule[OL].http://eprint.iacr.org/2007/480.
[43]P. Dusart, G. Letourneux and O. Vivolo. Differential Fault Analysis on A.E.S[OL]. http://eprint.iacr.org/2003/010.
[44]Boneh, D, DeMillo, R.A., Lipton, R.J.: On the Importance of checking cryptographic,Protocols forFaults[C].In: Fumy, W. (ed.) EUROCRYPT 1997. LNCS,vol. 1233:37-51.
[45]Biham, E., Shamir, A.: Differential Fault Analysis of Secret Key Cryptosystem[C] .In: Kaliski Jr., B.S. (ed.)CRYPTO 1997. LNCS, vol. 1294, Springer,Heidelberg 1997:513-525.
[46]Blomer, J., Seifert, J.P. Fault Based Cryptanalysis of the Advanced Encryption Standard (AES). In: Wright,R.N. (ed.) FC 2003. LNCS, vol. 2742.Springer, Heidelberg 2003: 162-181.
[47]J. Takahashi and T. Fukunaga.Differential fault analysis on AES with 192 and 256-Bit keys[OL].http://epr-int.iacr.org/2010/023.pdf.
[48]D. Mukhopadhyay.An Improved Fault Based Attack of the Advanced Encryption Standard[J]. Africacrypt2009,vol.5580 of LNCS,2009:421-434.
[49]An Improved Method of Differential Fault Analysis on the SMS4 Cryptosystem[C],In proceedings of theFirst International Symposium on Data, Privacy, and E-Commerce 2007, IEEE-CS, pp.175-180.
[50]刘祥忠．分组密码AES-128的差分故障攻击[J]，计算机技术与发展，2012(8):12-15．