Network Security: Random Numbers and Hashing PDF

Network Security IV. Random Numbers and Hashing Prof. Dr. Torsten Braun, Institut für Informatik Bern, 07.10.2024 – 14.10.2024 Network Security: Random Numbers and Hashing Random Numbers and Hashing Table of Contents 1. Random Numbers 2. Hashing 3 Network Security: Random Numbers and...

Network Security IV. Random Numbers and Hashing Prof. Dr. Torsten Braun, Institut für Informatik Bern, 07.10.2024 – 14.10.2024 Network Security: Random Numbers and Hashing Random Numbers and Hashing Table of Contents 1. Random Numbers 2. Hashing 3 Network Security: Random Numbers and Hashing 1. Random Numbers 1. Use of Random Numbers − Key distribution (vs nonces) − Session key generation − Public-key encryption − Symmetric stream encryption 4 Network Security: Random Numbers and Hashing 1. Random Numbers 2.1 Randomness Criteria Uniform distribution Independence − Frequency of occurrence of − No subsequence can be bits should be approximately inferred from another one. equal. 5 Network Security: Random Numbers and Hashing 1. Random Numbers 2.2 Unpredictability Criteria Forward Unpredictability Backward Unpredictability − If seed is unknown, − Seed should not be predictable next output should be from any output value. unpredictable. 6  Network Security: Random Numbers and Hashing 1. Random Numbers 3. Random Number Generation True Random Number Generator Pseudorandom Number Generator Pseudorandom Function Context-specific Source of true randomness Seed value, e.g. app/user ID Seed Conversion Deterministic Deterministic to binary Algorithm Algorithm Random bit stream Pseudorandom bit stream Pseudorandom value 7 Network Security: Random Numbers and Hashing 1. Random Numbers 4.1 TRNG: Entropy Sources − Sound / video input − Thermal noise − Disk drives with random fluctuations in rotational speed − Clock time 8 Network Security: Random Numbers and Hashing 1. Random Numbers 4.2 TRNG as Seed Input Generation for PRNG Entropy source TRNG Seed PRNG Pseudorandom bit stream 9 Network Security: Random Numbers and Hashing 1. Random Numbers 4.3 Non-Deterministic Random Bit Generator Test for variability, e.g., repetition count test adaptive proportion test 10 Network Security: Random Numbers and Hashing 1. Random Numbers 4.4 Intel Processor Chip with Random Number Generator Deterministic Random Bit Generator Enhanced Nondeterministic Random Number Generator 11 Network Security: Random Numbers and Hashing 1. Random Numbers 5.1 PRNG: Linear Congruential Generators − m: modulus, e.g., 231-1 Requirements for RNGs − a: multiplier − The function should be a full-period generating function. − c: increment That is, the function should − X0: seed generate all the numbers from 0 through m−1 before repeating. − Xn+1 = (a・Xn + c) mod m − The generated sequence should appear random. − The function should implement 12 efficiently with 32-bit arithmetic. Network Security: Random Numbers and Hashing 1. Random Numbers 5.2 PRNG: Blum Blum Shub Generator Initialize with seed s Generate x2 mod n Select least significant bit (0, 1) 13 Network Security: Random Numbers and Hashing 1. Random Numbers 5.3 PRNGs Using Block Cipher Modes of Operation Counter Mode Output Feedback Mode 1 + Value V Pseudorandom bits Pseudorandom bits 14 Network Security: Random Numbers and Hashing 1. Random Numbers 5.4 PRNG based on RSA 15 Network Security: Random Numbers and Hashing 1. Random Numbers 6. Comparison of PRNG and TRNG PRNG TRNG − Very efficient − Generally inefficient − Deterministic − Nondeterministic − Periodic − Aperiodic 16 Network Security: Random Numbers and Hashing 2. Hashing − Goal of (one-way) hashing function − Input: long message − Output: short block (called hash or message digest) − Often combined with secret keys − If possible: evenly distributed and random − Example usage: − Calculation of fingerprints to detect modifications of data (digital signatures) − Message authentication 17 Network Security: Random Numbers and Hashing 2. Hashing 1. Hashing using XOR Ci: ith bit of hash code − Effective for integrity checks, since each n-bit hash value is m: number of n-bit blocks in input equally likely. bij: ith bit in jth block − Problem: more predictably formatted data, ⊕: XOR e.g., lower probability for highest bit Ci = bi1 ⊕ bi2 ⊕... ⊕ bim in normal texts. → Rotation as another operation (rotated XOR) − Possible encryption with CBC 18 Network Security: Random Numbers and Hashing 2. Hashing 2.1 Cryptographic Hash Functions: Security Requirements − Variable input sizes − Fixed output size − Efficiency (hardware and software implementations) 19 Network Security: Random Numbers and Hashing 2. Hashing 2.2.1 Cryptographic Hash Functions: Security Requirements − Pre-image resistant − (Strong) Collision resistant (one-way property) − It is computationally infeasible − For any given hash value h it is to find any pair (M, M’) with computationally infeasible to find M ≠ M’ and H(M) = H(M’). a message M that produces h, i.e., finding M so that H(M) = h − Pseudo-randomness − 2nd pre-image resistant − Output of H meets standard (weak collision resistant) tests for pseudo-randomness − for any given block M, it is computationally infeasible to find M’, i.e., H(M) = H(M’) 20 Network Security: Random Numbers and Hashing 2. Hashing 2.2.2 Relationship among Hash Function Properties Preimage collision resistant resistant 2nd preimage resistant 21 Network Security: Random Numbers and Hashing 2. Hashing 2.3 Cryptographic Hash Functions: Brute-Force Attacks Effort for brute-for-attacks for m-bit hash values − 1st pre-image resistant: 2m − 2nd pre-image resistant: 2m − Collision resistant: 2m/2, cf. birthday paradox 22 Network Security: Random Numbers and Hashing 2. Hashing 2.4 Cryptographic Hash Functions: Cryptanalysis − focuses on internal structure of f − tries to find efficient techniques to produce collisions of f 23 Network Security: Random Numbers and Hashing 2. Hashing 2.5 Birthday Attack − Alice wants to fire Fred. − Random variable 0...k-1 − Bob wants to double Fred’s salary. − Probability that a repeated element is encountered exceeds 0.5 after √(k-1) − Alice signs firing letter. choices. Bob writes double salary letter and − n inputs: n (n-1) / 2 pairs of inputs substitutes signature. − k outputs: probability of equal pair: 1/k − Bob needs to find two messages − k/2 pairs for probability > 0.5 (letters) with the same message − n (n-1) / 2 > k / 2 → n > √k digest. − For an m-bit hash value, we can expect to find another message with the same hash value after √(2m) = 2m/2 attempts. 24 Network Security: Random Numbers and Hashing 2. Hashing 2.6 Birthday Paradox Example: How many persons needed to have a probability p > 0.5 that two persons share the same birthday ? − 365n different birthday combinations for n persons − 365・364・363・… ・(365 – (n-1)) cases with different birthdays − p = 1 – (365・364・363・…・ (365 – (n-1))) / 365n 25 Network Security: Random Numbers and Hashing 2. Hashing 3.1 General Structure of Secure Hash Code Y0 Y1 YL-1 b b b IV f f... f n 26 Network Security: Random Numbers and Hashing 2. Hashing 3.2.1 SHA-512 27  Network Security: Random Numbers and Hashing 2. Hashing 3.2.2 SHA-512 Ch(e, f, g) = (e ∧ f) ⊕ (¬e ∧ g) Maj(a, b, c) = (a ∧ b) ⊕ (a ∧ c) ⊕ (b ∧ c) F: 28 Network Security: Random Numbers and Hashing 2. Hashing 3.3.1 SHA-3: Sponge Construction state variable s 29  Network Security: Random Numbers and Hashing 2. Hashing 3.3.2 SHA-3: Iteration Function f theta rho rot(x,y) pi chi iota RC[i] 30 RC: round constant Network Security: Random Numbers and Hashing 2. Hashing 4.1 Applications: Message Authentication Code Message Message Hash Hash Message compare 31 Network Security: Random Numbers and Hashing 2. Hashing 4.2 Applications: Digital Signatures Message Message Hash ds(MD(m)) m Message Hash =? Hash 32 Network Security: Random Numbers and Hashing 2. Hashing 4.3 Applications: Authenticated Encryption 1. Encrypt-then-MAC 2. Encrypt-and-MAC 3. MAC-then-Encrypt 33 Network Security: Random Numbers and Hashing 2. Hashing 4.3.1 Encrypt-then-MAC − Only method that can be proved to achieve the highest level of security − used in TLS, SSH 34 Network Security: Random Numbers and Hashing 2. Hashing 4.3.2 Encrypt-and-MAC − can be made strongly secure − used in SSH 35 Network Security: Random Numbers and Hashing 2. Hashing 4.3.3 MAC-then-Encrypt − can be made strongly secure − used in TLS 36  Network Security: Random Numbers and Hashing 2. Hashing 4.4.1 Applications: Message Digest 5 Padding, Steps 128 Bit constant Message Length 1. Padding to length 448 mod 512 2. Append 64 bit length Transformation information 3. Initialization of 4 word buffer A: 01 23 45 67 Transformation B: 89 ab cd ef C: fe dc ba 98 D: 76 54 32 10 Transformation 4. Processing in 512 bit steps 37 Message Digest  Network Security: Random Numbers and Hashing 2. Hashing 4.4.2 Applications: MD5 Implementation /* Round 1; a = b + ((a + F(b,c,d) + X[k] + T[i])