Hidden Number Problem and Its Applications in ... - DPI Proceedings [PDF]

2016 International Conference on Service Science, Technology and Engineering (SSTE 2016) ISBN: 978-1-60595-351-9

Hidden Number Problem and Its Applications in Crypto Scheme Yu-Yun CHEN1,a,*, Jiong-Qi WANG1,b, Jun XU3,c 1

College of Science, National University of Defense Technology, Yanwachi 47, 410073 Changsha, China 2

College of Computer Science, National University of Defense Technology, Yanwachi 47, 410073 Changsha, China a

b

c

[email protected], [email protected], [email protected] *Corresponding author

Keywords: Hidden Number Problem, Lattice, Modular Polynomial, Crypto Scheme.

Abstract. This paper is based on the research result of Nguyen’s attacking against DSA .We extent the Hidden Number Method (HNM) from the univariate modular polynomials with one order to the univariate modular polynomials with higher order. There are many crypto schemes using the arithmetical and truncate operations. If the constant terms are partly known, these schemes can be written as the modular equations. We analysis a scheme using the arithmetical and truncate operations so as to improve the lattice model. On the supposed condition, we can recover the basic key with the probability 99%. Introduction Hidden Number Problem was introduced by Boneh and Venkatesan [1]. It is an important application of the lattice in cryptography. They started to care the HNP in 1996. They mapped the HNP to a CVP and used LLL lattice reduction [2] together with Babai’s nearest plane algorithm [3] to study the security of MSBs of the Diffie-Hellman key exchange and related schemes. To attack 160-bit DSA given multiple signatures, Howgrave-Graham and Smart [4] applied some similar techniques with a fixed signing key and knowledge of some bits from each nonce. They could recover the secret key given 8 bits of each nonce from 30 signatures, but they did not succeed with 4 bits. Experiments were done using NTL [5]. When the nonces are partially known, a provable polynomial-time was given by Nguyen and Shparlinski to attack against DSA [6], under some assumption on the modulus and on the hash function. A 160-bit key was recovered with only 3 bits of each nonce from 100 signatures, and the NTL was used as well. Nguyen and Shparlinski also showed that in the given improved lattice reduction techniques, it should be possible to recover the key with only 2 nonce bits know and they extended their result to the ECDSA. In this paper we extend the HNM of Nguyen’s attacking against DSA. We use the HNM [7, 8] to solve the multivariate polynomials and give different lattice models. There exist many crypto schemes which are designed with the arithmetical operations and the truncate operations, such as IDEA, Salsa20, MD5, SHA0, SHA1, SPECK and so on. We give a general model to use our

133

method in order to prove that the new method can be used not only in public key cipher but also in symmetric cipher such as block cipher and stream cipher. Organization The paper is organized as follows. In Sect.2, we introduce the basic conception of the lattice related to HNM. We describe the models used by Boneh and Venkatesan. In Sect.3, we construct the multivariate modular polynomials, give a general model of arithmetical and truncate operations and use the HNM to solve the modular polynomials. Sect.4 is summary. Basic notations and results In this paper, p is a prime number, Fp is a finite field of p elements,  s m is the remainder of s on division by m, for l > 0 , MSBl , p ( x ) denotes any integer u such that  x  p − u ≤ p 2l +1 . MSBl , p ( x )

is roughly equivalent to l most significant bits of x . However, this definition is more flexible. In particular, l needs not be an integer. In 1996, Boneh and Venkatesan gave the definition of Hidden Number Problem (HNP) as follow: Definition 1 (HNP). Recover α ∈ Fp such that for many known random t ∈ Fp , we are given MSBl , p (α t ) for some l > 0 . Boneh and Venkatesan gave a polynomial time algorithm based on the lattice reduction to solve HNP with l ≈ log1/2 p . Definition 2 (Lattices). Let {b1 ,..., bs } be a set of linearly independent vectors in R s . The set 

s





i =1



of vectors L =  z z = ∑ ci bi , c1 ,..., cs ∈ Z  is called an s-dimensional full rank lattice. The set

{b1 ,..., bs } is called a basis of L. Definition 3 (Closest Vector Problem, CVP). Given a vector r ∈ R s , find a lattice vector v ∈ L with r − v = min r − z . z∈L CVP is NP-complete. Theorem 1. There exists a deterministic polynomial time algorithm which, for a given lattice L and a vector r ∈ R s , finds a lattice vector v ∈ L satisfying the inequality  s log 2 log s  r − v ≤ exp  C  min r − z . log s  z∈L  For some absolute constant C > 0 .

(1)

