Hash FunctionsCryptographic Hash FunctionNon-crypto Hash (1)Non-crypto Hash (2)Non-crypto Hash (3)Popular Crypto HashesPublic Key NotationCrypto Hash Motivation: Digital SignaturesDigital SignaturesNon-repudiationNon-non-repudiationSlide 12Hashing and SignaturesCrypto Hash Function DesignSlide 15Hash FunctionCrypto Hash: Fun FactsHMACHow to Compute HMAC?Slide 20The Right Way to HMACHashing and BirthdaysPre-Birthday ProblemBirthday ProblemOf Hashes and BirthdaysSignature Birthday AttackSlide 27Slide 28Online Bid ExampleOnline BidSlide 31Weak Collision AttackTrudy Predicts Future?Slide 34Nostradamus AttackSlide 36Diamond StructureSlide 38Slide 39Slide 40Slide 41Nostradamus: Bottom LineHash Functions 1Hash FunctionsHash Functions 2Cryptographic Hash FunctionCrypto hash function h(x) must provideoCompression  output length is smalloEfficiency  h(x) easy to compute for any xoOne-way  given a value y it is infeasible to find an x such that h(x) = yoWeak collision resistance  given x and h(x), infeasible to find y  x such that h(y) = h(x)oStrong collision resistance  infeasible to find any x and y, with x  y such that h(x) = h(y)Many collisions exist, but cannot find anyHash Functions 3Non-crypto Hash (1)Data X = (X0,X1,X2,…,Xn-1), each Xi is a byteSpse hash(X) = X0+X1+X2+…+Xn-1Is this secure?Example: X = (10101010,00001111)Hash is 10111001But so is hash of Y = (00001111,10101010)Easy to find collisions, so not secure…Hash Functions 4Non-crypto Hash (2)Data X = (X0,X1,X2,…,Xn-1)Suppose hash isoh(X) = nX0+(n-1)X1+(n-2)X2+…+1Xn-1Is this hash secure? At leasth(10101010,00001111)h(00001111,10101010)But hash of (00000001,00001111) is same as hash of (00000000,00010001)Not secure, but it is used in the (non-crypto) application rsyncHash Functions 5Non-crypto Hash (3)Cyclic Redundancy Check (CRC)Essentially, CRC is the remainder in a long division calculationGood for detecting burst errorsEasy for Trudy to construct collisionsCRC sometimes mistakenly used in crypto applications (WEP)Hash Functions 6Popular Crypto HashesMD5  invented by Rivesto128 bit outputoNote: MD5 collision recently foundSHA-1  A US government standard (similar to MD5)o160 bit outputMany others hashes, but MD5 and SHA-1 most widely usedMessages are hashed in blocksHash Functions 7Public Key NotationSign message M with Alice’s private key: [M]AliceEncrypt message M with Alice’s public key: {M}Alice Then{[M]Alice}Alice = M[{M}Alice]Alice = MHash Functions 8Crypto Hash Motivation: Digital SignaturesSuppose Alice signs MoAlice sends M and S = [M]Alice to BoboBob verifies that M = {S}AliceIf M is big, [M]Alice is costly to computeSuppose instead, Alice signs h(M), where h(M) is much smaller than MoAlice sends M and S = [h(M)]Alice to BoboBob verifies that h(M) = {S}AliceHash Functions 9Digital SignaturesDigital signatures provide integrityoLike MAC and HMACWhy? Alice sends M and S = [h(M)]Alice to BobIf M changed to M or S changed to S (accident or intentional) Bob detects it:h(M)  {S}Alice, h(M)  {S}Alice, h(M)  {S}AliceHash Functions 10Non-repudiationDigital signature also provides for non-repudiationAlice sends M and S = [h(M)]Alice to BobAlice cannot “repudiate” signatureoAlice cannot claim she did not sign MWhy does this work? Is the same true of MAC?Hash Functions 11Non-non-repudiationAlice orders 100 shares of stock from BobAlice computes MAC using symmetric keyStock drops, Alice claims she did not orderCan Bob prove that Alice placed the order?No! Since Bob also knows symmetric key, he could have forged messageProblem: Bob knows Alice placed the order, but he cannot prove itHash Functions 12Non-repudiationAlice orders 100 shares of stock from BobAlice signs order with her private keyStock drops, Alice claims she did not orderCan Bob prove that Alice placed the order?Yes! Only someone with Alice’s private key could have signed the orderThis assumes Alice’s private key is not stolen (revocation problem)Hash Functions 13Hashing and SignaturesAlice signs h(M), sends M and S = [h(M)]Alice to Bob and Bob verifies h(M) = {S}AliceSecurity depends on public key system and hash functionSuppose Trudy can find collision: M  M with h(M) = h(M)Then Trudy can replace M with M and signature scheme is brokenHash Functions 14Crypto Hash Function DesignDesired property: avalanche effectoAny change to input affects lots of output bitsCrypto hash functions consist of some number of roundsoAnalogous to block cipher in CBC modeWant security and speedoAvalanche effect after few roundsoBut simple roundsHash Functions 15Crypto Hash Function DesignInput data split into blocksCompression function applied to blocksoCurrent block and previous block outputoOutput for last block is the hash valueFor hashes we consideroBlock size is 512 bitsoCompression function output is 128 bitsHash Functions 16Hash FunctionInput or “message” blocks M0,M1,…,MN1Addition is mod 232 per 32-bit wordThis is known as Merkle-Damgard constructionHash Functions 17Crypto Hash: Fun FactsIf msg is one 512-bit block: h(M) = f(IV,M) where f and IV known to TrudyFor 2 blocks: h(M) = f(f(IV,M0),M1) = f(h(M0),M1)In general h(M) = f(h(M0,M1,…,Mn2),Mn1)oIf