short-paper

Mind Your Nonces Moving: Template-Based Partially-Sharing Nonces Attack on SM2 Digital Signature Algorithm

Authors:

Hongsong ShiAuthors Info & Claims

ASIA CCS '15: Proceedings of the 10th ACM Symposium on Information, Computer and Communications Security

Pages 609 - 614

https://doi.org/10.1145/2714576.2714587

Published: 14 April 2015 Publication History

Abstract

This paper gives a partially-sharing nonces attack on SM2 Digital Signature Algorithm (SM2DSA). Templates, which are built in the scenario of no secrets known, are used to detect the collisions on the Most Significant Byte of the Nonces (MSBN). Targeting a real world smartcard with 8-bit precharged bus, the power consumption of data moving procedure after the random number generation is focused, on which the template building and matching phases are based. With the templates, we obtain a number of pairs of nonces whose first bytes are collided, then a lattice attack on SM2DSA is proposed to recover the private key. Experiments show that our attack works smoothly; our attack is the first implemented lattice attack on SM2DSA in a smartcard, which can also be extended to the other ECC algorithms like ECDSA.

References

[1]

C. Archambeau, E. Peeters, F.-X. Standaert, and J.-J. Quisquater. Template Attacks in Principal Subspaces. In L. Goubin and M. Matsui, editors, CHES 2006, volume 4249 of LNCS, pages 1--14. Springer, 2006.

Digital Library

[2]

R. Avanzi, H. Cohen, C. Doche, G. Frey, T. Lange, K. Nguyen, and F. Vercauteren. Handbook of Elliptic and Hyperelliptic Curve Cryptography. CRC Press, Boca Raton, 2005.

Digital Library

[3]

D. Boneh and R. Venkatesan. Hardness of Computing the Most Significant Bits of Secret Keys in Diffie-Hellman and Related Schemes. In N. Koblitz, editor, CRYPTO 1996, volume 1109 of LNCS, pages 129--142. Springer, 1996.

Digital Library

[4]

D. Boneh and R. Venkatesan. Rounding in Lattices and Its Cryptographic Applications. In M. E. Saks, editor, SODA 1997, pages 675--681. ACM/SIAM, 1997.

Digital Library

[5]

S. Chari, J. R. Rao, and P. Rohatgi. Template Attacks. In B. S. K. Jr., Çetin Kaya Koç, and C. Paar, editors, CHES 2002, volume 2523 of LNCS, pages 13--28. Springer, 2002.

Digital Library

[6]

O. Choudary and M. G. Kuhn. Efficient Template Attacks. In A. Francillon and P. Rohatgi, editors, CARDIS 2013, volume 8419 of LNCS, pages 253--270. Springer, 2014.

[7]

EMV. Integrated Circuit Card Specifications for Payment Systems. Version 4.3 (November 2011). http://www.emvco.com.

[8]

J.-C. Faugére, C. Goyet, and G. Renault. Attacking (EC)DSA Given Only an Implicit Hint. In L. R. Knudsen and H. Wu, editors, Selected Areas in Cryptography 2012, volume 7707 of LNCS, pages 252--274. Springer, 2013.

[9]

H. Hotelling. Analysis of a Complex of Statistical Variables Into Principal Components. J. Educ. Psych., 24, 1933.

[10]

N. Howgrave-Graham and N. P. Smart. Lattice Attacks on Digital Signature Schemes. Des. Codes Cryptography, 23(3):283--290, 2001.

Digital Library

[11]

R. Kannan. Minkowski's Convex Body Theorem and Integer Programming. Mathematics of Operations Research, 12(3):415--440, 1987.

Digital Library

[12]

P. C. Kocher. Timing Attacks on Implementations of Diffie-Hellman, RSA, DSS, and Other Systems. In N. Koblitz, editor, CRYPTO 1996, volume 1109 of LNCS, pages 104--113. Springer, 1996.

Digital Library

[13]

A. Lenstra, J. Lenstra, H.W., and L. Lovĺćsz. Factoring polynomials with rational coefficients. Mathematische Annalen, 261(4):515--534, 1982.

[14]

M. Liu, J. Chen, and H. Li. Partially Known Nonces and Fault Injection Attacks on SM2 Signature Algorithm. In D. Lin, S. Xu, and M. Yung, editors, Inscrypt 2013, volume 8567 of LNCS, pages 343--358. Springer, 2014.

[15]

M. Liu and P. Q. Nguyen. Solving BDD by Enumeration: An Update. In E. Dawson, editor, CT-RSA 2013, volume 7779 of LNCS, pages 293--309. Springer, 2013.

Digital Library

[16]

S. Mangard, E. Oswald, and T. Popp. Power Analysis Attacks: Revealing the Secrets of Smart Cards. Springer, 2007.

[17]

D. Naccache, P. Q. Nguyen, M. Tunstall, and C. Whelan. Experimenting with Faults, Lattices and the DSA. In S. Vaudenay, editor, Public Key Cryptography 2005, volume 3386 of LNCS, pages 16--28. Springer, 2005.

Digital Library

[18]

National Institute of Standards and Technology (NIST). FIPS Publication 186--4: Digital Signature Standard, 2013.

[19]

P. Q. Nguyen and I. Shparlinski. The Insecurity of the Elliptic Curve Digital Signature Algorithm with Partially Known Nonces. Des. Codes Cryptography, 30(2):201--217, 2003.

Digital Library

[20]

Office of State Commercial Cryptography Administration. Public Key Cryptographic Algorithm SM2 Based on Elliptic Curves (in Chinese). http://www.oscca.gov.cn/News/201012/News_1198.htm.

[21]

