Network Security: Symmetric Encryption PDF

Network Security II. Symmetric Encryption Prof. Dr. Torsten Braun, Institut für Informatik Bern, 23.09.2024 – 30.09.2024 Network Security: Symmetric Encryption Network Security: Symmetric Encryption Table of Contents 1. Symmetric Encryption Attacks 2. Block and Stream Ciphers 3. Substi...

Network Security II. Symmetric Encryption Prof. Dr. Torsten Braun, Institut für Informatik Bern, 23.09.2024 – 30.09.2024 Network Security: Symmetric Encryption Network Security: Symmetric Encryption Table of Contents 1. Symmetric Encryption Attacks 2. Block and Stream Ciphers 3. Substitution Techniques 4. Advanced Encryption Standard 5. Block Ciphers 3  Network Security: Symmetric Encryption 1. Symmetric Encryption Attacks 1. Symmetric Encryption Operation − Sender and Receiver − Receiver decrypts data with exchange common secret key. secret key. − Sender encrypts data with − Example: secret key. Advanced Encryption Standard 5404 3214 5404 3214 5673 1023 5673 1023 valid 11/24 dfdj59058trekj9r7r93j32rjr9rruj2wed valid 11/24 4 Network Security: Symmetric Encryption 1. Symmetric Encryption Attacks 2. Cryptanalysis and Brute Force Attacks Cryptanalysis Brute Force Attack Cryptanalytic attacks rely on Attacker tries every possible key on a − nature of algorithm, piece of ciphertext until intelligible − some knowledge of general plaintext translation into plaintext is obtained. characteristics, and − some sample plaintext-ciphertext pairs. 5  Network Security: Symmetric Encryption 1. Symmetric Encryption Attacks 3. Attack Models and what is known to attacker − Ciphertext only − Chosen ciphertext − encryption algorithm − encryption algorithm − ciphertext to be decoded − ciphertext to be decoded − Known plaintext − encryption algorithm − ciphertext (chosen by cryptanalyst) − ciphertext to be decoded + corresponding plaintext − pairs of (plaintext, ciphertext) − Chosen text − Chosen plaintext − encryption algorithm − encryption algorithm − ciphertext to be decoded − ciphertext to be decoded − plaintext + corresponding ciphertext − plaintext (chosen by cryptanalyst) (both can be chosen by cryptanalyst) + corresponding ciphertext 6 Network Security: Symmetric Encryption 1. Symmetric Encryption Attacks 4.1 Chosen Plaintext Attack Informally: − An adversary selects two messages m0, m1. − Oracle picks random bit b and encrypts mb. − Adversary should not guess b with non-negligible probability. 7 Network Security: Symmetric Encryption 1. Symmetric Encryption Attacks 4.2 Chosen Plaintext Attack Indistinguishability CPA indistinguishability experiment PrivKcpa A,Π (n): A private-key encryption scheme Π = (Gen, Enc, Dec) 1. A key k is generated by running Gen(1n). has indistinguishable encryptions under a chosen-plaintext attack, or is CPA-secure, 2. Adversary A is given input 1 n and oracle if for all probabilistic polynomial-time adversaries A access to Enck(·), and outputs a pair of messages m0 and m1 of the same length. there is a negligible function negl such that 3. A uniform bit b ∈ {0, 1} is chosen, and then Pr(PrivKcpa A,Π (n) = 1) ≤ 1/2 + negl(n), a ciphertext c ← Enck(mb) is computed and given to A. where the probability is taken over the randomness 4. The adversary A continues to have oracle used by A, as well as the randomness used in the access to Enck(·), and outputs bit b’. experiment. 5. The output of the experiment is defined to be 1 if b’ = b, 0 otherwise. In the former case: “A succeeds”. 8 Network Security: Symmetric Encryption 2. Block and Stream Ciphers 1. Block Cipher Operation Plaintext Ciphertext (b bits) (b bits) Ciphertext Plaintext (b bits) (b bits) 9 Network Security: Symmetric Encryption 2. Block and Stream Ciphers 2. Substitution and Permutation Substitution Permutation − specifies for each of the 2k possible − Specifies for each of the k input bits, values of the input: the k-bit output. the output position to which it goes, e.g., − This would be impractical to build for − 1st bit → 13th bit of output 64-bit blocks, but would be feasible − 2nd bit → 61st bit of output with blocks of length of 8 bits. − … − To specify a completely randomly − Specification of a completely chosen substitution for k-bit blocks randomly chosen permutation would take about k·2k bits. of k bits would take k・log2k bits. 10  Network Security: Symmetric Encryption 2. Block and Stream Ciphers 3. Block Cipher Example 64 bit input 8 bits 8 bits 8 bits 8 bits 8 bits 8 bits 8 bits 8 bits Substitution functions S1 S2 S3 S4 S5 S6 S7 S8 derived from key 8 bits 8 bits 8 bits 8 bits 8 bits 8 bits 8 bits 8 bits 64 bit intermediate Permutation, possibly 64 bit output based on key 11  Network Security: Symmetric Encryption 2. Block and Stream Ciphers 4. Stream Cipher Operation Key stream Key stream generator generator Keystream (should not be repeated) Keystream Plain text + Cipher text + Plain text 12 Network Security: Symmetric Encryption 2. Block and Stream Ciphers 5. Stream Cipher Design Considerations − Encryption sequence should have a large period. − Properties of true random number generation, e.g., equal 0 and 1 bits − Long keys 13 Network Security: Symmetric Encryption 3. Substitution Techniques 1. Caesar Cipher − Each letter is replaced by the letter k places away. − C = E(k, p) = (p + k) mod 26 − p = D(k, C) = (C - k) mod 26 − k = 3: − Plain: abcdefghijklmnopqrstuvwyxz − Cipher: defghijklmnopqrstuvwyxzabc − Example − Plaintext: meet me after the toga party − Ciphertext: phhw ph diwhu wkh wrjd sduwb − Brute-Force Attack (25 keys !) 14 Network Security: Symmetric Encryption 3. Substitution Techniques 2. Monoalphabetic Ciphers Permutations If the cipher line (cf. Caesar cipher) − Finite set of elements with each can contain any permutation, element appears exactly once. then there are 26! > 4・1026 keys − {a, b, c}: 6 = 3! permutations: abc, acb, bac, bca, cab, cba − In general: n! permutations for a set of n elements 15  Network Security: Symmetric Encryption 3. Substitution Techniques 2.1 Monoalphabetic Ciphers: Cryptanalysis − P and Z are probably equivalent to e and t. − {S, U, O, M, H} have high frequencies and probably correspond to letters from {a, h, i, n, o, r, s}. − {A, B, G, Y, I, J} have low frequencies and probably correspond to {b, j, k, q, v, x, z}. − Most common digram is ZW → th, P → e 16 Network Security: Symmetric Encryption 3. Substitution Techniques 2.2 Monoalphabetic Ciphers: Cryptanalysis 17 Network Security: Symmetric Encryption 3. Substitution Techniques 3. Multiple Letter Ciphers: Playfair M O N A R C H Y B D − Use of a 5 x 5 matrix, e.g., for keyword monarchy E F G I/J K − Encryption of letter pairs, 26 x 26 = 676 digrams. L P Q S T − Encryption rules U V W X Z 1. Repeating letters in the same pair are separated by a filler letter, e.g., ba lx lo on 2. 2 plaintext letters in the same row are each replaced by the letter to the right, e.g., ar → RM 3. 2 plaintext letters in the same column are each replaced by the letter beneath, e.g., mu → CM 4. Otherwise, each plaintext letter in a pair is replaced by the letter that lies in its own row and the column occupied by the other plaintext letter, e.g., hs → BP, ea → JM 18 Network Security: Symmetric Encryption 3. Substitution Techniques plaintext 4. Polyalphabetic Ciphers − Use of several monoalphabetic ciphers − A key determines which mono-alphabetic substitution rule is used. − Vigenere cipher consists of key 26 Caesar ciphers with shifts 0-25. − Plaintext: ATTACKATDAWN − Key: LEMONLEMONLE − Ciphertext: LXFOPVEFRNHR 19 Network Security: Symmetric Encryption 3. Substitution Techniques 5. Relative Occurrence of Letters 20 Network Security: Symmetric Encryption 3. Substitution Techniques 6. One-Time Pads − One-time use of random key as long as message − Perfect security − Problems: − Making large quantities of truly random keys − Key distribution 21 Network Security: Symmetric Encryption 4. Advanced Encryption Standard 1. Overview Encryption Decryption 22 Network Security: Symmetric Encryption 4. Advanced Encryption Standard 2. Encryption Round 23 Network Security: Symmetric Encryption 4. Advanced Encryption Standard 3. Substitute Bytes S-Box 24 Network Security: Symmetric Encryption 4. Advanced Encryption Standard 4. Shift Rows 1. Row: no change 2. Row: 1 byte circular shift 3. Row: 2 byte circular shift 4. Row: 3 byte circular shift 25 Network Security: Symmetric Encryption 4. Advanced Encryption Standard 5. Mix Columns Forward matrix Inverse matrix 26 Network Security: Symmetric Encryption 4. Advanced Encryption Standard 6. Add Round Key 27 Network Security: Symmetric Encryption 4. Advanced Encryption Standard 7. Key Expansion 28 Network Security: Symmetric Encryption 5. Block Ciphers Design Criteria Modes of Operation − Overhead 1. Electronic Code Book − Secure transmission of single values − Error recovery and propagation 2. Cipher Block Chaining − Diffusion − General purpose block transmissions − how plaintext statistics are reflected in − Authentication ciphertext 3. Cipher FeedBack Mode − Security − General purpose stream transmission − Authentication − whether ciphertext blocks leak information about plaintext blocks 4. Output Feedback Mode − Stream-oriented transmission over noisy channels 5. CounTeR Mode − General purpose, high-speed block transmissions 29 Network Security: Symmetric Encryption 5. Block Ciphers 1.1 Electronic Code Book Encryption message m1 m2 m3 m4 m5 m6 m7 m8 c1 c2 c3 c4 c5 c6 c7 c8 30 Network Security: Symmetric Encryption 5. Block Ciphers 1.2 Electronic Code Book Decryption c1 c2 c3 c4 c5 c6 c7 c8 m1 m2 m3 m4 m5 m6 m7 m8 message 31 Network Security: Symmetric Encryption 5. Block Ciphers 1.3 Electronic Code Book Problems − If a message has two identical blocks: The corresponding two blocks of ciphertext are also identical. − This will give the eavesdropper at least some information, which is useful depending on the context. 32 Network Security: Symmetric Encryption 5. Block Ciphers 1.4 Randomized Electronic Code Book Encryption m1 m2 m3 m4 m5 m6 m7 m8 - Low efficiency due to random number transmission - Attacker can rearrange blocks. r1 + r2 + r3 + r4 + r5 + r6 + r7 + r8 + c1 c2 c3 c4 c5 c6 c7 c8 33  Network Security: Symmetric Encryption 5. Block Ciphers 2.1 Cipher Block Chaining Encryption m1 m2 m3 m4 m5 m6 m7 m8 CRC to protect from modifications IV + + + + + + + + unpredic- table c1 c2 c3 c4 c5 c6 c7 c8 34 Network Security: Symmetric Encryption 5. Block Ciphers 2.2 Cipher Block Chaining Problems − Reception of a block, e.g., 64 bits, required before block can be decrypted. − 1 bit error has impact on whole block. 35 Network Security: Symmetric Encryption 5. Block Ciphers 2.3 ECB vs CBC 36  Network Security: Symmetric Encryption 5. Block Ciphers 3. Cipher FeedBack Mode shift register shift register IV (s bits) (s bits) select s bits select s bits select s bits m1 + m2 + mn + s bits s bits s bits c1 c2 cn s bits s bits s bits 37  Network Security: Symmetric Encryption 5. Block Ciphers 4. Output FeedBack Mode + no propagation of bit errors ! shift register - more vulnerable to message Nonce (s bits) stream modification attack than CFB ON O1 O2 m1 + m2 + mn + c1 c2 cn 38  Network Security: Symmetric Encryption 5. Block Ciphers 5. CounTeR Mode Counter_N+1 = Counter_N + 1 Counter_1 Counter_2 Counter_N + hardware efficiency + software efficiency + random access + security + simplicity... m1 + m2 + mn + c1 c2 cn 39 Thanks for Your Attention Prof. Dr. Torsten Braun, Institut für Informatik Bern, 23.09.2024 – 30.09.2024 40