Cache-timing attacks on AES

1 Cache-timingattacks on AESD anielJ. Bernstein?Department of Mathematics,Statistics,andComputerScienc e(M/C249)TheUniversity of Illinoisat ChicagoChicago,IL demonstratescompleteAESkeyrecoveryfromkn own-plaintexttimingsof a networkserver shouldbe blamedontheAESdesign,notontheparticularA ESlibraryusedby theserver;it is extremelydi cultto discussesseveralof theobstaclesin :sidechannels,timingattacks,softwaretimi ngattacks,cachetiming,loadtiming,array lookups,S-boxes,AES1 IntroductionThispaper reportssuccessfulextractionof a completeAESkey froma networkserver useditskeysolelyto encryptdatausingtheOpenSSLAES implementationona was a verysimpletimingattack. Presumablythesametechniquecanextractcomp leteAESkeysfromthemorecomplicatedservers actuallyusedto handleInternetdata,althoughtheattackswil loftenrequireextratimingsto averageoutthee ectsof of thistype limitedto thePentiumIII?

2 Havetested|anAMDA thlon,anIntelPentiumIII, anIntelPentiumM,anIBMP owerPCRS64IV,anda SunUltraSPARC III|hasshowncomparablelevelsofOpenSSLAES timingvariability. Presumablyit is possibleto carryoutsimilarattacks againstsoftwarerunningonallof choseto focusonthePentiumIII becausethePentiumIII is oneof themostcommonCPUsin today' theresomecarelessmistake in theOpenSSLimplementationof AES? AESitself:it is extremelydi cultto writeconstant-time?Theauthorwas supportedby theNationalScienceFoundationundergrant CCR{9983950,andby theAlfredP. thisdocument: IDof thisdocument:cd9faae9bd5308c440df50fc26a 517b4. Thisis apreliminaryversionmeant to announceideas;it willbe replacedby a nalversionmeant to recordtheideasforposterity.}

3 Theremay be bigchangesbeforethe forcedto lookat preliminaryversions,unlesstheywant to check historicalcredits;if youcitea preliminaryversion,pleaserepeatallideast hatyouareusingfromit, so thatit is extremelydi cultto loadanarray entryin timethatdoesnotdependontheentry' choseto focusonOpenSSLbecauseOpenSSLis oneof today'smostpopularcryptographictoolkits. (Constant timelow-speedAESsoftwareis fairlyeasytowritebutis alsounacceptableformany survivedthe rstroundof AEScompetitionif it hadbeenimplementedin thisway.)Is AEStheonlycryptographicfunctionvulnerabl eto thistype of attack? featureof AESsoftware,namelyitsheavyrelianceuponS- boxes,is sharedby cryptographicsoftwareformany example,[18, ]|\GCM"|does notachieve tolerablespeedwithout4096-byteS-boxes;pr esumablythisGCMsoftwareleaksa greatdealof secretinformationto a EncryptionAlgorithm,publishedby WheelerandNeedhamin [24];SHA-256,publishedin [1];Helix,publishedby Ferguson,Whiting,Schneier,Kelsey, Lucks,andKohnoin [11];andmy fewsimpleoperationsthattake constant timeoncommongeneral-purposeCPUs:32-bitad ditions,constant-distancerotations, no apparent incentive forimplementorsof thesefunctionsto useS-box lookupsor otheroperationswithinput-dependenttiming s.

4 Topspeedis easilyachievedby canbe interpretedas a callforfurtherresearch into such of thispaper through6 present theattackin identi estherelevant errorsin through15 focuson theextremelydi cultproblemof make noclaimsof novelty considerablymorecomplicated, considerablyeasierto exploit,and much moredi cultto controlthanindicatedin indexis a recipe noteon terminologyIn thispaper,S-box lookupsaretablelookupsusinginput-depende nt indices; ,loadsfrominput-dependent addressesin featureof software,notof themathematicalfunctionscomputedby example,onecanwriteAESsoftwarethatdoes notuseS-boxes,or (much faster) variousmathematicalfunctionsas \S-boxes."I have noideahow thiscompetingnotionof \S-box" is de the16-bit-to-8-bitfunction(x; y)7!

5 X yan\S-box"?Perhapsthereis a coherent de nitionof whatit meansfora functionto be an\S-box,"andperhapsthatde nitionisusefulin somecontexts,butit is clearlynottheright Summaryof AESAES scramblesa 16-byteinputnusinga 16-bytekeyk, a constant 256-bytetableS= (99;124;119;123;242; : : :), andanotherconstant 256-bytetableS0=(198;248;238;246;255; : : :). Thesetwo 256-bytetablesareexpandedinto four1024-bytetablesT0; T1; T2; T3de nedbyT0[b] = (S0[b]; S[b]; S[b]; S[b] S0[b]);T1[b] = (S[b] S0[b]; S0[b]; S[b]; S[b]);T2[b] = (S[b]; S[b] S0[b]; S0[b]; S[b]);T3[b] = (S[b]; S[b]; S[b] S0[b]; S0[b]):Here meansxor, ,additionof 16-byteauxiliaryarrays,xandy. The rstarray isinitializedtok. Thesecondarray is initializedton rstmodi esxas four4-bytearraysx0; x1; x2; (S[x3[1]] 1; S[x3[2]]; S[x3[3]]; S[x3[0]]).

