Foundations of Computer SecurityLecture 50: Cryptographic Hash FunctionsDr. Bill YoungDepartment of Computer SciencesUniversity of Texas at AustinLecture 50: 1 Cryptographic Hash FunctionsHash FunctionsA hash function is a function that converts variable-sized text intoa small datum, usually a fixed size integer.A cryptographic hash function has the additional qualities:it is difficult to construct a text that has a given hash,it is difficult to modify a given text without changing its hash,it is unlikely that two different messages will have the samehash.The hash value is sometimes called a message digest.Cryptographic hash functions are used to protect integrity.Lecture 50: 2 Cryptographic Hash FunctionsVocabularyA function f is preimage resistant if, given h, it is hard to find anym such that h = f (m).A function f is second preimage resistant if, given an input m1, itis hard to find m26= m1such that f (m1) = f (m2). This issometimes called weak collision resistance.A function f is (strong) collision resistant if it is hard to find twomessages m1and m2such that f (m1) = f (m2).Lecture 50: 3 Cryptographic Hash FunctionsBirthday AttacksIf a function f (x) yields any of H different outputs with equalprobability and H is sufficiently large, then we expect to obtain apair of different arguments x1and x2with f (x1) = f (x2) afterevaluating the function for about 1.25√H different arguments onaverage.What does this mean for a hash value of 128 bits? for 160 bits?Lecture 50: 4 Cryptographic Hash FunctionsCryptographic Hash FunctionsHash functions usually are used for integrity, not confidentiality.In a document retrieval system containing legal records, itmay be important to know that the copy retrieved is identicalto that stored.In a secure communications system, the correct transmissionof messages may override confidentiality concerns.A cryptographic hash function “binds” the bytes of a file togetherin a way that makes any alterations to the file apparent. We saythat we seal the file to make it tamper-proof (actuallytamper-resistant).Lecture 50: 5 Cryptographic Hash FunctionsUsing a Hash FunctionsThe process is as follows:Given a sensitive file f , compute the hash function h(f ) andstore the result securely.Each time the file is used or accessed, recompute the hash.Compare it to the stored value.If the two values match, it is likely that no changes have occurredto the file.Lecture 50: 6 Cryptographic Hash FunctionsCommon Hash AlgorithmsTwo widely used cryptographic hash functions are:MD5: (Message Digest 5) invented by Ron Rivest and RSALabs;SHA-1/SHA-2/SHS: (Secure Hash Algorithm or Standard) similarto MD5.MD5 hashes a message of any size to a 128-bit digest. SHA/SHSproduce a 160-bit digest.Lecture 50: 7 Cryptographic Hash FunctionsLessonsA cryptographic hash function takes an arbitrary text andproduces a fixed size bit string that depends on each value ofthe text.It should be difficult to find collisions—values that hash to thesame result.A hash can be used to show with high probability that a texthas not changed.Next lecture: Key ExchangeLecture 50: 8 Cryptographic Hash
View Full Document
Unlocking...