SeeingthroughMISTgivenaSmallFractionofanRSAPrivate

《SeeingthroughMISTgivenaSmallFractionofanRSAPrivate》由会员分享，可在线阅读，更多相关《SeeingthroughMISTgivenaSmallFractionofanRSAPrivate（16页珍藏版）》请在装配图网上搜索。

1、1/16Seeing through MIST given a Small Fraction of an RSA Private KeyColin D.WComodo Research Lab (Bradford,UK)Comodo Research Lab (Bradford,UK)RSA 2003Colin D.Walter,Comodo Research Lab,Bradford2/16OverviewHistoryThe MIST AlgorithmThreat Assumptions a Theorem.First Reconstruction of the KeySecond Re

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

3、spects 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 1514RSA 2003Colin D.Walter,Comodo Research Lab,Bradford4/16Reversed m-ary Expn To compute:P=CD mod N Q C;P 1;While D 0 doBe

4、gin 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;RSA 2003Colin D.Walter,Comodo Research Lab,Bradford5/16The 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 D mod m;If d 0 then P Qd P mod N;Q Qm m

5、od N;D D div m;Invariant:CD.Init=QD P mod N End;RSA 2003Colin D.Walter,Comodo Research Lab,Bradford6/16Security StrengthTHEOREM(CHES 2002)After a MIST exponentiation CD mod N using a typical,efficient choice of parameters:The number of exponents with the same pattern of squares and multiplies is at

6、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 N.RSA 2003Colin D.Walter,Comodo Research Lab,Bradford7/16Not

7、ationThe 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 RSA 2003Colin D.Walter,Comodo Research Lab,Bradford8/16A First AttackLet N=PQ for primes P and Q of equal bit

8、length.It is easy to show(N)lies in an interval of length D.RSA 2003Colin D.Walter,Comodo Research Lab,Bradford9/16A First Attack contdThe attacker has“guessed”j and j.He then computes an approximation for Dj=D div jusing his approximation for D.Since D is known to an accuracy with error less than j

9、,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 possibilitiesand the secret key is obtained.RSA 2003Colin D.Walter,Comodo Research Lab,Bradford10/16A First Attack contdBy the theorem applied to the lower half of D,the number of choi

10、ces 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 is introduced.Hence the search space is reduced to about 232EN3/10 or 232EN1/6 if the Sqr&Mult or op.sharing p

11、attern is known.RSA 2003Colin D.Walter,Comodo Research Lab,Bradford11/16A First Attack -conclusionOf course,N3/10 and N1/6 are still over 100 bits for sensible key lengths and so,even without key blinding,this attack is computationally infeasible.The first attack given in the proceedings tackles the

12、 similar,but more complex,case of assuming the most significant digits are guessed instead of the least significant.RSA 2003Colin D.Walter,Comodo Research Lab,Bradford12/16A First Attack -as in paperIf the most significant part Dj is guessed then D div Dj=j is known almost exactly.j is a product of

13、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 property usually unique.So Dj,Dj1,Dj2,.,D1,D0=D are all obtained,and the key recovered.RSA 2003Colin D.Walter,Comodo Research Lab,Bradford13/16The Sec

14、ond AttackThis attack uses the Boneh et al.results(derived from Coppersmith)to reduce the dimension of the search space by a factor of 4 instead 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

15、 as a product of base choices m.Specifically,=j for a large enough j.RSA 2003Colin D.Walter,Comodo Research Lab,Bradford14/16Second Attack contdIf 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)red

16、uced mod becomes a quadratic equation in x.We solve for x using CRT.Generally,there are 16 solutions or none(if 2335 divides).Now we can apply the theorem to factor N.RSA 2003Colin D.Walter,Comodo Research Lab,Bradford15/16Second Attack conclusionThere are N3/20 or N1/12 pattern-matching cases of j

17、N to consider;E possible choices for 1+k(N);B possible blinding factors,say(typically B=232);log(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 th

18、is may be computationally feasible.RSA 2003Colin D.Walter,Comodo Research Lab,Bradford16/16ConclusionA DPA attack on the MIST algorithm has been augmented using knowledge of the RSA public modulus in several ways.The attacks may become computationally feasible if parameters are poorly chosen.Other s

19、tandard algorithms provide no strength against such attacks(e.g.m-ary).Standard approaches such as key blinding,Standard approaches such as key blinding,longer keys,&larger public exponent longer keys,&larger public exponent all contribute to better security.all contribute to better security.RSA 2003Colin D.Walter,Comodo Research Lab,Bradford