Lecture 4 Striving for Confusion Structures have been found in DES that were undoubtedly inserted to strengthen the system against certain types of attack Structures have also been found that appear to weaken the system Lexar Corporation An Evalution of the DES 1976 CS588 Security and Privacy University of Virginia Computer Science David Evans http www cs virginia edu evans Menu Projects Enigma Continued Block Ciphers 10 Sept 2001 University of Virginia CS 588 2 Operation Day key distributed in code book Each message begins with message key randomly choosen by sender encoded using day key Message key sent twice to check After receiving message key re orient rotors according to key 10 Sept 2001 University of Virginia CS 588 3 Letter Permutations Symmetry of Enigma if Epos x y we know Epos y x Given message openings DMQ VBM E1 m1 D E4 m1 V VON PUY E1 m2 V E4 m2 P PUC FMQ With enough message openings we can build complete cycles for each position pair E1E4 DVPFKXGZYO EIJMUNQLHT BC RW A S Note Cycles must come in pairs of equal length Examples in Code Book had pairs of unequal length 10 Sept 2001 University of Virginia CS 588 4 Composing Involutions E1 and E4 are involutions x y y x Without loss of generality we can write E1 contains a1a2 a3a4 a2k 1a2k E2 contains a2a3 a4a5 a2ka1 E1 E2 a1 a2 a2 x a3 or x a1 a3 a4 a4 x a5 or x a1 10 Sept 2001 University of Virginia CS 588 5 Rejewski s Theorem E1 contains a1a2 a3a4 a2k 1a2k E4 contains a2a3 a4a5 a2ka1 E1E4 contains a1a3a5 a2k 1 a2ka2k 2 a4a2 The product of two involutions consists of pairs cycles of the same length For cycles of length n there are n possible factorizations 10 Sept 2001 University of Virginia CS 588 6 Factoring Permutations E1E4 DVPFKXGZYO EIJMUNQLHT BC RW A S A S AS o SA BC RW BR CW o BW CR or BW RC o WC BR 10 Sept 2001 University of Virginia CS 588 7 How many factorizations DVPFKXGZYO EIJMUNQLHT E1 E2 D a2 V a4 a2 V a4 P Once we guess a2 everything else must follow So only n possible factorizations for an n letter cycle Total to try 2 10 20 E2E5 and E3E6 likely to have about 20 to try also About 203 8000 factorizations to try still too many in pre computer days 10 Sept 2001 University of Virginia CS 588 8 Luckily Operators picked guessable message keys cillies Identical letters Easy to type e g QWE If we can guess P1 P2 P3 or known relationships can reduce number of possible factorizations If we re lucky this leads to E1 E6 10 Sept 2001 University of Virginia CS 588 9 1939 Early 1939 Germany changes scamblers and adds extra plugboard cables stop double transmissions Poland unable to cryptanalyze July 1939 Rejewski invites French and British cryptographers It is actually breakable Gives England replica Enigma machine constructed from plans 10 Sept 2001 University of Virginia CS 588 10 Bletchley Park Alan Turing leads British effort to crack Enigma Use cribs WETTER transmitted every day at 6am Still needed to brute force check 1M keys Built bombes to automate testing How many people worked on breaking Enigma 30 000 people worked at Bletchley Park on breaking Enigma 100 000 for Manhattan Project 10 Sept 2001 University of Virginia CS 588 11 Enigma Cryptanalysis Relied on combination of sheer brilliance mathematics espionage operator errors and hard work Huge impact on WWII Britain knew where German U boats were Advance notice of bombing raids But keeping code break secret more important than short term uses 10 Sept 2001 University of Virginia CS 588 12 End of classical ciphers A billion billion is a large number but it s not that large a number Whitfield Diffie 10 Sept 2001 University of Virginia CS 588 13 Goals of Cipher Diffusion and Confusion Claude Shannon 1945 Diffussion Small change in plaintext changes lots of ciphertext Statistical properties of plaintext hidden in ciphertext Confusion Statistical relationship between key and ciphertext as complex as possible So need to design functions that produce output that is diffuse and confused 10 Sept 2001 University of Virginia CS 588 14 Block Ciphers Stream Ciphers Encrypts small bit or byte units one at a time Block Ciphers Encrypts large chunks 64 bits at once Ciphers we have seen so far Changing one letter of message only changes one letter of ciphertext There were classical ciphers that had some diffusion Vigen re autokey Hill cipher 2 letter chunks 10 Sept 2001 University of Virginia CS 588 15 Ideal Block Cipher 64 bit blocks 264 possible plaintext blocks must have at least 264 corresponding ciphertext blocks There are 264 possible mappings Why not just create a random mapping Need a 264 64 bit table 1021 bits 14 quadrillion Need to distribute new table if compromised Approximate ideal random mapping using components controlled by a key 10 Sept 2001 University of Virginia CS 588 16 Feistel Cipher Structure Plaintext R0 Substitution L0 K1 Permutation Round L0 left half of plaintext R0 right half of plaintext F Li Ri 1 Ri Li 1 F Ri 1 Ki C Rn Ln L1 10 Sept 2001 n is number of rounds R1 undo last permutation 17 University of Virginia CS 588 One Round Feistel Li Ri 1 E L0 R0 Ri Li 1 F Ri 1 Ki L1 R0 R1 L0 F R0 K1 C R1 L1 L0 F R0 K1 R0 10 Sept 2001 University of Virginia CS 588 18 Ciphertext LD0 left half of ciphertext RD0 right half of ciphertext RD0 LD0 Substitution Decryption Kn LDi RDi 1 RDi LDi 1 F Permutation F RDi 1 Kn i 1 L1 R1 P RDn LDn n is number of rounds 10 Sept 2001 University of Virginia CS 588 19 Decryption LDi RDi 1 RDi LDi 1 F RDi 1 Kn i 1 D L0 F R0 K1 R0 LD0 L0 F R0 K1 RD0 R0 LD1 R0 RD1 LD0 F RD0 K1 L0 F R0 K1 F RD0 K1 L0 P RD1 LD1 L0 R0 Yippee 10 Sept 2001 University of Virginia CS 588 20 Multiple Rounds The entire round is a function fK L R R L F R K swap L R R L E swap swap fKr swap fKr 1 fK2 swap fK1 D fK1 swap fK2 fKr 1 swap fKr swap swap 10 Sept 2001 University of Virginia CS 588 21 Decryption swap fK swap fK L R swap fK swap R L F R K swap fK L F R K R swap R L F R K F R K swap R L L R So swap fK its own inverse 10 Sept 2001 University of Virginia CS 588 22 F What are the requirements on F For decryption to work none For security Hide patterns in plaintext Hide patterns in key Coming up with a good F is hard 10 Sept 2001 University of Virginia CS 588 23 DES NIST then NBS sought standard for data security 1973 IBM s Lucifer …