SeeingthroughMISTgivenaSmallFractionofanRSAPrivate

1、1/16RSA 2003Colin D. Walter, Comodo Research Lab, BradfordSeeing through MIST given a Small Fraction of an RSA Private K2/16RSA 2003Colin D. Walter, Comodo Research Lab, BradfordOverview History The MIST Algorithm Threat Assumptions a Theorem. First Reconstruction of the Key Second Reconstruction of

2、 the Key Conclusion3/16RSA 2003Colin D. Walter, Comodo Research Lab, BradfordHistory C. D. Walter Exponentiation using Division Chains IEEE TC 47, 1998 C. D. Walter MIST: An Efficient, Randomized Exponentiation Algorithm for Resisting Power Analysis CT-RSA 2002, LNCS 2271 C. D. Walter Some Security

3、Aspects of the MIST Randomized Exponentiation Algorithm CHES 2002, LNCS 2523 Boneh, Durfee & Frankel Exposing an RSA Private Key given a Small Fraction of its Bits AsiaCrypt 98, LNCS 15144/16RSA 2003Colin D. Walter, Comodo Research Lab, BradfordReversed m-ary Expn To compute: P = CD mod N Q C ;P

4、 1 ;While D 0 doBegin d D mod m ; If d 0 then P Qd P mod N; Q Qm mod N; D D div m ; Invariant: CD.Init = QD P mod N End ;5/16RSA 2003Colin D. Walter, Comodo Research Lab, BradfordThe MIST Expn Algorithm To compute: P = CD mod N Q C ;P 1 ;While D 0 doBegin Choose a random base m (from 2,3,5, say); d

5、D mod m ; If d 0 then P Qd P mod N; Q Qm mod N; D D div m ; Invariant: CD.Init = QD P mod N End ;6/16RSA 2003Colin D. Walter, Comodo Research Lab, BradfordSecurity StrengthTHEOREM (CHES 2002) After a MIST exponentiation CD mod N using a typical, efficient choice of parameters: The number of exponent

6、s with the same pattern of squares and multiplies is at least D3/5. The number of exponents with the same pattern of operand sharing is about D1/3.With just this information it is computationally infeasible to search for D.We will now improve these results using knowledge of the public modulus N.7/1

7、6RSA 2003Colin D. Walter, Comodo Research Lab, BradfordNotationThe chosen digit/base pairs (di, mi) satisfyD = d0+m0(d1+m1(d2+m2(.dn).) DefineDj = dj+ mj(dj+1+mj+1(dj+2+mj+2(.dn).) j = d0 + m0(d1 + m1 (d2 + m2(.dj1).)j = m0 m1 m2 . mj1Thenj = D mod jDj = D div jD = jDj + j 8/16RSA 2003Colin D. Walte

8、r, Comodo Research Lab, BradfordA First Attack Let N = PQ for primes P and Q of equal bit length.It is easy to show (N) lies in an interval of length D.9/16RSA 2003Colin D. Walter, Comodo Research Lab, BradfordA First Attack contdThe attacker has “guessed” j and j.He then computes an approximation f

9、or Dj = D div jusing his approximation for D. Since D is known to an accuracy with error less than j, Dj (the upper half of D) is determined up to a choice of at most 2 values.So D = jDj+j is determined up to a couple of possibilities and the secret key is obtained.10/16RSA 2003Colin D. Walter, Como

10、do Research Lab, BradfordA First Attack contdBy the theorem applied to the lower half of D, the number of choices for digit/base pairs is about N3/10 or N1/6 depending on how much we assume the attacker knows.He has E choices for approximating D and perhaps 232 extra choices if a 32-blinding factor

11、is introduced.Hence the search space is reduced to about 232EN3/10 or 232EN1/6 if the Sqr & Mult or op. sharing pattern is known.11/16RSA 2003Colin D. Walter, Comodo Research Lab, BradfordA First Attack - conclusion Of course, N3/10 and N1/6 are still over 100 bits for sensible key lengths and s

12、o, even without key blinding, this attack is computationally infeasible. The first attack given in the proceedings tackles the similar, but more complex, case of assuming the most significant digits are guessed instead of the least significant.12/16RSA 2003Colin D. Walter, Comodo Research Lab, Bradf

13、ordA First Attack - as in paper If the most significant part Dj is guessed then D div Dj = j is known almost exactly. j is a product of powers of 2, 3, 5 only. This property is so rare that the correct Dj is easily determined. The next digit/base pair (dj1, mj1) is chosen to give j1 the same propert

14、y usually unique. So Dj, Dj1, Dj2, ., D1, D0 = D are all obtained, and the key recovered.13/16RSA 2003Colin D. Walter, Comodo Research Lab, BradfordThe Second Attack This attack uses the Boneh et al. results (derived from Coppersmith) to reduce the dimension of the search space by a factor of 4 inst

15、ead of 2. Theorem. Suppose N = PQ, N1/4 and P mod is known. Then it is possible to factor N in time polynomial in log(N). Boneh uses this with as a power of 2. We take as a product of base choices m. Specifically, = j for a large enough j.14/16RSA 2003Colin D. Walter, Comodo Research Lab, BradfordSe

16、cond Attack contd If there is no key blinding, DE = 1+k(N) for some k E where (N) = (P1)(N/P1). Reducing mod changes unknown D to the guessed j and P to x = P mod , say. Now DE = 1+k(N) reduced mod becomes a quadratic equation in x. We solve for x using CRT. Generally, there are 16 solutions or none

17、 (if 2335 divides ). Now we can apply the theorem to factor N.15/16RSA 2003Colin D. Walter, Comodo Research Lab, BradfordSecond Attack conclusion There are N3/20 or N1/12 pattern-matching cases of j N to consider; E possible choices for 1+k(N); B possible blinding factors, say (typically B = 232); l

18、og(N) time to construct & find roots of quadratic; log(N)-polynomial time to factorise N; We conclude that N can be factored in time BEN3/20 or BEN1/12 times a poly in log(N). For no blinding, small E & short key this may be computationally feasible.16/16RSA 2003Colin D. Walter, Comodo Research Lab, Bradford