C. P. Schnorr and M. Euchner. Lattice Basis Reduction: Improved Practical Algorithms and Solving Subset Sum Problems. Mathematics of Programming, 66:181--191, 1994.

Digital Library

[22]

S. Shen and X. Lee. SM2 Digital Signature Algorithm draft-shen-sm2-ecdsa-01. http://tools.ietf.org/pdf/draft-shen-sm2-ecdsa-01.pdf.

[23]

V. Shoup. Number Theory C++ Library (NTL) version 5.5.2. http://www.shoup.net/ntl/.

[24]

F.-X. Standaert and C. Archambeau. Using Subspace-Based Template Attacks to Compare and Combine Power and Electromagnetic Information Leakages. In E. Oswald and P. Rohatgi, editors, CHES 2008, volume 5154 of LNCS, pages 411--425. Springer, 2008.

Digital Library

Cited By

Han GBai XGeng SQin B(2022)Efficient two-party SM2 signing protocol based on secret sharingJournal of Systems Architecture: the EUROMICRO Journal10.1016/j.sysarc.2022.102738132:COnline publication date: 1-Nov-2022
https://dl.acm.org/doi/10.1016/j.sysarc.2022.102738
Cao JCheng QWeng J(2022)EHNP Strikes Back: Analyzing SM2 ImplementationsProgress in Cryptology - AFRICACRYPT 202210.1007/978-3-031-17433-9_25(576-600)Online publication date: 6-Oct-2022
https://doi.org/10.1007/978-3-031-17433-9_25
Tuveri NHassan SGarcia CBrumley B(2018)Side-Channel Analysis of SM2Proceedings of the 34th Annual Computer Security Applications Conference10.1145/3274694.3274725(147-160)Online publication date: 3-Dec-2018
https://dl.acm.org/doi/10.1145/3274694.3274725
Show More Cited By

Index Terms

Mind Your Nonces Moving: Template-Based Partially-Sharing Nonces Attack on SM2 Digital Signature Algorithm
1. Theory of computation
  1. Design and analysis of algorithms
    1. Data structures design and analysis
      1. Pattern matching

Recommendations

Attacking OpenSSL Implementation of ECDSA with a Few Signatures
CCS '16: Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security

In this work, we give a lattice attack on the ECDSA implementation in the latest version of OpenSSL, which implement the scalar multiplication by windowed Non-Adjacent Form method. We propose a totally different but more efficient method of extracting ...
Partially Known Nonces and Fault Injection Attacks on SM2 Signature Algorithm
Information Security and Cryptology
Abstract
SM2 digital signature scheme, which is part of the Chinese public key cryptosystem standard SM2 issued by Chinese State Cryptography Administration, is based on the elliptic curve discrete logarithm problem. Since SM2 was made public, very few ...
A Novel Template Attack on wNAF Algorithm of ECC
CIS '14: Proceedings of the 2014 Tenth International Conference on Computational Intelligence and Security

Template attack is more powerful than SPA and CPA in some situations. In this paper, a novel template attack named DTTA is proposed to attack the wNAF algorithm of ECC. SM2 is the Chinese public key cryptosystem standard issued in 2010. Few results of ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ASIA CCS '15: Proceedings of the 10th ACM Symposium on Information, Computer and Communications Security

April 2015

698 pages

ISBN:9781450332453

DOI:10.1145/2714576

General Chairs:
Feng Bao
Huawei Technologies Pte Ltd, Singapore
,
Steven Miller
Singapore Management University, Singapore
,
Program Chairs:
Jianying Zhou
Institute for Infocomm Research, Singapore
,
Gail-Joon Ahn
Arizona State University, USA

Copyright © 2015 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGSAC: ACM Special Interest Group on Security, Audit, and Control

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 14 April 2015

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Short-paper

Funding Sources

12th Five-Year PlanThe National Development Foundation for Cryptological Research
National Natural Science Foundation of China

Conference

ASIA CCS '15

Sponsor:

SIGSAC

ASIA CCS '15: 10th ACM Symposium on Information, Computer and Communications Security

April 14 - March 17, 2015

Singapore, Republic of Singapore

Acceptance Rates

ASIA CCS '15 Paper Acceptance Rate 48 of 269 submissions, 18%;

Overall Acceptance Rate 418 of 2,322 submissions, 18%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
157
Total Downloads

Downloads (Last 12 months)9
Downloads (Last 6 weeks)1

Reflects downloads up to 30 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Han GBai XGeng SQin B(2022)Efficient two-party SM2 signing protocol based on secret sharingJournal of Systems Architecture: the EUROMICRO Journal10.1016/j.sysarc.2022.102738132:COnline publication date: 1-Nov-2022
https://dl.acm.org/doi/10.1016/j.sysarc.2022.102738
Cao JCheng QWeng J(2022)EHNP Strikes Back: Analyzing SM2 ImplementationsProgress in Cryptology - AFRICACRYPT 202210.1007/978-3-031-17433-9_25(576-600)Online publication date: 6-Oct-2022
https://doi.org/10.1007/978-3-031-17433-9_25
Tuveri NHassan SGarcia CBrumley B(2018)Side-Channel Analysis of SM2Proceedings of the 34th Annual Computer Security Applications Conference10.1145/3274694.3274725(147-160)Online publication date: 3-Dec-2018
https://dl.acm.org/doi/10.1145/3274694.3274725
Pan WZheng FZhao YZhu WJing J(2017)An Efficient Elliptic Curve Cryptography Signature Server With GPU AccelerationIEEE Transactions on Information Forensics and Security10.1109/TIFS.2016.260397412:1(111-122)Online publication date: 1-Jan-2017
https://dl.acm.org/doi/10.1109/TIFS.2016.2603974

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents