一种侧信道攻击Rainbow签名的算法
|
摘要
Rainbow是一种数字签名方案,它基于多元多项式结构构造,属于多变量密码体系。相比现有的签名方案,如RSA和ECC方案,Rainbow的特点是能够抵御量子计算机攻击,被认为是下一代签名方案的重要候选。基于Rainbow的重要性,该文对Rainbow的硬件安全进行了分析,提出了一种基于差分能量分析和故障分析的侧信道分析算法,将Rainbow作为目标,实施侧信道攻击。实现了Rainbow签名电路,并进行功耗采集,对采集的2 000条功耗曲线进行分析和计算,获取了Rainbow所有的密钥。
Rainbow is a digital signature scheme. It is based on multivariate polynomials, which belongs to multivariate public key cryptography. Compared with the existing signature schemes, e.g. rivest-shamir-adleman(RSA) and ellipse curve cryptography(ECC), Rainbow can resist quantum computer attacks, which is a candidate of the signature schemes of the next generation. According to the importance of Rainbow, in this paper, we present techniques to exploit differential power analysis(DPA) and fault analysis attacks for analyzing the effectiveness of side channel attacks on Rainbow signature. We implement a naive Rainbow scheme on hardware and propose a successful side channel attack on the implementation. Experimental results show that our attack successfully obtains all the pieces from the private keys of the Rainbow scheme and they clearly demonstrate that we need to protect Rainbow against side channel attacks.
Rainbow is a digital signature scheme. It is based on multivariate polynomials, which belongs to multivariate public key cryptography. Compared with the existing signature schemes, e.g. rivest-shamir-adleman(RSA) and ellipse curve cryptography(ECC), Rainbow can resist quantum computer attacks, which is a candidate of the signature schemes of the next generation. According to the importance of Rainbow, in this paper, we present techniques to exploit differential power analysis(DPA) and fault analysis attacks for analyzing the effectiveness of side channel attacks on Rainbow signature. We implement a naive Rainbow scheme on hardware and propose a successful side channel attack on the implementation. Experimental results show that our attack successfully obtains all the pieces from the private keys of the Rainbow scheme and they clearly demonstrate that we need to protect Rainbow against side channel attacks.
引文
[1]SHOR P.Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer[J].SIAM Review,1999,41(2):303-332.
[2]DING J,GOWER J E,SCHMIDT D S.Multivariate public key cryptosystems[M].Berlin:Springer,2006.
[3]THOMAE E,WOLF C.Solving underdetermined systems of multivariate quadratic equations revisited[C]//PKC 2012.Berlin:Springer,2012.
[4]PETZOLDT A,BULYGIN S,BUCHMANN J.Selecting parameters for the Rainbow signature scheme[C]//PQCrypto 2010.Darmstadt,Germany:Springer,2010.
[5]MOH T.A public key system with signature and master key functions[J].Communications in Algebra.1999,27(5):2207-2222.
[6]TANG S,YI H,DING J,et al.High-speed hardware implementation of Rainbow signature on FPGAs[C]//PQCrypto 2011.Taipei,Taiwan,China:Springer,2011.
[7]BALASUBRAMANIAN S,CARTER H W,BOGDANOVA,et al.Fast multivariate signature generation in hardware:the case of Rainbow[C]//ASAP 2008.Leuven,Belgium:IEEE,2008.
[8]YANG B Y,CHEN J M,CHEN Y H.TTS:High-speed signatures on a low-cost smart card[C]//CHES 2004.Cambridge,MA,USA:Springer,2004.
[9]CHEN I T,CHEN M S,CHEN T R,et al.SSEimplementation of multivariate PKCs on modern x86CPUs[C]//CHES 2009.Lausanne,Switzerland:Springer,2009.
[10]YI H,TANG S.Very small FPGA processor for multivariate signatures[J].Computer Journal,2016(7):1091-1101.
[11]BOGDANOV A,EISENBARTH T,RUPP A,et al.Time-area optimized public-key engines:MQ-cryptosystems as replacement for elliptic curves?[C]//CHES 2008.Washington,D.C.USA:Springer,2008.
[12]YANG B Y,CHENG C M,CHEN B R,et al.Implementing minimized multivariate PKC on low-resource embedded systems[C]//SPC 2006.York,UK:Springer,2006.
[13]KOCHER P C.Timing attacks on implementations of die-hellman,RSA,DSS,and other systems[C]//CRYPTO96.Santa Barbara,California,USA:Springer,1996.
[14]KOCHER P,JAE J,JUN B.Differential power analysis.[C]//CRYPTO 99.Santa Barbara,California,USA:Springer,1999.
[15]QUISQUATER J J,SAMYDE D.Electro-magnetic analysis(EMA):Measures and countermeasures for smart cards[C]//E-smart 2001.Cannes,France:Springer,2001.
[16]SKOROBOGATOV S P,ANDERSON R J.Optical fault induction attacks[C]//CHES 2002.Redwood Shores,CA,USA:Springer,2002.
[17]JOYE M,LENSTRA A K,QUISQUATER J J.Chinese remaindering based cryptosystems in the presence of faults[J].Journal of Cryptology,1998,12(4):241-245.
[18]MAYER-SOMMER R.Smartly analyzing the simplicity and the power of simple power analysis on smartcards[C]//CHES 2000.MA,USA:Springer,2000.
[19]MESSERGES T S,DABBISH E A,SLOAN R H.Examining smart-card security under the threat of power analysis attacks[J].IEEE Transactions on Computers,2002,51(5):541-552.
[20]MESSERGES T S.Using second-order power analysis to attack DPA resistant software[C]//CHES 2000.MA,USA:Springer,2000.
[21]BRIER E,CLAVIER C,OLIVIER F.Correlation power analysis with a leakage model[C]//CHES 2004.Cambridge,MA,USA:Springer,2004.
[22]MANGARD S,PRAMSTALLER N,OSWALD E.Successfully attacking masked AES hardware implementations[C]//CHES 2005.Edinburgh,UK:Springer,2005.
[23]AKKAR M L,COURTOIS N T,DUTEUIL R,et al.A fast and secure implementation of SFLASH[C]//PKC 2003.Miami,FL,USA:Springer,2003.
[24]OKEYA K,TAKAGI T,VUILLAUME C.On the importance of protectingδin SFLASH against side channel attacks[C]//ITCC 2004.Las Vegas,Nevada,USA:IEEE,2004.
[25]HASHIMOTO Y,TAKAGI T,SAKURAI K.General fault attacks on multivariate public key cryptosystems[C]//PQCrypto 2011.Taipei,Taiwan,China:Springer,2011.
[2]DING J,GOWER J E,SCHMIDT D S.Multivariate public key cryptosystems[M].Berlin:Springer,2006.
[3]THOMAE E,WOLF C.Solving underdetermined systems of multivariate quadratic equations revisited[C]//PKC 2012.Berlin:Springer,2012.
[4]PETZOLDT A,BULYGIN S,BUCHMANN J.Selecting parameters for the Rainbow signature scheme[C]//PQCrypto 2010.Darmstadt,Germany:Springer,2010.
[5]MOH T.A public key system with signature and master key functions[J].Communications in Algebra.1999,27(5):2207-2222.
[6]TANG S,YI H,DING J,et al.High-speed hardware implementation of Rainbow signature on FPGAs[C]//PQCrypto 2011.Taipei,Taiwan,China:Springer,2011.
[7]BALASUBRAMANIAN S,CARTER H W,BOGDANOVA,et al.Fast multivariate signature generation in hardware:the case of Rainbow[C]//ASAP 2008.Leuven,Belgium:IEEE,2008.
[8]YANG B Y,CHEN J M,CHEN Y H.TTS:High-speed signatures on a low-cost smart card[C]//CHES 2004.Cambridge,MA,USA:Springer,2004.
[9]CHEN I T,CHEN M S,CHEN T R,et al.SSEimplementation of multivariate PKCs on modern x86CPUs[C]//CHES 2009.Lausanne,Switzerland:Springer,2009.
[10]YI H,TANG S.Very small FPGA processor for multivariate signatures[J].Computer Journal,2016(7):1091-1101.
[11]BOGDANOV A,EISENBARTH T,RUPP A,et al.Time-area optimized public-key engines:MQ-cryptosystems as replacement for elliptic curves?[C]//CHES 2008.Washington,D.C.USA:Springer,2008.
[12]YANG B Y,CHENG C M,CHEN B R,et al.Implementing minimized multivariate PKC on low-resource embedded systems[C]//SPC 2006.York,UK:Springer,2006.
[13]KOCHER P C.Timing attacks on implementations of die-hellman,RSA,DSS,and other systems[C]//CRYPTO96.Santa Barbara,California,USA:Springer,1996.
[14]KOCHER P,JAE J,JUN B.Differential power analysis.[C]//CRYPTO 99.Santa Barbara,California,USA:Springer,1999.
[15]QUISQUATER J J,SAMYDE D.Electro-magnetic analysis(EMA):Measures and countermeasures for smart cards[C]//E-smart 2001.Cannes,France:Springer,2001.
[16]SKOROBOGATOV S P,ANDERSON R J.Optical fault induction attacks[C]//CHES 2002.Redwood Shores,CA,USA:Springer,2002.
[17]JOYE M,LENSTRA A K,QUISQUATER J J.Chinese remaindering based cryptosystems in the presence of faults[J].Journal of Cryptology,1998,12(4):241-245.
[18]MAYER-SOMMER R.Smartly analyzing the simplicity and the power of simple power analysis on smartcards[C]//CHES 2000.MA,USA:Springer,2000.
[19]MESSERGES T S,DABBISH E A,SLOAN R H.Examining smart-card security under the threat of power analysis attacks[J].IEEE Transactions on Computers,2002,51(5):541-552.
[20]MESSERGES T S.Using second-order power analysis to attack DPA resistant software[C]//CHES 2000.MA,USA:Springer,2000.
[21]BRIER E,CLAVIER C,OLIVIER F.Correlation power analysis with a leakage model[C]//CHES 2004.Cambridge,MA,USA:Springer,2004.
[22]MANGARD S,PRAMSTALLER N,OSWALD E.Successfully attacking masked AES hardware implementations[C]//CHES 2005.Edinburgh,UK:Springer,2005.
[23]AKKAR M L,COURTOIS N T,DUTEUIL R,et al.A fast and secure implementation of SFLASH[C]//PKC 2003.Miami,FL,USA:Springer,2003.
[24]OKEYA K,TAKAGI T,VUILLAUME C.On the importance of protectingδin SFLASH against side channel attacks[C]//ITCC 2004.Las Vegas,Nevada,USA:IEEE,2004.
[25]HASHIMOTO Y,TAKAGI T,SAKURAI K.General fault attacks on multivariate public key cryptosystems[C]//PQCrypto 2011.Taipei,Taiwan,China:Springer,2011.