Proj X10: The Rho Method (30 pts)
Background
The Rho method
is used to find
hash collisions without requiring
a lot of RAM. The idea is to keep
hashing the result of the previous
hash operation, the same way you do
when calculating password hashes with
many rounds.
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
Any computer with Python 2.7.
Calculating a MD5 Hash
In Python, execute this code,
as shown below.
import hashlib
print hashlib.new('md5', "a").hexdigest()
The md5 hash appears,
starting with 0cc,
as shown below.
Checking with an online MD5 calculator
shows that this hash is correct,
as shown below.
Truncating the Hash
To make a very simple case, we'll
keep only the right two characters
of the hash.
In Python, execute this code,
as shown below.
import hashlib
print hashlib.new('md5', "a").hexdigest()[-2:]
The result is 61,
the last two characters in the hash,
as shown below.
Iterated Hashing
Now we'll repeat the hash function many times.
There are 256 possible hash values, so you might
expect the sequence to go for 100 or more values
without repeating.
In Python, execute this code,
as shown below.
import hashlib
h = "a"
for i in range(50):
h = hashlib.new('md5', h).hexdigest()[-2:]
print h,
Adjusting the width of the window makes it easy
to see when the values start repeating,
as shown below.
Challenge X12.1: Different Starting Value (5 pts)
Start the truncated hash you used above with an
initial string of "password" instead of "a".
Enter the first repeated hash value
into the form below
to record your success.
X12.1: Recording Your Success (5 pts)
Use the form
below to record your score in Canvas.
Challenge X12.2: Three Characters (10 pts)
Keep the last three characters of the MD5 hash.
Use an initial string of "password".
Enter the first repeated hash value
into the form below
to record your success.
X12.2: Recording Your Success (10 pts)
Use the form
below to record your score in Canvas.
Challenge X12.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".
Start the truncated hash you used above with an
initial string of "password" instead of "a".
Enter the first repeated hash value
into the form below
to record your success.
X12.3: Recording Your Success (15 pts)
Use the form
below to record your score in Canvas.
Posted 2-26-19