# Gits 2012 #19 – Crypto 250

Question: SuperSecure
250 Points

Summary: xor-chained sha256 and sha512

Our goal is easily shown by this piece of code:

if(str1.startswith(teamname) and not str1 == (str2)): return ((hashMessage(str1)==hashMessage(str2)))

We need to find a collision for hashMessage function and one string should start with team name.

In hashMessage, update is called for each 64byte block of the message and an accumulator (chain). The result is the sha256 hash of the final accumulator value, converted to string.

Update is rather straightforward too:

update(chain, m) = chain ^ sha512(m ^ chain) ^ sha512(m)

We can’t make collisions for sha512. But we can just swap m and m ^ chain in the second message! So,

h1 = update(chain, TeamName) = chain ^ sha512(TeamName ^ chain) ^ sha512(TeamName) h2 = update(chain, TeamName ^ chain) = chain ^ sha512(TeamName) ^ sha512(TeamName ^ chain)

Here’s keygen:

import sys from base64 import * from netbsd import *   def s2n(s): if not len(s): return 0 return int(s.encode("hex"), 16)   def n2s(n): s = hex(n)[2:].rstrip("L") if len(s) % 2 != 0: s = "0" + s return s.decode("hex")   name = sys.argv[1] TeamName = name.ljust(64)   s1 = TeamName s2 = n2s(s2n(TeamName) ^ 0x200)   s1, s2 = map(b64encode, [s1, s2]) print s1, s2 print check(name, s1, s2)
\$ py netbsdKG.py 'More Smoked Leet Chicken' TW9yZSBTbW9rZWQgTGVldCBDaGlja2VuICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIA== TW9yZSBTbW9rZWQgTGVldCBDaGlja2VuICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAiIA== True