Create a gist now

Instantly share code, notes, and snippets.

@pdaian /collisions.py Secret
Last active Mar 25, 2017

What would you like to do?
SHA256 short ID collision mining tool (unoptimized)
# Lots of code stolen from https://raw.githubusercontent.com/Simmesimme/cry-hash/master/03/collisions.py
import hashlib, random, time
from string import digits, ascii_uppercase, ascii_lowercase
from itertools import product
from multiprocessing import Pool
chars = digits + ascii_uppercase + ascii_lowercase
# Define our f(x), as in the blog post
def get_truncated_hash(message, k, prefix):
return hashlib.sha256(prefix + message).hexdigest()[:k * 2]
# Birthday attack (https://en.wikipedia.org/wiki/Birthday_attack)
def simple_birthday(k, prefix):
hash_table = dict()
for n in range(1, 200):
for comb in product(chars, repeat=n):
s = ''.join(comb)
hash = get_truncated_hash(s, k, prefix)
if hash in hash_table:
if hash_table[hash] != s:
print_results(s, hash_table[hash], hash, k, prefix, "birthday")
return
else:
hash_table[hash] = s
print "fail"
# Floyd's algorithm (https://en.wikipedia.org/wiki/Cycle_detection)
def floyd(k, prefix, initial):
x0 = initial
m0 = None
m1 = None
turtle = get_truncated_hash(x0, k, prefix)
hare = get_truncated_hash(turtle, k, prefix)
while turtle != hare:
turtle = get_truncated_hash(turtle, k, prefix)
hare = get_truncated_hash(get_truncated_hash(hare, k, prefix), k, prefix)
pre_period_length = 0
turtle = x0
while turtle != hare:
m0 = turtle
turtle = get_truncated_hash(turtle, k, prefix)
hare = get_truncated_hash(hare, k, prefix)
pre_period_length += 1
if pre_period_length is 0:
print "Failed to find a collision: x0 was in a cycle!"
return
period_length = 1
hare = get_truncated_hash(turtle, k, prefix)
while turtle != hare:
m1 = hare
hare = get_truncated_hash(hare, k, prefix)
period_length += 1
print_results(m0, m1, get_truncated_hash(m0, k, prefix), k, prefix, "floyd")
# Brent's algorithm (https://en.wikipedia.org/wiki/Cycle_detection)
def brent(k, prefix, initial):
x0 = initial
m0 = None
m1 = None
turtle = x0
hare = get_truncated_hash(turtle, k, prefix)
power = period_length = 1
while turtle != hare:
if power == period_length:
turtle = hare
power *= 2
period_length = 0
hare = get_truncated_hash(hare, k, prefix)
period_length += 1
pre_period_length = 0
turtle = hare = x0
for i in range(period_length):
hare = get_truncated_hash(hare, k, prefix)
while turtle != hare:
m0 = turtle
m1 = hare
turtle = get_truncated_hash(turtle, k, prefix)
hare = get_truncated_hash(hare, k, prefix)
pre_period_length += 1
if pre_period_length is 0:
print "Failed to find a collision: x0 was in a cycle!"
return
print_results(m0, m1, get_truncated_hash(m0, k, prefix), k, prefix, "brent")
# Pretty print any collisions we do find
def print_results(m0, m1, hash, k, prefix, method):
print "Message A:", prefix + m0
print "Message B:", prefix + m1
print "Same hash:", hash
print method
print time.time()
# For measurement purposes
print time.time()
# Warm up with a 4-byte simple Birthday attack
simple_birthday(4, "Perhaps. ")
# Spawn three processing running Brent's, three running Floyd's with different intiial vectors
# (so they search different graphs)
def proc_wrapper(initial):
# Any initial value less than 7 spawns Floyd's, otherwise Brent's (can use negative values)
# (just to keep it simple)
if int(initial) < 7:
return floyd(8, "Perhaps. ", initial)
return brent(8, "Perhaps. ", initial)
if __name__ == '__main__':
print time.time()
# Spawn 6 processes and go!
p = Pool(6)
p.map(proc_wrapper, ["1", "2", "3", "8", "9", "10"])
michaeljs1990 commented Jun 15, 2016 edited

i'm confused by Floyd's algorithm as used here. Can you really encounter a hash cycle as line 47-51 seems to try and determine?

Edit: as usual just being dumb. Took a little more time to see what is actually going on in these functions and it makes sense now.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment