# Information security corona excersises
## Hash functions 1:
### Given:
- hash function with a hash value of $n$ bits (e.g. 128 bts)
- limited storage capacity ($N_1$ hash values), e.g. 4TB
- Assuming $N_1 << 2^{(n/2)}$

### Question:
- How many hash computations are required to find two messages with identical hash values with a given probability P (e.g. 95%)?
- Compute this with the given valeus
- Assume a modern PC can compute 10 million hash values per second, how much time would be required?

### Answer:

2.2.3: HashMac Slide 11:
- Probability of having 2 messages from a group of $k$ messages with the same hash values is: $P(N,k)=1–N!/((N –k)! N^k)$
- Approx = $P(N,k) = 1 - exp(-k²/(2N))
- -> from which $k ≈ -N^{1/2} ln(1–P(N,k)$

$N = 2^n$ for hash values with $n$ bits

Thus:
- N = $2^{128}$
- k = -(2^{128}^{1/2}*ln(1-P(N,k)))
- Given: P(N,k) = 0.95
- ln(1-P(N,k)) ~= -3 (-2.9957)
- k = 3* N^{1/2} = 3* 2^{128/2} = 3* 2^{64}
Storage ~= 2^38
Total req met 95% ~= 2^90

2^38 hashes -> 2^38/2^128 different hashes
1 new -> check if any match chance of 'collision' = 2^38/2^65

### Solution:
- Says we have N1 precomputed (N1 ~= 2^{38})
- Then we have N possible hashes (N ~=2^{128})
- N - N_1 not precomputed
- P_0(N_2, N_1, N): probability that all N_2 hashes have NOT been precomputed = (C_0^{N_1} * C_{N_2}^{N-N_1}) /C_{N_2}^{N} = (N-N_1)*(N-N_2)!/(N!(N-N_1-N_2)!) = PI_{k=0}^{N_1-1} (N-N_2 - k) /(N -k)
- = PI_{k=0N_}^{N_1-1}(1 - N_2/(N-k)) =(N_1 << N) (1-N_2/N)^{N_1}
- ~= (e^{-N_2/N}^{N_1}) ~= e^{N_1*N_2/N}
- P_0 = 0.05 => N2 = N/N_1 (ln(1/P_0) = 3*2^{90} ~= 3*10^27
- ~= 10^12 years