are Inse ure (Extended Abstra t) DanBoneh 1 ,Antoine Joux 2
,andPhongQ.Nguyen 3
1
StanfordUniversity,ComputerS ien eDepartment
Stanford,CA94305,USA
dabo s.stanford.edu andhttp:// rypto.stanford.edu/~dabo/
2
DCSSI,18rueduDo teurZamenhof,
92131Issy-les-MoulineauxCedex,Fran e
jouxens.fr
3
E oleNormaleSuperieure,Departementd'Informatique,
45rued'Ulm,75005Paris, Fran e
pnguyenens.fr andhttp://www.di.ens.fr/~pnguyen/
Abstra t. Wepresentanatta konplainElGamalandplainRSA
en- ryption. The atta k shows that without proper prepro essing of the
plaintexts, bothElGamal andRSA en ryptionare fundamentally
inse- ure.Namely,whenone usesthesesystemsto en rypta (short)se ret
keyof asymmetri ipher itis often possible tore overthe se retkey
from the iphertext. Our results demonstrate that prepro essing
mes-sagespriortoen ryptionisanessentialpartofbothsystems.
1 Introdu tion
Intheliteratureweoftenseeades riptionofRSAen ryptionasC=hM e
imod
N (the publi keyis hN;ei)and a des riptionof ElGamal en ryption as C =
hMy r
;g r
imodp(the publi keyishp;g;yi).Similardes riptionsarealsogiven
intheoriginalpapers[17,9℄.Ithasbeenknownformanyyearsthatthis
simpli- eddes riptionofRSAdoesnotsatisfybasi se uritynotions,su hassemanti
se urity (see[6℄ for asurveyof atta ks).Similarly, a versionof ElGamal
om-monly used in pra ti edoesnot satisfybasi se uritynotions(even under the
De isionDiÆe-Hellmanassumption[5℄) 1
.Toobtainse uresystemsusingRSA
and ElGamal one must apply a prepro essing fun tion to the plaintext prior
to en ryption, or a onversion to the en ryption fun tion (see [10,16,13℄ for
instan e). Re entstandardsforRSA [15℄ useOptimal Asymmetri En ryption
1
ImplementationsofElGamaloftenuseanelementg2Z
p
ofprimeorderqwhereqis
mu hsmallerthanp.Whenthesetofplaintextsisequaltothesubgroupgenerated
by g,theDe ision DiÆeHellman assumptionimpliesthatElGamalissemanti ally
se ure.Unfortunately,implementationsofElGamaloftenen ryptanm-bitmessage
in therandomora lemodel [4℄.Currently, thereis noequivalentprepro essing
standardforElGamalen ryption,althoughseveralproposalsexist[1,10,16,13℄.
Unfortunately, many textbook des riptions of RSA and ElGamal do notview
these prepro essingfun tions asan integralpartoftheen ryption s heme.
In-stead, ommondes riptionsare ontentwithanexplanationoftheplainsystems.
Inthis paperwegiveasimple,yet powerful,atta kagainstbothplainRSA
andplainElGamalen ryption.Theatta killustrates thatplainRSA andplain
ElGamal are fundamentally inse ure systems. Hen e, any des ription of these
ryptosystems annot ignore theprepro essing stepsused in full RSA and full
ElGamal. Ouratta k learlydemonstratesthe importan e of prepro essing. It
anbeusedtomotivatetheneedforprepro essingin introdu tory texts.
Ouratta kisbasedonthefa tthat publi keyen ryptionistypi allyused
toen ryptsession-keys.Thesesession-keysaretypi allyshort,i.e.lessthan128
bits.Theatta kshowsthatwhenusingplainRSAorplainElGamaltoen rypt
anm-bitkey,itisoftenpossibletore overthekeyintimeapproximately2 m=2
.
Inenvironmentswheresession-keysarelimitedto 64-bit keys(e.g. due to
gov-ernmentregulations),ouratta kshowsthatbothplainRSAandplainElGamal
result in a ompletely inse uresystem. We experimented with the atta k and
showedthatitworkswellinpra ti e.
1.1 Summaryof results
SupposetheplaintextM ismbitslong.Forillustrationpurposes,whenm=64
weobtainthefollowingresults:
{ ForanyRSApubli keyhN;ei,givenC=M e
modNitispossibletore over
M in the time it takes to ompute 22 m=2
modular exponentiations. The
atta k su eeds withprobability18% (the probability is overthe hoi e of
M2f0;1;:::;2 m
1g).Thealgorithmrequires2 m=2
mbitsofmemory.
{ Lethp;g;yibeanElGamalpubli key.Whentheorderofgisatmostp=2 m
,
itis possible to re overM from anyElGamal iphertext of M in the time
ittakesto ompute22 m=2
modularexponentiations. Theatta ksu eeds
with probability 18% (over the hoi e of M), and requires 2 m=2
m bits of
memory.
{ Lethp;g;yibean ElGamalpubli key. Suppose p 1=qs where s >2 m
andthedis retelogproblemforsubgroupsofZ
p
ofordersistra table,i.e.
takestime T for somesmallT. Whentheorder ofg is p 1,itis possible
to re overM from any iphertext of M in time T and 22 m=2
modular
exponentiations.Theatta ksu eedswithprobability18%(overthe hoi e
ofM),andrequires2 m=2
mbitsofmemory.
{ Let hp;g;yi be an ElGamal publi key. Suppose again p 1 = qs where
s> 2 m
and thedis rete log problem for subgroupsof Z
p
of order s takes
timeTforsomesmallT.Whentheorderofgiseitherp 1oratmostp=2 m
,
it is possible to re over M from any iphertext of M in time T plus one
the hoi e of M). Thepre omputations taketime 2 m=2
T and 2 m=2
modu-larexponentiations. The spa erequirement anoptionally be de reasedto
2 m=4
log
2
s bits without in reasing the omputation time, however with a
lossintheprobabilityof su ess.
Allatta ks anbeparallelized,ando eravarietyoftrade-o s,withrespe tto
the omputationtime,thespa erequirement,andtheprobabilityofsu ess.For
instan e,thesu essprobabilityof18% anberaisedto35%ifthe omputation
time isquadrupled.Notethat the rstresultappliestoRSA withanarbitrary
publi exponent(smallorlarge).Theatta kbe omesslightlymoreeÆ ientwhen
the publi exponente is small. The se ond resultapplies to the usualmethod
in whi h ElGamal is used in pra ti e.The third resultapplies when ElGamal
en ryptionisdoneintheentiregroup,howeverp 1hasasmallsmoothfa tor(a
64-bit smoothfa tor).Thefourthresultde reasestheon-line workof boththe
se ond and the third results, provided an additional pre omputation stage. It
anoptionallyimprovethetime/memorytrade-o .Thethirdandfourthresults
assumethat p 1 ontainsasmoothfa tor: su h apropertywasusedin other
atta ksagainstdis rete-logs hemes(see[2,14℄forinstan e).
1.2 Splitting probabilities forintegers
Our atta ks anbe viewed asa meet-in-the-middle method based on thefa t
that a relatively small integer (e.g., a session-key) an often be expressed as
aprodu t of mu h smallerintegers.Note that re ent atta ks onpadding RSA
signatures hemes[7℄userelatedideas.Roughlyspeaking,these atta ksexpe t
ertainrelativelysmallnumbers(su hashashedmessages)tobesmooth.Here,
wewill be on ernedwiththe size ofdivisors. Existinganalyti resultsforthe
boundsweneedarerelativelyweak.Hen e,wemainlygiveexperimentalresults
obtainedusingthePari/GP omputerpa kage[3℄.
Let M be a uniformly distributed m-bit integer. We are interested in the
probabilitythatM anbewrittenas:
{ M=M 1 M 2 withM 1 2 m1 andM 2 2 m2
.Seetable 1forsomevalues.
{ M=M 1 M 2 M 3 withM i 2 m i
.Seetable2forsomevalues.
{ M=M 1 M 2 M 3 M 4 withM i 2 mi
. Seetable3forsomevalues.
The experimental results given in the tables have been obtained by fa toring
a large number of randomly hosen m-bit integers with uniform distribution.
Sometheoreti alresults anbeobtainedfromthebook [11℄.Morepre isely,for
1=2 <1,letP
(m)betheprobabilitythat auniformly distributedinteger
M in [1:::2 m 1℄ anbewrittenasM =M 1 M 2 withbothM 1 andM 2 lessor equalto2 m
.It anbeshownthatP
1=2
(m)tends(slowly)tozeroasmgrowsto
in nity. Thisfollows(after alittle work)from resultsin [11℄[Chapter2℄onthe
P 1=2 (m)=O loglogm p logm m Æ ; (1) where Æ = 1 1+loglog2 log2
0:086.On the other hand, when > 1=2, P
(m)
nolongertendsto zero,asone aneasilyobtainthefollowingasymptoti lower
bound,whi h orre ts[8,Theorem4,p 377℄:
liminfP
(m)log (2 ); (2)
This is be ausethe probabilitymust in lude allnumbersthat are divisibleby
a prime in the interval [2 m=2
;2 m
℄, and the bound follows from well-known
smoothness probabilities.
Ouratta ks o er a variety of trade-o s,due to the freedom in the
fa tor-ization form,and in the hoi esof the m
i
's: thesplitting probability givesthe
su ess probability of the atta k, the other parameters determine the ost in
termsofstorageand omputation time.
Table 1.Experimentalprobabilitiesofsplittingintotwofa tors.
Bit-lengthmm 1 m 2 Probability 40 20 20 18% 21 21 32% 22 22 39% 20 25 50% 64 32 32 18% 33 33 29% 34 34 35% 30 36 40%
Table2.Experimentalprobabilitiesofsplittingintothreefa tors.
Bit-lengthmm 1 =m 2 =m 3 Probability 64 22 4% 23 6.5% 24 9% 25 12%
1.3 Organization ofthe paper
Bit-lengthmm1=m2=m3=m4Probability
64 16 0.5%
20 3%
en ryption wheng generatesa\small"subgroupofZ
p
.Using similarideas,we
presentin Se tion 4an atta kon plain ElGamal en ryption when g generates
allZ
p
,andanatta konplainRSA inSe tion 5.
2 The subgroup rounding problems
Re allthattheElGamalpubli keysystem[9℄en ryptsmessagesinZ
p
forsome
prime p.Let g beanelementofZ
p
oforder q. Theprivatekeyisanumberin
the range 1 x <q. The publi key is a tuple hp;g;yi where y = g x
modp.
Toen ryptamessageM 2Z
p
theoriginal s hemeworksasfollows:(1)pi ka
randomr in therange1x<q, and(2) omputeu=My r
modpand v=
g r
modp.Theresulting iphertextisthepairhu;vi.Tospeeduptheen ryption
pro essoneoftenusesanelementgofordermu hsmallerthanp.Forexample,
pmaybe1024bitslongwhileqisonly512bitslong.
Fortherestofthisse tionweassumeg2Z
p
is anelementoforder qwhere
q p.For on retenessonemaythinkofpas1024bitslongandq as512bits
long.LetG
q
bethesubgroupofZ
p
generatedbyg.ObservethatG
q isextremely sparse inZ p . Onlyonein 2 512 elementsbelongs toG q .Wealso assumeM isa
short message of lengthmu h smaller thanlog
2
(p=q). Forexample, M is a64
bitslongsession-key.
Tounderstand the intuitionbehind theatta kit is bene ial to onsider a
slight modi ation of the ElGamal s heme. After the random r is hosenone
en rypts amessage M by omputing u =M+y r
modp. That is, we \blind"
themessagebyadding y r
ratherthanmultiplyingbyit. The iphertext isthen
hu;vi where v is de ned as before. Clearly y r
is a randomelement of G
q . We
obtainthefollowingpi ture:
g
2
y
r
u
M
p
0
g
4
g
g
3
ThemarksrepresentelementsinG
q
.Sin eMisarelativelysmallnumber,
en ryption ofM amountstopi kingarandom elementinG
q
andthen slightly
movingawayfromit.AssumingtheelementsofG
q
areuniformlydistributedin
Z
p
theaveragegapbetweenelementsofG
q
ismu hlargerthanM.Hen e,with
high probability, there is a uniqueelement z 2 G
q
that is suÆ iently lose to
satisfyingju zj<2 .Ifwe ould ndz given uwe ouldre overM.Hen e,
weobtaintheadditiveversionofthesubgrouproundingproblem:
Additivesubgrouprounding: letzbeanelementofG
q
andanintegersatisfying
<2 m
.Givenu=z+ modp ndz.WhenmissuÆ ientlysmall,zisuniquely
determined(withhighprobabilityassumingG
q
isuniformlydistributed inZ
p ).
Going ba k to the original multipli ative ElGamal s heme we obtain the
multipli ativesubgrouproundingproblem.
Multipli ative subgroup rounding: letz bean element of G
q
and aninteger
satisfying<2 m
.Givenu=zmodp ndz.WhenmissuÆ ientlysmallz,is
uniquelydetermined(withhighprobabilityassumingG
q
isuniformlydistributed
in Z
p ).
An eÆ ient solutionto either problemwould implythat the orresponding
plain ElGamal en ryption s heme is inse ure. We are interested in solutions
that runintime O( p
)or,evenbetter,O(log). Inthenextse tionweshow
asolutiontothemultipli ativesubgrouproundingproblem.
Thereasonwerefer to these s hemes as\plain ElGamal"is that messages
are en rypted as is. Our atta ks show the danger of using the system in this
way. Forproperse urity onemustpre-pro ess themessagepriorto en ryption
ormodifytheen ryptionme hanism.Forexample,one oulduseDHAES[1℄or
aresultdueto Fujisaki andOkamoto[10℄,orevenmorere ently[16,13℄.
3 Algorithms for multipli ative subgroup rounding
Wearegivenanelementu2Z
p
oftheformu=zmodpwherezisarandom
elementof G
q
andjj<2 m
.Ourgoalisto nd,whi hwe anassumeto be
positive.Asusual,weassumethatm,thelengthofthemessagebeingen rypted,
is mu h smaller than log
2
(p=q). Then with high probability is unique. For
example, take p to be 1024 bits long, q to be 512 bits long and m to be 64.
We rst give asimplemeet-in-the-middle strategy for multipli ative subgroup
rounding. Byredu tiontoaknapsa k-likeproblem, wewill thenimproveboth
the on-line omputation time and the time/memory trade-o of the method,
providedthatpsatis esanadditional,yetrealisti ,assumption.
3.1 A meet-in-the-middlemethod
Suppose anbewritten as=
1 2 where 1 2 m 1 and 2 2 m 2 .For
instan e,one antakem
1 =m
2
=m=2.Weshowhowto ndfromuinspa e
O(2 m1 )and2 m1 +2 m2
modularexponentiations.Observethat
u=z=z 1 2 modp: Dividingby 2
andraisingbothsidesto thepowerofqyields:
(u= 2 ) q =z q q = q modp:
We an now build a table of size 2 m
1
ontaining the values
1
modp for all
1
=0;:::;2 m
1
.Thenforea h
2 =0;:::;2 m 2 we he kwhetheru q = q 2 modp
is present in the table. If so, then =
1
2
is a andidate value for .
Assumingisunique,therewillbeonlybeonesu h andidate,althoughthere
willprobablybeseveralsuitablepairs(
1 ;
2 ).
Thealgorithmaboverequiresapriori2 m2
+2 m1
modularexponentiationsand
2 m1
log
2
pbitsofmemory.However,wedonotneedtostorethe ompletevalue
of q
1
modpinthetable:AsuÆ ientlylargehashvalueisenough,asweareonly
lookingfor\ ollisions".Forinstan e,one antakethe2max(m
1 ;m 2 )least signif-i antbitsof q 1
modp,sothatthespa erequirementisonly2 m1+1 max(m 1 ;m 2 ) bitsinsteadof2 m 1 log 2
p.Lessbitsareevenpossible,forwe an he kthe
valid-ityofthe(few) andidatesobtained.Notealsothatthetableonlydependsonp
and q: thesametable anbeused forall iphertexts.Forea h iphertext,one
needs to omputeat most2 m
2
modular exponentiations. For ea h
exponentia-tion,onehasto he kwhetherornotitbelongstothetable,whi h anbedone
withO(m
1
) omparisonson ethetableissorted.
Itisworthnotingthat
1 and
2
neednotbeprime.Theprobabilitythata
randomm-bitinteger(su has) anbeexpressedasaprodu toftwointegers,
onebeinglessthanm
1
bitsandtheotheronebeinglessthanm
2
bits,isdis ussed
in Se tion1.2.
By hoosingdi erentvaluesofm
1 andm
2
(notne essarilym=2),oneobtains
varioustrade-o swithrespe ttothe omputationtime,thestoragerequirement,
and the su ess probability. For instan e, when the system is used to en rypt
a 64-bit session key, if we pi k m
1 = m
2
= 32, the algorithm su eeds with
probabilityapproximately18%(withrespe ttothesessionkey),anditrequires
ontheorderof eightbillionexponentiations, farlessthanthetimeto ompute
dis retelogin Z
p .
Weimplementedtheatta kusingVi torShoup'sNTLlibrary[19℄.The
tim-ingsshouldnotbe onsideredasoptimal,theyaremeanttogivearoughideaof
theatta keÆ ien y, omparedtoexhaustivesear hatta ksonthesymmetri
al-gorithm.Runningtimesaregivenforasingle500MHz64-bitDECAlpha/Linux.
Ifm=40and m
1 =m
2
=20,andweusea160-bitqand a512-bitp,the
pre- omputationsteptakes40minutes,andea hmessageisre overedinlessthan1
hourand30minutes.FromSe tion1.2,italsomeansthat,givenonlythepubli
keyandthe iphertext, a40-bit message anbere overedin lessthan6hours
onasingleworkstation,withprobability39%.
3.2 Redu tion to knapsa k-like problems
Wenowshowhowtoimprovetheon-line omputation time(2 m=2
modular
ex-ponentiations)andthetime/memorytrade-o ofthemethod.Wetransformthe
multipli ativerounding problemintoalinearproblem,providedthatpsatis es
theadditionalassumptionp 1=qrswheres2 m
issu hthatdis retelogsin
subgroupsofZ
p
oforders anbeeÆ iently omputed.Forinstan e,ifp e1
1 p
ek
k
is theprime fa torizationofs, dis retelogsin a y li groupof orders anbe
omputedwith O( P k e i (logs+ p p i
of Z p .Forallx 2Z p , x qr
belongs to thesubgroup G
s
of order sgenerated by
! qr
.
Thelinear problem that we will onsider is known asthe k-table problem:
givenktablesT
1 ;:::;T
k
ofintegersandatargetintegern,thek-table problem
istoreturnallexpressions(possiblyzero)ofnoftheformn=t
1 +t 2 ++t k wheret i 2T i
.Thegeneralk-tableproblemhasbeenstudiedbyS hroeppeland
Shamir[18℄,be auseseveralNP- ompleteproblems(e.g.,theknapsa kproblem)
anberedu ed to it.Wewill apply (slightly modi ed) known solutionsto the
k-table problems,fork=2;3and4.
Themodular2-tableproblem Supposethat anbewrittenas=
1 2 , with 0 1 2 m1 and 0 2 2 m2 , as in Se tion 3.1. We have u q = q 1 q 2
modpandtherefore:
u qr = qr 1 qr 2 modp;
whi h anberewrittenas
log(u qr )=log( qr 1 )+log( qr 2 )mods;
wherethelogarithmsarewithrespe tto ! qr . WebuildatableT 1 onsistingoflog( qr 1 )forall 1 =0;:::;2 m1 ,andatable T 2 onsistingoflog( qr 2 )forall 2 =0;:::;2 m2
.These tablesareindependent
of .Theproblemis nowto expresslog (u qr )asamodularsumt 1 +t 2 , where t 1 2 T 1 and t 2 2 T 2
. The number of targets t
1 +t 2 is 2 m1+m2 . Hen e, we
expe tthis problemtohaveveryfewsolutionswhens2 m1+m2
.Theproblem
involvesmodularsums,butit anof oursebeviewedasa2-tableproblemwith
twotargetslog(u qr
)andlog (u qr
)+s.The lassi almethodto solvethe2-table
problemwithatargetnisthefollowing:
1. SortT 1 in in reasingorder; 2. SortT 2 in de reasingorder;
3. RepeatuntileitherT
1 orT
2
be omesempty(inwhi h aseallsolutionshave
alreadybeenfound):
(a) Computet= rst(T
1
)+ rst(T
2 ).
(b) Ift=n,outputthesolutionwhi h hasbeenfound,and delete rst(T
1 ) fromT 1 ,and rst(T 2 )fromT 2 ; ( ) Ift<ndelete rst(T 1 )from T 1 ; (d) Ift>ndelete rst(T 2 )from T 2 ;
Itiseasytoseethatthemethodoutputsallsolutionsofthe2-tableproblem,in
time2 min(m 1 ;m 2 )+1
.Thespa erequirementisO(2 m 1 +2 m 2 ).
Sin e the original problem involvesmodular sums, it seems at rst glan e
thatwehavetoapplythepreviousalgorithmtwi e(withtwodi erenttargets).
T
2
is sorted in des endingorder, n T
2
is sorted in as ending order. The set
(n T
2
)modsthoughnotne essarily sorted,is almostsorted. Morepre isely,
twoadja entnumbersarealwaysintherightorder,totheex eptionofasingle
pair. This isbe ausen T
2
is ontained in anintervalof lengths. Thesingle
pairofadja entnumbersinreverseorder orrespondstothetwoelementsaand
b ofT
2
surrounding s n. Thesetwoelements aneasilybefoundby asimple
di hotomy sear h for s n in T
2
. And on e the elements are known, we an
a ess (n T
2
) (mod s) in as ending order by viewing T
2
as a ir ular list,
startingourenumerationof T
2
byb,andstoppingata.
The total ost of the method is the following. The pre omputation of
ta-bles T 1 and T 2 requires 2 m 1 +2 m 2
modular exponentiations and dis rete log
omputations in a subgroup of Z
p
of order s, and the sort of T
1 and T 2 . The spa erequirementis(2 m 1 +2 m 2 )log 2
sbits.Forea h iphertext,werequireone
modular exponentiation,oneeÆ ientdis rete log(to omputethetarget), and
2 min(m 1 ;m 2 )+1
additions.Hen e,weimprovedtheon-lineworkofthemethodof
Se tion 3.1: loosely speaking, we repla ed modular exponentiations by simple
additions.Wenowshowhowtode rease thespa erequirementofthemethod.
Themodular3-tableproblem Thepreviousapproa h aneasilybeextended
to anarbitrarynumberoffa torsof .Supposefor instan e anbe written
as= 1 2 3 whereea h i islessthan2 m i .Weobtain log(u qr )= 3 X i=1 log( qr i )mods;
where the logarithms are with respe t to ! qr
. In a pre omputation step, we
omputeinatableT
i
allthelogarithmsof qr i modpfor0 i <2 m i .Weare
left withamodular3-table problemwithtarget log(u q
r).Themodular3-table
problemwithtargetnmodulos aneasilybesolvedintimeO(2 m 1 +min(m 2 ;m 3 ) )
andspa eO(2 m 1 +2 m 2 +2 m 3
).ItsuÆ estoapplythemodular2-tablealgorithm
ontablesT
2 andT
3
,foralltargets(n t
1 )mods,witht 1 2T 1 .
Hen e,wede reasedthespa erequirementofthemethodofSe tion3.2,by
(slightly) in reasing the on-line omputation work and de reasing the su ess
probability (see Se tion 1.2 for theprobability of splitting into three fa tors).
More pre isely, if m 1 = m 2 = m 3
= m=3, the on-line work is one modular
exponentiation,onedis reteloginagroupoforders,and2 2n=3
additions.Sin e
anadditionisvery heap,thismightbeusefulforpra ti alpurposes.
Themodular4-tableproblem Using3fa torsdidnotimprovethetime/memory
trade-o oftheon-line omputationwork.Indeed,forbothmodular2-tableand
modular 3-tableproblems, ouralgorithms satisfyTS =O(2 m
),where T isthe
1 2 3 4 i
2 m
i
.Forinstan e, one an takem
1 =m 2 =m 3 =m 4 =m=4. Weshowhowto ndfromlog(u qr )intimeO(2 m1+m2 +2 m3+m4 )andspa eO( P 4 i=1 2 mi ),
pro-videdapre omputationstageof P
4
i=1 2
mi
modularexponentiationsanddis rete
log omputationsin agroupof orders.
Wehavelog(u qr )= P 4 i=1 log( qr i
)mods:Again,in apre omputationstep,
we ompute in atable T
i
all the logarithms of qr i modp for 0 i < 2 m i .
Weareleftwithamodular4-tableproblem,whosesolutionswillrevealpossible
hoi es of 1 , 2 , 3 and 4
. S hroeppel and Shamir [18℄ proposed a lever
solutiontothebasi 4-tableproblem,usingthefollowingidea.Anobvious
solu-tiontothe4-tableproblemistosolvea2-tableproblembymergingtwotables,
that is, onsideringsumst
1 +t 2 andt 3 +t 4
separately.However,thealgorithm
for the 2-tablealgorithm des ribedin Se tion 3.2 a essesthe elementsof the
sortedsupertablessequentially,andthusthereisnoneedtostoreallthepossible
ombinations simultaneouslyin memory. All we needis theabilityto generate
them qui kly (on-line, upon request) in sorted order. To implement this idea,
twopriorityqueuesareused:
{ Q 0 storespairs(t 1 ;t 2 )fromT 1 T 2
,enablesarbitraryinsertionsanddeletions
tobedoneinlogarithmi time,andmakesthepairswiththesmallestt
1 +t
2
suma essiblein onstanttime.
{ Q 00 storespairs(t 3 ;t 4 )fromT 3 T 4
,enablesarbitraryinsertionsanddeletions
tobedoneinlogarithmi time, andmakesthepairswiththelargestt
3 +t
4
suma essiblein onstanttime.
Thisleadstothefollowingalgorithmforatargetn:
1. Pre omputation:
{ SortT
2
intoin reasingorder,andT
4
intode reasingorder;
{ InsertintoQ 0
allthepairs(t
1 ; rst(T 2 ))fort 1 2T 1 ; { InsertintoQ 00
allthepairs(t
3 ; rst(T 4 ))fort 3 2T 3 .
2. Repeat until either Q 0
or Q 00
be omes empty (in whi h ase all solutions
havebeenfound):
{ Let(t
1 ;t
2
)bethepairwithsmallestt
1 +t 2 inQ 0 ; { Let(t 3 ;t 4
)bethepairwithlargestt
3 +t 4 inQ 00 ; { Computet=t 1 +t 2 +t 3 +t 4 .
{ Ift=n,weoutputthesolution,andapplywhatisplanned whent<n
ort>n. { Ift<ndo delete(t 1 ;t 2 )fromQ 0 ; ifthesu essort 0 2 oft 2 in T 2 isde ned,insert(t 1 ;t 0 2 )intoQ 0 ; { Ift>ndo delete(t 3 ;t 4 )fromQ 00 ; ifthesu essort 0 4 oft 4 in T 4 isde ned,insert(t 3 ;t 0 4 )intoQ 00 ; Atea hstage,at 1 2T 1
anparti ipateinatmostonepairinQ 0 ,andat 3 2T 3 00
thepriorityqueuesisboundedbyO(jT 1 j+jT 3 j)=O(2 1 +2 3 ).Ea hpossible
pair an be deleted from Q 0
at most on e, and the same holds for Q 00
. Sin e
at ea h iteration, one pairis deleted from Q 0
orQ 00
, the numberof iterations
annotex eedthenumberofpossiblepairs,whi hisO(2 m1+m2
+2 m3+m4
).
Finally,asinthe2-table ase,wenotethatthisalgorithm anbeadaptedto
modular sums,by hangingthestartingpointsin T
2 andT
4
tomakesure that
themodularsetsareenumeratedinthe orre torder.Hen e,itisnotne essary
toapply the4-tablealgorithmon4targets.If m
1 =m 2 =m 3 =m 4 =m=4,we
obtainatime omplexity ofO(2 m=2
)and aspa e omplexityof onlyO(2 m=4
),
whi himprovesthetime/memorytradeo ofthemethodsofSe tions3.2and3.2.
Theprobabilitythatarandomm-bitinteger(su has) anbeexpressedasa
produ toffourintegers
i
,where
i
haslessthanm
i
bits,isgiveninSe tion1.2.
Di erentvaluesofm 1 ;m 2 ;m 3 andm 4
(notne essarilym=4),giverisetodi erent
trade-o s with respe t to the omputation time, the storage requirement, and
thesu essprobability.
Our experiments show that, as expe ted, the method requires mu h less
omputingpowerthanabrute-for eatta konthe64-bitkeyusingthesymetri
en ryption algorithm. We implemented the atta k on a PII/Linux-400 MHz.
Hereis anumeri alexample,usingDSS-likeparameters:
q=762503714763387752235260732711386742425586145191
p=12445297195020897327961146684569284985257444765520858655057634418042 7926821830
38633894759924784265833354926964504544903320941144896341512703447024 972887681
The 160-bitnumber q divides the 512-bit numberp 1. The smoothpart of
p 1is4783175916271391134111752 7
,whi hisa69-bitnumber.
Ouratta kre overedthe64-bitse retmessage14327865741237781950inonly2
hoursandahalf(wewerelu ky,asthemaximalrunningtimefor64bitsshould
bearound14hours).
4 An atta k on ElGamal using a generator of Z
p
So far,our atta kson ElGamalen ryption apply when the publi keyhp;g;yi
usesanelementg2Z
p
whoseorderismu hlessthanp.Althoughmany
imple-mentationsofElGamalusesu hg,itisworthstudyingwhethera
\meet-in-the-middleatta k"ispossiblewhenggeneratesallofZ
p
.Weshowthattheansweris
positive,althoughwe annotdire tlyusethealgorithmforsubgrouprounding.
Lethp;g;yibeanElGamalpubli keywhereg generatesallofZ
p
.Suppose
an m-bit message M is en rypted using plain ElGamal, i.e. the iphertext is
hu;vi where u=My r
and v = g r
. Suppose s isa fa tor ofp 1 sothat in
the subgroup of Z
p
or order s the dis rete log problem is not too diÆ ult (as
in Se tion 3.2), i.e.takestime T for somesmall T. Forexample, s may bean
integerwithonlysmallprime divisors(asmoothinteger).
Weshowthat whens>2 m
itisoftenpossibletore overtheplaintextfrom
the iphertextin time2 m=2
mplusthetimeittakesto omputeonedis retelog
in the subgroup of Z
of order s. We refer to this subgroup as G
s
bitsmoothfa tor.
Letu =My r
and v = g r
be an ElGamal iphertext. As before, suppose
M=M 1 M 2 wherebothM 1 andM 2
arelessthan2 m=2 .Letq=(p 1)=sthen: M 1 y r =u=M 2 modp.Hen e, M q 1 (y r ) q =u q =M q 2 modp
We annotuse the te hnique of Se tion 3.1 dire tly sin ewedo notknowthe
value of y rq . Fortunately, y rq is ontained in G s
. Hen e, we an ompute y rq
dire tlyusing thepubli keyy and v =g r
. Indeed,suppose wehad aninteger
a su h that y q = (g q ) a . Then y rq = g rqa = v qa . Computing a amounts to
omputing asingledis rete login G
s
.On e a is foundthe problemis redu ed
to ndinghM 1 ;M 2 isatisfying: M q 1 v qa =u q =M q 2 modp (3)
Thete hniquesofSe tion 3.1 annowbeused to ndallsu hhM
1 ;M
2 iinthe
timeittakesto ompute2 m=2
exponentiations.Sin ethesubgroupG
s
ontains
at least 2 m
elements the number of solutions is bounded by m. The orre t
solution anthenbeeasilyfoundbyothermeans,e.g.bytryingallm andidate
plaintextsuntiloneofthemsu eedsasa\session-key".
Note that all the te hniques of Se tion 3.2 an also be applied. The
on-lineworkof2 m=2
modularexponentiationsisthen de reasedto2 m=2
additions,
providedthepre omputationofmanydis reteloginG
s
.Indeed,bytaking
loga-rithmsin(3),oneisleftwithamodular2-tableproblem.Splittingtheunknown
messageMinadi erentnumberoffa torsleadstoothermodulark-table
prob-lems. One an thus obtain various trade-o s with respe t to the omputation
time, the memory spa e, and the probability of su ess, as des ribed in
Se -tion3.2.
Tosummarize,wheng generatesallofZ
p
themeet-in-the-middleatta k an
often be used to de rypt ElGamal iphertexts in time 2 m=2
as long as p 1
ontainsanm-bitsmoothfa tor.
5 A meet-in-the-middle atta k on plain RSA
To on ludeweremarkthatthesamete hniqueusedforthesubgrouprounding
problem an be used to atta kplain RSA. This wasalso noti ed in [8℄. In its
simplestform,theRSAsystem[17℄en ryptsmessagesinZ
N
where N=pq for
some largeprimes p and q. Thepubli key is hN;ei and the private key is d,
where ed=1mod (N)with (N) =(p 1)(q 1). A messageM 2Z
N is
then en rypted into = M e
modN. To speed up the en ryption pro ess one
oftenusesapubli exponentemu hsmallerthanN,su hase=2 16
+1.
Supposethem-bitmessageM anbewrittenasM =M
1 M 2 withM 1 2 m1 andM 2 2 m2 .Then: M e =M e 1 modN:
We an nowbuild atable of size 2 1
ontainingthe valuesM
1
modN for all
M
1
=0;:::;2 m
1
.Thenforea hM
2 =0;:::;2 m 2 ,we he kwhether =M e 2 mod
N is presentin thetable. Any ollisionwill reveal the messageM. As in
Se -tion3.1,wenotethatstoringthe ompletevalueofM e
1
modN isnotne essary:
forinstan e, storingthe2max(m
1 ;m
2
)least signi antbits should beenough.
Theatta kthusrequires2 m1+1
max(m
1 ;m
2
)bitsofmemoryandtakes2 m2
mod-ularexponentiations(we anassumethatthetablesortisnegligible, ompared
to exponentiations).
Usinganon-optimizedimplementation(based ontheNTL[19℄ library),we
obtainedthefollowingresults.Thetimings givearoughideaoftheatta k
eÆ- ien y, omparedtoexhaustivesear hatta ksonthesymmetri algorithm.
Run-ning timesaregivenforasingle500MHz64-bit DECAlpha/Linux.Ifm=40
andm
1 =m
2
=20,andweuseapubli exponent2 16
+1witha512-bitmodulus,
thepre omputationsteptakes3minutes,andea hmessageis re overedinless
than10minutes.FromSe tion1.2,italsomeansthat,givenonlythepubli key
and the iphertext, a40-bit message anbe re overedin lessthan 40 minutes
onasingleworkstation,withprobabilityatleast39%.
6 Summary and open problems
We showed that plain RSA and plain ElGamal en ryption are fundamentally
inse ure.Inparti ular,whentheyareusedtoen ryptanm-bitsession-key,the
key an often be re overed in time approximately 2 m=2
. Hen e, although an
m-bit key is used, the e e tive se urity provided by the system is only m=2
bits. Thesesresultsdemonstratetheimportan e ofaddingaprepro essingstep
su has OAEPto RSA andapro ess su h asDHAESto ElGamal.Theatta k
presentedin the paper an be used to motivate the need for prepro essing in
introdu torydes riptionsofthese systems.
Thereareanumberofopenproblemsregardingthisatta k:
Problem 1: IsthereaO(2 m=2
)timealgorithmforthemultipli ativesubgroup
roundingproblemthatworksforall?
Problem 2: IsthereaO(2 m=2
)timealgorithmfortheadditivesubgroup
round-ingproblem?
Problem 3: Can either the multipli ative or additive problems be solved in
timelessthan(2 m=2
)?Isthereasub-exponentialalgorithm (in2 m
)?
A knowledgments
Wethank PaulvanOors hotand DavidNa a he forseveral onversationson
thisproblem.WethankAdiShamirforinformingusofreferen e[18℄.Wethank
Igor Shparlinski for providing us (1) and informing us of referen e [11℄. We
1. M. Abdalla,M. Bellare,P.Rogoway,\DHAES:Anen ryptions hemebased
ontheDiÆe-Hellmanproblem",manus ript,1998.
2. R.J.Anderson,S.Vaudenay,\Minding yourp'sand q's",Pro ofAsia rypt
'96,LNCS1163,Springer-Verlag,pp.26{35,1996.
3. C. Batut, K. Belabas, D. Bernardi, H. Cohen, M. Olivier,
\Pari/GP omputer pa kage version 2", available at
http://hasse.mathematik.tu-muen hen .de/n tsw/ pari /Wel ome.
4. M. Bellare,P.Rogaway,\Optimalasymmetri en ryption|howtoen rypt
usingRSA",Pro .Euro rypt'94,LNCS950,Springer-Verlag,1995.
5. D. Boneh, \The De ision DiÆe-Hellman Problem", Pro . ANTS-III, LNCS
1423,Springer-Verlag,1998.
6. D. Boneh,\Twenty YearsofAtta ksonthe RSA ryptosystem",Noti es of
theAMS,46(2):203{213,1999.
7. J.-S. Coron, D. Na a he,J. P. Stern, \On the Se urity of RSA Padding",
Pro .ofCrypto'99,LNCS1666,Springer-Verlag,pp.1{18,1999.
8. J.-S. Coron, M. Joye, D. Na a he, P. Paillier, \New Atta ks on PKCS#1
v1.5En ryption",Pro .ofEuro rypt'2000,LNCS1807,Springer-Verlag,pp.
369{381,2000.
9. T.ElGamal,\Apubli key ryptosystemandasignatures hemebasedonthe
dis retelogarithm",IEEETrans.onInformationTheory,31(4):469{472,1985.
10. E.Fujisaki, T.Okamoto, \Se ureIntegration ofAsymmetri andSymmetri
En ryptionS hemes",Pro .of Crypto'99,LNCS1666, Springer-Verlag,pp.
537{554,1999.
11. R.R.Hall,G.Tenenbaum,\Divisors",CambridgeUniversityPress,1988.
12. A. Menezes,P. v.Oors hot,S.Vanstone,\Handbookof Applied
Cryptogra-phy",CRCPress,1997.
13. T. Okamoto and D. Point heval, \PSEC-3: Provably Se ure Ellipti Curve
En ryptionS heme",SubmissiontoIEEEP1363a, 2000.
14. P.vOors hot,M.J.Wiener,\OnDiÆe-HellmanKeyAgreementWithShort
Exponents",Pro .Euro rypt'96,LNCS1070,Springer-Verlag,1996.
15. PKCS1,\Publi KeyCryptographyStandardNo.1Version2.0",RSALabs.
16. D.Point heval,\Chosen-CiphertextSe urityforanyOne-WayCryptosystem",
Pro .PKC'2000,LNCS1751,Springer-Verlag,2000.
17. R. L. Rivest., A. Shamir, L. M. Adleman \ A method for obtaining
digi-tal signaturesandpubli -key ryptosystems", Communi ationsof theACM,
21(2):120{126,1978.
18. R.S hroeppel,A.Shamir,\AT =O(2 n=2
),S=O(2 n=4
)algorithmfor ertain
NP- ompleteproblems",SIAMJ.Comput.,10(3):456{464,1981.
19. V. Shoup, \Number Theory C++ Library (NTL) version 3.7", available at
