Introduction Independent Study Notes

IndependentStudyNotesAaronL.PaoliniIntroductionThefollowingisasummaryonselectedtopicsfroma2006wintersessionindependentstudy.Overthecourseofthewinter,numerousacademicpapersandtextswerereadinordertogainsomeinsightintothepracticeofcryptanalysis.Onecommonpracticewhenanalyzingaparticularcipheristheintentionalweakeningoftheciphertobestudied.Notonlydoesthismakeanalysisfeasible,itisalsousefulinthatitmayrevealweaknesspertainingspecificallytocertainelementswithinthecipher.Suchweaknessescanbeusedtoattackafullerversionofthecipher,aswellasimprovethecipher’ssecuritybyfixingthatparticularelement.Thefollowingdocumentattemptstosummarizeaselectnumberofcommonattacksthathavebeenusedwithsomedegreeofsuccessagainstcertainblockciphers.Attheendofthedocumentisalistofworksthathavebeenread.AStatementaboutModernCryptanalysisUnlikethecryptanalysisofthelastfewdecades,moderncryptanalysisislargelytheoreticalinnature.Keysthatwereonce56bits(forDES)havesincegrowntoashighas256bits(ormoreinsomecases),makingmanyattacksinfeasibletotestexperimentally.Ofcourse,suchattacksareimportant,butremainimpracticaltocarryoutduetothelimitsofmoderncomputingequipment.ContentsGeneralizedAttackMethods1.ClassicCryptanalyticAttacks2.DifferentialCryptanalysis3.LinearCryptanalysis4.SlideAttacks5.BoomerangAttacks6.Meet-in-the-MiddleAttacks7.Side-ChannelAttacksOtherObservations8.OnKhinchin’sMathematicalFoundationsofInformationTheory9.OnCommonBlockCipherElementsBibliography(Seefinalpages)ClassicalCryptanalysisOverviewWhileciphersofthepasthavebeenthoroughlybroken,thepracticeofperformingcryptanalysisonearlyciphersservesasagentleintroductiontothisfieldofstudy.FrequencyAnalysis(substitution,affine)Bothmonoalphabeticsubstitutionandaffinecipherssuccumbeasilytoamethodofattackknownasfrequencyanalysis.Essentially,byrecordingthefrequencyofsinglecharacters,digrams,andtrigramsinaparticularciphertextandcomparingtheseresultsagainstpreviouslyobtainedfrequencycharacteristicsforthatparticularlanguage,onecanattempttodecodetheciphertext.Foralargeenoughciphertext(sothatuniquedecipherabilityisobtainable)andforafineenoughexpectedfrequencydistribution,thismethodcertainlyworks.Ofcourse,someadditionalmanualanalysismaybenecessarytofullyrecovertheplaintext,butforthemostpart,highfrequencycharacteristicsusuallyholdwellenoughtomaketheattempteddecodingreadable,albeitwithminorerrors.Correctingsucherrorsistrivial.DifferentialCryptanalysisOverviewDifferentialcryptanalysisisoneoftheearliermethodsofblockciphercryptanalysisthatprovedtobeeffectiveagainstcertainblockcipherssuchasFEALandreduced-roundDES.Ingeneral,thisattackexamineshowagivenchangeintheinputofacipherwillaffecttheresultantplaintext.This“difference”isusuallydefinedtobetheXORoftwobitstrings(twoplaintextsortwociphertexts).Considerthef-functioninputofagivenFeistelalgorithm,suchasDES.Giventwoplaintexts(X1andX2)withagivenXOR(X1XORX2),thereexistsanon-uniformoutputXOR(Y1XORY2)distribution.Thatistosay,fortheentirerangeofpossibleplaintextpairswithagivenXORvalue,thereexistsanoutputXORvaluethatoccurswithaprobabilityPoutthatisgreaterthanotherpossibleoutputXORvalues.Thischaracteristicisthebasisforachosenplaintextcryptanalyticattackagainstaalgorithmthatexhibitsthisbehavior.OnMultipleRoundsandDifferentialCharacteristicsForann-roundcipher,thereexistsann-rounddifferentialcharacteristicwithanassociatedprobabilityp.Thisn-rounddifferentialcharacteristicissimplytheconcatenationofnsinglerounddifferentialcharacteristics,eachwithanassociatedprobabilitypi.Theoverallprobabilitypissaidtobethemultiplicationofallper-rounddifferentialprobabilities,althoughthisonlyholdstrueiftheroundsareconsideredindependentofoneanother.Whilethisnotthecase,p,ascalculated,isconsideredtobecloseenoughtoitsactualvalue.Atthispoint,itmaybebeneficialtoclarifytheconceptoftheprobabilitypforagivenn-rounddifferentialcharacteristic.Essentially,theprobabilitythatforagivenroundinputXOR(X1XORX2),anexpectedroundoutputXOR(Y1XORY2)willoccurwithaprobabilitypi.Theprobabilitythatthedesiredper-roundcharacteristicswillholdoverallroundsinthecipherisgivenbyp.Obviously,thehigherthisoverallprobabilityis,themorefavorabletheconditionsforacryptanalyticattack.Thus,itiswisetochoosecarefullytheinputXORoftheplaintextpairanddesiredoutputXORtoyieldthehighestoveralln-rounddifferentialcharacteristicprobabilityp.Forexample,inadifferentialattackontheDataEncryptionStandard(DES)itisbeneficialfortherighthalfoftheinputXORtoevaluatetozero.Suchatechniquegreatlyimprovesthedifferentialcharacteristic’sprobability,asanf-functioninputXORofzerowillresultinanf-functionoutputofzerowithprobability1.OnDifferentialCryptanalysisandDESInthecaseofDES,keybitsarecalculatedbyconsideringthefinalf-functioninput(essentiallythelefthalfoftheciphertext)andanexpectedf-functionoutputthatholdswithprobabilityp.Thef-roundoutputcannotbeknownforcertainasitismaskedbythelefthalfofthepreviousroundinputtogivetherighthalfoftheciphertext.OneofthefirsteffectivemethodsofcryptanalysisontheDataEncryptionStandardwasdifferentialcryptanalysis,ifonlyreducedroundversions(usually3to12