HashFunction.md (2061B)
1 # Hash Function 2 3 Ch. 5 4 5 **Definition:** A hash function is a function f(k) that takes a key value k (x.r = k where x is an object) and outputs a natural number. 6 7 f : K -> N where K is the set of all possible keys and N is the natural numbers. 8 9 Oftentimes we also want to state that the set of valid outputs (image of f) is from 0 to m-1 where m is the length of the array we are using to store the objects of the given hash value. 10 11 ### n-bit hash functions 12 13 **Definition:** n-bit hash functions are hash functions such that their image is the natural numbers from 0 to 2^n-1. 14 15 These hash function can then map to all permuations of bits with a length of n. 16 17 ### Important aspects of the hashing function 18 19 1. Speed 20 2. One-way 21 3. Deterministic 22 4. Uniform 23 24 Speed - this means the time to compute the hash for the inputs is generally fast 25 26 One-way - this means it is hard to go the opposite direction namely from N -> K 27 28 Deterministic - this means for the same input the output should always be the same 29 30 Uniform - the distribution, with respect to K, should be roughly uniform across the image of the function - [0, m-1] 31 32 ### Perfect 33 34 A hash function is perfect if for all valid inputs, there are no collisions (one-to-one). 35 36 $f:K \to N$ is a perfect hash function if 37 $\forall x,y\in K, f(x) \neq f(y) \text{ where } y \neq x$ 38 39 ## Cryptographic hash functions 40 41 The above is discussing hash functions, primarily in the context of [hashtables](HashTable.md), but expectations differ when using hash functions for cryptography. 42 43 ### Requirements for a good cryptographic hash function 44 45 1. Deterministic 46 2. Any size input results in a fixed size output 47 3. Preimage resistance 48 - Given y such that hash(x) = y it shouldn't be reasonable to find x. 49 4. 2nd preimage resistance 50 - Given x,y such that hash(x) = y it shouldn't be reasonable to find x' such that hash(x') = y. 51 5. Collision resistance 52 - It isn't reasonable to find x != z such that hash(x) = hash(z) 53 - This was the broken expectation that led to sha-1 and md5 being considered insecure