Cryptographic Hash Functions and Applications
This collection of images and text introduces topics such as pseudorandom permutations, MACs, hash functions, and cryptographic hash function applications. It covers concepts like the pigeonhole principle, hash collisions, collision-resistant hash functions, and keyed hash functions. The content delves into the formalization of collision resistance, key generation algorithms, and the definition of collision-resistance hash functions. It also explores the intuition behind collision-resistant hash functions and the complexities associated with finding collisions in hash functions.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Homework 2 Posted Due Friday, February 17that the beginning of class. Topics Pseudorandom Permutations (Weak) Pseudorandom Functions MACs Hashing 1
Cryptography CS 555 Topic 12: Cryptographic Hash Functions 2
Recap Authenticated Encryption Encrypt then Authenticate Enc?? = c,Mac?? c where c = Enc?? ? Today s Goals: Cryptographic Hash Functions Merkle-Damg rd Transform 3
Hash Functions H(x)=y Short Output: y Long Input: x 4
Pigeonhole Principle You cannot fit 10 pigeons into 9 pigeonholes 5
Hash Collisions By Pigeonhole Principle there must exist x and y s.t. H(x) = H(y) 6
Classical Hash Function Applications Hash Tables O(1) lookup* Good hash function should yield few collisions * Certain terms and conditions apply 7
Collision-Resistant Hash Function Intuition: Hard for computationally bounded attacker to find x,y s.t. H(x) = H(y) How to formalize this intuition? Attempt 1: For all PPT A, Pr ??,?1?= ?,? ?.? ? ? = ?(?) ????(?) The Problem: Let x,y be given s.t. H(x)=H(y) ??,?1?= (?,?) We are assuming that |x| > |H(x)|. Why? H(x)=x is perfectly collision resistant! (but with no compression) 8
Keyed Hash Function Syntax Two Algorithms Gen(1?;?) (Key-generation algorithm) Input: Random Bits R Output: Secret key s ??(?) (Hashing Algorithm) Input: key ? and message m 0,1 (unbounded length) Output: hash value ??(?) 0,1 ? Fixed length hash function ? 0,1 ? with ? > ? 9
Collision Experiment (????????,(?)) s x1,x2 ?????1 = ???2 ?? ?????? ??? ?????, (?)= 1 0 s = Gen(1?;?) Definition: Definition: (Gen,H) is a collision resistant hash function if ??? ? ? (negligible) s.t Pr ??? ?????, (?)=1 ?(?) 10
Collision Experiment (????????,(?)) s For simplicity we will sometimes just say that H (or Hs) is a collision x1,x2 Key is not key secret (just random) ?????1 = ???2 ?? ?????? ??? ?????, (?)= 1 resistant hash function 0 s = Gen(1?;?) Definition: Definition: (Gen,H) is a collision resistant hash function if ??? ? ? (negligible) s.t Pr ??? ?????, (?)=1 ?(?) 11
Theory vs Practice Most cryptographic hash functions used in practice are un-keyed Examples: MD5, SHA1, SHA2, SHA3 Tricky to formally define collision resistance for keyless hash function There is a PPT algorithm to find collisions We just usually can t find this algorithm 12
Weaker Requirements for Cryptographic Hash Target-Collision Resistance s,x x ????? = ??? ?? ?????? ??? ????????, (?)= 1 0 s = Gen(1?;?) ? 0,1? Question: Question: Why is collision resistance stronger? 13
Weaker Requirements for Cryptographic Hash Preimage Resistance (One-Wayness) s,? x ??? ??????????, (?)= 1 ????? = ? 0 ?? ?????? s = Gen(1?;?) ? 0,1 (?) Question: Question: Why is collision resistance stronger? 14
Merkle-Damgrd Transform Most cryptographic hash functions accept fixed length inputs What if we want to hash arbitrary length strings? Construction: (Gen,h) fixed length hash function from 2n bits to n bits ??(?1, ,??) = ? ? ? ?0? ?1 ?? 1 ?? 15
Merkle-Damgrd Transform Construction: (Gen,h) fixed length hash function from 2n bits to n bits ??(?) = 1. Break x into n bit segments x1,..,xd (pad last block by zeros if needed) 2. ?0= 0? (initialization) 3. For i = 1 to d+1 1. ??= ??? 1 ?i 4. Output ??+1 16
Merkle-Damgrd Transform Theorem: If (Gen,h) is collision resistant then so is (Gen,H) Proof: Show that any collision in Hs yields a collision in hs. Thus a PPT attacker for (Gen,H) can be transformed into PPT attacker for (Gen,h). Suppose that ??(?) = ??(? ) (note x and x may have different lengths) 17
Merkle-Damgrd Transform Theorem: If (Gen,h) is collision resistant then so is (Gen,H) Proof: Suppose that ??(?) = ??(? ) Case 1: |x|=|x | (proof for case two is similar) ?? ??(?) = ??+1= ??? ?? = ??(? ) = ??+1 = ??? ?? ?? ??=??? No Found collision Yes? ??? 1 ?? 1 = ??? 1 ?? 1 18
Merkle-Damgrd Transform Theorem: If (Gen,h) is collision resistant then so is (Gen,H) Proof: Suppose that ??(?) = ??(? ) Case 1: |x|=|x | (proof for case two is similar) ?? then we will find a collision If for some i we have ?? ?? ?? But x and x are different! 19
Next Class Read Katz and Lindell 5.3-5.4 + A.4 Appendix A.4 ( Birthday Problem ) HMACs + Generic Attacks on Hash Functions Work on Homework 2 20
