Foundations of Network and Foundations of Network and Computer SecurityComputer SecurityJJohn BlackLecture #7Sep 13th2005CSCI 6268/TLEN 5831, Fall 2005CBC MAC (again)•Review:– A common method is the CBC MAC:• CBC MAC is stateless (no nonce N is used)• Proven security in the ACMA model provided messages are all of once fixed length• Resistance to forgery quadratic in the aggregate length of adversarial queries plus any insecurity of AES• Widely used: ANSI X9.19, FIPS 113, ISO 9797-1AESKM1AESKAESKtagM2MmVarying Message Lengths: XCBC• There are several well-known ways to overcome this limitation of CBC MAC• XCBC, is the most efficient one known, and is provably-secure (when the underlying block cipher is computationally indistinguishable from random)– Uses blockcipher key K1 and needs two additional n-bit keys K2 and K3 which are XORed in just before the last encipherment• A proposed NIST standard (as “CMAC”)AESK1M1AESK1AESK1tagM2MmK2 if n divides |M|K3 otherwiseUMAC: MACing Faster• In many contexts, cryptography needs to be as fast as possible– High-end routers process > 1Gbps– High-end web servers process > 1000 requests/sec• But AES (a very fast block cipher) is already more than 15 cycles-per-byte on a PPro– Block ciphers are relatively expensive; it’s possible to build faster MACs• UMAC is roughly ten times as fast as current practiceUMAC follows the Wegman-Carter Paradigm• Since AES is (relatively) slow, let’s avoid using it unless we have to– Wegman-Carter MACs provide a way to process M first with a non-cryptographic hash function to reduce its size, and then encrypt the resultMessage Mhash functionhash keyencryptencryption keyhash(M)tagThe Ubiquitous HMAC• The most widely-used MAC (IPSec, SSL, many VPNs)• Doesn’t use a blockcipher or any universal hash family– Instead uses something called a “collision resistant hash function” H• Sometimes called “cryptographic hash functions”• Keyless object – more in a moment•HMACK(M) = H(K ⊕ opad || H(K ⊕ ipad || M))• opad is 0x36 repeated as needed• ipad is 0x5C repeated as neededNotes on HMAC•Fast– Faster than CBC MAC or XCBC• Because these crypto hash functions are fast•Slow– Slower than UMAC and other universal-hash-family MACs• Proven security– But these crypto hash functions have recently been attacked and may show further weaknesses soonWhat are cryptographic hash functions?OutputMessagee.g., MD5,SHA-1Hash Function• A cryptographic hash function takes a message from{0,1}*and produces a fixed size output• Output is called “hash” or “digest” or “fingerprint”• There is no key• The most well-known are MD5 and SHA-1 but thereare other options• MD5 outputs 128 bits• SHA-1 outputs 160 bits% md5Hello There^DA82fadb196cba39eb884736dcca303a6%T ← A << 5 + gt(B, C, D) + E + Kt+ WtSHA-1...M1M2Mmfor i = 1 to m doWt= {t-th word of Mi0 ≤ t ≤ 15( Wt-3⊕ Wt-8⊕ Wt-14⊕ Wt-16 ) << 1 16 ≤ t ≤ 79A ← H0i-1; B ← H1i-1; C ← H2i-1; D ← H3i-1; E ← H4i-1for t = 1 to 80 doE ← D; D ← C; C ← B >> 2; B ← A; A ← TH0i← A + H0i-1; H1i← B + H1i-1; H2i← C+ H2i-1; H3i← D + H3i-1; H4i← E + H4i-1endendreturn H0mH1mH2mH3mH4m512 bits160 bitsReal-world applications• Message authentication codes (HMAC) • Digital signatures (hash-and-sign)• File comparison (compare-by-hash, eg, RSYNC)• Micropayment schemes• Commitment protocols• Timestamping• Key exchange•...Hash functions are pervasiveA cryptographic propertyBAD: H(M) = M mod 701(quite informal)1. Collision resistance given a hash function it is hard to find two colliding inputsHM{0,1}nHM’StringsMore cryptographic properties1. Collision resistance given a hash function it is hard to find two colliding inputs3. Preimage resistance given a hash function andgiven an hash outputit is hard to invert that output2. Second-preimage given a hash function andresistance given a first input, it is hard to find a second inputthat collides with the first3Merkle-Damgard constructionIVM1M2M3h1h2h3= H (M)nkFixed initial valueChaining valueCompression functionf ffkMD Theorem: if f is CR, then so is HMiT ← A << 5 + gt(B, C, D) + E + Kt+ Wt...M1M2Mmfor i = 1 to m doWt= {t-th word of Mi0 ≤ t ≤ 15( Wt-3⊕ Wt-8⊕ Wt-14⊕ Wt-16 ) << 1 16 ≤ t ≤ 79A ← H0i-1; B ← H1i-1; C ← H2i-1; D ← H3i-1; E ← H4i-1for t = 1 to 80 doE ← D; D ← C; C ← B >> 2; B ← A; A ← TH0i← A + H0i-1; H1i← B + H1i-1; H2i← C+ H2i-1; H3i← D + H3i-1; H4i← E + H4i-1endendreturn H0mH1mH2mH3mH4m512 bits160 bitsH0..4i-1160 bits160 bitsHash Function Security• Consider best-case scenario (random outputs)• If a hash function output only 1 bit, how long would we expect to avoid collisions?– Expectation: 1× 0 + 2 × ½ + 3 × ½ = 2.5• What about 2 bits?– Expectation: 1 × 0 + 2 × ¼ + 3 × ¾ ½ + 4 × ¾ ½ ¾ + 5 × ¾ ½ ¼ ≈ 3.22• This is too hard…Birthday Paradox• Need another method– Birthday paradox: if we have 23 people in a room, the probability is > 50% that two will share the same birthday• Assumes uniformity of birthdays– Untrue, but this only increases chance of birthday match• Ignores leap years (probably doesn’t matter much)– Try an experiment with the class…Birthday Paradox (cont)• Let’s do the math– Let n equal number of people in the class– Start with n = 1 and count upward• Let NBM be the event that there are No-Birthday-Matches• For n=1, Pr[NBM] = 1• For n=2, Pr[NBM] = 1 × 364/365 ≈ .997• For n=3, Pr[NBM] = 1 × 364/365 × 363/365 ≈ .991•…• For n=22, Pr[NBM] = 1 × … × 344/365 ≈ .524• For n=23, Pr[NBM] = 1 × … × 343/365 ≈ .493– Since the probability of a match is 1 – Pr[NBM] we see that n=23 is the smallest number where the probability exceeds 50%Occupancy Problems• What does this have to do with hashing?– Suppose each hash output is uniform and random on {0,1}n– Then it’s as if we’re throwing a ball into one of 2nbins at random and asking when a bin contains at least 2 balls• This is a well-studied area in probability theory called “occupancy problems”– It’s well-known that the probability of a collision occurs around the square-root of the number of bins• If we have 2nbins, the square-root is 2n/2Birthday Bounds• This