CryptographyResearch OpportunitiesOverviewReadingsDefinitionsWarning!Historical CiphersCaesar CipherAttacksFrequency analysisBrute forceVigenere cipherVigenere analysisVigenere Analysisn-gram analysisSubstitution cipherPermutation CipherModern CiphersEnigma cryptanalysisData Encryption Standard (DES)Feistel Network“F” of DESDES CriticismDifferential CryptanalysisChosen PlaintextKey sizeTriple-DESAES contestAES CriteriaAES Selection ProcessAES FinalistsAES winnerDES and AES reduxMidterm StatisticsMessage SizeElectronic Code BookPlaintextCiphertextRandomized EncryptionCipher Block Chaining (CBC)CBC DiagramCBC DecryptionCipher Block ChainingPropagating CBCCiphertext Feedback ModeCFB diagramCFB decryptionCFBOutput FeedbackOFB diagramOFB propertiesStream CiphersLFSRsLFSR-based stream ciphersRC4Slide 56Stream cipher concernsCounter ModeOne-Time PadsFor exams & homeworksCryptographyCS461 - Spring 2007Nikita BorisovResearch Opportunities•Information Trust Institute undergraduate research internship programhttp://www.iti.uiuc.edu/iti_funding_opportunities.htmlApply by March 5Overview•Introduction to cryptography and cryptanalysis•Historical ciphers•DES and AES•Stream ciphers and cipher modesReadings•Ch. 9 of textbook•“Applied Cryptography” by Bruce SchneierAccessible description of cryptographic primitives•“Handbook of Applied Cryptography” by Menezes, van Oorschot, VanstoneDense, makes a good referenceAvailable online•http://www.cacr.math.uwaterloo.ca/hac/Definitions•CryptosystemTransforms plaintext into ciphertext using a keyciphertext unintelligible without knowledge of key•CryptographyCryptology (design of cryptosystems) +cryptanalysis (study of cryptosystems)•Always go hand in handWarning!•“A little knowledge is a dangerous thing”Very true in cryptographyHistorical Ciphers•Caesar cipherCaesar Cipher•More formally:Encrypt(Letter, Key) = (Letter + Key) (mod 26)Decrypt(Letter, Key) = (Letter - Key) (mod 26)•Encrypt(“NIKITA”, 3) = “QLNLWD”•Decrypt(“QLNLWD”, 3) = “NIKITA”Attacks•Ciphertext only attack:Recover plaintext knowing only the ciphertext•Ciphertext:HSPAA SLRUV DSLKN LPZHK HUNLY VBZAO PUNFrequency analysisHSPAA SLRUV DSLKN LPZHK HUNLY VBZAO PUN•Find most frequent letters4 times: L3 times: A, H, N, P, S, U•Guess: Decrypt(L) = EKey = L-E = 7Decrypt(HSPAA SLRUV DSLKN LPZHK HUNLY VBZAO PUN, 7) = ALITT LEKNO WLEDG EISAD ANGER OUSTH INGBrute force•Ciphertext = IGKYGXOYOTYKIAXKDecrypt(IGKYGXOYOTYKIAXK, 1) = HFJXFWNXNSXJHZWJDecrypt(IGKYGXOYOTYKIAXK, 2) = GEIWEVMWMRWIGYVIDecrypt(IGKYGXOYOTYKIAXK, 3) = FDHVDULVLQVHFXUHDecrypt(IGKYGXOYOTYKIAXK, 4) = ECGUCTKUKPUGEWTGDecrypt(IGKYGXOYOTYKIAXK, 5) = DBFTBSJTJOTFDVSFDecrypt(IGKYGXOYOTYKIAXK, 6) = CAESARISINSECUREVigenere cipher•A different caesar cipher per letter MORESECURETHANCAESAR (Ciphertext)+ SECRETSECRETSECRETSE (Key)= FTUWXYVZUWYBTSFSJMTWM (13) + A (19) = F (6) mod 26O (15) + E (5) = T (20) mod 26...Vigenere analysis•Key space?26Length(Key)10-20 characters to prevent brute force on modern computers•Frequency analysis?Doesn’t work because of different keysVigenere Analysis•Guess period = p•Construct p frequency tablesCryptanalyze each onehttp://math.ucsd.edu/~crypto/java/EARLYCIPHERS/Vigenere.html•Better yet, recover periodLook for repeated n-gramsn-gram analysis•JBEDH WKDIT ZVIRR FEVYJ VSNTY BWTEG MLGMT QNIFG LRIIN KAIXQ GEZLX YUXEC TCZDG OMBRX IOPGH WVQJL RRIIJ SPVLE DEPEW HVYYM SYBTR DXHZM WIUNU IGAYQ NHRIT VDMTY XRKXY PCTCV HJRFV IJIMA MXWLF GEJLECTC: 59, 136 (7, 11)ED: 89, 2 (87)FG: 38, 154 (2, 4, 29)GM: 29, 32 (3)HW: 4, 74 (2,5,7)II: 82, 42 (2, 4, 8, 5)IJ: 145, 83 (2, 31)IT: 123, 8 (5, 23)JL: 157, 78 (79)LE: 158, 88 (2, 5, 7)YB: 101, 24 (7, 11)LR: 40, 79 (3,13)MT: 33, 127 (2, 47)RF: 14, 142 (2, 4, .., 128)RII: 81, 41 (2, 4, 8, 5)RI: 41,81,122 (1)RR: 13, 80 (67)TC: 137, 60 (7, 11)TY: 23, 128 (3, 5, 7)VI: 11, 144 (7, 19)VY: 17, 96 (79)XY: 133, 54 (79)Substitution cipher•Each letter gets mapped to another letterE.g. A -> E, B -> R, C -> Q, ...•What’s the key space?26!•Cryptogram puzzles in newspapersHow do you solve them?Permutation Cipher•Rearrange letters instead of substituting them•E.g.Plaintext = “HELLO WORLD” H W E O L R L L O DCiphertext = “HWEOLRLLOD”Modern Ciphers•EnigmaMachine to encrypt German communications in WWIIConsisted of plug board, 3 rotors, and reflector boardEach implemented a substitutionRotors shifted after each letter, so like Vigenere, but with period of about 16,900Enigma cryptanalysis•Brute force out of the question1023 keys if plugboard is known, or 10114 if unknown•Known plaintext attackLearn (or guess) part of plaintext, decrypt the restHow to obtain plaintext?•“Nothing to report” is a common one•“eins” (1) appeared in 90% of messages•Set up mines in some area, look for reports•Bombe, designed by Alan TuringAutomated cryptanalysis based on known plaintext and frequency analysis testsData Encryption Standard (DES)•Designed at IBM in 1975Based on Lucifer designed by Feistel and CoppersmithChanges suggested by the NSA•Standardized by NIST in 1977Official cipher for civilian cryptographyReviewed by the NSA•Combines substitutions and permutationsOperates on bitsFeistel Network•Iterative structure•Efficient hardware implementation•Non-linear element F provides security•Multiple rounds provide mixing (diffusion) between the two halves“F” of DESDES Criticism•NSA involvement in DES design was criticized•Allegedly, they:Made it deliberately weaker (56-bit keys)Modified S-boxes•Idea is that the NSA made DES easy for them to break, but not everyone elseDifferential Cryptanalysis•Invented in 1990 by Shamir and Biham•Linear encryption:E(P xor ∆) = E(P) xor E(∆)•Non-linear element (S-boxes) designed to prevent this•Differential characteristicE(P xor ∆) = E(P) xor ∆’ with “high” probabilityObtain many pairs E(P xor ∆) and E(P)Look for statistical patterns, recover keyChosen Plaintext•Chosen plaintext attackFind encryption of particular plaintext (pairs in this case), use it to recover key / decrypt other messagesIs this a practical attack?•Not practical for DES247 chosen plaintexts required!S-boxes were found to specifically resist differential attacksKey
View Full Document