sponge.py

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")