Cache time-behavior analysis on AES

Cachetime-behavioranalysisonAESMichaelNeve1andJean-PierreSeifert1andZhenghongWang2,1IntelCorporationCTGSTLTrustedPlatformLaboratory2111NE25thAvenueHillsboro,Oregon97124,USA{michael.neve.de.mevergnies,jean-pierre.seifert}@intel.com2PrincetonUniversityDepartmentofElectricalEngineeringPrincetonArchitectureLaboratoryforMultimediaandSecurityPrinceton,NewJersey08540,[e-mail]rnstein[Ber]claimsthesuccessfulextractionofanAESkeyfromanetworkserverthroughanotherclientcomputer.Hisside-channelattackwasactuallythemostsimplestconceivabletiminganalysisofAES.AlthoughBernsteingavenothoroughanalysisofhismethodologyortheunderlyingtechniquethepapercontainedthefullC-sourcecode.Thiswasactuallyveryusefultorepeat,analyzeandextendhisexperimentsandtechnique.OurpaperimprovesupontheworkdonebyBernsteininthefollowingways:1.Wepresentathoroughanalysisofhisusedmethodologyherebyformallyprovingwhyandhowhistechniqueworks.FromthisanalysiswealsoderiveagenerallimitonthenumberofderivablekeybitsthroughhistechniquewhichdependsonthearchitectureoftheunderlyingCPU.2.Weshowtheresultsofseveralimportantpracticalexperiments.ThoseunderminefirstthatthepureBernsteintechniquecannotextractinpracticeallkeybits—evenwhenthesamplespaceisdrasticallyincreased.Second,theygiveevidence,thattheBernsteintechniqueitselfcannotbechangedsimplyintoarealremoteside-channelanalysis—byjustlettingtheclientcomputermeasuringhimselftheroundtriptimesofhisqueriestotheserver.3.MotivatedbytheaboveshortcomingsofBernstein’stechniqueweimproveuponhistechnique:whileheusesonlyfirstroundinformation,weshowhowtousethisfirstroundinformationtoextractsecondroundinformation.Thus,usingamuchlowernumberofsamplesthissecondroundanalysisallowsforadirectfullAESkeyrecoverythroughsimpleoveralltimingmeasurements.OurresultsaimatsolvingtwofundamentalopenproblemsrelatedtothiskindofAESside-channelanalysis:i.)WhatareappropriateAESsoftwareimplementationscombatingthoseAESside-channelvulnerabilities?ii.)IsatrulyremoteAESkeyrecoverythroughtiminganalysisreallypossible?Keywords:AES,Cache-stateanalysis,Side-channelanalysis,S-boxtables,Statisticalinformationleakage,Timinganalysis.1IntroductionAscrutinizedsecurityanalysisofamoderncomputersystemisaparticularlydifficulttask.Thisisduetothefactthatallovertandcovertchannelsmustbeconsidered.OvertchannelsusetheWorkdonewhilebeingwithIntelCorporation,2111NE25thAvenue,Hillsboro,OR97124,USA,forasummerinternship.system’sprotecteddataobjectstotransferinformationinasecureway.Thatis,onesubjectwritesintoadataobjectandanothersubjectreadsfromthatobject.Subjectsinthiscontextarenotonlyactiveusers,butarealsoprocessesandproceduresactingonbehalfofusers.Thechannels,suchasbuffers,files,sharedmemories,threadsignals,etc.areovertbecausetheentityusedtoholdtheinformationisadataobject;thatis,itisanobjectthatisnormallyviewedasadatacontainer.Covertchannels,incontrast,useentitiesorsystemresourcesnotnormallyviewedasadatacontainertotransferinformationbetweensubjects.Thesemetadataobjects,suchasfilelocks,busyflags,branchpredictiontables,executiontime,etc.areneededtoregisterthestateofthesystem.Unfortunately,thosechannelscanleadtoillegitimatechannelsviolatingthesystem’ssecuritypromises.ThisobservationwasveryearlycapturedinthefundamentalpaperontheconfinementproblembyLampson[Lam].Overtchannelsarecontrolledbyenforcingtheaccesscontrolpolicyofthesystembeingdesignedandimplemented.Thispolicystateswhenandhowovertreadsandwritesofdataobjectsmaybemade.Onepartofthesecurityanalysismustverifythesystem’simplementationcorrectlyimplementsthestatedaccesscontrolpolicy.RecognizinganddealingwithCovertchannelsismoreelusive.Objectsusedtoholdtheinfor-mationbeingtransferredarenormallynotviewedasdataobjects,butcanoftenbemanipulatedmaliciouslyinordertotransferinformation.Inaddition,theuseofacovertchannelrequirescol-lusionbetweenasubjectwithauthorizationtosignalorleakinformationandanunauthorizedobject.Drivenbystrongmilitaryandgovernmentsecurityrequirementstherehasbeentradition-allyalargeamountofcovertchannelresearch,cf.[Lam,Kem83,Kem02].However,notethatanauthorizedobjectdoesnotnecessarilyneedssecretcollusionwithanunauthorizedobject.Forinstance,justtheexecutiontimeofanauthorizedobjectcouldleakinformationtoanunauthorizedobject,cf.Kocher’sfundamentalwork[Koc].Thisisthencalledaside-channel,cf.[CNK],asanauthorizedprogramsleaksunintentionallyinformation,potentiallyexploitablebyanunauthorizedobject,i.e.,anotherprocessrunninginparalleltotheauthorizedprocess.Butuntilveryrecentlythoseside-channelvulnerabilitieshadnorelevancefortheclassicalPCworldsofarandwereonlyaimedtowardsembeddedsecuritydevices.However,startingwithTrustedComputingefforts[AFS,CEPW,EP,ELMP+,Pea,Smi1,TCG]basedupontheclassicalPCarchitectureanewresearch-vectorischallengingthosePCcentricsecurityeffortsthroughside-channelattacks,cf.[BB,Ber,BZBMP,HK,Per,ST,TSSSM,OST].InthisnewPCsoftwareside-channelarenaespeciallythreerecentlypublishedpaperswereofparticularpublicinterest,namely[Ber,Per,OST].Thereasonisthatallthreewere(mainly)exploitingonemajoringredient