6 Replace(x0; x1; x2; x3) with(e x0; e x0 x1; e x0 x1 x2; e x0 x1 x2 x3).AESthenmodi esyas four4-bytearraysy0; y1; y2; (y0; y1; y2; y3) with(T0[y0[0]] T1[y1[1]] T2[y2[2]] T3[y3[3]] x0;T0[y1[0]] T1[y2[1]] T2[y3[2]] T3[y0[3]] x1;T0[y2[0]] T1[y3[1]] T2[y0[2]] T3[y1[3]] x2;T0[y3[0]] T1[y0[1]] T2[y1[2]] T3[y2[3]] x3).I learnedthisviewof AESfromsoftwarepublishedby Barretoin [4].AESmodi esxagain,using 2 insteadof 1; modi esyagain;modi esxagain,using 4; modi esyagain;andso onfora totalof forthexmodi cationsare1;2;4;8;16;32;64;128;27; ,theymodi cationuses(S[]; S[]; S[]; S[]) ratherthanT0[] T1[] T2[] T3[].The nalvalueofyis theoutputAESk(n).Notethattheevolutionofx is independent ofn. Onecanexpandkinto theeleven valuesofx, togetheroccupying176bytes,andthenreuseth osevaluesforeachn.

7 Thiskey expansionis notalways a good idea;if many keysarehandledsimultaneouslythenthetimet o loadtheprecomputedvaluesofxfrommemorymay exceedthetimeneededto Summaryof the attackHereis thesimplestconceivabletimingattack lookupT0[k[0] n[0]] speculatethatthetimeforthisarray lookupdependsonthearray index;thatthetimeforthewholeAEScomputati oniswell correlatedwiththetimeforthisarray lookup;that,consequently, theAEStimingsleakinformationaboutk[0] n[0];andthatonecandeducetheexactvalueofk [0]fromthedistributionof AEStimingsas a functionofn[0].Similarcomments applytok[1] n[1],k[2] n[2], ,forexample,thattheattacker watchesthetimetakenby thevictimto handlemanyn's, totalstheAEStimesforeach possiblen[13],and observes thattheoverallAEStimeis maximumwhenn[13]is, say, alsoobserves,by carryingoutexperiments withknownkeyskona computerwiththesameAESsoftwareandthesame CPU,thattheoverallAEStimeis maximumwhenk[13] n[13]is, say, 8.

8 Theattacker concludesthatthevictim'sk[13]is 147 8 = triedthisembarrassinglysimpleAEStimingat tack againsta simpleserveranddiscoveredthatit through6 explainexactlywhatI did,so thatotherscanreproducemy ThetargetedserverThecompleteserver software, , is shownin is given a 16-byteAESkey listensforUDPpacketssent to port10000of variablelengthbutalways beginwitha copiesthenonceto itsresponse,alongwitha high-precisionreceipttimestampobtainedfr omtheCPU'scyclecounter:*(unsignedint *) (out+ 32) = timestamp();..for (i = 0;i < 16;++i)out[i]= in[i];Theserver copiestherestof thepacket into a workareahaving3*lenbytes,wherelenis thepacket length:unsignedcharworkarea[len* 3];..for (i = 16;i< len;++i)workarea[i]= in[i];Theserver alsoscramblesthenonceusingOpenSSL:AES_en crypt(in,workarea,&expanded);A realserver wouldnextusethescramblednonceto verifyanauthenticatorfortheincomingpacke t, simplysendsback a scrambledzero(precomputed),alongwithanou tgoingtimestamp:for (i = 0;i < 16;++i)out[16+ i] = scrambledzero[i];*(unsignedint *) (out+ 36) = timestamp();Theserver does notsendany otherinformationto theclient, anddoes notuseitskey in any ,I wrotethisserver to minimizetheamount of noisein thetimingsavailableto theclient.

9 However,addingnoisedoes notstoptheattack: theclientsimplyaveragesover a largernumber of samples,as in [7].In particular,reducingtheprecisionof theserver'stimestamps,or eliminatingthemfromtheserver'sresponses, does notstoptheattack: theclient simplyusesround-triptimingsbasedonitsloc alclock, andcompensatesfortheincreasednoiseby averagingover a largernumber of Preparationfor the attackIn theattacker'srole,I compiledandrantheserver :% gcc 19 2003% gcc -O3 -o printenv| wc -c549% . < /dev/zeroAt thispoint theserver was listeningforUDPpacketson port1000of IP was usinga knownAESkey, ,fromanothercomputer,I sent random400-bytepacketsto theserver,usingthestudyprogram(alsox86-s peci c)shownin AppendixB:% gcc -O3 -o.

10 > linessuch as thefollowing:13 4008 :Theserver was sent 4196901400-bytepacketshavingn[13]= 8. It handledthosepacketsin 3087:895cyclesonaverage,witha deviationof 129 theaverageover allchoicesofn[13],theaverageforn[13]= 8 was 3 :063is anestimateof thedeviationin thisdi erence:if thedistributionoftimingsis closetonormal,witha deviationaround129:512cycles,thenanavera geof 4196901such timingshasa deviationaround129:512=p4196901 0:063cycles.(Thedeviationin theaverageover all choicesofn[13]is, presumably,1=16thas large,andis ignored.)Otherlinesshow similarinformationforotherchoicesofn[13] .Herearethetopcyclecounts:3:108above averageforn[13]= 8; 2:763above averageforFig. [13]a ectsOpenSSLAES timingsfork= 0 ona PentiumIII thechoiceofn[13],from0 theaveragenumber of cyclesforabout222400-bytepacketswiththat choiceofn[13],minus theaveragenumber of cyclesforallchoicesofn[13].