C 106: The Rho Method (30 pts)

Background

In this project, we won't conserve RAM, but just find cycles in hash functions.

If you hash a starting value, and then hash that hash, and repeat this process, you don't keep getting different numbers forever. Eventually you get a repeated value, and after that all further values are repeats, going in a loop, as shown below.

Figure from Serious Cryptography

What You Need

Calculating a MD5 Hash

import hashlib
print(hashlib.new('md5', "a".encode('ascii')).hexdigest())

Checking with an online MD5 calculator shows that this hash is correct, as shown below.

Truncating the Hash

In Python, execute this code, as shown below.

import hashlib
print(hashlib.new('md5', "a".encode('ascii')).hexdigest()[-2:])

Iterated Hashing

In Python, execute this code, as shown below.

import hashlib
h = "a"

for i in range(50):
  h = hashlib.new('md5', h.encode('ascii')).hexdigest()[-2:]
  print(h, end = ' ') 

C 106.1: Different Starting Value (5 pts) Start the truncated hash you used above with an initial string of "password" instead of "a". The first repeated hash value is the flag.

C 106.2: Three Characters (10 pts) Keep the last three characters of the MD5 hash. Use an initial string of "password". The first repeated hash value is the flag.

C 106.3: 32-bit Hash (15 pts) Keep the last eight characters of the MD5 hash (a total of 32 bits). Use an initial string of "password". The first repeated hash value is the flag.