Spam and Flags CTF 2019 Teaser - QuadHash

1_multicollision.py

#-*- coding:utf-8 -*-

from common import *


def extend(alg, prefhashes):
    if alg == 0:
        prefhash = prefhashes[alg]
        table = {}
        seen = set()
        while True:
            s = gen()
            if s in seen: continue
            seen.add(s)

            h = mdhash_blocks(s, alg, prefhash)
            if h in table:
                sb = table[h]
                return s, sb, (h,)
            else:
                table[h] = s

    pools = [
        {prefhashes[alg]: ()}
    ]
    while True:
        pool2 = {}
        # find one
        for h, s in pools[-1].items():
            break

        ta, tb, loprefhashes = extend(alg-1, prefhashes)
        for h, s in pools[-1].items():
            for t in (ta, tb):
                hx = mdhash_blocks(t, alg, h)
                if hx in pool2:
                    ha, ta = pool2[hx]
                    hb = h
                    tb = t

                    sa = [ta]
                    sb = [tb]
                    while len(pools) > 1:
                        ha, ta = pools[-1][ha]
                        hb, tb = pools[-1][hb]
                        sa.append(ta)
                        sb.append(tb)
                        pools.pop()
                    return "".join(sa[::-1]), "".join(sb[::-1]), loprefhashes + (hx,)

                else:
                    pool2[hx] = h, t
        pools.append(pool2)
        prefhashes = loprefhashes
        if alg >= 2:
            print "===" * (3-alg), len(pools)


s1, s2, prefhashes = extend(3, CS)
open("col1", "w").write(s1)
open("col2", "w").write(s2)
print s1, "%08x %08x %08x %08x" % (mdhash_blocks(s1, 0, CS[0]), mdhash_blocks(s1, 1, CS[1]), mdhash_blocks(s1, 2, CS[2]), mdhash_blocks(s1, 3, CS[3]))
print s2, "%08x %08x %08x %08x" % (mdhash_blocks(s2, 0, CS[0]), mdhash_blocks(s2, 1, CS[1]), mdhash_blocks(s2, 2, CS[2]), mdhash_blocks(s2, 3, CS[3]))
print " ".join("%08x" % h for h in prefhashes)

# 11 minutes
# SaF{h3y_sMAlL_inNEr_sT4Te_i5_w0rSE_w1th_enCRYpt1On}

common.py

#-*- coding:utf-8 -*-

from random import *
import ctypes

lib = ctypes.cdll.LoadLibrary("./problem.so")

def mdhash_alg(s, alg):
    return lib.hash_full(s, len(s), alg)

CS = 0x67452301, 0xefcdab89, 0x98badcfe, 0x10325476

def mdhash_block(s, alg, c):
    # assert len(s) == 64
    return lib.hash_block(s, c, alg)

def mdhash_blocks(s, alg, c):
    assert len(s) & 63 == 0
    return lib.hash_blocks(s, len(s), c, alg)


N1 = 9
N2 = 2
S1 = "apple, cider, elite,".split()
S2 = "bear, deer,".split()


def pregen():
    res = []
    for i in xrange(N1):
        res.append(choice(S1))
    for i in xrange(N2):
        res.append(choice(S2))
    shuffle(res)
    return "".join(res)

print "pregen..."
pool = list({pregen() for i in xrange(2**22)})
print "done"

def gen():
    return choice(pool)