logo

SCIENCE CHINA Information Sciences, Volume 62 , Issue 3 : 032105(2019) https://doi.org/10.1007/s11432-018-9515-9

Partially known information attack on SM2 key exchange protocol

More info
  • ReceivedMay 15, 2018
  • AcceptedJul 4, 2018
  • PublishedJan 24, 2019

Abstract

SM2 key exchange protocol is a part of the SM2 public key cryptographic algorithm based on elliptic curves which has been issued by Chinese State Cryptography Administration since 2010. Under the guide of Chinese government, SM2 has been widely used in Chinese commercial applications. This paper gives the first partially known information attack on SM2 key exchange protocol. Our attack is based on a technique modified from the hidden number problem (HNP) which was introduced originally to study the bit security of Diffie-Hellman and related schemes. We present a polynomial-time algorithm which could recover the user's secret key when given about half least significant bits of the two unknown intermediate values in each congruence over about 30 to 40 instances. Compared with the standard HNP, our approach deals with congruence involved two independent unknown variables and each of them possesses the same size as the secret key. Moreover, our results almost coincide with the previous best result among the same field considering the extreme case in which one variant is completely revealed.


Acknowledgment

This work was supported by National Key Research and Development Program of China (Grant Nos. 2016YFB0800902, 2016YFF0204004), and National Nature Science Foundation of China (Grant No. 61402536). The authors would like to thank the anonymous referees for their valuable comments.


Supplement

Appendix

Proof of Lemma 4

