Cryptographic Hash Functions in Data Security Engineering

Mustansiriyah University Faculty of Engineering Cryptographic Hash Functions Course name: Data Security Computer Engineering Dep. Lecturer: Fatimah Al-Ubaidy Class: Third Year A Hash function (H) accepts a variable-length block of data Mas input and produces a fixed-size hash value h= H(M). A good hash function has the property that the results of applying the function to a large set of inputs will produce outputs that are evenly distributed and apparently random. In general terms, the principal object of a hash function is data integrity. A Cryptographic hash function: is an algorithm for which it is computationally infeasible to find either (a) a data object that maps to a pre-specified hash result (the one-way property) or (b) two data objects that map to the same hash result (the collision-free property). Because of these characteristics, hash functions are often used to determine whether or not data has changed. Applications of Cryptographic Hash Functions: (1) Message authentication, (2)Digital Signature, (3)One-way password file, (4)Intrusion detection, (5) Virus detection, (6)Pseudorandom number generation. Message Authentication: is a mechanism or service used to verify the integrity of a message. It assures that data received are exactly as sent (i.e., contain no modification, insertion, deletion, or replay). When a hash function is used to provide message authentication, the hash function value is often referred to as a message digest. * One-way password file: in which a hash of a password is stored by an operating system rather than the password itself. When a user enters a password, the hash of that password is compared to the stored hash value for verification. * Intrusion detection and virus detection: store H(F) for each file on a system and secure the hash values. One can later determine if a file has been modified by recomputing H(F). An intruder would need to change F without changing H(F). 1

Mustansiriyah University Faculty of Engineering Cryptographic Hash Functions Course name: Data Security Computer Engineering Dep. Lecturer: Fatimah Al-Ubaidy Class: Third Year Security Requirements of the Hash Functions: (1) Variable input size, (2) Fixed output size, (3) Efficiency, (4) Preimage resistant, (5) Second preimage resistant, (6) Collision resistant, (7) Pseudorandomness. * Preimage resistant, it is computationally infeasible to find any input that hashes to that output, i.e., given y, it is difficult to find an x such that h(x) = y. * Second preimage resistant, it is computationally infeasible to find any second input which has the same output as that of a specified input, i.e., given x, it is difficult to find a second preimage x x such that h(x) = h(x ). * Collision resistant, if this property is also satisfied, then it is referred to as a strong hash function. A strong hash function protects against an attack in which one party generates a message for another party to sign (if it is hard to find two inputs that hash to the same output). Attacks on Hash Functions: 1) Birthday Attack: the probability that in a set of n randomly chosen people, some pair of them will have the same birthday. Applied to hash function attacks, this means you have a 50% chance to break the collision resistance. 2) Brute-Force Attack: is to pick values of y at random and try each value until a collision occurs. 3) Preimage and Second Preimage Attack: For a preimage or second preimage attack, an adversary wishes to find a value y such that H(y) is equal to a given hash value h. 4) Collision Attack: For a collision resistant attack, an adversary wishes to find two messages or data blocks, x and y, that yield the same hash function. 2

Mustansiriyah University Faculty of Engineering Cryptographic Hash Functions Course name: Data Security Computer Engineering Dep. Lecturer: Fatimah Al-Ubaidy Class: Third Year Popular Hash Functions: 1) Message Digest (MD): MD5 was most popular and widely used hash function for quite some years. The MD family comprises of hash functions MD2, MD4, MD5 and MD6. It is a 128-bit hash function. In 2004, collisions were found in MD5 and hence it is no longer recommended for use. 2) Secure Hash Algorithm (SHA): It is the most widely used hash function. SHA was developed by NIST and published in 1993. It has several versions such as SHA-1, SHA-256, SHA-512, ..etc. Comparison of SHAs Parameters 3

Mustansiriyah University Faculty of Engineering Cryptographic Hash Functions Course name: Data Security Computer Engineering Dep. Lecturer: Fatimah Al-Ubaidy Class: Third Year SHA-512 Logic: The algorithm takes as input a message with a maximum length of less than 2128 bits and produces as output a 512-bit message digest. The input is processed in 1024-bit blocks. The overall processing of a message to produce a digest can be summarized as follows: Step 1 Append padding bits. The message is padded so that its length is congruent to 896 modulo 1024 [length K 896 (mod 1024)]. Padding is always added, even if the message is already of the desired length. Thus, the number of padding bits is in the range of 1 to 1024. The padding consists of a single 1 bit followed by the necessary number of 0 bits. Step 2 Append length. A block of 128 bits is appended to the message. This block is treated as an unsigned 128-bit integer (most significant byte first) and contains the length of the original message (before the padding). Step 3 Initialize hash buffer. A 512-bit buffer is used to hold intermediate and final results of the hash function. The buffer can be represented as eight 64-bit registers (a, b, c, d, e, f, g, h). Step 4 Process message in 1024-bit blocks. The heart of the algorithm is a module that consists of 80 rounds. Each round takes as input the 512-bit buffer value, abcdefgh, and updates the contents of the buffer. The output of the eightieth round is added to the input to the first round (Hi-1) to produce Hi using addition modulo 264. Step 5 Output. After all N1024-bit blocks have been processed, the output from he Nth stage is the 512- bit message digest. 4