MeePwn CTF 2017: |\/|/-\T|-| (100)

Tue 18 July 2017 · 2 min read

We are given a file, hack.py, which looks as follows.

from Crypto.Util.number import *
from hashlib import md5

flag = "XXX"
assert len(flag) == 4
pad = bytes_to_long(md5(flag).digest())

hack = 0

for char in flag:
    hack+= pad
    hack*= ord(char)

print hack
print pad
print hack % pad
#hack = 64364485357060434848865708402537097493512746702748009007197338675
#flag_to_submit = "MeePwnCTF{" + flag + "}"

Looking at the loop, hack will be like \(abcdx + bcdx + cdx + dx\), with \(x\) is the value of pad. The value of hack is not quite long. Factoring hack leads to 13 prime factors (11 distincts prime factors). We can search which one is \(x\) by brute-force, and then try to solve the remaining equation.

After dividing hack with \(x\), the remaining value will be in a form like \(abcd + bcd + cd + d\). We can find a proper factor of the remaining equation, and then substract it with 1, and the remaining value will in a form like \(abc + bc + c\). This means we can recursively do this and it will be the correct sequence if we can make it 0 and MD5(flag) is the same as our candidate padding. We will use DFS to recursively find the candidate.

Here is the Python script to find the value of flag:

import string
from Crypto.Util.number import *
from hashlib import md5

primes = [3,3,5,5,7,107,487,607,28429,29287,420577267963,3680317203978923,1002528655290265069]
hack = 64364485357060434848865708402537097493512746702748009007197338675
flen = 14
total = 1

for p in primes:
    total = total * p
assert(hack == total)

mask = 2 ** len(primes)
cand = []
for i in range(mask):
    q = 1
    for j in range(len(primes)):
    if ((i & (1<<j)) != 0):
        q = q * primes[j]

    if (2 ** 120 <= q and q <= 2 ** 128):
    cand.append(q)

def check(d, t, a, h):
    if d == 0 and t == 0:
    flag = "".join([chr(c) for c in a])
    if (bytes_to_long(md5(flag).digest()) == h):
        print(flag)
    return
    if t == 0:
    return

    if (d,t) in vis:
    return

    vis.add((d,t))


    for c in string.printable:
    x = ord(c)
    if t % x == 0:
        check(d-1, (t // x) - 1, [x] + a, h)

for pad in cand:
    t = hack // pad
    vis = set()
    check(flen, t, [], pad)

Flag is: MeePwnCTF{d0y0ul1keM@TH?}

Related Posts