Since $\|{\boldsymbol~r}\|_\infty<\kappa\eta$, we have \begin{align*}&|r_i|=|ne_i+2^{l'}y+\overline{x}_it_{i,1}-t_{i,2}|<\kappa\eta< 1, \mathrm{for} 1\leq i\leq m, \\ &|r_{m+1}|=\left|\frac{2^{l'}\eta}{n}y\right|<\kappa\eta, \\ & |r_{m+2i}|=\left|\frac{\eta}{2^l}t_{i,1}\right|< \kappa\eta< 1, \mathrm{for} 1\leq i\leq m, \\ & |r_{m+2i+1}|=\left|\frac{\eta}{2^{l'}}t_{i,2}\right|< \kappa\eta< 1, \mathrm{for} 1\leq i\leq m, \end{align*} which implies \begin{align*}&2^{l'}y+\overline{x}_it_{i,1}-t_{i,2}=0 \mathrm{mod} n, \mathrm{for} 1\leq i\leq m, \\ &|y|<\frac{\kappa n}{2^{l'}}, \\ &|t_{i,1}|<\kappa 2^l, |t_{i,2}|<\kappa 2^{l'}, \mathrm{for} 1\leq i\leq m. \end{align*} Assume the following relations for $1\leq~i\leq~m$, \begin{align*}&2^{l'}y=\kappa_yn+2^{l'}y_1+y_0 \mathrm{with} |\kappa_y|<\kappa, 0\leq y_1<n/2^{l'} \mathrm{and} 0\leq y_0<n, \\ &t_{i,2}=\kappa_i2^{l'}+t'_{i,2} \mathrm{with} 0\leq t'_{i,2}<2^{l'} \mathrm{and} |\kappa_i|<\kappa, \\ &t'_{i,1}=t_{i,1}+{\overline{x}_i}^{-1}(y_0-\kappa_i2^{l'}) \mathrm{mod} n, \\ &\overline{x}_i\cdot{\overline{x}_i}^{-1}=1+\kappa'_{i}n, \\ &e'_i=e_i+\kappa_y+\kappa'_{i}(y_0-\kappa_i2^{l'}). \end{align*} Then the vector ${\boldsymbol~r}'={\boldsymbol~z}'~{\boldsymbol~B}$ is also a lattice point with coordinates vector ${\boldsymbol~z}=(e'_1,\ldots,e'_m,y_1,t'_{1,1},t'_{1,2},\ldots,t'_{i,1},t'_{i,2},\ldots,t'_{m,1},\\t'_{m,2})$, which satisfies \begin{eqnarray*}|r'_i|&=&|ne'_i+2^{l'}y_1+\overline{x}_it'_{i,1}-t'_{i,2}| \\ &=&|ne'_i+2^{l'}y-\kappa_yn-y_0+\overline{x}_i(t_{i,1}+{\overline{x}_i}^{-1}(y_0-\kappa_i2^{l'}))+\kappa_in2^{l'}-t_{i,2}| \\ &=&|n(e'_i-\kappa_y-\kappa'_{i}(y_0-\kappa_i2^{l'}))+2^l y+\overline{x}_it_{i,1}-t_{i,2}| \\ &=&|ne_i+2^{l'}y+\overline{x}_it_{i,1}-t_{i,2}| \\ &=&|r_i|<\kappa\eta< 1, \mathrm{for} 1\leq i\leq m. \end{eqnarray*}

This implies that $ne'_i+2^{l'}y_1+\overline{x}_it'_{i,1}-t'_{i,2}=0$. Therefore, we obtain \begin{eqnarray*}2^{l'}y_1+\overline{x}_it'_{i,1}-t'_{i,2}&=&0 \mathrm{mod} n, \mathrm{for} 1\leq i\leq m. \end{eqnarray*}

For some fixed $y$, consider the event $E$ defined as $2^{l'}y_1-t'_{i,2}\neq0~\mathrm{mod}~n$ for all $i$. We first prove the upper bound for the probability that $E$ happens. For any $1\leq~i\leq~m$, we have \begin{equation} {\overline{x}_i}^{-1}= t'_{i,1}(2^{l'}y_1-t'_{i,2})^{-1} \mathrm{mod} n. \tag{6}\end{equation} There exist at most $(2\kappa~2^l-1)\cdot(2\kappa2^{l'}-1)$ number of possible tuples $(t_{i,1},~t_{i,2})$ which lead to a non-zero ${\overline{x}_i}^{-1}$. Thus the probability that Eq. (6) has a non-zero solution on $(t_{i,1},~t_{i,2})$ is less than \begin{eqnarray*}P_i(y) = \frac{(2\kappa 2^l-1)\cdot(2\kappa2^{l'}-1)}{n} \leq \frac{\kappa^2 2^{l+l'+2}}{n}. \end{eqnarray*}

Because all $\{\overline{x}_i\}_{i=1}^m$ are independent, the probability that $E$ happens under the condition of fixed $y$ is less than $$\prod_{i=1}^mP_i(y)\leq\frac{\kappa^{2m}2^{(l+l'+2)m} }{n^m}.$$

Denote $P_E$ as the probability that $E$ happens. With the bound for $y$, we obtain \begin{eqnarray*}P_E &\leq& \frac{\kappa n}{2^{l'}}\cdot\frac{\kappa^{2m}2^{(l+l'+2)m} }{n^m} \\ &=&\frac{\kappa^{2m+1}2^{(l+l'+2)m-l'}}{n^{m-1}}. \end{eqnarray*}

Consequently, there exists some $w\in[1,m]$ such that $$2^{l'}y_1-t'_{w,2}=0 \mathrm{mod} n$$ holds with probability $1-P_E$.

Since $t'_{w,2}$ and $y_1$ are bounded by $2^{l'}$ and $n/2^{l'}$ respectively, we get $$2^{l'}y_1=t'_{w,2}=0,$$ which implies $y_1=0$ and this completes the proof.


References

[1] Office of State Commercial Cryptography Administration. Public key cryptographic alforithm SM2 based on elliptic curves (in chinese). 2010. http://www.oscca.gov.cn/UpFile/2010122214822692.pdf. Google Scholar

[2] ISO/IEC 11889-1:2015--Information technology--Trusted platform module library Part 1: Architecture. International Organization for Standardization. August 2015. Google Scholar

[3] ISO/IEC 14888-3:2016--Information technology Security techniques Digital signatures with appendix Part 3: Discrete logarithm based mechanisms. International Organization for Standardization. March 2016. Google Scholar

[4] Diffie W, Hellman M. New directions in cryptography. IEEE Trans Inform Theor, 1976, 22: 644-654 CrossRef Google Scholar

[5] Howgrave-Graham N A, Smart N P. Lattice attacks on digital signature schemes. Dess Codes Cryptography, 2001, 23: 283-290 CrossRef Google Scholar

[6] Liu M, Nguyen P Q. Solving BDD by enumeration: an update. In: Topics in Cryptology--CT-RSA 2013. Berlin: Springer, 2013. 7779: 293--309. Google Scholar

[7] Nguyen P Q. The dark side of the hidden number problem: lattice attacks on DSA. In: Cryptography and Computational Number Theory. Basel: Birkhäuser, 2001. 321--330. Google Scholar

[8] Nguyen , Shparlinski . The Insecurity of the Digital Signature Algorithm with Partially Known Nonces. J Cryptology, 2002, 15: 151-176 CrossRef Google Scholar

[9] Boneh D, Venkatesan R. Hardness of computing the most significant bits of secret keys in Diffie-Hellman and related schemes. In: Advances in Cryptology--CRYPTO'96. Berlin: Springer, 1996. 1109: 129--142. Google Scholar

[10] Shani B. On the bit security of elliptic curve Diffie-Hellman. In: Proceedings of the 20th IACR International Conference on Practice and Theory in Public-Key Cryptography. Berlin: Springer, 2017. 10174: 361--387. Google Scholar

[11] Liu M, Chen J, Li H. Partially known nonces and fault injection attacks on SM2 signature algorithm. In: Proceedings of the 9th International Conference on Information Security and Cryptology. Cham: Springer, 2013. 8567: 343--358. Google Scholar

[12] 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. In: Advances in Cryptology--ASIACRYPT 2014. Berlin: Springer, 2014. 8873: 262--281. Google Scholar

[13] Bleichenbacher D. On the generation of one-time keys in DL signature schemes. In: Presentation at IEEE P1363 Working Group Meeting, 2000. Google Scholar

[14] Bleichenbacher D. On the generation of dsa one-time keys. In Presentation at Cryptography Research Inc., 2007. Google Scholar

[15] De Mulder E, Hutter M, Marson M E, et al. Using Bleichenbacher's solution to the hidden number problem to attack nonce leaks in 384-bit ECDSA. In: Cryptographic Hardware and Embedded Systems--CHES 2013. Berlin: Springer, 2013. 8086: 435--452. Google Scholar

[16] Boneh D, Halevi S, Howgrave-Graham N A. The modular inversion hidden number problem. In: Advances in Cryptology--ASIACRYPT 2001. Berlin: Springer, 2001. 2248: 36--51. Google Scholar

[17] Shparlinski I E. Playing hide-and-seek with numbers: the hidden number problem, lattices and exponential sums. In: Proceedings of Symposia in Applied Mathematics, 2005. 62: 153--177. Google Scholar

[18] Hlav. Google Scholar

[19] Fan S, Wang W, Cheng Q. Attacking OpenSSL implementations of ECDSA with a few signatures. In: Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security. New York: ACM, 2016. 1505--1515. Google Scholar

[20] Lenstra A K, Lenstra Jr. H W, Lov?sz L. Factoring polynomials with rational coefficients. Math Ann, 1982, 261: 515-534 CrossRef Google Scholar

[21] Chen Y, Nguyen P Q. BKZ 2.0: better lattice security estimates. In: Advances in Cryptology--ASIACRYPT 2011. Berlin: Springer, 2011. 7073: 1--20. Google Scholar

[22] Schnorr C P, Euchner M. Lattice basis reduction: Improved practical algorithms and solving subset sum problems. Math Programming, 1994, 66: 181-199 CrossRef Google Scholar

[23] Aono Y, Nguyen P Q. Random sampling revisited: lattice enumeration with discrete pruning. In: Advances in Cryptology--EUROCRYPT 2017. Cham: Springer, 2017. 10211: 65--102. Google Scholar

[24] Aono Y, Wang Y, Hayashi T, et al. Improved progressive BKZ algorithms and their precise cost estimation by sharp simulator. In: Advances in Cryptology--EUROCRYPT 2016. Berlin: Springer, 2016. 9665: 789--819. Google Scholar

[25] Zheng Z, Wang X, Xu G. Orthogonalized lattice enumeration for solving SVP. Sci China Inf Sci, 2018, 61: 032115 CrossRef Google Scholar

[26] Micciancio D, Goldwasser S. Complexity of Lattice Problems: a Cryptographic Perspective. Norwell: Kluwer Academic Publishers, 2002. 14--22. Google Scholar

[27] Schnorr C P. A hierarchy of polynomial time lattice basis reduction algorithms. Theor Comput Sci, 1987, 53: 201-224 CrossRef Google Scholar

[28] Schnorr C P, Hörner H. Attacking the Chor-Rivest cryptosystem by improved lattice reduction. In: Advances in Cryptology--EUROCRYPT'95. Berlin: Springer, 1995. 921: 1--12. Google Scholar

[29] Babai L. On Lovász' lattice reduction and the nearest lattice point problem. Combinatorica, 1986, 6: 1-13 CrossRef Google Scholar

[30] Kannan R. Algorithmic Geometry of Numbers. Annu Rev Comput Sci, 1987, 2: 231-267 CrossRef Google Scholar

[31] Shoup V. Number theory C+ library (NTL) vesion 6.0.0. http://www.shoup.net/ntl/. Google Scholar

[32] Kannan R. Minkowski's Convex Body Theorem and Integer Programming. Math OR, 1987, 12: 415-440 CrossRef Google Scholar

  • Figure 1

    (Color online) The hit rate of attacks on 20 random instances, each derived simulatively from a leakage of the SM2 key exchange protocol with parameter size (a) 64 bits and (b) 256 bits.

  •   

    Algorithm 1 Partially known information attack on SM2 key exchange protocol

    Require:An integer $m$, $\{\mathrm{LSB}_{l}(r_i)\}_{i=1}^m$, $\{\mathrm{LSB}_{l&apos;}(t_i)\}_{i=1}^m$, $\{\overline{x}_i\}_{i=1}^m$;

    Output:$\mathrm{LSB}_{l&apos;}(d_{\rm~A})$, where $d_{\rm~A}$ is the private key of client A;

    $\kappa\leftarrow(1+2^{(3m+1)\log\log~(3m+1)/\log~(3m+1)}\sqrt{2m+1})/2$;

    Select $\delta>0$ such that $\kappa\delta<1$;

    Compute $\beta_i=\mathrm{LSB}_{l&apos;}(t_i)-\overline{x}_i\mathrm{LSB}_{l}(r_i)$;

    ${\boldsymbol~v}\leftarrow(\beta_1,\beta_2,\ldots,\beta_m,\frac{\delta}{2},\frac{\delta}{2},\ldots,\frac{\delta}{2})\in~\mathbb{R}^{3m+1}$;

    Call algorithm from Lemma 2.2 to obtain a lattice vector ${\boldsymbol~w}\in~L$ with ${\boldsymbol~w}=(c&apos;_1,\ldots,c&apos;_m,d&apos;,k_{1,1},k_{1,2},\ldots,~k_{m,1},k_{m,2}){\boldsymbol~B}$, which is close to ${\boldsymbol~v}$;

    Return $d&apos;~\mathrm{mod}~n~\mathrm{mod}~2^{l&apos;}$.

Copyright 2020 Science China Press Co., Ltd. 《中国科学》杂志社有限责任公司 版权所有

京ICP备17057255号       京公网安备11010102003388号