Modes of Operation Raj Jain Washington University in Saint Louis Saint Louis MO 63130 Jain cse wustl edu Audio Video recordings of this lecture are available at http www cse wustl edu jain cse567 06 Washington University in St Louis CSE571S 6 1 2007 Raj Jain Overview 1 2 3 4 Modes of Operation ECB CBC OFB CFB CTR Privacy Integrity DES Attacks 3DES and its design Ref Chapter 4 of textbook Washington University in St Louis CSE571S 6 2 2007 Raj Jain Modes of Operation 1 2 3 4 5 Electronic Code Book ECB Cipher Block Chaining CBC Cipher Feedback Mode CFB Output Feedback Mode OFB Counter Mode CTR Washington University in St Louis CSE571S 6 3 2007 Raj Jain 1 Electronic Code Book ECB Each block is independently encoded Problem Identical Input Identical Output Can insert encoded blocks Washington University in St Louis CSE571S 6 4 2007 Raj Jain Cipher Block Chaining CBC Add a random number before encoding Washington University in St Louis CSE571S 6 5 2007 Raj Jain CBC Cont Use Ci as random number for i 1 Need Initial Value IV If no IV then one can guess changed blocks Example Continue Holding Start Bombing Washington University in St Louis CSE571S 6 6 2007 Raj Jain CBC Cont Attack 1 Change selected bits in encrypted message Garbled text not detected by computers Attack 2 Attacker knows plain text and cipher text Can change plain text 32 bit CRC may not detect 64 bit CRC may be better Washington University in St Louis CSE571S 6 7 2007 Raj Jain k Bit Output Feedback Mode OFB IV is used to generate a stream of blocks Stream is used a one time pad and XOR ed to plain text Washington University in St Louis CSE571S 6 8 2007 Raj Jain OFB Cont Advantages Stream can be generated in advance 1 bit error in transmission affects only one bit of plain text Message can be any size All messages are immediately transmitted Disadvantage Plain text can be trivially modified Only left most k bits of the block can be used Washington University in St Louis CSE571S 6 9 2007 Raj Jain k Bit Cipher Feedback Mode CFB Key Stream blocks use previous block as IV k bits of encoded streams are used to generate next block Washington University in St Louis CSE571S 6 10 2007 Raj Jain CFB Cont Stream cannot be generated in advance In practice k 8 bit or 64 bit If a byte is added or deleted that byte and next 8 bytes will be affected No block rearranging effect Washington University in St Louis CSE571S 6 11 2007 Raj Jain Counter Mode CTR If the same IV and key is used again Xor of two encrypted messages Xor of plain text IV is incremented and used to generated one time pad Advantage Pre computed Washington University in St Louis CSE571S 6 12 2007 Raj Jain Message Authentication Code MAC Cryptographic checksum or Message Integrity Code MIC CBC residue is sent with plain text Washington University in St Louis CSE571S 6 13 2007 Raj Jain Weak and Semi Weak Keys Recall that 56 bit DES key is divided in two halves and permuted to produce C0 and D0 Keys are weak if C0 and D0 after permutation result in All 0 s All 1 s Alternating 10 or 01 Four possibilities for each half 16 week keys Washington University in St Louis CSE571S 6 14 2007 Raj Jain Privacy Integrity Can t send encrypted message and CBC residue 1 Use strong CRC 2 Use CBC residue with another key The 2nd CBC can be weak as in Kerberos Kerberos uses K F0F0 F0F0 as the 2nd key Washington University in St Louis CSE571S 6 15 2007 Raj Jain Privacy Integrity Cont 3 Use hash with another key Faster than encryption 4 Use Offset Code Book OCB http www cs ucdavis edu rogaway papers draftkrovetz ocb 00 txt Washington University in St Louis CSE571S 6 16 2007 Raj Jain MISTY1 Block cipher with 128 bit keys With 4 to 8 rounds Each round consists of 3 subrounds Secure against linear and differential cryptanalysis Named after the inventors Matsui Mitsuru Ichikawa Tetsuya Sorimachi Toru Tokita Toshio and Yamagishi Atsuhiro A k a Mitsubishi Improved Security Technology Recommended for Japanese government use Patented Described in RFC 2994 Ref http en wikipedia org wiki MISTY1 Washington University in St Louis CSE571S 6 17 2007 Raj Jain KASUMI Selected by 3GPP 64 bit block cipher with 128 bit key A variant of MISTY1 Needs limited computing power Works in real time voice KASUMI with counter mode and output feedback modes This algorithm is known as f8 Washington University in St Louis CSE571S 6 18 2007 Raj Jain GSM Encryption Three stream ciphers A5 1 A5 2 A5 3 Description of A5 1 and A5 2 were never released to public but were reverse engineered and broken A5 3 is based KASUMI Washington University in St Louis CSE571S 6 19 2007 Raj Jain DES Attacks 1997 RSA Lab set a prize of 10k Curtin and Dolske used combined power of Internet computers to find the key using a brute force method 1998 Electronic Frontier Foundation EFF showed that a 250k machine could find any DES key in max 1 week Avg 3 days 2001 EFF combined the cracker with Internet to crack DES in 1 day Differential Cryptanalysis and Linear cryptanalysis can be used to crack DES NIST recommended 3DES Washington University in St Louis CSE571S 6 20 2007 Raj Jain 3DES c ek1 dk2 ek3 m m dk3 ek2 dk1 c k1 and k2 should be independent but k3 can be independent or k3 k1 k3 k1 results in 112 bit strength Washington University in St Louis CSE571S 6 21 2007 Raj Jain CBC Outside vs Inside Washington University in St Louis CSE571S 6 22 2007 Raj Jain CBC Outside vs Inside Cont Washington University in St Louis CSE571S 6 23 2007 Raj Jain Key 3DES Design Decisions 1 3 stages 2 Two keys 3 E D E 4 CBC Outside Washington University in St Louis CSE571S 6 24 2007 Raj Jain 1 Why not 2DES ek1 ek2 m 2DES is only twice as secure as DES 57 bit key Suppose you know m1 c1 m2 c2 c1 ek1 ek2 m1 dk1 c1 ek2 m1 k1 and k2 can be found by preparing two 2 56 entry tables Table 1 contains all possible encryptions of m1 Table 2 contains all possible decryptions of c1 Sort both tables Find matching entries potential k1 k2 pairs Try these pairs on m2 c2 Washington University in St Louis CSE571S 6 25 2007 Raj Jain 2 Why Only Two Keys k3 k1 is as secure as k3 k1 Given m c pairs it is easy to find 3 keys such that ek1 dk2 ek3 m r But finding the keys when k3 k1 is difficult Washington University in St Louis CSE571S 6 26 2007 Raj Jain 3 Why E D E and not E E E E and D are both equally strong encryptions With k1 k2 EDE E a 3DES system can talk to …