Skip to content
{{ message }}

Instantly share code, notes, and snippets.

# pdaian/collisions.py Secret

Last active Nov 28, 2018
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.
to join this conversation on GitHub. Already have an account? Sign in to comment