DES缓存攻击技术研究
摘要
信息安全不仅是各国政府和军事部门关切的问题,也是企事业单位需要解决的。所以美国国家标准局(NIST)于1977年公布由IBM公司研制的一种加密算法,批准它作为非机要部门使用的数据加密标准,简称DES。DES是Data Encryption Standard的缩写。自从公布以来,它一直超越国界,成为国际上商用保密通信和计算机通信最常用的加密算法。多年来DES一直活跃在国际保密通信的舞台上,扮演了十分突出的角色。
但由于DES分组大小和密钥长度分别是64位和56位,这成为DES的主要安全弱点。进入20世纪90年代以后,Eli Biham和Adi Shamir提出“差分密码分析”,Mitsuru Matsui提出了“线性密码分析”,但这些方法需要很大的选择明文数量,付出很大的代价才能解出一个密钥。
旁路攻击是一种新兴的攻击方法,它利用密码算法加密过程中产生的环境信息来达到破解密码算法的目的。旁路攻击已经成为一种密码分析的有效手段。缓存攻击是一种基于缓存的旁路攻击,它利用加密平台的缓存特性来获取相关的密钥信息。基于缓存的旁路攻击能够作用于一切实现于“Cache Memory”层次存储结构计算机设备上的查表实现的DES算法,从而危害到服务器、桌面以及嵌入式等各种领域的主流计算机系统。
目前,在国外已经有了一些关于使用缓存分析攻击DES的论文发表,Paul Kocher于1996年首先提出了旁路攻击,并对能量分析攻击进行了研究。J.Kelsey,B.Schneier,D.Wagner,and C.Hall后来提出了缓存分析攻击,但国内相应的研究才刚刚起步,所以本文将DES算法作为研究缓存分析攻击的目标算法,探索缓存分析攻击方法和研究思路,并提出相应的防御措施。
本文根据DES在访问数组时缓存表现出来的“命中”和“未命中”的特性,对DES算法进行分析。在介绍DES算法和缓存结构的基础上,分析了缓存攻击DES的原理和两种攻击模型,并且进行了软件实现。
Information security is not only concerned by the governments and the military sectors, but also by the Enterprises .So United States National Bureau of Standards (NIST) published an algorithm developed by IBM, and ratify it as the Data Encryption Standard for the non-confidential departments in 1977, DES is the acronym. Since its publication, it has become the major encryption algorithms for confidential communications of international commerce and computer. DES has become a well known and widely used cryptosystem for many years.
However, DES has major weakness because of the only 56-bit-long key size and the 64-bit-long block size. When it came to 1990s, Eli Biham and Adi Shamir proposed differential cryptanalysis, and Mitsuru Matsui proposed the linear cryptanalysis. But both the methods need huge number of plaintexts to decrypt the key.
Side-channel attack is a new method to analysis cryptography. It makes use of the environment information which is generated in encryption to decrypt the cryptography. It has been an effective method. Cache attack is one kind of side-channel attack that based on cache. It makes use of the cache feature to gain some information of the key. It can be used for all DES algorithm that implemented with table-lookup and run under the machine with cache, so it can harm many computer system, such as server, desktop and embedded system.
At present, there have been some papers about how to use cache to attack DES encryption. In 1996 Paul Kocher first proposed the side channel attacks and did some research on the power analysis attack. J. Kelsey, B. Schneier, D. Wagner, and C. Hall put forward cache analysis attacks while the domestic related research just made the first step. So this paper intends to make use of the cache attack to DES to explore the cache analysis method and put forward defensive measures.
According to the characteristic of hitting or missing showed by the visiting arrays cache operation in the DES encryption progress, this paper proposes a analysis technique of cache attack to DES. On the basis of the DES algorithm and Cache structure, we introduce the principle of DES, and analysis two attacking models and implemented it.
但由于DES分组大小和密钥长度分别是64位和56位,这成为DES的主要安全弱点。进入20世纪90年代以后,Eli Biham和Adi Shamir提出“差分密码分析”,Mitsuru Matsui提出了“线性密码分析”,但这些方法需要很大的选择明文数量,付出很大的代价才能解出一个密钥。
旁路攻击是一种新兴的攻击方法,它利用密码算法加密过程中产生的环境信息来达到破解密码算法的目的。旁路攻击已经成为一种密码分析的有效手段。缓存攻击是一种基于缓存的旁路攻击,它利用加密平台的缓存特性来获取相关的密钥信息。基于缓存的旁路攻击能够作用于一切实现于“Cache Memory”层次存储结构计算机设备上的查表实现的DES算法,从而危害到服务器、桌面以及嵌入式等各种领域的主流计算机系统。
目前,在国外已经有了一些关于使用缓存分析攻击DES的论文发表,Paul Kocher于1996年首先提出了旁路攻击,并对能量分析攻击进行了研究。J.Kelsey,B.Schneier,D.Wagner,and C.Hall后来提出了缓存分析攻击,但国内相应的研究才刚刚起步,所以本文将DES算法作为研究缓存分析攻击的目标算法,探索缓存分析攻击方法和研究思路,并提出相应的防御措施。
本文根据DES在访问数组时缓存表现出来的“命中”和“未命中”的特性,对DES算法进行分析。在介绍DES算法和缓存结构的基础上,分析了缓存攻击DES的原理和两种攻击模型,并且进行了软件实现。
Information security is not only concerned by the governments and the military sectors, but also by the Enterprises .So United States National Bureau of Standards (NIST) published an algorithm developed by IBM, and ratify it as the Data Encryption Standard for the non-confidential departments in 1977, DES is the acronym. Since its publication, it has become the major encryption algorithms for confidential communications of international commerce and computer. DES has become a well known and widely used cryptosystem for many years.
However, DES has major weakness because of the only 56-bit-long key size and the 64-bit-long block size. When it came to 1990s, Eli Biham and Adi Shamir proposed differential cryptanalysis, and Mitsuru Matsui proposed the linear cryptanalysis. But both the methods need huge number of plaintexts to decrypt the key.
Side-channel attack is a new method to analysis cryptography. It makes use of the environment information which is generated in encryption to decrypt the cryptography. It has been an effective method. Cache attack is one kind of side-channel attack that based on cache. It makes use of the cache feature to gain some information of the key. It can be used for all DES algorithm that implemented with table-lookup and run under the machine with cache, so it can harm many computer system, such as server, desktop and embedded system.
At present, there have been some papers about how to use cache to attack DES encryption. In 1996 Paul Kocher first proposed the side channel attacks and did some research on the power analysis attack. J. Kelsey, B. Schneier, D. Wagner, and C. Hall put forward cache analysis attacks while the domestic related research just made the first step. So this paper intends to make use of the cache attack to DES to explore the cache analysis method and put forward defensive measures.
According to the characteristic of hitting or missing showed by the visiting arrays cache operation in the DES encryption progress, this paper proposes a analysis technique of cache attack to DES. On the basis of the DES algorithm and Cache structure, we introduce the principle of DES, and analysis two attacking models and implemented it.
引文
[1]侯方勇,谷大武,李小勇.基于Cache的AES攻击:研究进展[J].信息安全与通信保密,2007年8期.
[2]Kocher,P.C.:Timing Attacks on Implementations of Diffie-Hellman,RSA,DSS,and Other Systems,In:Koblitz,N.(ed.)CRYPTO 1996.LNCS,vol.1109,Springer,Heidelberg,pp.104-113.
[3]J.Kelsey,B.Schneier,D.Wagner,C.Hall,Side Channel Cryptanalysis of Product Ciphers,Journal of Computer Security,vol.8,pp.141-158,2000.
[4]Y.Tsunoo and E.Tsujihara and K.Minematsu and H.Miyauchi,Cryptanalysis of Block Ciphers Implemented on Computers with Cache,In International Symposium on Information Theory and Its Applications (ISITA),2002.
[5]D.Page,Theoretical Use of Cache memory as a Cryptanalytic side-Channel,Technical Report CSTR-02-003,Department of Computer Science,University of Bristol,June 2002 available at http://www.cs.bris.ac.uk/
[6]B.Schneier,APPLIED CRYPTOGRAPHY,John Wiley & Sons,Inc.,1996.
[7]卢开澄.计算机密码学[M].清华大学出版社,2003.12.
[8]易建勋编著.微处理器(CPU)的结构与性能[M].高等院校计算机与信息技术应用新技术教材.清华大学出版社,2003.
[9]张文政,张文科.能量密码分析[M].成都电子科技大学.
[10]Yukiyasu Tsunoo,Etsuko Tsujihara,Maki Shigeri,Hiroyasu Kubo,Kazuhiko Minematsu,Improving cache attacks by considering cipher structure,Published online:18 November 2005 Springer-vedag 2005.
[11]邓高明,张鹏,陈开颜,赵强.Cache在旁路攻击中的理论应用及其仿真实现[J].微电子学与计算机,2007.
[12]Hill M D.Aspects of cache memory and instruction buffer performance [R].Technical Report CSD-87-381,University of California,Berkeley,1987.11.
[13]James Alexander Muir,Techniques of Side Channel Cryptanalysis, University of Waterloo,2001.
[14]E.Biham and A.Shamir,Differential Fault Analysis of Secret Key Cryptosystems,In B.Kaliski,editor,in Cryptology-CRYPTO'97,volume 1294 of LNCS,pages 513-525.Springer-Verlag,1997.
[15]D.Page,Partitioned Cache Architecture as a side channel Defence Mechanism,2005,http://epdnt.iacr.org/2005/280.pdf.
[16]Kocher,P.C.:Timing Attacks on Implementations of Diffie-Heliman,RSA,DSS,and Other Systems.In:Koblitz,N.(ed.)CRYPTO 1996.LNCS,vol.1109,Springer,Heidelberg,pp.104-113.
[17]J.Kelsey,B.Schneier,D.Wagner,C.Hall,Side Channel Cryptanalysis of Product Ciphers,Journal of Computer Security,vol.8,pp.141-158,2000.
[18]National Institute of Standards and Technology,ANSI C Reference Code V2.0(October 24,2000),available at http://csrc.nist.gov/CryptoToolkit/aes/rijndael/
[19]Daniel J.Bernstein,Cache-timing attacks on AES,2005,http://cr.yp.to/antiforgery/cachetiming-20050414.pdf.
[20]Joseph Bonneau,Ilya Mironov,Cache-Collision Timing Attacks Against AES,http://www.stan ford.edu/～jbonneau/AES_timing.pdf.
[21]Percival,C.Cache missing for fun and profit(2005),http://www.daemonology.net/hyperthreading-considered-harmful/.
[22]李丁,吕永其.能量分析攻击基本原理与实践验证[M]
[23]徐隽.密码分析中的“时间内存替换”[J].Netinfo Security,2004.
[24]李欣.RSA公钥密码算法的能量分析攻击与防御研究.电子科技大学学位论文,20060509.
[26]李欣.针对OpenSSL的远程时间攻击及其防御策略研究.通信与信息技术2005中国西部青年通信学术会议论文集.2005.11.
[27]石伟.抗功耗分析攻击逻辑的研究与实现,国防科学技术大学学位论文.20061101.
[2]Kocher,P.C.:Timing Attacks on Implementations of Diffie-Hellman,RSA,DSS,and Other Systems,In:Koblitz,N.(ed.)CRYPTO 1996.LNCS,vol.1109,Springer,Heidelberg,pp.104-113.
[3]J.Kelsey,B.Schneier,D.Wagner,C.Hall,Side Channel Cryptanalysis of Product Ciphers,Journal of Computer Security,vol.8,pp.141-158,2000.
[4]Y.Tsunoo and E.Tsujihara and K.Minematsu and H.Miyauchi,Cryptanalysis of Block Ciphers Implemented on Computers with Cache,In International Symposium on Information Theory and Its Applications (ISITA),2002.
[5]D.Page,Theoretical Use of Cache memory as a Cryptanalytic side-Channel,Technical Report CSTR-02-003,Department of Computer Science,University of Bristol,June 2002 available at http://www.cs.bris.ac.uk/
[6]B.Schneier,APPLIED CRYPTOGRAPHY,John Wiley & Sons,Inc.,1996.
[7]卢开澄.计算机密码学[M].清华大学出版社,2003.12.
[8]易建勋编著.微处理器(CPU)的结构与性能[M].高等院校计算机与信息技术应用新技术教材.清华大学出版社,2003.
[9]张文政,张文科.能量密码分析[M].成都电子科技大学.
[10]Yukiyasu Tsunoo,Etsuko Tsujihara,Maki Shigeri,Hiroyasu Kubo,Kazuhiko Minematsu,Improving cache attacks by considering cipher structure,Published online:18 November 2005 Springer-vedag 2005.
[11]邓高明,张鹏,陈开颜,赵强.Cache在旁路攻击中的理论应用及其仿真实现[J].微电子学与计算机,2007.
[12]Hill M D.Aspects of cache memory and instruction buffer performance [R].Technical Report CSD-87-381,University of California,Berkeley,1987.11.
[13]James Alexander Muir,Techniques of Side Channel Cryptanalysis, University of Waterloo,2001.
[14]E.Biham and A.Shamir,Differential Fault Analysis of Secret Key Cryptosystems,In B.Kaliski,editor,in Cryptology-CRYPTO'97,volume 1294 of LNCS,pages 513-525.Springer-Verlag,1997.
[15]D.Page,Partitioned Cache Architecture as a side channel Defence Mechanism,2005,http://epdnt.iacr.org/2005/280.pdf.
[16]Kocher,P.C.:Timing Attacks on Implementations of Diffie-Heliman,RSA,DSS,and Other Systems.In:Koblitz,N.(ed.)CRYPTO 1996.LNCS,vol.1109,Springer,Heidelberg,pp.104-113.
[17]J.Kelsey,B.Schneier,D.Wagner,C.Hall,Side Channel Cryptanalysis of Product Ciphers,Journal of Computer Security,vol.8,pp.141-158,2000.
[18]National Institute of Standards and Technology,ANSI C Reference Code V2.0(October 24,2000),available at http://csrc.nist.gov/CryptoToolkit/aes/rijndael/
[19]Daniel J.Bernstein,Cache-timing attacks on AES,2005,http://cr.yp.to/antiforgery/cachetiming-20050414.pdf.
[20]Joseph Bonneau,Ilya Mironov,Cache-Collision Timing Attacks Against AES,http://www.stan ford.edu/～jbonneau/AES_timing.pdf.
[21]Percival,C.Cache missing for fun and profit(2005),http://www.daemonology.net/hyperthreading-considered-harmful/.
[22]李丁,吕永其.能量分析攻击基本原理与实践验证[M]
[23]徐隽.密码分析中的“时间内存替换”[J].Netinfo Security,2004.
[24]李欣.RSA公钥密码算法的能量分析攻击与防御研究.电子科技大学学位论文,20060509.
[26]李欣.针对OpenSSL的远程时间攻击及其防御策略研究.通信与信息技术2005中国西部青年通信学术会议论文集.2005.11.
[27]石伟.抗功耗分析攻击逻辑的研究与实现,国防科学技术大学学位论文.20061101.