Tags: python 

Rating: 4.0

from Crypto.Cipher import AES
from SocketServer import ThreadingMixIn
from BaseHTTPServer import HTTPServer, BaseHTTPRequestHandler
import sys
import random
import os

class Hasher:
def __init__(self):
self.aes = AES.new('\x00'*16)

def reset(self):
self.state = '\x00'*16

def ingest(self, block):
"""Ingest a block of 10 characters """
block += '\x00'*6
state = ""
for i in range(16):
state += chr(ord(self.state[i]) ^ ord(block[i]))

print(state.encode("hex"))
self.state = self.aes.encrypt(state)
print(self.state.encode("hex"))

def final_ingest(self, block):
"""Call this for the final ingestion.

Calling this with a 0 length block is the same as calling it one round
earlier with a 10 length block.
"""
if len(block) == 10:
self.ingest(block)
self.ingest('\x80' + '\x00'*8 + '\x01')
elif len(block) == 9:
self.ingest(block + '\x81')
else:
self.ingest(block + '\x80' + '\x00'*(8-len(block)) + '\x01')

def squeeze(self):
"""Output a block of hash information"""
result = self.state[:10]
self.state = self.aes.encrypt(self.state)
return result

def hash(self, s):
"""Hash an input of any length of bytes. Return a 160-bit digest."""
self.reset()
blocks = len(s) // 10
for i in range(blocks):
self.ingest(s[10*i:10*(i+1)])
self.final_ingest(s[blocks*10:])

return self.squeeze() + self.squeeze()

class HashHandler(BaseHTTPRequestHandler):
def do_GET(self):
if self.path in ['/favicon.ico', '/index.html']:
# Stop.
self.send_response(409)
return

try:
to_hash = self.path[1:].decode('hex')
except TypeError:
# Bad hex.
self.send_response(418)
return

if to_hash == GIVEN:
# Nice try.
self.send_response(451)
return

result = HASHER.hash(to_hash)
if result != TARGET:
# Wrong
self.send_response(400)
return
self.send_response(200)
self.end_headers()
self.wfile.write(FLAG)

class ThreadedHTTPServer(ThreadingMixIn, HTTPServer):
pass

# High-level solution
# ------------------------------------------------------------------------
# We basically find a collision for the last 6 bytes of the state.
# One is obtained forward starting with 10 random bytes and 6 null bytes
# Other one is obtained with 9 random bytes \x81 and the last 6 bytes of the state of the message we need a collision.
# This collision gives us the first block and third block of the collision.
# The second block can computed with a XOR.

# Code solution
def enc(v):
aes = AES.new('\x00'*16)
return aes.encrypt(v)

def xor(s1,s2):
return ''.join(chr(ord(a) ^ ord(b)) for a,b in zip(s1,s2))

forward = {}

# Building the Meet In The Middle forward lookup table
print "Forward ..."
for i in xrange(2**24):
if i % (2**16) == 0:
print i
aes = AES.new('\x00'*16)
v = os.urandom(10) + '\x00'*6
enc_ = aes.encrypt(v)
forward[enc_[-6:]] = v

# Find a match backward
print "Backward ..."
for j in xrange(2**40):
aes = AES.new('\x00'*16)
v = os.urandom(9) + '\xff\x77\x40\x56\x0a\x1d\x64' # 9 random bytes and 10th byte was computed so that it's \x81
dec = aes.decrypt(v)

if dec[-6:] in forward:
print "Found !"
print dec.encode("hex")
print v.encode("hex")
print forward[dec[-6:]].encode("hex")

first_block = forward[dec[-6:]]
first_block_enc = enc(forward[dec[-6:]])

second_block = xor(first_block_enc, dec)
second_block_enc = enc(dec)

last_block = xor(second_block_enc, "ef43cd0580d0491c117e7740560a1d64".decode("hex"))

print "Given"
HASHER = Hasher()
GIVEN = 'I love using sponges for crypto'
given = HASHER.hash(GIVEN)

print "Collision"
HASHER = Hasher()
collision = first_block[:10] + second_block[:10] + last_block[:9]
coll_hash = HASHER.hash(collision)

print "Collision sanity check"
print given.encode("hex")
print coll_hash.encode("hex")
print (coll_hash == given)

print "Solution !!!!"
print collision.encode("hex")

Original writeup (https://gist.github.com/HoLyVieR/790d19c294e138ebd9993ed029bd85ad).