*insert story / introduction about why it's called a paradox + use*
Birthday version
Question 1
What is the probability that 1 person has the same birthday as you?
Solution
Let be the event that someone has the same birthday as you and be the complementary event
The events are mutually exclusive =>
Let be the events that person does not have your birthday
Then
Reminder: if are independent events
Question 2
What is the probability that 2 out of people in a room share the same birthday?
Suppose the birthdays are distributed independently and uniformly
Solution
Let be the event that 2 people have the same birthday, let be the complementary event (no 2 people have the same birthday)
Event 1 = Person 1 is born =>
Event 2 = Person 2 is born on a different day than Person 1 =>
General case
Question 1
Instead of days we have
Question 2
Instead of days we have
Code examples
An useful approximation
From the Taylor approximation we know for
Apply for each event:
If we want to solve for knowing we take the =>
Finding a collision
Let be a hash function with
Let's denote
Algorithm
1. Choose random distinct messages in
2. Compute for
3. Look for If not found go to step 1
Example:
Consider the following hash function:
We make the following function to find the hashes:
We use it as follows:
Eliminating Storage Requirements with Pollard's Rho
While the above algorithm works to find a hash collision in time , it also requires storing hash values. As such, it represents a classic time-space tradeoff over the naive approach, which involves randomly selecting pairs of inputs until they hash to the same value. While the naive approach does not require any additional storage, it does have runtime .
However, there is a better approach combining the best of both worlds: constant storage requirements and runtime. This approach is based on Pollard's Rho algorithm, which is better-known for its application to solving discrete logarithms. The core insight behind the algorithm is that by the Birthday Paradox, we expect to encounter a hash collision after trying random inputs. However, it is possible to detect whether a collision has occurred without needing to store all of the inputs and hashes if the inputs are chosen in a clever way.
This is done by choosing the next input based on the hash of the previous input, according to the following sequence:
Where is our hash function and is a "sufficiently random" function which takes a hash value and produces a new. We define the composition of the functions to be.
By the Birthday Paradox, we expect that the sequence will have a collision (where for two distinct values ) after values. But once this occurs, then the sequence will begin to cycle, because .
Therefore, we can detect that a collision has occurred by using standard cycle-detection algorithms, such as !
And finally, we can locate the first place in the sequence where the collision occurred, which will let us determine what the colliding inputs to the hash function are. This is done by determining how many iterations apart the colliding inputs are, and then stepping together one iteration at a time until the collision occurs.
For Floyd's tortoise and hare, this is done by noting that when we found our collision after iterations, we were comparing . And because the sequence is cyclic, if the first colliding input is , then it collides with. So we define the new sequence , and step through the and sequences together until we find our collision!
This is implemented in the following code snippet.
Finally, there is a third algorithm for finding hash collisions in time, namely the based on Distinguished Points. While it does have additional storage requirements over Pollard's Rho, the main advantage of this algorithm is that it parallelizes extremely well, achieving runtime when run on processors.
Resources
- wiki entry
- wiki entry
- vsauce2 video
⋮
Event n = Person n is born on a different day than Person 1,...,n−1⇒⇒Pr(En)=365365−(n−1)
import hashlib
import random
from Crypto.Util.number import long_to_bytes, bytes_to_long
def small_hash(m, hash_bits):
'''
Arguments
m: bytes -- input
hash_bits: int -- number of bits of the hash
Returns:
{bytes} - hash of the message of dimension `hash_bits`
'''
assert hash_bits > 0, "no negative number of bits"
mask = (1 << hash_bits) - 1 # Mask of bits
t = hashlib.sha256(m).digest() # the hash in bytes
t = bytes_to_long(t)
t = t & mask # get the last 12 bits
return long_to_bytes(t)
def small_hash_colision(M_bits, T_bits):
'''
Arguments
M_bits: int -- dimension of the message space
T_bits: int -- dimension of the hash space
Returns:
{(bytes, bytes, bytes)} -- message1, message2, hash
or
{(b'', b'', b'')} -- if no collision found
'''
N = 1<<T_bits
print('Hash size: ', N)
# This is `s`
num_samples = 1 * isqrt(N)
num_samples += num_samples//5 + 1 # num_samples = 1.2 * isqrt(N) + 1
print(f'Making a list of {num_samples} hashes')
print(f'Probability of finding a collision is {same_birthday(num_samples, N)}')
m_list = []
t_list = []
# Make a list of hashes
for i in range(num_samples):
m = random.getrandbits(M_bits) # Get random message
#m = random.randint(0, M_bits-1)
m = long_to_bytes(m)
t = small_hash(m, T_bits) # Hash it
if m not in m_list:
m_list.append(m)
t_list.append(t)
# Check for collisionn
for i in range(len(t_list)):
for j in range(i+1, len(t_list)):
if t_list[i] == t_list[j]:
print('Collision found!')
return m_list[i], m_list[j], t_list[i]
else:
print('Collision not found :(')
return b"", b"", b""
M_bits = 30
T_bits = 20
m1, m2, t = small_hash_colision(M_bits, T_bits)
print(m1, m2, t)
print(small_hash(m1, T_bits) == small_hash(m2, T_bits))
# Hash size: 1048576
# Making a list of 1229 hashes
# Probability of finding a collision is 0.513213460854798
# Collision found!
# b'!\xafB\xc5' b'4F\xb6w' b'\x01y\xf7'
# True
# TODO:
# have the two hash functions used in this chapter be the same
from Crypto.Hash import SHA256
from Crypto.Util.number import bytes_to_long, long_to_bytes
from tqdm.autonotebook import tqdm
# bits in hash output
n = 30
# H
def my_hash(x):
x = bytes(x, 'ascii')
h = SHA256.new()
h.update(x)
y = h.digest()
y = bytes_to_long(y)
y = y % (1<<n)
y = int(y)
return y
# g
def get_message(r):
x = "Crypto{" + str(r) + "}"
return x
# f
def f(r):
return my_hash(get_message(r))
"""
initialization
This routine will find a hash collision in sqrt time with constant space.
"""
seed = 0
x0 = get_message(seed)
x = x0
y = f(x)
"""
detect collision
using Floyd / tortoise and hare cycle finding algorithm
expected number of iterations is ~ sqrt(pi/2) * 2^(n/2),
we run for up to 4 * 2^(n/2) iterations
"""
for i in tqdm(range(4 << (n//2))):
if f(x) == f(y):
break
x = f(x)
y = f(y)
y = f(y)
"""
locate collision
"""
x = x0
y = f(y)
for j in tqdm(range(i)):
if f(x) == f(y):
break
x = f(x)
y = f(y)
m1 = get_message(x)
m2 = get_message(y)
assert my_hash(m1) == f(x)
assert my_hash(m2) == f(y)
print("[+] seeds for messages: {}, {}".format(x, y))
print("[+] messages: {}, {}".format(m1, m2))
print("[+] collided hashes of messages: {}, {}".format(my_hash(m1), my_hash(m2)))
# 31% 40391/131072 [00:03<00:08, 10666.20it/s]
# 30% 12032/40391 [00:00<00:02, 13112.15it/s]
#
# [+] seeds for messages: 404842900, 254017312
# [+] messages: Crypto{404842900}, Crypto{254017312}
# [+] collided hashes of messages: 1022927209, 1022927209