approachessss17.com

ProtectingAESwithShamir'sSecretSharingSchemeLouisGoubin1andAngeMartinelli1,21VersaillesSaint-Quentin-en-YvelinesUniversityLouis.
Goubin@prism.
uvsq.
fr2ThalesCommunicationsjean.
martinelli@fr.
thalesgroup.
comAbstract.
CryptographicalgorithmsembeddedonphysicaldevicesareparticularlyvulnerabletoSideChannelAnalysis(SCA).
Themostcom-moncountermeasureforblockcipherimplementationsismasking,whichrandomizesthevariablestobeprotectedbycombiningthemwithoneorseveralrandomvalues.
Inthispaper,weproposeanoriginalmaskingschemebasedonShamir'sSecretSharingscheme[23]asanalternativetoBooleanmasking.
WedetailitsimplementationfortheAESusingthesametoolthanRivainandProuinCHES2010[17]:multi-partycomputation.
Wethenconductasecurityanalysisofourschemeinor-dertocompareittoBooleanmasking.
Ourresultsshowthatforagivenamountofnoisetheproposedscheme-implementedtotherstorder-providesthesamesecuritylevelas3rdupto4thorderbooleanmasking,togetherwithabettereciency.
Keywords:SideChannelAnalysis(SCA),Masking,AESImplementa-tion,Shamir'sSecretSharing,Multi-partycomputation.
1IntroductionSideChannelAnalysisisacryptanalyticmethodinwhichanattackeranalyzesthesidechannelleakage(e.
g.
thepowerconsumption,producedduringtheexecutionofacryptographicalgorithmembeddedonaphysicaldevice.
SCAexploitsthefactthatthisleakageisstatisticallydependentontheintermediatevariablesthatareinvolvedinthecomputation.
Someofthesevariablesarecalledsensitiveinthattheyarerelatedtoasecretdata(e.
g.
thekey)andaknowndata(e.
g.
theplaintext),andrecoveringinformationonthemthereforeenablesecientkeyrecoveryattacks[12,3,9].
ThemostcommoncountermeasuretoprotectimplementationsofblockciphersagainstSCAistousemaskingtechniques[4,10]torandomizethesensitivevari-ables.
Theprincipleistocombineoneorseveralrandomvalues,calledmasks,witheveryprocessedsensitivevariable.
MasksandmaskedvariablespropagateFullversionofthepaperpublishedintheproceedingsofCHES2011throughoutthecipherinsuchawaythatanyintermediatevariableisindepen-dentofanysensitivevariable.
Thismethodensuresthattheleakageataninstanttisindependentofanysensitivevariable,thusrenderingSCAdiculttoper-form.
Themaskingcanbeimprovedbyincreasingthenumberofrandommasksthatareusedpersensitivevariable.
Amaskingthatinvolvesdrandommasksiscalledadth-ordermaskingandcanalwaysbetheoreticallybrokenbya(d+1)th-orderSCA,namelyanSCAthattargetsd+1intermediatevariablesatthesametime[14,22,19].
However,thenoiseeectsimplythatthecomplexityofadth-orderSCAincreasesexponentiallywithdinpractice[4].
Thedth-orderSCAresistance(foragivend)isthusagoodsecuritycriterionforimplementationsofblockciphers.
In[18]RivainandProugiveageneralmethodtoimplementadth-ordermaskingschemetotheAESusingsecureMulti-PartyComputation.
Insteadoflookingforperfecttheoreticalsecurityagainstdth-orderSCAasdonein[18],analternativeapproachconsistsinlookingforpracticalresistancetotheseattacks.
Itmayforinstancebeobservedthattheeciencyofhigher-orderSCAisrelatedtothewaythemasksareintroducedtorandomizesensitivevari-ables.
ThemostwidelystudiedmaskingschemesarebasedonBooleanmaskingwheremasksareintroducedbyexclusive-or(XOR).
Firstorderbooleanmaskingenablessecuringimplementationsagainstrst-orderSCAquiteeciently[1,17].
Itishoweverespeciallyvulnerabletohigher-orderSCA[14]duetotheintrinsicphysicalpropertiesofelectronicdevices.
Othermaskingschemesmayprovidebetterresistanceagainsttheseattacksusingvariousoperationstorandomizesensitivevariables.
Thisapproachwillbefurtherinvestigatedinthispaper.
Relatedwork.
In[26,6],theauthorsproposetouseananefunctioninsteadofjustXORtomasksensitivevariables,thusimprovingthesecurityoftheschemeforalowcomplexityoverhead.
However,thiscountermeasureisdevel-opedonlytothe1thorderanditisnotclearhowitcanbeextendedtohigherorders.
In[11,17]theauthorsexplainhowtousesecureMulti-PartyComputa-tiontoprocessthecipheronsharedvariables.
TheyuseasharingschemebasedonXOR,implementingbooleanmaskingtoanyordertosecuretheAESblockcipher.
Atlast,in[20],ProuandRochegiveahardwareorientedglitchfreewaytoimplementblockciphersusingShamir'sSecretSharingschemeandBen-Oretal.
securemulti-partycomputation[2]protocoloperatingon2d+1sharestothwartd-thorderSCA.
Ourcontribution.
Inthispaper,weproposetocombinebothapproachesinim-plementingamaskingschemebaseduponShamir'sSecretSharingscheme[23],calledSSSmaskingandprocessedusingMulti-partyComputationmethods.
Namely,wepresentanimplementationoftheblockciphersuchthatevery8-bitintermediateresultz∈GF(256)ismanipulatedundertheform(xi,P(xi))i=0.
.
d,wherexi∈GF(256)isarandomvaluegeneratedbeforeeachnewexecutionofthealgorithmandP(X)∈GF(256)[X]isapolynomialofdegreedsuchthatP(0)=z.
OurschememaintainsthesamecompatibilityasBooleanmaskingwiththelineartransformationsofthealgorithm.
Moreover,thefactthatthemasksareneverprocessedalonepreventsthemtobetargetedbyahigher-orderSCA,thusgreatlyimprovestheresistanceoftheschemetosuchattacks.
Organizationofthepaper.
WestrecalltheAESandShamir'ssecretshar-ingschemeinSect.
2.
InSect.
3,weshowhowSSSmaskingcanbeappliedtotheAESandgivesomeimplementationresults.
Sect.
4analyzestheresistanceofourmethodtohigh-orderSCAandSect.
5concludesthepaper.
2Preliminaries2.
1TheAdvancedEncryptionStandardTheAdvancedEncryptionStandard(AES)isablockcipherthatiterate10timesaroundtransformation.
Eachoftheseinvolvesfourstages:AddRoundKey,ShiftRows,MixColumn,andSubByte,thatensurethesecurityofthescheme.
Inthissection,werecallthefourmainoperationsinvolvedintheAESencryptionAlgorithm.
Foreachofthem,wedenotebys=(si,j)0≤i,j≤3thestateattheinputofthetransformation,andbys=(si,j)0≤i,j≤3thestateattheoutputofthetransformation.
1.
AddRoundKey:Letk=(ki,j)0≤i,j≤3denotetheroundkey.
EachbyteofthestateisXOR-edwiththecorrespondingroundkeybyte:(si,j)←(si,j)(ki,j).
2.
SubBytes:eachbyteofthestatepassesthroughthe8-bitAESS-boxS:si,j←S(si,j).
3.
ShiftRows:eachrowofthestateiscyclicallyshiftedbyacertainoset:si,j←si,jimod4.
4.
MixColumns:eachcolumnofthestateismodiedasfollows:(s0,c,s1,c,s2,c,s3,c)←MixColumnsc(s0,c,s1,c,s2,c,s3,c)whereMixColumnscimplementsthefollowingoperations:s0,c←(02·s0,c)(03·s1,c)s2,cs3,cs1,c←s0,c(02·s1,c)(03·s2,c)s3,cs2,c←s0,cs1,c(02·s2,c)(03·s3,c)s3,c←(03·s0,c)s1,cs2,c(02·s3,c),where·andrespectivelydenotethemultiplicationandtheadditionintheeldGF(2)[X]/p(X)withp(X)=X8+X4+X3+X+1,andwhere02and03respectivelydenotetheelementsXandX+1.
Inthefollowing,wewillassumethatMixColumnscisimplementedass0,c←xtimes(s0,cs1,c)tmps0,cs1,c←xtimes(s1,cs2,c)tmps1,cs2,c←xtimes(s2,cs3,c)tmps2,cs3,c←s0,cs1,cs2,ctmp,wheretmp=s0,cs1,cs2,cs3,candwherethextimesfunctionisimple-mentedasalook-uptablefortheapplicationx→02·x.
2.
2Shamir'sSecretSharingschemeInsomecryptographiccontextonesmayneedtoshareasecretbetween(atleast)duserswithoutanyk1063O-MIAon2OBooleanMasking160160000650000>106>106AttacksagainstSSSMasking2O-DPAon1OSSSMasking>106>106>106>106>1062O-MIAon1OSSSMasking500000>106>106>106>1063O-DPAon2OSSSMasking>106>106>106>106>1063O-MIAon2OSSSMasking>106>106>106>106>1065ConclusionInthispaperweproposeanewalternativetobooleanmaskingtosecureimple-mentationsofAESagainstsidechannelattacksusingShamir'sSecretSharingschemetosharesensitivevariables.
Wegiveimplementationresultsandcon-ductasecurityanalysisthatclearlyshowthatourschemecanprovideagoodcomplexity-securitytrade-ocomparedtobooleanmasking.
Inparticular,onsmartcardimplementation,whereSNRvalueisaround1/2,1OSSSmaskingprovidesbothabettersecurityandcomplexitythan3Obooleanmasking.
Onhardwareimplementationswherethenoisecanbedrasticallyreduced,1OSSSmaskingistobecomparedto4thorderbooleanmasking,whichincreasethead-vantageofSSSmasking.
Table6resumethecomplexitoftheinversionalgorithminthesescnarii.
MaskingschemeXORmultiplications2jRandombytesRAMO1-SSS(Algo.
2)5872181818O1-SSS(Algo.
3)365414620O3-boolean(σ=2)10864122018O4-boolean(σ≈0)176100154825Table6.
ComplexityofinversionalgorithmsforsimilarsecuritylevelsTheseresultsshowthattheopeningtosecretsharingandsecuremulti-partycomputationcanprovideagoodalternativetobooleanmasking.
ThismaybeaninterestingwaytothwartHO-SCA.
Itisanopenresearchtopictotrythesecurityandcomplexityofsuchamaskingusingotherkindsofsecretsharingscheme.
References1.
Mehdi-LaurentAkkarandC.
Giraud.
AnImplementationofDESandAES,SecureagainstSomeAttacks.
InC.
K.
Koc,D.
Naccache,andC.
Paar,editors,Crypto-graphicHardwareandEmbeddedSystems–CHES2001,volume2162ofLectureNotesinComputerScience,pages309–318.
Springer,2001.
2.
MichaelBen-Or,ShaGoldwasser,andAviWigderson.
Completenesstheoremsfornon-cryptographicfault-tolerantdistributedcomputation(extendedabstract).
InSTOC,pages1–10.
ACM,1988.
3.
E.
Brier,C.
Clavier,andF.
Olivier.
CorrelationPowerAnalysiswithaLeakageModel.
InM.
JoyeandJ.
-J.
Quisquater,editors,CryptographicHardwareandEm-beddedSystems–CHES2004,volume3156ofLectureNotesinComputerScience,pages16–29.
Springer,2004.
4.
S.
Chari,C.
S.
Jutla,J.
R.
Rao,andP.
Rohatgi.
TowardsSoundApproachestoCounteractPower-AnalysisAttacks.
InWiener[27],pages398–412.
5.
ChristopheClavierandKrisGaj,editors.
CryptographicHardwareandEmbed-dedSystems–CHES2009,volume5747ofLectureNotesinComputerScience.
Springer,2009.
6.
GuillaumeFumaroli,AngeMartinelli,EmmanuelProu,andMatthieuRivain.
Anemaskingagainsthigher-ordersidechannelanalysis.
InSelectedAreasinCryptography,volume6544ofLectureNotesinComputerScience.
Springer,2010.
7.
RosarioGennaro,MichaelO.
Rabin,andTalRabin.
Simpliedvssandfact-trackmultipartycomputationswithapplicationstothresholdcryptography.
InPODC,pages101–111,1998.
8.
BenediktGierlichs,LejlaBatina,BartPreneel,andIngridVerbauwhede.
RevisitingHigher-OrderDPAAttacks:MultivariateMutualInformationAnalysis.
Cryptol-ogyePrintArchive,Report2009/228,2009.
http://eprint.
iacr.
org/.
9.
BenediktGierlichs,LejlaBatina,PimTuyls,andBartPreneel.
MutualInforma-tionAnalysis.
InElisabethOswaldandPankajRohatgi,editors,CryptographicHardwareandEmbeddedSystems–CHES2008,volume5154ofLectureNotesinComputerScience,pages426–442.
Springer,2008.
10.
L.
GoubinandJ.
Patarin.
DESandDierentialPowerAnalysis–TheDuplicationMethod.
InC.
K.
KocandC.
Paar,editors,CryptographicHardwareandEmbeddedSystems–CHES'99,volume1717ofLectureNotesinComputerScience,pages158–172.
Springer,1999.
11.
YuvalIshai,AmitSahai,andDavidWagner.
PrivateCircuits:SecuringHardwareagainstProbingAttacks.
InD.
Boneh,editor,AdvancesinCryptology–CRYPTO2003,volume2729ofLectureNotesinComputerScience,pages463–481.
Springer,2003.
12.
P.
Kocher,J.
Jae,andB.
Jun.
DierentialPowerAnalysis.
InWiener[27],pages388–397.
13.
StefanMangard,ElisabethOswald,andThomasPopp.
PowerAnalysisAttacks–RevealingtheSecretsofSmartcards.
Springer,2007.
14.
T.
S.
Messerges.
UsingSecond-orderPowerAnalysistoAttackDPAResistantSoftware.
InC.
K.
KocandC.
Paar,editors,CryptographicHardwareandEmbeddedSystems–CHES2000,volume1965ofLectureNotesinComputerScience,pages238–251.
Springer,2000.
15.
D.
Pointcheval,editor.
TopicsinCryptology–CT-RSA2006,volume3860ofLectureNotesinComputerScience.
Springer,2006.
16.
EmmanuelProuandMatthieuRivain.
TheoreticalandPracticalAspectsofMutualInformationBasedSideChannelAnalysis.
InMichelAbdalla,DavidPointcheval,Pierre-AlainFouque,andDamienVergnaud,editors,AppliedCryp-tographyandNetworkSecurity–ANCS2009,volume5536ofLectureNotesinComputerScience,pages499–518.
Springer,2009.
17.
EmmanuelProuandMatthieuRivain.
ProvablySecureHigher-OrderMaskingofAES.
InStefanMangardandFranois-XavierStandaert,editors,CryptographicHardwareandEmbeddedSystems–CHES2010,volume6225ofLectureNotesinComputerScience,pages413–427.
Springer,2010.
18.
EmmanuelProuandMatthieuRivain.
TheoreticalandPracticalAspectsofMutualInformationBasedSideChannelAnalysis(ExtendedVersion).
ToappearintheInt.
JournalofAppliedCryptography(IJACT),2010.
19.
EmmanuelProu,MatthieuRivain,andRegisBevan.
StatisticalAnalysisofSec-ondOrderDierentialPowerAnalysis.
IEEETrans.
Comput.
,58(6):799–811,2009.
20.
EmmanuelProuandThomasRoche.
Higher-orderglitchesfreeimplementationoftheaesusingsecuremulti-partycomputationprotocols.
InCryptographicHard-wareandEmbeddedSystems–CHES2011,LectureNotesinComputerScience.
Springer.
21.
MatthieuRivain,EmmanuelProu,andJulienDoget.
Higher-OrderMaskingandShuingforSoftwareImplementationsofBlockCiphers.
InClavierandGaj[5],pages171–188.
22.
KaiSchrammandChristofPaar.
HigherOrderMaskingoftheAES.
InPointcheval[15],pages208–225.
23.
AdiShamir.
HowtoShareaSecret.
CommunicationsoftheACM,22(11):612–613,November1979.
24.
Francois-XavierStandaert,TalMalkin,andMotiYung.
AUniedFrameworkfortheAnalysisofSide-ChannelKeyRecoveryAttacks.
InAntoineJoux,editor,AdvancesinCryptology–EUROCRYPT2009,volume5479ofLectureNotesinComputerScience,pages443–461.
Springer,2009.
25.
Francois-XavierStandaert,NicolasVeyrat-Charvillon,ElisabethOswald,BenediktGierlichs,MarcelMedwed,MarkusKasper,andStefanMangard.
Theworldisnotenough:Anotherlookonsecond-orderdpa.
CryptologyePrintArchive,Report2010/180,2010.
http://eprint.
iacr.
org/.
26.
ManfredvonWillich.
Atechniquewithaninformation-theoreticbasisforprotect-ingsecretdatafromdierentialpowerattacks.
InIMAint.
Conf.
,volume2260ofLectureNotesinComputerScience,pages44–62.
Springer,2001.
27.
M.
J.
Wiener,editor.
AdvancesinCryptology–CRYPTO'99,volume1666ofLectureNotesinComputerScience.
Springer,1999.
AComputingtheproductinGF(256)TheSSSmaskingandtheprocessingoftheAESinvolvesmultiplicationsintheeldGF(28).
Insoftwareapplications,themostecientwaytoimplementtheproductintheeldGF(256)istouseprecomputedlog/alogtables.
Theconstructionofthesetablesisbasedonthefactthatallnon-zeroelementsinaniteeldGF(2n)canbeobtainedbyexponentiationofageneratorinthiseld.
LetαbeageneratorofGF(256).
Wedenelog(αi)=iandalog(i)=αi.
Theseresultsarestoredintwotablesof2n1wordsofnbits.
Ifa,barenon-zero,thentheproducta·bcanbecomputedusinglog/alogtablesasa·b=alog[(log(a)+log(b))mod(2n1)].
(13)Inordertocomputetheadditionmodulo2n1,leta,b∈GF(2n),andletcdenotethecarryassociatedwiththeoperationa+bmod(2n).
Then,a+bmod(2n1)canbecomputedfroma+bmod(2n)andcasfollows.
Algorithm6Input:a,b∈GF(2n)Output:s=a+bmod(2n1)1.
s←a+bmod2n2.
s←s+cmod2n3.
ifs=2n1thens=04.
ReturnsSimilarlytheinversionofanon-zeroelementa∈GF(2n)canbeimplementedusinglog/alogtablesasa1=alog[log(a)mod(2n1)].
(14)