Downloaded 63 times
![Fact About ROC 01 Oracle cannot use formula or algorithm to create the digest Suppose oracle uses the formula h(M) = M mon n, M1 + M2 = M3 h(M3) = (M1+M2) mod n = M1 mod n + M2 mod n = [ h(M1) + h(M2) ] mod n should have some randomness. eg, secure bidding problem 03 In practice we use pseudo-random functions 02 Unfortunately, a random oracle does not exist since it requires infinite storage](https://image.slidesharecdn.com/hash-191031153453/75/Random-Oracle-Model-Hashing-Cryptography-Network-Security-7-2048.jpg)
![Preimage Attack Algorithm input: h, D Choose, any X0 ε x, |x0| = q for any message M[i] ε x if (h(M[i]) == D)return M[i] else return fail Probability that the hash of an M[i] match with D = 1/N Probability it does not match with D = 1 - 1/N Probability, none of q queries match with D = ( 1 - 1/N )q Success probability Pr[success] = 1 - ( 1 - 1/N )q e-x = 1 - x + x2/2! - x3/3! + x4/4! + …. According Taylor Series If N is large, replace 1-1/N = e-1/N pr [success] = 1 - e-q/N If probability 0.5, q = ln(0.5)N = 0.69 x 2n Attacks on Random Oracle Model](https://image.slidesharecdn.com/hash-191031153453/75/Random-Oracle-Model-Hashing-Cryptography-Network-Security-13-2048.jpg)
![Preimage Attack Algorithm input: h, M Calculate D = h(M) Choose, any X0 ε x{M}, |x0| = q-1 for any message M[i] ε x if (h(M[i]) == D)return M[i] else return fail pr [success] = 1 - e-(q-1)/N If probability 0.5, q = ln(0.5)N + 1 = 0.69 x 2n + 1 Attacks on Random Oracle Model](https://image.slidesharecdn.com/hash-191031153453/75/Random-Oracle-Model-Hashing-Cryptography-Network-Security-17-2048.jpg)
![Preimage Attack Algorithm input: h Choose, any x0 ε , |x0| = q for any message pair M[i], M[i`] ε x if (h(M[i]) == h(M[i`]))return M[i], M[i`] else return fail P (hash of M[0] and M[1] does not collide) = 1 - 1/N P (hash of M[0] and M[1] does not collide with M[3]) ( 1 - 1/N ) ( 1 - 2/N ) Probability of q hash value does cot collide (1- 1/N) (1 - 2/N) (1 - 3/N) ………………… ( 1 - (q-1)/N) q-1 q-1 Pr[ No Collisions] = Σ (1 - i/N) = Σ e -i/n = e -q2/N I=1 I=1 pr [collisions/success] = 1 - e -q2/N If probability 0.5, q = sqrt ( ln(0.5)N ) = 1.18 x sqrt(N) = 1.18 x 2n/2 [ N = 2n ] Attacks on Random Oracle Model](https://image.slidesharecdn.com/hash-191031153453/75/Random-Oracle-Model-Hashing-Cryptography-Network-Security-20-2048.jpg)
Uploaded byMahbubur Rahman
Random Oracle Model & Hashing - Cryptography & Network Security
This document discusses hashing and the random oracle model. It defines cryptographic hash functions as deterministic functions that map arbitrary strings to fixed-length outputs in a way that appears random. The random oracle model assumes an ideal hash function that behaves like a random function. The document discusses collision resistance, preimage resistance, and birthday attacks as they relate to finding collisions or preimages with a given hash function. It provides examples of calculating the number of messages an attacker would need to find collisions or preimages with different probabilities. The document concludes by listing some applications of cryptographic hash functions like password storage, file authenticity, and digital signatures.
In this document
Powered by AI
Introduction to the topic of hashing by Sadman Ahmmed, focusing on the random oracle model.
Overview of the presentation covering document integrity, fingerprinting, attacks on the random oracle model, and various related topics.
Scenario depicting message integrity involving Alice, Oscar, and message interference with representations for original and altered messages.
Presentation of a hash function as a solution for message integrity, detailing input and output lengths (e.g., SHA-1, 160 bits).
Definition of cryptographic hash functions, their deterministic nature, public operations, and examples like MD4, MD5, and SHA-1.
Explanation of the ideal hash function model, its deterministic outputs, and its operations for previously encountered inputs.
Key facts about random oracles, emphasizing their lack of existence and the necessity of pseudo-random functions for practical applications.
Discussion on collisions due to the pigeonhole principle, showcasing message to digest lengths with illustrative examples.
Exploration of the birthday paradox, calculating the probability of shared birthdays among a group of 23 people.
Depiction of a one-way problem in message interference involving Alice, Oscar, and potential decryption attempts.
Emphasis on the one-way property of hashes ensuring distinct outputs for differing inputs.
Explanation of preimage attacks, highlighting the difficulty of finding an input that produces a given hash output.
Algorithmic approach to preimage attacks, including probabilities of matching hash outputs and calculations involved.
Illustration of time required for a cryptographic attack with a 64-bit digest, demonstrating practical vulnerabilities.
Scenario illustrating collision resistance, with an example involving financial transactions between Alice and Oscar.
Definition of weak collision resistance related to the difficulty of finding two distinct inputs with the same hash.
Continuation of the preimage attack algorithm focusing on calculating probabilities for success in attempts.
Further discussion of finding collisions, specifically in digital signatures and the implications of collisions.
Defining strong collision resistance in hashing terms, the difficulty of finding any input pair with identical hashes.
Detailed probability calculations regarding successful collision detection in hash outputs across multiple inputs.
Example scenario outlining the time estimate to find two colliding messages using a hash function with a 64-bit digest.
Different applications of cryptographic hash functions including password storage, file authenticity, digital signatures, and commitments.
Random Oracle Model & Hashing - Cryptography & Network Security
- 1. Hashing & Random OracleModel Sadman Ahmmed | B150305029
- 2. TOC Document and Fingerprint PigeonholePrinciple Attacks on Random Oracle Model Checking Integrity Cryptographic Hash Function Criteria Random Oracle Model Birthday Paradox Applications
- 3. Problem of theday (message integrity) Alice X Oscar interfere x X > X’ X’
- 4. Solution (Hash Function) Alice X Oscar interferex X > X’ X’ message x (arbitrary length) eg : 1TB hash value y = h(x) fixed length, eg : SHA-1 160 bits h( x ) y = h(x)h(x) != h(x’)
- 5. Cryptographic Hash Function 01A function h maps arbitrary strings of data to fixed length output 02 Deterministic and public, but the mapping should look “random” h : {0, 1} ∗ → {0, 1} d 03 No secret key, all operations public, anyone can compute h, polytime computation. Example : MD4, MD5, SHA-1 document/message message digest/fingerprint/authentication tag
- 6. Random Oracle Model‘h’ Ideal model of the hash function. we assume there exists an oracle h such that on input , x ∈ {0, 1}∗ yes Message Message Digest hello 1001 hi 1110 h : {0, 1} ∗ → {0, 1} 4 hello T H H T Hash Table x If x has seen before y returns h(x) it previously output yes generate deterministic random value no store output
- 7. Fact About ROC 01 Oraclecannot use formula or algorithm to create the digest Suppose oracle uses the formula h(M) = M mon n, M1 + M2 = M3 h(M3) = (M1+M2) mod n = M1 mod n + M2 mod n = [ h(M1) + h(M2) ] mod n should have some randomness. eg, secure bidding problem 03 In practice we use pseudo-random functions 02 Unfortunately, a random oracle does not exist since it requires infinite storage
- 8. Collision (Pigeonhole principle) InputSpace : infinity Assume 4 bits length Hash Space : fixed Assume 4 bits length n pigeonhole > n+1 pigeons > at least 1 nole is occupied by 2 pigeons n pigeonhole > kn+1 pigeons > at least 1 nole is occupied by k+1 pigeons Digest should be shorter than the message, so there are some digests, correspond to more than one message. Eg, pigeonhole = 4, pigeons = 16 or n = 4, kn+1 = 16, so k is larger than 3. At least 1 digest corresponds to (k+1) messages. 22 = 424 = 16 Obj 1 Obj 2 Obj 3 Obj 4 Obj 5 . 0 1 2 3
- 9. Birthday Paradox How manypeople must be there in a room to make the probability 50% that at-least two people in the room have same birthday? Not easy to calculate 2 people share same rather 2 people not share the same birthday. Probability of 23 people not having same birthday = 365/365 x 364/365 x 363/365 x …… x (people 23) 343/365 = 364! / ( 342! X 36522 ) = .492703 > 49.3% Chance we do = 1 - .4927 = .507 > 50.7%
- 10. Alice Bob Oscar X try to decryptX Done or undone interfere X X > X’ X’ Another Problem (One Way)
- 11. Alice Bob Oscar X Knows h( ) interfereX X > X’ X’ Solution h(x) h(x) != h(x’)
- 12. Preimage Attack Given y∈ {0, 1} d it is hard to find an x such that h(x) = y aka. one way Can’t be done : lossless compression, check sum Preimage Resistance Cryptographic Hash Function Criteria Birthday Problem 1 What is the minimum number, k, of the students in a classroom such that it is likely that at least one student has a predefined birthday?
- 13. Preimage Attack Algorithm input: h,D Choose, any X0 ε x, |x0| = q for any message M[i] ε x if (h(M[i]) == D)return M[i] else return fail Probability that the hash of an M[i] match with D = 1/N Probability it does not match with D = 1 - 1/N Probability, none of q queries match with D = ( 1 - 1/N )q Success probability Pr[success] = 1 - ( 1 - 1/N )q e-x = 1 - x + x2/2! - x3/3! + x4/4! + …. According Taylor Series If N is large, replace 1-1/N = e-1/N pr [success] = 1 - e-q/N If probability 0.5, q = ln(0.5)N = 0.69 x 2n Attacks on Random Oracle Model
- 14. Example : A cryptographichash function uses a digest of 64 bits. How many digests does Oscar need to create to find the original message with the probability more than 0.5? Suppose, Oscar can test 230 messages per second it takes ( 0.69 x 2 64 )/ 2 30 = 0.69 x 2 34 seconds, or more than 500 years. k ≈ 0.69 × 2n ≈ 0.69 x 2 64
- 15. Alice Bob Oscar X Found x’, h(x’)= h(x) X = give oscar 20$ X’ = give oscar 20000$ X’ TCR h(x) h(x) == h(x’)
- 16. Preimage Attack Cryptographic HashFunction Criteria Birthday Problem 2 What is the minimum number, k, of the students in a classroom such that it is likely that at least one student has the same birthday as the student selected by the professor? Given x it is hard to find x ' such that h(x) = h(x ' ) where x != x’ aka, Weak collision-resistance, target collision resistance Second Preimage Resistance
- 17. Preimage Attack Algorithm input: h,M Calculate D = h(M) Choose, any X0 ε x{M}, |x0| = q-1 for any message M[i] ε x if (h(M[i]) == D)return M[i] else return fail pr [success] = 1 - e-(q-1)/N If probability 0.5, q = ln(0.5)N + 1 = 0.69 x 2n + 1 Attacks on Random Oracle Model
- 18. Alice Bob Oscar x1 Found x1,x2, h(x1)= h(x2) CR, Digital Signature (x1, y)(x2, y)
- 19. Preimage Attack Cryptographic HashFunction Criteria Birthday Problem 3 What is the minimum number, k, of the students in a classroom such that it is likely that at least two students have the same birthday? It is hard to find any pair of inputs x, x ' such that h(x) = h(x ' ) where x != x’ aka , Strong collision-resistance Collision Resistance
- 20. Preimage Attack Algorithm input: h Choose,any x0 ε , |x0| = q for any message pair M[i], M[i`] ε x if (h(M[i]) == h(M[i`]))return M[i], M[i`] else return fail P (hash of M[0] and M[1] does not collide) = 1 - 1/N P (hash of M[0] and M[1] does not collide with M[3]) ( 1 - 1/N ) ( 1 - 2/N ) Probability of q hash value does cot collide (1- 1/N) (1 - 2/N) (1 - 3/N) ………………… ( 1 - (q-1)/N) q-1 q-1 Pr[ No Collisions] = Σ (1 - i/N) = Σ e -i/n = e -q2/N I=1 I=1 pr [collisions/success] = 1 - e -q2/N If probability 0.5, q = sqrt ( ln(0.5)N ) = 1.18 x sqrt(N) = 1.18 x 2n/2 [ N = 2n ] Attacks on Random Oracle Model
- 21. Example : A cryptographichash function uses a digest of 64 bits. How many digests does Oscar need to create to find two messages with the same digest with the probability more than 0.5? Suppose, Oscar can test 220 messages per second it takes 1.18 × 212 seconds, or less than two hours k ≈ 1.18 x 2 n/2 ≈ 1.18 x 2 64/2 ≈ 1.18 x 2 32
- 22. ● Password Storage ●File Authenticity ● Digital Signature, guarantees that the message came from a said source ● Commitments: In a secure bidding, Alice wants to bid value x, but does not want to reveal the bid until the auction is over. Alice then computes h(x), and publicize it, which serves as her commitment. When bidding is over, then she can reveal x, and x can be verified using h(x) Application