6-1©2007 Raj JainCSE571SWashington University in St. LouisModes of Modes of OperationOperationRaj Jain Washington University in Saint LouisSaint Louis, MO [email protected]/Video recordings of this lecture are available at :http://www.cse.wustl.edu/~jain/cse567-06/6-2©2007 Raj JainCSE571SWashington University in St. LouisOverviewOverview1. Modes of Operation: ECB, CBC, OFB, CFB, CTR2. Privacy+Integrity3. DES Attacks4. 3DES and its designRef: Chapter 4 of textbook.6-3©2007 Raj JainCSE571SWashington University in St. LouisModes of OperationModes of Operation1. Electronic Code Book (ECB)2. Cipher Block Chaining (CBC)3. Cipher Feedback Mode (CFB)4. Output Feedback Mode (OFB)5. Counter Mode (CTR)6-4©2007 Raj JainCSE571SWashington University in St. Louis1. Electronic Code Book (ECB)1. Electronic Code Book (ECB)! Each block is independently encoded! Problem:" Identical Input ⇒ Identical Output" Can insert encoded blocks6-5©2007 Raj JainCSE571SWashington University in St. LouisCipher Block Chaining (CBC)Cipher Block Chaining (CBC)! Add a random number before encoding6-6©2007 Raj JainCSE571SWashington University in St. LouisCBC (Cont)CBC (Cont)! Use Cias random number for i+1! Need Initial Value (IV)! If no IV, then one can guess changed blocks! Example: Continue Holding, Start Bombing6-7©2007 Raj JainCSE571SWashington University in St. LouisCBC (Cont)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.6-8©2007 Raj JainCSE571SWashington University in St. Louiskk--Bit Output Feedback Mode (OFB)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 text6-9©2007 Raj JainCSE571SWashington University in St. LouisOFB (Cont)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 used6-10©2007 Raj JainCSE571SWashington University in St. Louiskk--Bit Cipher Feedback Mode (CFB)Bit Cipher Feedback Mode (CFB)! Key Stream blocks use previous block as IV! k-bits of encoded streams are used to generate next block6-11©2007 Raj JainCSE571SWashington University in St. LouisCFB (Cont)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 effect6-12©2007 Raj JainCSE571SWashington University in St. LouisCounter Mode (CTR)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-computed6-13©2007 Raj JainCSE571SWashington University in St. LouisMessage Authentication Code (MAC)Message Authentication Code (MAC)! Cryptographic checksum or Message Integrity Code (MIC)! CBC residue is sent with plain text6-14©2007 Raj JainCSE571SWashington University in St. LouisWeak and SemiWeak and Semi--Weak KeysWeak 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 keys6-15©2007 Raj JainCSE571SWashington University in St. LouisPrivacy + IntegrityPrivacy + Integrity! Can't send encrypted message and CBC residue.1. Use strong CRC2. Use CBC residue with another key." The 2nd CBC can be weak, as in Kerberos." Kerberos uses K+F0F0…F0F0 as the 2nd key.6-16©2007 Raj JainCSE571SWashington University in St. LouisPrivacy + Integrity (Cont)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/draft-krovetz-ocb-00.txt6-17©2007 Raj JainCSE571SWashington University in St. LouisMISTY1MISTY1! Block cipher with 128 bit keys! With 4 to 8 rounds. Each round consists of 3 sub-rounds.! 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/MISTY16-18©2007 Raj JainCSE571SWashington University in St. LouisKASUMIKASUMI! 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.6-19©2007 Raj JainCSE571SWashington University in St. LouisGSM EncryptionGSM 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 KASUMI6-20©2007 Raj JainCSE571SWashington University in St. LouisDES AttacksDES 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 3DES6-21©2007 Raj JainCSE571SWashington University in St. Louis3DES3DES! 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 strength6-22©2007 Raj JainCSE571SWashington University in St. LouisCBC: Outside vs. InsideCBC: Outside vs. Inside6-23©2007 Raj JainCSE571SWashington University in St. LouisCBC: Outside vs. Inside (Cont)CBC: Outside vs. Inside (Cont)6-24©2007 Raj JainCSE571SWashington University in St. LouisKey 3DES Design DecisionsKey 3DES Design Decisions1. 3 stages2. Two keys3. E-D-E4. CBC Outside6-25©2007 Raj JainCSE571SWashington University in St. Louis1. Why not 2DES?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!