第3章分組密碼與數(shù)據(jù)加密標(biāo)準(zhǔn)

第3章分組密碼與數(shù)據(jù)加密標(biāo)準(zhǔn)ModernBlockCiphersmodernblockciphersoneofthemostwidelyusedtypesofcryptographicalgorithmsprovidesecrecy/authenticationservicesfocusonDES(DataEncryptionStandard)toillustrateblockcipherdesignprinciplesModernBlockCiphersmodernbloBlockvsStreamCiphersblockciphersprocessmessagesinblocks,eachofwhichisthenen/decrypted

likeasubstitutiononverybigcharacters64-bitsormorestreamciphers

processmessagesabitorbyteatatimewhenen/decryptingmanycurrentciphersareblockciphersbroaderrangeofapplicationsBlockvsStreamCiphersblockcBlockCipherPrinciplesmostsymmetricblockciphersarebasedonaFeistelCipherStructureneededsincemustbeabletodecryptciphertexttorecovermessagesefficientlyblockcipherslooklikeanextremelylargesubstitution

wouldneedtableof264entriesfora64-bitblockinsteadcreatefromsmallerbuildingblocksusingideaofaproductcipherBlockCipherPrinciplesmostsyIdealBlockCipherIdealBlockCipherClaudeShannonandSubstitution-PermutationCiphersClaudeShannonintroducedideaofsubstitution-permutation(S-P)networksin1949paperformbasisofmodernblockciphersS-Pnetsarebasedonthetwoprimitivecryptographicoperationsseenbefore:substitution(S-box)permutation(P-box)provideconfusion&diffusionofmessage&keyClaudeShannonandSubstitutioConfusionandDiffusioncipherneedstocompletelyobscurestatisticalpropertiesoforiginalmessageaone-timepaddoesthismorepracticallyShannonsuggestedcombiningS&Pelementstoobtain:diffusion–dissipatesstatisticalstructureofplaintextoverbulkofciphertextconfusion–makesrelationshipbetweenciphertextandkeyascomplexaspossibleConfusionandDiffusioncipherFeistelCipherStructureFeisteldevisedFeistelcipherbasedonconceptofinvertibleproductcipherpartitionsinputblockintotwohalvesprocessthroughmultipleroundswhich

performasubstitutiononleftdatahalfbasedonroundfunctionofrighthalf&subkeythenhavepermutationswappinghalvesimplementsShannon’sS-PnetconceptFeistelCipherStructureFeisteFeistelCipherStructureFeistelCipherStructureFeistelCipherDesignElementsblocksizekeysizenumberofroundssubkeygenerationalgorithmroundfunctionfastsoftwareen/decryptioneaseofanalysisFeistelCipherDesignElementsFeistelCipherDecryptionFeistelCipherDecryptionDataEncryptionStandard(DES)mostwidely

usedblockcipherinworldadoptedin1977byNBS(nowNIST)asFIPSPUB46encrypts64-bitdatausing56-bitkeyhaswidespreadusehasbeenconsiderablecontroversyoveritssecurityDataEncryptionStandard(DES)DESHistoryIBMdevelopedLucifercipherbyteamledbyFeistelinlate60’sused64-bitdatablockswith128-bitkeythenredevelopedasacommercialcipherwithinputfromNSAandothersin1973NBSissuedrequestforproposalsforanationalcipherstandardIBMsubmittedtheirrevisedLuciferwhichwaseventuallyacceptedastheDESDESHistoryIBMdevelopedLucifDESDesignControversyalthoughDESstandardispublic,itwasconsiderablecontroversyoverdesign

inchoiceof56-bitkey(vsLucifer128-bit)becausedesigncriteriawereclassified

subsequenteventsandpublicanalysisshowinfactdesignwasappropriateuseofDEShasflourishedespeciallyinfinancialapplicationsstillstandardisedforlegacyapplicationuseDESDesignControversyalthoughDESEncryptionOverviewDESEncryptionOverviewInitialPermutationIPfirststepofthedatacomputationIPreorderstheinputdatabitsevenbitstoLHhalf,oddbitstoRHhalfquiteregularinstructure(easyinh/w)example:

IP(675a69675e5a6b5a)=(ffb2194d004df6fb)InitialPermutationIPfirststDESRoundStructureusestwo32-bitL&RhalvesasforanyFeistelciphercandescribeas: Li

=Ri–1 Ri

=Li–1

F(Ri–1,Ki)Ftakes32-bitRhalfand48-bitsubkey:expandsRto48-bitsusingpermEaddstosubkeyusingXORpassesthrough8S-boxestoget32-bitresultfinallypermutesusing32-bitpermPDESRoundStructureusestwo32DESRoundStructureDESRoundStructureSubstitutionBoxesShaveeightS-boxeswhichmap6to4bits