HNP and CVP [7] Let d ≥ 1 be integer. Given ti , ui = MSBl , p (α ti ) , i = 1,..., d , we build the lattice L ( p, l , t1 , ⋅⋅⋅, td ) spanned by the rows of the matrix:

134

p 0    0 t 1

0 p 0 t2

0     0  p 0  td 1 2l 1  0

(2)

The unknown vector v    t1  p , ,  td  p ,  2l 1  belongs to L  p, l , t1 , , td  and is close to the known vector u   u1 , , ud ,0 : v  u  O  p2l  . It is proved that for almost all t1 , , td , v is the only lattice vector which can be so close to u . In fact, even within the approximation factor of Theorem 1, that is within the distance of order p2l o( d ) , this is still the only lattice vector. Assume that w    t1 , ,  td ,  2l 1   mod p  with     mod p  is another lattice vector with w  u  p2l o( d ) . Then w  v  p 2 l  o ( d ) .

(3)

Therefore, for each i  1, , d ,     ti   p2l o( d ) , p2l o( d )   mod p  . For every fixed   0  mod p  , Pr  t   h, h   mod p   

tFp

2h  1 , p

(4) d

 2h  1   l o ( d )  ti   h, h   mod p  , i  1,..., d    thus, t ,...,Pr .   . In our settings      and h  p2 t  F 1 d p  p  Because  (and thus      ) may belong to p  1 distinct residue classes, we conclude that (3)

holds with probability at most P  p  2l o( d )  . Choose l  d  2 log1/2 p  , and then P  1/ p . This means that CVP algorithm returns v with the probability  1  1 p . d

Our Results The Principle The principle of Nguyen’s attacking against DSA is to solve the univariate congruence equation with one order. How about higher order? Let the univariate congruence equation with higher order as follows:

Bi 0  Bi1 x  Bi 2 x 2  ...  Bin x n  Ai mod p

(5)

p is a prime number, Bij  Fp , some consecutive bits of Bij and Ai are known, how to solve x ,

0i d , 0 j n? k Let Ai  Ai 0  Ai1  2 , where Ai 0 is known and Ai1 is unknown, 0  Ai 0  2k , 0  Ai1  p 2k , then

Bi 0  Bi1 x  Bi 2 x 2  ...  Bin x n  Ai 0  Ai1  2k mod p

135

⇒ 2 − k Bi1 x + 2 − k Bi 2 x 2 + ... + 2 − k Bin x n − 2 − k ( Ai 0 − Bi 0 ) = Ai1 p

(6)

p

−k −k Let tij =  2 Bij  p , ui =  2 ( Ai 0 − Bi 0 )  p , 0 < i ≤ d , 1 ≤ j ≤ n , then

0 < ti1 x + ti 2 x 2 + ... + tin x n − ui

p

< p 2k ,

⇒ ti1 x + ti 2 x 2 + ... + tin x n − ( ui + p 2k +1 ) < p 2k +1 , p

0> 6 ) & 0 X 1FF 4) L = X × 388 512 What we have known are L1 ,L Ld , what we want to do is to find the exact Q0 ,LQ16 . When we use the HNM described as above, we can find the exact Q0 ,LQ16 . We use the LLL algorithm (δ = 0.99 ) [2, 5] and the number of the equations is 16, the probability of success is 99%. Summary In this paper, we describe the HNP, introduce the Hidden Number Method (HNM), and extent the HNM from the univariate modular polynomials with one order to the univariate modular polynomials with higher order. We construct a general model and solve the modular polynomials. The probability of success is 99%. References [1] 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, (1996) 129-142. [2] A. Lenstra, H. Lenstra, and L. Lovász. Factoring polynomials with rational coefficients. Mathematische Annalen, 261(1982) 515-534. [3] L. Babai. On Lovász’ Lattice reduction and the nearest lattice point problem. Combinatorica, 6(1) (1986) 1-13. [4] N. Howgrave-Graham and N.P.Smart. Lattice attacks on digital signature schemes. Designs, Codes and Cryptography, 23(3): (2001) 283-290. [5] V. Shoup. NTL: A Library for Doing Number Theory, (2012). [6] P.Q. Nguyen and I.E. Shparlinski. The insecurity of the elliptic curve digital signature algorithm with partially known nonces. J. Cryptology, (2001). [7] Igor E. Shparlinski, Playing ”Hide-and-Seek” in finite fields: Hidden Number Problem and its Applications, Slides. [8] E De Mulder, M. Hutter, M. E. Marson and P. Pearson. Using Bleichenbacher’s solution to the hidden number problem to attack nonce leaks in 384-bit ECDSA. Cryptographic Hardware and Embedded Systems – CHES, (2013) 33-45.

137