An Enhanced Lattice Attack to DSA and ECDSA Scheme

doi:10.3969/j.issn.1671-1122.2022.02.002

Abstract

Abstract:

The basic idea behind one type of lattice attack to DSA and ECDSA scheme is to construct a system of congruences, and convert the hidden number problem into the nearest vector problem. if one of the solutions of the congruences is below a certain bound, the private key can be found by solving the closest vector. If the bound becomes larger, the size of solution within which the attack is effective can be broadened accordingly, thus reducing the level to construct such congruences. A new bound based on the oretical analysis and calculation was presented. The new bound was 6.92 times larger than the original one, reducing the level to launch an effective lattice attack significantly. This paper designed and implemented experiment to verify this new bound by collecting signatures from OpenSSL. The results show that under the new bound, the lattice attack only require solution vector’s elements’ 3 most significant bits to be known, compared with 6 most significant bits to be known before. For DSA, the success rate is about 80% with a lattice of size 350. For ECDSA, the success rate is about 97% with a lattice of size 260. Furthermore, by subtracting a base vector from the solution vector, the requirement of known bits can be reduced to just one, the difficulty to mount an attack can be reduced even further.

Key words: lattice attack, hidden number problem, closest vector problem, DSA, ECDSA

CLC Number:

TP309

YU Fajiang, JIA Yaomin. An Enhanced Lattice Attack to DSA and ECDSA Scheme[J]. Netinfo Security, 2022, 22(2): 11-20.

Figures/Tables 6

References 28