eachS-boxisactually4little4bitboxesouterbits1&6(rowbits)selectonerowof4innerbits2-5(colbits)aresubstituted,resultis8lotsof4bits,or32bitsrowselectiondependsonbothdata&keyfeatureknownasautoclaving(autokeying)example:S(1809123d11173839)=5fd25e03SubstitutionBoxesShaveeightDESKeyScheduleformssubkeysusedineachroundinitialpermutationofthekey(PC1)whichselects56-bitsintwo28-bithalves16stagesconsistingof:rotatingeachhalfseparatelyeither1or2placesdependingonthekeyrotationscheduleKselecting24-bitsfromeachhalf&permutingthembyPC2foruseinroundfunctionFnotepracticaluseissuesinh/wvss/wDESKeyScheduleformssubkeysDESDecryptiondecryptmustunwindstepsofdatacomputation

withFeisteldesign,doencryptionstepsagainusingsubkeysinreverseorder(SK16…SK1)IPundoesfinalFPstepofencryption1stroundwithSK16undoes16thencryptround….16throundwithSK1undoes1stencryptroundthenfinalFPundoesinitialencryptionIPthusrecoveringoriginaldatavalueDESDecryptiondecryptmustunwAvalancheEffectkeydesirablepropertyofencryptionalgorithmwhereachangeofone

inputorkeybitresultsinchangingapproxhalfoutputbitsmakingattemptsto“home-in”byguessingkeysimpossibleDESexhibitsstrongavalancheAvalancheEffectkeydesirableStrengthofDES–KeySize56-bitkeyshave256=7.2x1016valuesbruteforcesearchlookshardrecentadvanceshaveshownispossiblein1997onInternetinafewmonthsin1998ondedicatedh/w(EFF)inafewdaysin1999abovecombinedin22hrs!stillmustbeabletorecognizeplaintextmustnowconsideralternativestoDESStrengthofDES–KeySize56-bStrengthofDES–AnalyticAttacksnowhaveseveralanalyticattacksonDESutilisesomedeepstructureofthecipherbygatheringinformationaboutencryptionscaneventuallyrecoversome/allofthesub-keybitsifnecessarythenexhaustivelysearchfortherestgenerallythesearestatisticalattacksdifferentialcryptanalysislinearcryptanalysisrelatedkeyattacksStrengthofDES–AnalyticAttStrengthofDES–TimingAttacksattacksactualimplementationofcipheruseknowledgeofconsequencesofimplementationtoderiveinformationaboutsome/allsubkeybitsspecificallyusefactthatcalculationscantakevaryingtimesdependingonthevalueoftheinputstoitparticularlyproblematiconsmartcardsStrengthofDES–TimingAttacDifferentialCryptanalysisoneofthemostsignificantrecent(public)advancesincryptanalysisknownbyNSAin70'scfDESdesignMurphy,Biham&Shamirpublishedin90’spowerfulmethodtoanalyseblockciphersusedtoanalysemostcurrentblockcipherswithvaryingdegreesofsuccessDESreasonablyresistanttoit,cfLuciferDifferentialCryptanalysisoneDifferentialCryptanalysisastatisticalattack

againstFeistelciphers

usescipherstructurenotpreviouslyuseddesignofS-Pnetworkshasoutputoffunctionfinfluencedbybothinput&keyhencecannottracevaluesbackthroughcipherwithoutknowingvalueofthekeydifferentialcryptanalysiscomparestworelatedpairsofencryptionsDifferentialCryptanalysisastDifferentialCryptanalysisComparesPairsofEncryptionswithaknowndifferenceintheinputsearchingforaknowndifference

inoutputwhensamesubkeysareusedDifferentialCryptanalysisComDifferentialCryptanalysishavesomeinputdifferencegivingsomeoutputdifferencewithprobabilitypiffindinstancesofsomehigherprobabilityinput/outputdifferencepairsoccurringcaninfersubkeythatwasusedinroundthenmustiterateprocessovermanyrounds(withdecreasingprobabilities)DifferentialCryptanalysishaveDifferentialCryptanalysisDifferentialCryptanalysisDifferentialCryptanalysisperformattackbyrepeatedlyencryptingplaintextpairswithknowninputXORuntilobtaindesiredoutputXOR

whenfoundifintermediateroundsmatchrequiredXORhavearightpairifnotthenhaveawrongpair,relativeratioisS/Nforattackcanthendeducekeysvaluesfortheroundsrightpairssuggestsamekeybitswrongpairsgiverandomvaluesforlargenumbersofrounds,probabilityissolowthatmorepairsarerequiredthanexistwith64-bitinputsBihamandShamirhaveshownhowa13-rounditeratedcharacteristiccanbreakthefull16-roundDESDifferentialCryptanalysisperfLinearCryptanalysisanotherrecentdevelopmentalsoastatisticalmethod

mustbeiteratedoverrounds,withdecreasingprobabilitiesdevelopedbyMatsuietalinearly90'sbasedonfindinglinearapproximationscanattackDESwith243knownplaintexts,easierbutstillinpractiseinfeasibleLinearCryptanalysisanotherreLinearCryptanalysisfindlinearapproximationswithprobp!=?P[i1,i2,...,ia]C[j1,j2