ASIS CTF Finals 2020 Writeup

この大会は2020/12/12 0:00(JST)~2020/12/14 0:00(JST)に開催されました。
今回もチームで参戦。結果は442点で351チーム中43位でした。
自分で解けた問題をWriteupとして書いておきます。

Baby MD5 (PPC)

x_headから始まり、m回md5(hex)をした結果と、y_headから始まりn回md5(hex)をした結果が同じになるx, yを提示する必要がある。y_headは必ず"dead"で、16進数文字列になっていることも考えると、x_headから始まるxで(m-n)回md5(hex)をしたら、"dead"から始まる文字列になっていればよい。このときのdeadから始まる文字列がyになる。これを元にプログラムにする。

import socket
import re
from itertools import *
from string import *
from hashlib import *

def recvuntil(s, tail):
    data = ''
    while True:
        if tail in data:
            return data
        data += s.recv(1)

def md5_repeat(s, num):
    h = s
    for _ in range(num):
        h = md5(h).hexdigest()
    return h

s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
s.connect(('66.172.10.203', 2570))

data = recvuntil(s, '\n').rstrip()
print data
pattern = 'that (.+)\(X\)\[-6:\] = (.+) and len\(X\) = (.+)'
m = re.search(pattern, data)
alg = m.group(1)
h_tail = m.group(2)
length = int(m.group(3))

for c in product(printable, repeat=4):
    text = 'a' * (length - 4) + ''.join(c)
    if alg == 'md5':
        h = md5(text).hexdigest()
    elif alg == 'sha1':
        h = sha1(text).hexdigest()
    elif alg == 'sha224':
        h = sha224(text).hexdigest()
    elif alg == 'sha256':
        h = sha256(text).hexdigest()
    elif alg == 'sha384':
        h = sha384(text).hexdigest()
    elif alg == 'sha512':
        h = sha512(text).hexdigest()
    if h[-6:] == h_tail:
        print text
        s.sendall(text + '\n')
        break

data = recvuntil(s, '[Q]uit\n').rstrip()
print data

print 'B'
s.sendall('B\n')
data = recvuntil(s, '[Q]uit\n').rstrip()
print data

print 'C'
s.sendall('C\n')
data = recvuntil(s, '[Q]uit\n').rstrip()
print data

(m, n, x_head, y_head) = eval(data.split('\n')[0].split(' = ')[1])

for c in product(printable, repeat=4):
    x = x_head + ''.join(c)
    y = md5_repeat(x, m - n)
    if y.startswith(y_head):
        break

print 'R'
s.sendall('R\n')
data = recvuntil(s, ':  \n').rstrip()
print data
print x
s.sendall(x + '\n')
data = recvuntil(s, ': \n').rstrip()
print data
print y
s.sendall(y + '\n')
data = recvuntil(s, '\n').rstrip()
print data

実行結果は以下の通り。

Please submit a printable string X, such that sha1(X)[-6:] = ca9c8d and len(X) = 15
aaaaaaaaaaa2P49
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
+  hi powerful coders! Your mission is to find weird hash collision,   +
+  its baby level, so dont over-think please!!                         +
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
| Options:
|       [B]aby hash function
|       [C]onditions
|       [R]eport collision!
|       [Q]uit
B
def babymd5(m, n, x_head, y_head, x, y):
        if x.startswith(x_head) and y.startswith(y_head):
                for _ in range(m):
                        xhash = md5(x.encode('utf-8')).hexdigest()
                        x = xhash
                for _ in range(n):
                        yhash = md5(y.encode('utf-8')).hexdigest()
                        y = yhash
                if xhash == yhash:
                        return True
        return False

| Options:
|       [B]aby hash function
|       [C]onditions
|       [R]eport collision!
|       [Q]uit
C
| (m, n, x_head, y_head) = (253, 24, 'RGo', 'dead')
| Options:
|       [B]aby hash function
|       [C]onditions
|       [R]eport collision!
|       [Q]uit
R
| please send first string, x:
RGo05Jq
| please send second string, y:
deade6fb5659e840a21ab581aec4aa09
| Congrats! You find the collision!! the flag is: ASIS{MD5_c0L1iD!N9_iZ_4pProX1mA73lY_1.47*10^-29}
ASIS{MD5_c0L1iD!N9_iZ_4pProX1mA73lY_1.47*10^-29}