sec-02-crypto.pdf

Symmetric-Key Cryptography Vorlesung “Einführung in die IT-Sicherheit” Prof. Dr. Martin Johns Overview Topic of the unit Symmetric-key Cryptography Parts of the unit Part #1: Basics of cryptography Part #2: Classic ciphers Part #3: Block and stream ciphers Part #4: Block cipher modes Page 2 Cryptogr...

Symmetric-Key Cryptography Vorlesung “Einführung in die IT-Sicherheit” Prof. Dr. Martin Johns Overview Topic of the unit Symmetric-key Cryptography Parts of the unit Part #1: Basics of cryptography Part #2: Classic ciphers Part #3: Block and stream ciphers Part #4: Block cipher modes Page 2 Cryptography Cryptography (kryptos: secret; graphein: writing) Art and science of keeping information secure Protection of con dentiality and integrity Cryptanalysis = study of attacks against cryptography Steganography (steganos: covered; graphein: writing) Art and science of hiding information Deniability and unobservability of communication fi Page 3 Examples Cryptography Steganography Message encrypted using the Enigma during WW2 Hidden message from the classic series “Heroes” Page 4 Cryptosystems KE M Alice E KD C D Encryption M Decryption C? Attacker Cryptographic system for en/decrypting messages M = plaintext message C = ciphertext message KE = encryption key KD = decryption key Page 5 Bob More on Cryptosystems Cipher (encryption and decryption functions) Keyspace Set of possible values for the keys KE and KD Symmetric-key cryptography E(M, KE) = C and D(C, KD) = M KE = KD (Sender and receiver use the same key K) Public-key cryptography ← next lecture KE ≠ KD (Public key KE and private key KD) Page 6 Confusion and Di usion What makes a cryptographic cipher strong? That’s a di cult question … Confusion property Complex relation between key and plaintext/ciphertext Getting K from M and C should be hard Di usion property Complex relation between plaintext and ciphertext Getting M from C should be hard ff ffi ff Page 7 Kerckho s’s Principle Assume that the cipher is known to the attacker Security should depend on the key only (no obscurity) What makes a cryptographic key strong? Set of possible keys (keyspace) very large Testing all keys of a simple cipher (Brute-force attack) Page 8 ff Kerckho s’s Principle ff Key size My Laptop 1 Million Cores 32 bit 6 seconds 0 seconds 64 bit 850 years 7 hours 128 bit 1022 years 1016 years 256 bit 1059 years 1052 years Some Attack Types Classic attack types of cryptanalysis Ciphertext-only attack Attacks involving only ciphertext messages C Known-plaintext and chosen-plaintext attack Attacks involving known/chosen plaintext M for C Not so subtle attack types Brute-force attack Guessing of all possible keys K from the keyspace Purchase-key attack Attacks involving blackmailing, theft and bribery Page 9 Estimating Risk Model of attacker using resources Unconditionally secure (also: absolute security) unbreakable with in nite resources and all possible attacks Computationally secure (also: practical security) unbreakable with available resources and known attacks Risk trade-o : attack costs vs. possible pro t Page 10 fi Security level of a cryptosystem fi Computation power, data complexity and time ff Overview Topic of the unit Symmetric-key Cryptography Parts of the unit Part #1: Basics of cryptography Part #2: Classic ciphers Part #3: Block and stream ciphers Part #4: Block cipher modes Page 11 Ancient Ciphers Simple substitution ciphers Rotate alphabet by k characters Examples: Caesar cipher, ROT13 Keyspace ridiculously small Monoalphabetic substitution ciphers Permute characters of alphabet Keyspace signi cantly larger Character frequencies are preserved Page 12 fi (Fig. from cryptomuseum.com) Vigenère Cipher Popular polyalphabetic substitution cipher Also known as “le chi re indéchi rable” ;-) Combination of multiple simple substitution ciphers Rotations determined by a word (key) Easy to break: Kasiski and Friedman tests Message T H I S A T E S T Running key K E Y K E Y K E Y +10 +4 +24 +10 +4 +24 +10 +4 +24 D L G C E R O W R Ciphertext ff Page 13 ff Vigenère Cipher Popular polyalphabetic substitution cipher Also known as “le chi re indéchi rable” ;-) Combination of multiple simple substitution ciphers Rotations determined by a word (key) Easy to break: Kasiski and Friedman tests Message T H I S A T E S T Running key K E Y K E Y K E Y +10 +4 +24 +10 +4 +24 +10 +4 +24 D L G C E R O W R Ciphertext Polyalphabetic ff Page 13 ff Period Rotor Machines Russian Rotor Machine M-125 (Fialka) Page 14 (Fig. from cryptomuseum.com) One-Time Pad XOR ciphers (Variant of Vigenère Cipher) E(M, K) = M ⊕ K = C D(C, K) = C ⊕ K = M Why does this work? M ⊕ (K ⊕ K) = M ⊕ 0 = M One-time pad = XOR cipher with constraints 1. Key length equals message length 2. Key bits are truly random (not pseudo-random) 3. Key is used only once and destroyed Page 15 Security of One-Time Pad Randomness and XOR Let K be a random bit with Pr(K = 1) = 0.5 For any bit M holds Pr(M ⊕ K = 1) = 0.5 E ect on security of one-time pad Given ciphertext C = M ⊕ K, each plaintext equally likely unconditionally secure (Shannon 1949) Example: C = 01 M = 00 for K = 01 M = 10 for K = 11 ff Page 16 M = 01 for K = 00 M = 11 for K = 10 One-Time Pad in Practice? Intelligence and military services Regular use during cold war Major problems Key exchange di cult True randomness required Not very practical today Inspiration for other methods, e.g. stream ciphers One-time pad as used by the Russian KGB Page 17 ffi Overview Topic of the unit Symmetric-key Cryptography Parts of the unit Part #1: Basics of cryptography Part #2: Classic ciphers Part #3: Block and stream ciphers Part #4: Block cipher modes Page 18 Modern Symmetric Ciphers Sophisticated design of substitutions and permutations Often round-based encryption and decryption algorithms Trade-o : security vs. e ciency and portability Common building blocks Substitution (S-Box) 0 0 1 00→10 01→11 11→00 10→01 0 Page 19 ffi Modern ciphers ff 1 0 Permutation (P-Box) 0 1 1 0 0 1 0 1 1 0 Example: Data Encryption Standard (DES) 16 Rounds 56 bit key used to generate 48 bit subkeys S-Box-based function f(x,y) DES'\'Funk9onsweise'(II) ' Li −1 ⊕ Li = Ri −1 Page 20 Ri −1 f ( Ri −1, K i ) Ri Block and Stream Ciphers Block ciphers Encryption and decryption of xed-size blocks Examples: AES, Serpent, Two sh, IDEA and DES M 0 1 0 1 0 1 … 0 C 1 1 1 0 0 0 0 0 1 … 1 Stream ciphers Encryption and decryption of bit streams Examples: RC4, A5/1, Rabbit and Salsa20 M 0 0 1 0 1 0 Page 21 fi 0 fi 1 0 … C 1 1 1 0 1 1 … Block Ciphers Block ciphers Encryption and decryption in blocks (e.g., 64 or 128 bit) Padding of short messages, splitting of long messages Di erent modes of operations: ECB, CBC, OFB, CTR,... Block M Encryption K C ff Page 22 k bits E Block Block C K k bits M D Block k bits Decryption k bits Example: Advanced Encryption Standard (AES) Standardized block cipher (also known as Rijndael) Developed by Belgian cryptographs Daemen and Rijmen Winner of public competition by NIST in 2000 Secure but also e cient in software and hardware Block cipher with 128 bit Substitution-permutation network (S-Box & P-Box) Key size: 128, 192 and 256 bits Rounds: 10, 12 and 14 depending on key size So far only impractical attacks known against AES Page 23 ffi Example: Advanced Encryption Standard (AES) Standardized block cipher (also known as Rijndael) Developed by Belgian cryptographs Daemen and Rijmen Winner of public competition by NIST in 2000 Secure but also e cient in software and hardware Block cipher with 128 bit Substitution-permutation network (S-Box & P-Box) Key size: 128, 192 and 256 bits Rounds: 10, 12 and 14 depending on key size # Python from Cryp to.Cipher aes = AES import AE.new(key, S A E S. M O DE_CBC, i crypt = a v) es.encryp t(msg) aes = AES.new(key, AES.MODE_ msg = aes CBC, iv).decrypt( crypt) So far only impractical attacks known against AES Page 23 ffi Stream ciphers Stream ciphers Bit-wise encryption and decryption of data Application of pseudo-random number generator (PRNG) Security usually dependent on quality of PRNG K Key stream … PRNG ⊕ Page 24 M Message stream … C Cipher stream … Example: RC4 Cipher Common stream cipher Developed by Ron Rivest for RSA Security Leaked to the public in 1994 (ARC4 = Alleged RC4) Cipher design Key size: 40 to 256 bits Key-scheduling algorithm initializing substitution S-box Keystream computed by swapping elements in S-box Some known weaknesses, e.g., in WEP implementation Page 25 Example: RC4 Cipher Common stream cipher Developed by Ron Rivest for RSA Security Leaked to the public in 1994 (ARC4 = Alleged RC4) Cipher design Key size: 40 to 256 bits Key-scheduling algorithm initializing substitution S-box Keystream computed by swapping elements in S-box # Python from Cryp to.Cipher import AR arc4 = AR C4 C 4. n e w ( key) crypt = a rc4.encry pt(msg) arc4 = AR C4.new(ke msg = arc y) 4.decrypt (crypt) Some known weaknesses, e.g., in WEP implementation Page 25 Further Ciphers Stream ciphers: GSM Standard A5/1 (1987) and A5/2 (1989) Block ciphers: AES contest nalists Serpent by R. Anderson, E. Biham and L. Knudsen (1998) Two sh by B. Schneier (1998) Stream ciphers: eSTREAM candidates Salsa20 by D. J. Bernstein (2004) … fi fi Page 26 Overview Topic of the unit Symmetric-key Cryptography Parts of the unit Part #1: Basics of cryptography Part #2: Classic ciphers Part #3: Block and stream ciphers Part #4: Block cipher modes Page 27 Electronic Code Book Mode: Electronic Code Book (ECB) Independent encryption and decryption of message blocks Simple and e cient (concurrent) implementation Vulnerable to known-plaintext and replay attacks Block1 M K C Page 28 ffi E Block1 Block2 K K E Block2 BlockN...... E BlockN Cipher-Block Chaining Mode: Cipher-Block Chaining (CBC) Chaining of cipher blocks using XOR operator (Largely) resistant against known-plaintext and replay attacks Block1 M IV ⊕ K E C Page 29 Block1 Block2... ⊕ K E Block2 BlockN... ⊕ K... E BlockN ECB vs CBC Original image ECB encryption Taken from Wikipedia: Block cipher modes of operation Page 30 CBC Encryption Counter Mode Mode: Counter Mode (CTR) Block cipher used as stream cipher Random access to blocks (synchronization) still possible Nonce K M Block1 C Page 31 Ctr+1 Nonce E ⊕ Block1 K Block2 Ctr+2... E ⊕... Block2 Nonce Ctr+N K BlockN... E ⊕ BlockN Summary Page 32 Summary Cryptography (“keeping information secure”) Encryption and decryption of messages Security should depend on key, not algorithm Symmetric-key cryptosystems Sender and receiver use same key Di erent cipher types (block and stream cipher) Mode of operation dependent on application ff Page 33