«

»

Jan
30

Gits 2012 #19 – Crypto 250

Question: SuperSecure
250 Points
Use your team name and generate a valid answer. (File)

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

2 comments

  1. rockosov says:

    good WriteUp & keygen! May be, you will post solution of Crypto400 (about modified Diffie-Hellman algorithm)?

  2. hellman says:

    Thx! Yes, I will :)

Leave a Reply to rockosov Cancel reply

Your email address will not be published.

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>