exploit.py

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

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 "Before:", state.encode("hex")
    self.state = self.aes.encrypt(state)
    print "After:", 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()

def main():
    HASHER = Hasher()
    GIVEN = 'I love using sponges for crypto'
    TARGET = HASHER.hash(GIVEN)

    D='cba5d1139c347a3c6fc8afcfecd21a8d'.decode("hex")
    # AES(AES(a) xor b) xor c = D
    # AES(AES(a) xor b) = D xor c
    aes=AES.new("\x00"*16)
    print "Precalculating..."
    if 0:
        poss={}
        for i in xrange(2**24):
            if i%100000==0:
                print i,"/",2**24
            c=str(i)
            c=c+(16-len(c))*"\x00"
            D_xor_c="".join(chr(ord(q1)^ord(q2)) for q1, q2 in zip(D, c))
            preimage=aes.decrypt(D_xor_c)
            suffix=preimage[10:]
            poss[suffix]=(preimage, c)
        # AES(a) xor b is in poss set
        # Let's brute force a, and check if it has good suffix.
        for i in xrange(2**32):
            if i%100000==0:
                print i,"/",2**24
            a=str(i)
            a=a+(16-len(a))*"\x00"
            aes_a=aes.encrypt(a)
            suffix=aes_a[10:]
            if suffix in poss:
                print i, poss[suffix]
                break
    # Precalculated values...
    a=10935004 
    a=str(a)
    a=a+(16-len(a))*"\x00"
    aes_a=aes.encrypt(a)
    preimage='bI\xa5\xb2}*\xe5k\xbe\xad\xf3+\x86\\\x80\x07'
    c='10779991\x00\x00\x00\x00\x00\x00\x00\x00'
    b="".join(chr(ord(q1)^ord(q2)) for q1, q2 in zip(preimage, aes_a))

    text=a[:10]+b[:10]+c[:10]+"o"
    myhash=HASHER.hash(text)
    print "Hashes equal:", (TARGET)==(myhash)

    print "Input:", text.encode("hex")


main()