Symmetric Key Crypto.ppt

Part1 Cryptography1 SymmetricKeyCrypto Thechiefformsofbeautyareorderandsymmetry Aristotle Part1 Cryptography2 SymmetricKeyCrypto Streamcipher basedonone timepadExceptthatkeyisrelativelyshortKeyisstretchedintoalongkeystreamKeystreamisusedjustlikeaone timepadBlockcipher basedoncodebookconceptBlockcipherkeydeterminesacodebookEachkeyyieldsadifferentcodebookEmploysboth confusion and diffusion Part1 Cryptography3 StreamCiphers Part1 Cryptography4 StreamCiphers Onceuponatime notsoverylongago streamcipherswerethekingofcryptoToday notaspopularasblockciphersWe lldiscusstwostreamciphers A5 1BasedonshiftregistersUsedinGSMmobilephonesystemRC4BasedonachanginglookuptableUsedmanyplaces Part1 Cryptography5 A5 1 ShiftRegisters A5 1uses3shiftregistersX 19bits x0 x1 x2 x18 Y 22bits y0 y1 y2 y21 Z 23bits z0 z1 z2 z22 Part1 Cryptography6 A5 1 Keystream Ateachstep m maj x8 y10 z10 Examples maj 0 1 0 0andmaj 1 1 0 1Ifx8 mthenXstepst x13 x16 x17 x18xi xi 1fori 18 17 1andx0 tIfy10 mthenYstepst y20 y21yi yi 1fori 21 20 1andy0 tIfz10 mthenZstepst z7 z20 z21 z22zi zi 1fori 22 21 1andz0 tKeystreambitisx18 y21 z22 Part1 Cryptography7 A5 1 EachvariablehereisasinglebitKeyisusedasinitialfillofregistersEachregistersteps ornot basedonmaj x8 y10 z10 KeystreambitisXORofrightmostbitsofregisters X Y Z Part1 Cryptography8 A5 1 Inthisexample m maj x8 y10 z10 maj 1 0 1 1RegisterXsteps Ydoesnotstep andZstepsKeystreambitisXORofrightbitsofregistersHere keystreambitwillbe0 1 0 1 X Y Z Part1 Cryptography9 ShiftRegisterCrypto ShiftregistercryptoefficientinhardwareOften slowifimplementinsoftwareInthepast verypopularToday moreisdoneinsoftwareduetofastprocessorsShiftregistercryptostillusedsomeResource constraineddevices Part1 Cryptography10 RC4 Aself modifyinglookuptableTablealwayscontainsapermutationofthebytevalues0 1 255InitializethepermutationusingkeyAteachstep RC4doesthefollowingSwapselementsincurrentlookuptableSelectsakeystreambytefromtableEachstepofRC4producesabyteEfficientinsoftwareEachstepofA5 1producesonlyabitEfficientinhardware Part1 Cryptography11 RC4Initialization S i ispermutationof0 1 255key i containsNbytesofkeyfori 0to255S i iK i key i modN nextij 0fori 0to255j j S i K i mod256swap S i S j nextii j 0 Part1 Cryptography12 RC4Keystream Foreachkeystreambyte swapelementsintableandselectbytei i 1 mod256j j S i mod256swap S i S j t S i S j mod256keystreamByte S t Usekeystreambyteslikeaone timepadNote first256bytesshouldbediscardedOtherwise relatedkeyattackexists Part1 Cryptography13 StreamCiphers StreamcipherswerepopularinthepastEfficientinhardwareSpeedwasneededtokeepupwithvoice etc Today processorsarefast sosoftware basedcryptoisusuallymorethanfastenoughFutureofstreamciphers Shamirdeclared thedeathofstreamciphers Maybegreatlyexaggerated Part1 Cryptography14 BlockCiphers Part1 Cryptography15 Iterated BlockCipher Plaintextandciphertextconsistoffixed sizedblocksCiphertextobtainedfromplaintextbyiteratingaroundfunctionInputtoroundfunctionconsistsofkeyandoutputofpreviousroundUsuallyimplementedinsoftware Part1 Cryptography16 FeistelCipher Encryption Feistelcipherisatypeofblockcipher notaspecificblockcipherSplitplaintextblockintoleftandrighthalves P L0 R0 Foreachroundi 1 2 n computeLi Ri 1Ri Li 1 F Ri 1 Ki whereFisroundfunctionandKiissubkeyCiphertext C Ln Rn Part1 Cryptography17 FeistelCipher Decryption StartwithciphertextC Ln Rn Foreachroundi n n 1 1 computeRi 1 LiLi 1 Ri F Ri 1 Ki whereFisroundfunctionandKiissubkeyPlaintext P L0 R0 Formula works foranyfunctionFButonlysecureforcertainfunctionsF Part1 Cryptography18 DataEncryptionStandard DESdevelopedin1970 sBasedonIBM sLucifercipherDESwasU S governmentstandardDESdevelopmentwascontroversialNSAsecretlyinvolvedDesignprocesswassecretKeylengthreducedfrom128to56bitsSubtlechangestoLuciferalgorithm Part1 Cryptography19 DESNumerology DESisaFeistelcipherwith 64bitblocklength56bitkeylength16rounds48bitsofkeyusedeachround subkey Eachroundissimple forablockcipher Securitydependsheavilyon S boxes EachS boxesmaps6bitsto4bits Part1 Cryptography20 Li 1 L R Ri 1 expand shift shift key key S boxes compress Li R Ri 28 28 28 28 28 28 48 32 48 32 32 32 32 OneRoundofDES 48 32 Ki Pbox Li Ri 1Ri Li 1 F Ri 1 Ki P L0 R0 Part1 Cryptography21 DESExpansionPermutation Input32bits012345678910111213141516171819202122232425262728293031Output48bits310123434567878910111211121314151615161718192019202122232423242526272827282930310 Part1 Cryptography22 DESS box 8 substitutionboxes orS boxesEachS boxmaps6bitsto4bitsS boxnumber1inputbits 0 5 inputbits 1 2 3 4 0000000100100011010001010110011110001001101010111100110111101111001110010011010001001011111011100000111010011011000101100100000111010000111101110100111000101101000110100110110010111001010100111000100100000111101000110101100010101111111100100101110011101001010000111111110010000010010010010001011101011011001111101010000001101101 101010 0110 Part1 Cryptography23 DESP box Input32bits012345678910111213141516171819202122232425262728293031Output32bits156192028112716014222541730917231331262818122952110324 Part1 Cryptography24 DESSubkey 56bitDESkey numbered0 1 2 55Lefthalfkeybits LK49423528211470504336292215815144373023169252453831Righthalfkeybits RK5548413427201365447403326191255346393225181142417103 Part1 Cryptography25 DESSubkey Forroundsi 1 2 16LetLK LKcircularshiftleftbyri LetRK RKcircularshiftleftbyri LefthalfofsubkeyKiisofLKbits131610230422714520922181132571562619121RighthalfofsubkeyKiisRKbits1223281826111221641915201027524171321703 Part1 Cryptography26 DESSubkey Forrounds1 2 9and16theshiftriis1 andinallotherroundsriis2Bits8 17 21 24ofLKomittedeachroundBits6 9 14 25ofRKomittedeachroundCompressionpermutationyields48bitsubkeyKifrom56bitsofLKandRKKeyschedulegeneratessubkey Part1 Cryptography27 DESLastWord Almost Aninitialpermutationbeforeround1HalvesareswappedafterlastroundAfinalpermutation inverseofinitialperm appliedto R16 L16 Noneofthisservessecuritypurpose Part1 Cryptography28 Li 1 Ri 1 expand shift shift key key S boxes compress Li Ri 28 28 28 28 28 28 48 32 48 32 32 32 32 OneRoundofDES 48 32 Ki Pbox Li Ri 1Ri Li 1 F Ri 1 Ki P L0 R0 Part1 Cryptography29 SecurityofDES SecuritydependsheavilyonS boxesEverythingelseinDESislinearThirty yearsofintenseanalysishasrevealedno backdoor Attacks essentiallyexhaustivekeysearchInescapableconclusionsDesignersofDESknewwhattheyweredoingDesignersofDESwerewayaheadoftheirtime Part1 Cryptography30 BlockCipherNotation P plaintextblockC ciphertextblockEncryptPwithkeyKtogetciphertextCC E P K DecryptCwithkeyKtogetplaintextPP D C K Note P D E P K K andC E D C K K ButP D E P K1 K2 andC E D C K1 K2 whenK1 K2 Part1 Cryptography31 TripleDES Today 56bitDESkeyistoosmallExhaustivekeysearchisfeasibleButDESiseverywhere sowhattodo TripleDESor3DES 112bitkey C E D E P K1 K2 K1 P D E D C K1 K2 K1 WhyEncrypt Decrypt Encryptwith2keys Backwardcompatible E D E P K K K E P K And112bitsisenough Part1 Cryptography32 3DES WhynotC E E P K K Trickquestion it sstilljust56bitkeyWhynotC E E P K1 K2 A semi practical knownplaintextattackPre computetableofE P K1 foreverypossiblekeyK1 resultingtablehas256entries ThenforeachpossibleK2computeD C K2 untilamatchintableisfoundWhenmatchisfound haveE P K1 D C K2 Resultgivesuskeys C E E P K1 K2 Part1 Cryptography33 BlockCipherModes Part1 Cryptography34 MultipleBlocks Howtoencryptmultipleblocks Doweneedanewkeyforeachblock Asbadas orworsethan aone timepad Encrypteachblockindependently Makeencryptiondependonpreviousblock Thatis canwe chain theblockstogether Howtohandlepartialblocks Wewon tdiscussthisissue Part1 Cryptography35 ModesofOperation Manymodes wediscuss3mostpopularElectronicCodebook ECB modeEncrypteachblockindependentlyMostobvious buthasaseriousweaknessCipherBlockChaining CBC modeChaintheblockstogetherMoresecurethanECB virtuallynoextraworkCounterMode CTR modeBlockciphersactslikeastreamcipherPopularforrandomaccess Part1 Cryptography36 ECBMode Notation C E P K GivenplaintextP0 P1 Pm Mostobviouswaytouseablockcipher EncryptDecryptC0 E P0 K P0 D C0 K C1 E P1 K P1 D C1 K C2 E P2 K P2 D C2 K ForfixedkeyK thisis electronic versionofacodebookcipher withoutadditive Withadifferentcodebookforeachkey Part1 Cryptography37 ECBCutandPaste SupposeplaintextisAlicedigsBob TrudydigsTom Assuming64 bitblocksand8 bitASCII P0 Alicedi P1 gsBob P2 Trudydi P3 gsTom Ciphertext C0 C1 C2 C3Trudycutsandpastes C0 C3 C2 C1DecryptsasAlicedigsTom TrudydigsBob Part1 Cryptography38 ECBWeakness SupposePi PjThenCi CjandTrudyknowsPi PjThisgivesTrudysomeinformation evenifshedoesnotknowPiorPjTrudymightknowPiIsthisaseriousissue Part1 Cryptography39 AliceHatesECBMode Alice suncompressedimage andECBencrypted TEA Whydoesthishappen Sameplaintextyieldssameciphertext Part1 Cryptography40 CBCMode Blocksare chained togetherArandominitializationvector orIV isrequiredtoinitializeCBCmodeIVisrandom butnotsecretEncryptionDecryptionC0 E IV P0 K P0 IV D C0 K C1 E C0 P1 K P1 C0 D C1 K C2 E C1 P2 K P2 C1 D C2 K Analogoustoclassiccodebookwithadditive Part1 Cryptography41 CBCMode Identicalplaintextblocksyielddifferentciphertextblocks thisisgood IfC1isgarbledto say GthenP1 C0 D G K P2 G D C2 K ButP3 C2 D C3 K P4 C3 D C4 K Automaticallyrecoversfromerrors Cutandpasteisstillpossible butmorecomplex andwillcausegarbles Part1 Cryptography42 AliceLikesCBCMode Alice suncompressedimage AliceCBCencrypted TEA Whydoesthishappen Sameplaintextyieldsdifferentciphertext Part1 Cryptography43 CounterMode CTR CTRispopularforrandomaccessUseblockcipherlikeastreamcipherEncryptionDecryptionC0 P0 E IV K P0 C0 E IV K C1 P1 E IV 1 K P1 C1 E IV 1 K C2 P2 E IV 2 K P2 C2 E IV 2 K CBCcanalsobeusedforrandomaccessWithasignificantlimitation Part1 Cryptography44 Integrity Part1 Cryptography45 DataIntegrity Integrity detectunauthorizedwriting i e modificationofdata Example Inter bankfundtransfersConfidentialitymaybenice integrityiscriticalEncryptionprovidesconfidentiality preventsunauthorizeddisclosure EncryptionalonedoesnotprovideintegrityOne timepad ECBcut and paste etc Part1 Cryptography46 MAC MessageAuthenticationCode MAC UsedfordataintegrityIntegritynotthesameasconfidentialityMACiscomputedasCBCresidueThatis computeCBCencryption savingonlyfinalciphertextblock theMAC Part1 Cryptography47 MACC