Authentication network Identification and assurance of origin of information 2021/2/3
Authentication 2021/2/3 21 network Identification and assurance of origin of information
Authentication with shared secrets SECRET SECRET sg, H(SECRET_msg, Alice Bob Alice wants to ensure that nobody modifies message in transit (both integrity and authentication) slide 22
slide 22 Authentication with Shared Secrets msg, H(SECRET,msg) Alice wants to ensure that nobody modifies message in transit (both integrity and authentication) Alice Bob SECRET SECRET
Hash Functions, Main dea Hash function H message message digest y bit strings of any length n-bit bit strings H is a lossy compression function Collisions: h(x)=h(x)for some inputs X, X Result of hashing shouldlook random"(make this precise later) Intuition half of digest bits are"1, any bit in digest is"1 "half the time Cryptographic hash function needs a few properties slide 23
slide 23 Hash Functions: Main Idea bit strings of any length n-bit bit strings . . . . . x’ x’’ x y’ y Hash function H H is a lossy compression function Collisions: h(x)=h(x’) for some inputs x, x’ Result of hashing should “look random” (make this precise later) Intuition: half of digest bits are “1”; any bit in digest is “1” half the time Cryptographic hash function needs a few properties… “message digest” message
One-Way Intuition hash should be hard to invert *“ Preimage resistance” Let h(X)=yEo, 1n for a random x Given y, it should be hard to find any x such that h(x=y How hard? Brute-force: try every possible x, see if h(x)=y SHA-1(common hash function has 160-bit output Suppose have hardware that' l do 23o trials a pop Assuming 234 trials per second, can do 289 trials per year Will take 2/years to invert SHA-1 on a random image slide 24
slide 24 One-Way Intuition: hash should be hard to invert “Preimage resistance” Let h(x’)=y{0,1}n for a random x’ Given y, it should be hard to find any x such that h(x)=y How hard? Brute-force: try every possible x, see if h(x)=y SHA-1 (common hash function) has 160-bit output Suppose have hardware that’ll do 230 trials a pop Assuming 234 trials per second, can do 289 trials per year Will take 271 years to invert SHA-1 on a random image
“ Birthday Paradox T people Suppose each birthday is a random number taken from K days(K=365)-how many possibilities? *K(samples with replacement
“Birthday Paradox” T people Suppose each birthday is a random number taken from K days (K=365) – how many possibilities? KT (samples with replacement)