第3章 分组密码和数据加密标准

第3章分组密码与数据加密标准ModernBlockCiphersmodernblockciphersoneofthemostwidelyusedtypesofcryptographicalgorithmsprovidesecrecy/authenticationservicesfocusonDES(DataEncryptionStandard)toillustrateblockcipherdesignprinciplesBlockvsStreamCiphersblockciphersprocessmessagesinblocks,eachofwhichisthenen/decryptedlikeasubstitutiononverybigcharacters•64-bitsormorestreamciphersprocessmessagesabitorbyteatatimewhenen/decryptingmanycurrentciphersareblockciphersbroaderrangeofapplicationsBlockCipherPrinciplesmostsymmetricblockciphersarebasedonaFeistelCipherStructureneededsincemustbeabletodecryptciphertexttorecovermessagesefficientlyblockcipherslooklikeanextremelylargesubstitution•wouldneedtableof264entriesfora64-bitblockinsteadcreatefromsmallerbuildingblocksusingideaofaproductcipherIdealBlockCipherClaudeShannonandSubstitution-PermutationCiphersClaudeShannonintroducedideaofsubstitution-permutation(S-P)networksin1949paperformbasisofmodernblockciphersS-Pnetsarebasedonthetwoprimitivecryptographicoperationsseenbefore:•substitution(S-box)•permutation(P-box)provideconfusion&diffusionofmessage&keyConfusionandDiffusioncipherneedstocompletelyobscurestatisticalpropertiesoforiginalmessageaone-timepaddoesthismorepracticallyShannonsuggestedcombiningS&Pelementstoobtain:diffusion–dissipatesstatisticalstructureofplaintextoverbulkofciphertextconfusion–makesrelationshipbetweenciphertextandkeyascomplexaspossibleFeistelCipherStructureFeisteldevisedFeistelcipherbasedonconceptofinvertibleproductcipherpartitionsinputblockintotwohalvesprocessthroughmultipleroundswhichperformasubstitutiononleftdatahalfbasedonroundfunctionofrighthalf&subkeythenhavepermutationswappinghalvesimplementsShannon’sS-PnetconceptFeistelCipherStructureFeistelCipherDesignElementsblocksizekeysizenumberofroundssubkeygenerationalgorithmroundfunctionfastsoftwareen/decryptioneaseofanalysisFeistelCipherDecryptionDataEncryptionStandard(DES)mostwidelyusedblockcipherinworldadoptedin1977byNBS(nowNIST)asFIPSPUB46encrypts64-bitdatausing56-bitkeyhaswidespreadusehasbeenconsiderablecontroversyoveritssecurityDESHistoryIBMdevelopedLucifercipherbyteamledbyFeistelinlate60’sused64-bitdatablockswith128-bitkeythenredevelopedasacommercialcipherwithinputfromNSAandothersin1973NBSissuedrequestforproposalsforanationalcipherstandardIBMsubmittedtheirrevisedLuciferwhichwaseventuallyacceptedastheDESDESDesignControversyalthoughDESstandardispublic,itwasconsiderablecontroversyoverdesigninchoiceof56-bitkey(vsLucifer128-bit)becausedesigncriteriawereclassifiedsubsequenteventsandpublicanalysisshowinfactdesignwasappropriateuseofDEShasflourishedespeciallyinfinancialapplicationsstillstandardisedforlegacyapplicationuseDESEncryptionOverviewInitialPermutationIPfirststepofthedatacomputationIPreorderstheinputdatabitsevenbitstoLHhalf,oddbitstoRHhalfquiteregularinstructure(easyinh/w)example:IP(675a69675e5a6b5a)=(ffb2194d004df6fb)DESRoundStructureusestwo32-bitL&RhalvesasforanyFeistelciphercandescribeas:Li=Ri–1Ri=Li–1F(Ri–1,Ki)Ftakes32-bitRhalfand48-bitsubkey:•expandsRto48-bitsusingpermE•addstosubkeyusingXOR•passesthrough8S-boxestoget32-bitresult•finallypermutesusing32-bitpermPDESRoundStructureSubstitutionBoxesShaveeightS-boxeswhichmap6to4bitseachS-boxisactually4little4bitboxesouterbits1&6(rowbits)selectonerowof4innerbits2-5(colbits)aresubstituted,resultis8lotsof4bits,or32bitsrowselectiondependsonbothdata&key•featureknownasautoclaving(autokeying)•example:S(1809123d11173839)=5fd25e03DESKeyScheduleformssubkeysusedineachroundinitialpermutationofthekey(PC1)whichselects56-bitsintwo28-bithalves16stagesconsistingof:•rotatingeachhalfseparatelyeither1or2placesdependingonthekeyrotationscheduleK•selecting24-bitsfromeachhalf&permutingthembyPC2foruseinroundfunctionFnotepracticaluseissuesinh/wvss/wDESDecryptiondecryptmustunwindstepsofdatacomputationwithFeisteldesign,doencryptionstepsagainusingsubkeysinreverseorder(SK16…SK1)IPundoesfinalFPstepofencryption1stroundwithSK16undoes16thencryptround….16throundwithSK1undoes1stencryptroundthenfinalFPundoesinitialencryptionIPthusrecoveringoriginaldatavalueAvalancheEffectkeydesirablepropertyofencryptionalgorithmwhereachangeofoneinputorkeybitresultsinchangingapproxhalfoutputbitsmakingattemptsto“home-in”byguessingkeysimpossibleDESexhibitsstrongavalancheStrengthofDES–KeySize56-bitkeyshave256=7.2x1016valuesbruteforcesearchlookshardrecentadvanceshaveshownispossible•in1997onInternetinafewmonths•in1998ondedicatedh/w(EFF)inafewdays•in1999abovecombinedin22hrs!stillmustbeabletorecognizeplaintextmustnowconsideralternativestoDESStrengthofDES–AnalyticAttacksnowhaveseveralanalyticattacksonDESutilisesomedeepstructureofthecipher•bygatheringinformationaboutencryptions•caneventuallyrecoversome/allofthesub-keybits•ifnecessarythenexhaustivelysearchfortherestgenerallythesearestatisticalattacks•differentialcryptanalysis•linearcryptanalysis•relatedkeyattacksStrengthofDES–TimingAttacksattacksactualimplementationofcipheruseknowledgeofconseq