Cryptography and Network Security Chapter 11Chapter 11 – Cryptographic Hash FunctionsHash FunctionsCryptographic Hash FunctionHash Functions & Message Authent-icationHash Functions & Digital SignaturesOther Hash Function UsesTwo Simple Insecure Hash FunctionsHash Function RequirementsAttacks on Hash FunctionsBirthday AttacksHash Function CryptanalysisBlock Ciphers as Hash FunctionsSecure Hash AlgorithmRevised Secure Hash StandardSHA VersionsSHA-512 OverviewSHA-512 Compression FunctionSHA-512 Round FunctionSlide 20SHA-3SHA-3 RequirementsSummaryCryptography and Cryptography and Network SecurityNetwork SecurityChapter 11Chapter 11Fifth EditionFifth Editionby William Stallingsby William StallingsLecture slides by Lawrie BrownLecture slides by Lawrie BrownChapter 11 – Cryptographic Chapter 11 – Cryptographic Hash FunctionsHash FunctionsEach of the messages, like each one he had ever Each of the messages, like each one he had ever read of Stern's commands, began with a number read of Stern's commands, began with a number and ended with a number or row of numbers. No and ended with a number or row of numbers. No efforts on the part of Mungo or any of his experts efforts on the part of Mungo or any of his experts had been able to break Stern's code, nor was had been able to break Stern's code, nor was there any clue as to what the preliminary number there any clue as to what the preliminary number and those ultimate numbers signified.and those ultimate numbers signified.——Talking to Strange Men, Talking to Strange Men, Ruth RendellRuth RendellHash FunctionsHash Functionscondenses arbitrary message to fixed sizecondenses arbitrary message to fixed sizeh = H(M)h = H(M) usually assume hash function is publicusually assume hash function is publichash used to detect changes to messagehash used to detect changes to messagewant a cryptographic hash functionwant a cryptographic hash functioncomputationally infeasible to find data mapping computationally infeasible to find data mapping to specific hash (one-way property)to specific hash (one-way property)computationally infeasible to find two data to computationally infeasible to find two data to same hash (collision-free property)same hash (collision-free property)Cryptographic Hash FunctionCryptographic Hash FunctionHash Hash Functions Functions & Message & Message Authent-Authent-icationicationHash Functions & Digital Hash Functions & Digital SignaturesSignaturesOther Hash Function UsesOther Hash Function Usesto create a one-way password fileto create a one-way password filestore hash of password not actual store hash of password not actual passwordpasswordfor intrusion detection and virus detectionfor intrusion detection and virus detectionkeep & check hash of files on systemkeep & check hash of files on systempseudorandom function (PRF) or pseudorandom function (PRF) or pseudorandom number generator (PRNG)pseudorandom number generator (PRNG)Two Simple Insecure Hash Two Simple Insecure Hash FunctionsFunctionsconsider two simple insecure hash functionsconsider two simple insecure hash functionsbit-by-bit exclusive-OR (XOR) of every blockbit-by-bit exclusive-OR (XOR) of every blockCCii = b = bi1i1 xor b xor bi2i2 xor . . . xor b xor . . . xor bimim a longitudinal redundancy checka longitudinal redundancy checkreasonably effective as data integrity checkreasonably effective as data integrity checkone-bit circular shift on hash valueone-bit circular shift on hash valuefor each successive for each successive n-bit n-bit blockblock•rotate current hash value to left by1bit and XOR blockrotate current hash value to left by1bit and XOR blockgood for data integrity but useless for securitygood for data integrity but useless for securityHash Function RequirementsHash Function RequirementsAttacks on Hash FunctionsAttacks on Hash Functionshave brute-force attacks and cryptanalysishave brute-force attacks and cryptanalysisa preimage or second preimage attacka preimage or second preimage attackfind find yy s.t. s.t. H(y) H(y) equals a given hash value equals a given hash value collision resistancecollision resistancefind two messages find two messages xx & & yy with same hash so with same hash so H(x) = H(y)H(x) = H(y) hence value 2hence value 2m/2 m/2 determines strength of determines strength of hash code against brute-force attackshash code against brute-force attacks128-bits inadequate, 160-bits suspect128-bits inadequate, 160-bits suspectBirthday AttacksBirthday Attacksmight think a 64-bit hash is securemight think a 64-bit hash is securebut by but by Birthday ParadoxBirthday Paradox is not is notbirthday attack birthday attack works thus:works thus:given user prepared to sign a valid message xgiven user prepared to sign a valid message xopponent generates 2opponent generates 2mm//22 variations x’ of x, all with variations x’ of x, all with essentially the same meaning, and saves themessentially the same meaning, and saves themopponent generates 2opponent generates 2mm//22 variations y’ of a desired variations y’ of a desired fraudulent message yfraudulent message ytwo sets of messages are compared to find pair with two sets of messages are compared to find pair with same hash (probability > 0.5 by birthday paradox)same hash (probability > 0.5 by birthday paradox)have user sign the valid message, then substitute the have user sign the valid message, then substitute the forgery which will have a valid signatureforgery which will have a valid signatureconclusion is that need to use larger MAC/hashconclusion is that need to use larger MAC/hashHash Function CryptanalysisHash Function Cryptanalysiscryptanalytic attacks exploit some property cryptanalytic attacks exploit some property of alg so faster than exhaustive searchof alg so faster than exhaustive searchhash functions use iterative structurehash functions use iterative structureprocess message in blocks (incl length)process message in blocks (incl length)attacks focus on collisions in function fattacks focus on collisions in function fBlock Ciphers as Hash Block Ciphers as Hash FunctionsFunctionscan use block ciphers as hash functionscan use block ciphers as hash functionsusing Husing H00=0 and zero-pad of final block=0 and zero-pad of final blockcompute: Hcompute: Hii = E = EMMii [H [Hi-1i-1]]and use final block as the hash valueand use