一种对RSA-CRT的错误模攻击
摘要
RSA[1]算法于1977年由Ron Rivest, Adi Shamir和Len Adleman提出,并被广泛应用于加密和数字签名等公钥密码算法中。RSA的安全性依赖于大数的因子分解,分解N是最直接的攻击方法。为了改善RSA的解密速度,一般采用RSA算法的变形RSA-CRT[2],其解密速度是经典RSA的4倍。
1997年,Boneeh, Demillo和Lipton指出RSA-CRT容易受到错误攻击的威胁,即假设攻击者通过植入错误签名,可以利用错误签名和正确签名的关系将N进行分解。这种攻击适用于将消息m经过编码处理的RSA加密算法,比如RSA PKCS#1v1.5或者Full-Domain Hash [3]。 Seifert[4]于2005年利用RSA公开的模N对RSA进行错误攻击。此攻击适用于RSA的数字签名,随后Brier et al[5]提出了密钥恢复攻击,并在文献[6,7,8,9]中做出改进。但后来改进的密钥恢复攻击仅适用于不含CRT的RSA加密算法,而且比Brier etal攻击需要更多的错误签名。
2012年Eric Brier, David Naccache, Phong Q. Nguyen和Mehdi Tibouchi[10]利用正交格原理提出了一种新的RSA错误模攻击。他们利用恢复密钥的方法来对RSA-CRT签名进行攻击,其中攻击是需要注入的激光技术来实现错误模的生成。这种攻击灵活使用了RSA-CRT签名中的各项参数,即：然后生成RSA-CRT签名：利用错误模注入技术得到错误签名σ′,即：对生成的两种签名σ和σ′使用中国剩余定理可计算出：通过签名对(σ,σ′)可以构造出带有未知整参数α，β的多组线性组合。最后利用格的约化算法来恢复参数σp和σq，最终达到分解八’的目的。实践证明他们的方法是高效的,假设敌手能够获得5对正确的签名与错误的签名,利用-台标准的计算机就可以在几秒钟内将N进行分解。
本文根据上述的错误模攻击提出了新的攻击RSA-CRT的方法,计算效率更高,通过转换上述攻击中生成的v=σp·α+σq·β∈Z,将v进一步变形：观察可知α+β=N+1,因此可得：并引入参数ω=(σ·(N+1)-v)/N,通过变形可以得到：
通过证明可以得出ω是一个整数。最后通过敌手的假设对ω进行讨论和精确求解,利用二分法求解N的最小素因子min(p,q),实现对大整数N的分解,最终达到攻击RSA-CRT的目的。
本文的攻击需要对ω进行讨论,根据ω所定义的形式可以获知,如果σmin(p,q),那么ω>0。文章针对ω这一特性可以确定最小素因子的上下限,最多经过log N次尝试后可以确定出最小素因子。
错误模N′的有两种不同的情况,不同的错误模V′所需要的错误实例也是不同的,即一种是错误N′与初始的N相差一个未知比特；另一种是错误N′与初始N′的不同要少于最低有效位比特的一半：最低有效位比特的错误数量最多不能超过N长度的一半。此外,我们假设攻击者可以根据自己的需要向模拟器请求签名,模拟器亦必须无条件的回复攻击者的签名请求,这样,攻击者可以从回复的签名中寻找适合攻击的签名。
本文章节安排如下,第一章介绍RSA公钥算法的基础知识,包括利用中国剩余定理进行快速求解的参数设置，利用正交格求解RSA-CRT的错误模攻击。第二章介绍构造新参数ω以及攻击的严格理论证明。第三章将对前后两种的错误模攻击进行分析比较。第四章给出两种错误模N的分析。
RSA[1] was proposed by Ron Rivest, Adi Shamir and Len Adleman in1977, and is widely used in encryption and digital signature. The security of RSA depends on the factor of large integer, and the effective attack is to decompose N. In order to speed up the decryption of RSA, we ordinary vise the Chinese Remainder Theorem(CRT)[2], which is4times of the classic RSA.
Back in1997, Boneeh. Demillo and Lipton showed that RSA-CRT imple-mentations are vulnerable to fault attacks. Assuming that the adversary uses the relation of fault signatures and correct signatures to decompose N by in-jecting fault signatures. This attack applies to any deterministic padding func-tion, such as RSA PKCS#1v1.5or Full-Domain Hash[3]. In2005, Seifert[4] introduced a new type of RSA fault attacks, by inducing faults on the RSA public modulus. The initial attack only allowed to bypass RSA verification, but key-recovery attacks were later discovered by Brier et al[5], and improved or extended in. These key-recovery attacks only apply to RSA without CRT, and they require significantly more faults than Boneh et al.'s attack.
In2012Eric Brier, David Naccache, Phong Q. Nguyen and Mehdi Tibouchi[10] presented new key-recovery attacks on RSA-CRT signatures based on the or-thogonal lattice techniques, which injected faults into the public modulus with physical experiments with laser shot. This attack needs to apply every param-eter of RSA-CRT neatly: returns the signature of RSA-CRT: we can get fault signature σ' by injecting faults into the public mmodulus: by applying the Chinese Remainder Theorem to σ and σ', the adversary can compute we construct linear combinations of unknown integers a and/3by signature pairs (σ.σ'). Applying orthogonal lattice techniques to recovery σp and ρq, the adversary could discover the factorization. They are very effective in practice: they disclose the RSA factorization within a few seconds using only5fault and correct signatures on a standard PC.
In this paper we show another modulus fault attack against RSA-CRT borrowing ideas from before with higher efficiency. Using v=σp·α+σq·β∈Z generated before, we transform v: Moreover, observe that α+β=X+1. Therefore, we have: Hence, if we let ω=(σ·(N+1)-v)/N, we get:
This value ω is an integer. The adversary can discuss and analyze the ω by assumption, the smallest prime factor min(p, q) of N can be recovered by dichotomy, then the adversary could attack RSA-CRT.
In such a setting, the adversary need to analyze the property of the ω. He gets ω=0if σ0otherwise. Trying this process again at most log N times, the bound of the smallest prime factor could be determined.
Carrying out this attack need the following two fault models:either the faulted moduli only differ from the public modulus on a single byte of un-known position and unknown value, or the faulted moduli may differ from the public modulus by many bytes, but the differences are restricted to the least significant bits, up to half of the modulus size. By the way, we assume further that the adversary can ask signatures of his choice, signatures are computed without padding and physical device under consideration will answer arbitrary signature queries.
This paper is organized as follows. Chapter1recalls some basic facts about RSA algorithm, how to set parameters of using the Chinese Remain-der Theorem to speed up signature generation and modulus fault attacks of orthogonal lattice techniques. Chapter2generalizes the constructions of new parameter ω and gives the certification of attack. In Chapter3, we give the comparison of two fault modulus attacks. Finally, in Chapter4, we extend analysis of two fault models.
1997年,Boneeh, Demillo和Lipton指出RSA-CRT容易受到错误攻击的威胁,即假设攻击者通过植入错误签名,可以利用错误签名和正确签名的关系将N进行分解。这种攻击适用于将消息m经过编码处理的RSA加密算法,比如RSA PKCS#1v1.5或者Full-Domain Hash [3]。 Seifert[4]于2005年利用RSA公开的模N对RSA进行错误攻击。此攻击适用于RSA的数字签名,随后Brier et al[5]提出了密钥恢复攻击,并在文献[6,7,8,9]中做出改进。但后来改进的密钥恢复攻击仅适用于不含CRT的RSA加密算法,而且比Brier etal攻击需要更多的错误签名。
2012年Eric Brier, David Naccache, Phong Q. Nguyen和Mehdi Tibouchi[10]利用正交格原理提出了一种新的RSA错误模攻击。他们利用恢复密钥的方法来对RSA-CRT签名进行攻击,其中攻击是需要注入的激光技术来实现错误模的生成。这种攻击灵活使用了RSA-CRT签名中的各项参数,即：然后生成RSA-CRT签名：利用错误模注入技术得到错误签名σ′,即：对生成的两种签名σ和σ′使用中国剩余定理可计算出：通过签名对(σ,σ′)可以构造出带有未知整参数α，β的多组线性组合。最后利用格的约化算法来恢复参数σp和σq，最终达到分解八’的目的。实践证明他们的方法是高效的,假设敌手能够获得5对正确的签名与错误的签名,利用-台标准的计算机就可以在几秒钟内将N进行分解。
本文根据上述的错误模攻击提出了新的攻击RSA-CRT的方法,计算效率更高,通过转换上述攻击中生成的v=σp·α+σq·β∈Z,将v进一步变形：观察可知α+β=N+1,因此可得：并引入参数ω=(σ·(N+1)-v)/N,通过变形可以得到：
通过证明可以得出ω是一个整数。最后通过敌手的假设对ω进行讨论和精确求解,利用二分法求解N的最小素因子min(p,q),实现对大整数N的分解,最终达到攻击RSA-CRT的目的。
本文的攻击需要对ω进行讨论,根据ω所定义的形式可以获知,如果σ
错误模N′的有两种不同的情况,不同的错误模V′所需要的错误实例也是不同的,即一种是错误N′与初始的N相差一个未知比特；另一种是错误N′与初始N′的不同要少于最低有效位比特的一半：最低有效位比特的错误数量最多不能超过N长度的一半。此外,我们假设攻击者可以根据自己的需要向模拟器请求签名,模拟器亦必须无条件的回复攻击者的签名请求,这样,攻击者可以从回复的签名中寻找适合攻击的签名。
本文章节安排如下,第一章介绍RSA公钥算法的基础知识,包括利用中国剩余定理进行快速求解的参数设置，利用正交格求解RSA-CRT的错误模攻击。第二章介绍构造新参数ω以及攻击的严格理论证明。第三章将对前后两种的错误模攻击进行分析比较。第四章给出两种错误模N的分析。
RSA[1] was proposed by Ron Rivest, Adi Shamir and Len Adleman in1977, and is widely used in encryption and digital signature. The security of RSA depends on the factor of large integer, and the effective attack is to decompose N. In order to speed up the decryption of RSA, we ordinary vise the Chinese Remainder Theorem(CRT)[2], which is4times of the classic RSA.
Back in1997, Boneeh. Demillo and Lipton showed that RSA-CRT imple-mentations are vulnerable to fault attacks. Assuming that the adversary uses the relation of fault signatures and correct signatures to decompose N by in-jecting fault signatures. This attack applies to any deterministic padding func-tion, such as RSA PKCS#1v1.5or Full-Domain Hash[3]. In2005, Seifert[4] introduced a new type of RSA fault attacks, by inducing faults on the RSA public modulus. The initial attack only allowed to bypass RSA verification, but key-recovery attacks were later discovered by Brier et al[5], and improved or extended in. These key-recovery attacks only apply to RSA without CRT, and they require significantly more faults than Boneh et al.'s attack.
In2012Eric Brier, David Naccache, Phong Q. Nguyen and Mehdi Tibouchi[10] presented new key-recovery attacks on RSA-CRT signatures based on the or-thogonal lattice techniques, which injected faults into the public modulus with physical experiments with laser shot. This attack needs to apply every param-eter of RSA-CRT neatly: returns the signature of RSA-CRT: we can get fault signature σ' by injecting faults into the public mmodulus: by applying the Chinese Remainder Theorem to σ and σ', the adversary can compute we construct linear combinations of unknown integers a and/3by signature pairs (σ.σ'). Applying orthogonal lattice techniques to recovery σp and ρq, the adversary could discover the factorization. They are very effective in practice: they disclose the RSA factorization within a few seconds using only5fault and correct signatures on a standard PC.
In this paper we show another modulus fault attack against RSA-CRT borrowing ideas from before with higher efficiency. Using v=σp·α+σq·β∈Z generated before, we transform v: Moreover, observe that α+β=X+1. Therefore, we have: Hence, if we let ω=(σ·(N+1)-v)/N, we get:
This value ω is an integer. The adversary can discuss and analyze the ω by assumption, the smallest prime factor min(p, q) of N can be recovered by dichotomy, then the adversary could attack RSA-CRT.
In such a setting, the adversary need to analyze the property of the ω. He gets ω=0if σ
Carrying out this attack need the following two fault models:either the faulted moduli only differ from the public modulus on a single byte of un-known position and unknown value, or the faulted moduli may differ from the public modulus by many bytes, but the differences are restricted to the least significant bits, up to half of the modulus size. By the way, we assume further that the adversary can ask signatures of his choice, signatures are computed without padding and physical device under consideration will answer arbitrary signature queries.
This paper is organized as follows. Chapter1recalls some basic facts about RSA algorithm, how to set parameters of using the Chinese Remain-der Theorem to speed up signature generation and modulus fault attacks of orthogonal lattice techniques. Chapter2generalizes the constructions of new parameter ω and gives the certification of attack. In Chapter3, we give the comparison of two fault modulus attacks. Finally, in Chapter4, we extend analysis of two fault models.
引文
[1]R. L. Rivest, A. Shamir, and L. M. Adleman. A method for obtaining digital signatures and public-key cryptosystems. Commun. ACM,21(2): 120-126,1978.
[2]D. Boneh, R. A. DwMillo, and R. J. Lipton. On the importance of eliminati-ing errors in cryptographic computations. J. Cryptology,14(2):101-119, 2001.
[3]M. Bellare and P. Rpgaway. The exact security of digital signatures:How to sign with RSA and Rabin. In EUROCRYPT, page 399-416,1996.
[4]J.-P. Serfert. On authenticated computing and rsa-based authentication. In V. Atluri, C. Meadows, and A. Juels, editors, ACM Conference on Computer and Communications Security, pages 122-127. ACM.2005.
[5]E. Brier, B. Chevallier-Mames, M. Ciet, and C. Clavier. Why one should also secure RSA public key elements. In L. Goubin and M. Matsui, editors, CHES, volume 4249 of Lecture Notes in Computer Science, pages 324-338. Springer,2006.
[6]J. A. Muir. Scifert's RSA fault attack:Simplified analysis and general-izations. In P. Ning, S. Qing, and N. LI, editors, ICICS, volume 4307 of Lecture Notes in Computer Science, pages 420-434. Springer,2006.
[7]A. Berzati, C. Canovas, and L. Goubin. Perturbating RSA public keys: An improved attack. In E. Oswald and P. Rohatgi, editors, CHES, volume 5154 of Lecture Notes in Computer Science, pages 380-395. Springer,2008.
[8]A. Berzati, C. Canovas, J.-G. Dumas, and L. Goubin. Fault attacks on RSA public keys:Left-to-right implementations are also vulnerable. In M. Fischlin, editor, CT-RSA, volume 5473 of Lecture Notes in Computer Science, pages 414-428. Springer,2009.
[9]A. Berzati, C. Canovas, and L. Goubin. Public key perturbation of random-ized RSA implementations. In S. Mangard and F.-X. Standaert, editors, CHES, volume 6225 of Lecture Notes in Computer Science, pages 306-319. Springer,2010.
[10]Eric Brier, David Naccache, Phong Q. Nguyen, and Mehdi Tibouch. Mod-ulus fault attacks against RSA-CRT signatures. In:Preneel, B., Takagi, T. (eds.) ChES 2011. LNCS, volume 6917, pp.192-206. Springer,2011.
[11]A. K. Lenstra, H. W. Lenstra, jr., M. S. Manasse, and J. M. Pollard. The number field sieve. In proceeding of the 22nd Annual ACM Symposium on the Theory of Xomputation, pages 564-572,1990.
[12]T. L. Grobler, W. T. Penzhorn. Fast decryption method for the RSA cryptosystem. Cryptosystem. IEEE AFRICON 2004.1,361-364.
[13]HK. Rosen. Elementary number theory and its apolications. AT&T Bell Laboratories,1993.
[14]J.-J. Quisquater and C. Couvrur. Fast decipherment algorithm for RSA public-key cryptosystems. Electronic Letters, no.18, pp.905-907,1982.
[15]P. M. Gruber and C. G.Lekkerkerker. Geometry of numbers. North-Holland, Amsterdam,1969.
[16]H. Cohen. A course in computational algebraic number theory. Springer-Verlag, Berlin,1993.
[17]A. K. Lenstra, H. W. Lenstra, and L. Lovasz. Factoring polynomials with rationalcoefficient. Math. Ann.,261:515-534,1982.
[18]A. Joux and J. Stern. Lattice reduction:a toolbox for the cryptanalyst (to appear in J. of Cryptology).
[19]P. Q. Nguyen and J. Stern. Merkle-Hellman revistied:A cryptoanalysisi of the Qu-Vanstone cryptosystem based on group factorizations. In B. S. Kaliski Jr., editor, CRYPTO, volume 1294 of Lecture Notes in Computer Science, pages 198-212. Springer,1997.
[20]P. Q. Nguyen and J. Stern. Cryptanalysis of a fast public key cryp-tosysyten presented at SAC:97. In S. E. Tavares and H. Meijer, editors, Selected Areas in Cryptography, volume 1556 of Lecture Notes in Comput-er Science, pages 218-218. Springer,1997.
[2]D. Boneh, R. A. DwMillo, and R. J. Lipton. On the importance of eliminati-ing errors in cryptographic computations. J. Cryptology,14(2):101-119, 2001.
[3]M. Bellare and P. Rpgaway. The exact security of digital signatures:How to sign with RSA and Rabin. In EUROCRYPT, page 399-416,1996.
[4]J.-P. Serfert. On authenticated computing and rsa-based authentication. In V. Atluri, C. Meadows, and A. Juels, editors, ACM Conference on Computer and Communications Security, pages 122-127. ACM.2005.
[5]E. Brier, B. Chevallier-Mames, M. Ciet, and C. Clavier. Why one should also secure RSA public key elements. In L. Goubin and M. Matsui, editors, CHES, volume 4249 of Lecture Notes in Computer Science, pages 324-338. Springer,2006.
[6]J. A. Muir. Scifert's RSA fault attack:Simplified analysis and general-izations. In P. Ning, S. Qing, and N. LI, editors, ICICS, volume 4307 of Lecture Notes in Computer Science, pages 420-434. Springer,2006.
[7]A. Berzati, C. Canovas, and L. Goubin. Perturbating RSA public keys: An improved attack. In E. Oswald and P. Rohatgi, editors, CHES, volume 5154 of Lecture Notes in Computer Science, pages 380-395. Springer,2008.
[8]A. Berzati, C. Canovas, J.-G. Dumas, and L. Goubin. Fault attacks on RSA public keys:Left-to-right implementations are also vulnerable. In M. Fischlin, editor, CT-RSA, volume 5473 of Lecture Notes in Computer Science, pages 414-428. Springer,2009.
[9]A. Berzati, C. Canovas, and L. Goubin. Public key perturbation of random-ized RSA implementations. In S. Mangard and F.-X. Standaert, editors, CHES, volume 6225 of Lecture Notes in Computer Science, pages 306-319. Springer,2010.
[10]Eric Brier, David Naccache, Phong Q. Nguyen, and Mehdi Tibouch. Mod-ulus fault attacks against RSA-CRT signatures. In:Preneel, B., Takagi, T. (eds.) ChES 2011. LNCS, volume 6917, pp.192-206. Springer,2011.
[11]A. K. Lenstra, H. W. Lenstra, jr., M. S. Manasse, and J. M. Pollard. The number field sieve. In proceeding of the 22nd Annual ACM Symposium on the Theory of Xomputation, pages 564-572,1990.
[12]T. L. Grobler, W. T. Penzhorn. Fast decryption method for the RSA cryptosystem. Cryptosystem. IEEE AFRICON 2004.1,361-364.
[13]HK. Rosen. Elementary number theory and its apolications. AT&T Bell Laboratories,1993.
[14]J.-J. Quisquater and C. Couvrur. Fast decipherment algorithm for RSA public-key cryptosystems. Electronic Letters, no.18, pp.905-907,1982.
[15]P. M. Gruber and C. G.Lekkerkerker. Geometry of numbers. North-Holland, Amsterdam,1969.
[16]H. Cohen. A course in computational algebraic number theory. Springer-Verlag, Berlin,1993.
[17]A. K. Lenstra, H. W. Lenstra, and L. Lovasz. Factoring polynomials with rationalcoefficient. Math. Ann.,261:515-534,1982.
[18]A. Joux and J. Stern. Lattice reduction:a toolbox for the cryptanalyst (to appear in J. of Cryptology).
[19]P. Q. Nguyen and J. Stern. Merkle-Hellman revistied:A cryptoanalysisi of the Qu-Vanstone cryptosystem based on group factorizations. In B. S. Kaliski Jr., editor, CRYPTO, volume 1294 of Lecture Notes in Computer Science, pages 198-212. Springer,1997.
[20]P. Q. Nguyen and J. Stern. Cryptanalysis of a fast public key cryp-tosysyten presented at SAC:97. In S. E. Tavares and H. Meijer, editors, Selected Areas in Cryptography, volume 1556 of Lecture Notes in Comput-er Science, pages 218-218. Springer,1997.