[1]	FIPS PUB 186-4 Digital Signature Standard (DSS)[S]. USA: Department of Commerce/National Institute of Standards and Technology: Federal Information Processing Standards Publication, 2013.
[2]	ARANHA D F, NOVAES F R, TAKAHASHI A, et al. LadderLeak: Breaking ECDSA with Less than One Bit of Nonce Leakage[C]//ACM. 2020 ACM SIGSAC Conference on Computer and Communications Security (CCS’20), November 9-13, 2020, NY, USA. New York: ACM, 2020: 225-242.
[3]	MA Ziqiang, LI Bingyu, CAI Quanwei, et al. Applications and Developments of the Lattice Attack in Side Channel Attacks[C]//ACNS. ACNS 2020: Applied Cryptography and Network Security Workshops, February 5-9, 2020, New Orleans, USA. Heidelberg: Springer, 2020: 435-452.
[4]	BONEH D, VENKATESAN R. Hardness of Computing the Most Significant Bits of Secret Keys in Diffie-Hellman and Related Schemes[C]//Springer. CRYPTO’1996: Advances in Cryptology, August 18-22, 1996, California, USA. Heidelberg: Springer, 1996: 129-142.
[5]	MICCIANCIO D, GOLDWASSER S. Complexity of Lattice Problems[M]. Heidelberg: Springer, 2002.
[6]	LENSTRA A K, LENSTRA H W, LOVÁSZ L. Factoring Polynomials with Rational Coefficients[J]. Mathematische Annalen, 1982, 261(4):515-534. doi: 10.1007/BF01457454 URL
[7]	BABAI L. On Lovasz’ Lattice Reduction and the Nearest Lattice Point Problem[J]. Combinatorica, 1986, 6(1):1-13. doi: 10.1007/BF02579403 URL
[8]	HOWGRAVE-GRAHAM N A, SMART N P. Lattice Attacks on Digital Signature Schemes[J]. Designs, Codes and Cryptography, 2001, 23(3):283-290. doi: 10.1023/A:1011214926272 URL
[9]	NGUYEN P Q, SHPARLINSKI I E. The Insecurity of the Digital Signature Algorithm with Partially Known Nonces[J]. Journal of Cryptology, 2003, 15(3):151-176. doi: 10.1007/s00145-002-0021-3 URL
[10]	NGUYEN P Q, SHPARLINSKI I E. The Insecurity of the Elliptic Curve Digital Signature Algorithm with Partially Known Nonces[J]. Designs, Codes and Cryptography, 2001, 30(2):201-217. doi: 10.1023/A:1025436905711 URL
[11]	HLAVAC M, ROSA T. Extended Hidden Number Problem and Its Cryptanalytic Applications[C]//Springer. SAC 2006: Selected Areas in Cryptography, August 17-18, 2006, Montreal, Canada. Heidelberg: Springer, 2006: 114-133.
[12]	BENGER N, POL J V D, SMART N P, et al. Ooh Aah Just a Little Bit: A Small Amount of Side Channel Can Go a Long Way[C]//Springer. Cryptographic Hardware and Embedded Systems-CHES 2014, September 23-26, 2014, Busan, Republic of Korea. Heidelberg: Springer, 2014: 75-92.
[13]	POL J V D, SMART N P, YAROM Y. Just a Little Bit More[C]//Springer. Cryptographers’ Track at the RSA Conference (CT-RSA 2015), April 20-24, 2015, San Francisco, CA, USA. Heidelberg: Springer, 2015: 3-21.
[14]	FAN Shuqin, WANG Wenbo, CHENG Qingfeng. Attacking OpenSSL Implementation of ECDSA with a Few Signatures[C]//ACM. 2016 ACM SIGSAC Conference on Computer and Communications Security (CCS’16), October 24-28, 2016, Vienna, Austria. New York: ACM, 2016: 1505-1515.
[15]	RYAN K. Return of the Hidden Number Problem: A Widespread and Novel Key Extraction Attack on ECDSA and DSA[EB/OL]. https://www.researchgate.net/publication/346703657_Return_of_the_Hidden_Number_Problem_A_Widespread_and_Novel_Key_Extraction_Attack_on_ECDSA_and_DSA, , 2018-11-20.
[16]	ARANHA D F, FOUQUE P A, GÉRARD B, et al. GLV/GLS Decomposition, Power Analysis, and Attacks on ECDSA Signatures with Single-bit Nonce Bias[C]//Springer. International Conference on the Theory and Application of Cryptology and Information Security 2014, December 7-11, 2014, Taibei, Taiwan, China. Heidelberg: Springer, 2014: 262-281.
[17]	GENKIN D, PACHMANOV L, PIPMAN I, et al. ECDSA Key Extraction from Mobile Devices via Nonintrusive Physical Side Channels[C]//ACM. 2016 ACM SIGSAC Conference on Computer and Communications Security (CCS’16), October 24-28, 2016, Vienna, Austria. New York: ACM, 2016: 1626-1638.
[18]	BELGARRIC P, FOUQUE P A, MACARIO-RAT G, et al. Side-channel Analysis of Weierstrass and Koblitz Curve ECDSA on Android Smartphones[C]//Springer. Cryptographers’ Track at the RSA Conference 2016, February 29-March 4, 2016, San Francisco, CA, USA. Heidelberg: Springer, 2016: 232-256.
[19]	ZHANG Kaiyu, XU Sen, GU Dawu, et al. Practical Partial-nonce-exposure Attack on ECC Algorithm[C]//IEEE. 13th International Conference on Computational Intelligence and Security (CIS), December 15-18, 2017, Hong Kong, China. Piscataway: IEEE, 2017: 248-252.
[20]	CAO Weiqiong, FENG Jingyi, CHEN Hua, et al. Two Lattice-based Differential Fault Attacks Against ECDSA with wNAF Algorithm[C]//Springer. Information Security and Cryptology-ICISC 2015, November 25-27, 2015, Seoul, Republic of Korea. Heidelberg: Springer, 2015: 297-313.
[21]	NGUYEN P Q, TIBOUCHI M. Fault Analysis in Cryptography[M]. Heidelberg: Springer, 2012.
[22]	BRUMLEY B B, TUVERI N. Remote Timing Attacks Are Still Practical[C]//Springer. Computer Security-ESORICS 2011, September 12-14, 2011, Leuven, Belgium. Heidelberg: Springer, 2011: 355-371.
[23]	MOGHIMI D, SUNAR B, EISENBARTH T, et al. TPM-FAIL: TPM Meets Timing and Lattice Attacks[EB/OL]. https://arxiv.org/abs/1911.05673, 2019-11-13.
[24]	TIBOUCHI M. Attacks on (EC) DSA with Biased Nonces[EB/OL]. https://ecc2017.cs.ru.nl/slides/ecc2017-tibouchi.pdf, 2017-11-13.
[25]	POULAKIS D. New Lattice Attacks on DSA Schemes[J]. Journal of Mathematical Cryptology, 2016, 10(2):135-144.
[26]	ADAMOUDIS M, DRAZIOTIS K A, POULAKIS D. Enhancing an Attack to DSA Schemes[C]//Springer. International Conference on Algebraic Informatics (CAI 2019), June 30-July 4, 2019, Niš, Serbia. Heidelberg: Springer, 2019: 13-25.
[27]	ADAMOUDIS M, DRAZIOTIS K A, POULAKIS D. Attacking (EC) DSA with Partially Known Multiples of Nonces[J]. IACR Cryptol ePrint Archive, 2021, 35(10):347-356.
[28]	SUN Chao, ESPITAU T, TIBOUCHI M, et al. Guessing Bits: Improved Lattice Attacks on (EC)DSA[J]. IACR Transactions on Cryptographic Hardware and Embedded Systems, 2021, 28(1):391-413.

已知比特数$l$	格的维度最小值$d$
1	5110
2	270
3	135

	仅前2 bit为0	仅前1 bit为0
DSA	76%	57%
ECDSA	89%	87%