Balsn CTF 2019 - Collision (crypto)

0_writeup.md

In this challenge we see a password-verification program. The password is quite long:

assert 16 < len(passwd) < 70

The first few checks verify md5, sha1 and sha3_224 digests. Due to long password, it is unlikely to use them to recover the password. Then, three transformations applied aiming to "destroy" the password: exponentiation modulo a prime, iterated encryption with DES and AES. Though, it is easy to see that they are trivially invertible. For the final "destroyed" value, the omnihash tool is used, which checks the password using 72 different hash functions, including many CRC variants. We are given the digests of these functions in the hash.json file.

CRC functions are totally not cryptographically secure: they are affine functions. Therefore, we can efficiently use them to deduce information about the hashed value. One may try to use the definition of CRC functions as modular reductions in the ring of polynomials over GF(2) and use the Chinese Remainder Theorem to reconstruct the value. However, CRCs have lots of subtle details, like order of bits, polynomial modulus, length encoding (padding), constant addition. Figuring out all of these details would be a real pain.

Instead, we can directly use the fact that the functions are affine and construct a system of linear equations. An m-bit CRC function applied to n-bit string s can be expressed as CRC(s) = A ⨉ s ⊕ c, where A is an m ⨉ n matrix and c is an m-bit vector. The matrix columns correspond to evaluations of the CRC function on unit vectors and c = CRC(0). In this way we can reconstruct them given a blackbox oracle to the CRC function. Recovering s is reduced to solving the system of linear equations.

Note that we have to use known 8-byte prefix and 8-byte suffix. After that, the kernel of the linear system has dimension 10, meaning that if there is a solution, then there are exactly 1024 of them. This is a small amount and we can enumerate over all of them. The right one can be identified using one of strong hash functions given in the hash.json file.

The final password (hex):

c7d0425d8f844bd7c5fc59005ca6b56f12e971d32a82004dda88d3ad4766e75c ed502149347257ffb0cd8a99bdc39598d2107cbdd35b501257156b095da5f31d

The flag: Balsn{Th3_M0r3__7He_bEtT3r??}

1_main.py

#!/usr/bin/python3 -u

import codecs
import hashlib

from art import youShallNotPass
from lib import printflag


if __name__ == '__main__':
    passwd = input('Password: ')
    try:
        passwd = codecs.decode(passwd, 'hex')
        assert 16 < len(passwd) < 70
    except:
        print('Nope')
        exit(255)

    if hashlib.md5(passwd).hexdigest() != 'cd86c62d1c8d808a96e49511e0b79158':
        print(youShallNotPass)
        exit(255)

    print('Enjoy your flag :)')
    printflag(passwd)

2_lib.py

import hashlib
import subprocess
import json
from Crypto.Cipher import AES, DES
from Crypto.Util.number import bytes_to_long, long_to_bytes


def omnihash(x):
    ret = subprocess.check_output(['omnihash', '-jcs'], input=x)
    return json.loads(ret)[0][0]


def printflag(x):
    # Update August, 2004 (commit 40de8d): MD5 is broken...
    if hashlib.sha1(x).hexdigest() != '3a4a6c4047f9350493cdabcf719d8e4f3b3c1f2f':
        print('I said you shall not pass!!!')
        return False
    
    # Update Feb, 2017 (commit 56fcd9): Fxxk, SHA1 is broken too
    if hashlib.sha3_224(x).hexdigest() != 'c529d3db40ac50bf3b5c1957b7ef4e632f6fb34ae83b165caed6658d':
        print('Why do you keep trying to hack into my home???? Go away QAQQQQQQ!!!!!')
        return False
    
    # Update May, 2019 (commit c10d5a): Check all well-known hashes

    # Destroy the value
    p = int("""\
    6816b2bba5ad70478c1beadb176b9ab17cb172841b10277f538f9d837f2\
    2bdd807b970605c63859c739571cc535fd0c6879149b2d2eb676a182fd7\
    5ff343e75a22ce75c36a775157c34f17\
    """.replace(' ', ''), 16)
    x = bytes_to_long(x)
    x = pow(x, 31337, p)
    x = long_to_bytes(x)
    
    # Destroy again
    for _ in range(10):
        k = x[:16]
        aes = AES.new(k, AES.MODE_CFB, k)
        x = aes.encrypt(x[16:]) + k

    # Destroy one more time
    x = b'QAQQAQQQ' + x
    for _ in range(10):
        k = hashlib.sha256(x[:8]).digest()[:8]
        des = DES.new(k, DES.MODE_CFB, k)
        x = k + des.encrypt(x[8:])

    # Check
    x = x + b'OAOOAOOO'
    hash = omnihash(x)
    with open('hash.json') as f:
        target = json.load(f)
    if all(hash[k] == v for k, v in target.items()):
        with open('../flag.txt') as f:
            print(f.read())

3_hash.json

{
    "BLAKE2B512": "ea79779358bda662d24c2d28ec0c3b810848302687b5665d0551265081331288ce2f8b2763e9a31cfaa52ef47a602b6c14e89a1025434c16fd5896da2d013eb0",
    "BLAKE2S256": "6ea2c8f7806c003125213b7cdbf2074b766180d2c58e2a55f36f9c9c3022ae8f",
    "BLAKE2b": "ea79779358bda662d24c2d28ec0c3b810848302687b5665d0551265081331288ce2f8b2763e9a31cfaa52ef47a602b6c14e89a1025434c16fd5896da2d013eb0",
    "BLAKE2s": "6ea2c8f7806c003125213b7cdbf2074b766180d2c58e2a55f36f9c9c3022ae8f",
    "CRC-16": "0x4a58",
    "CRC-16-BUYPASS": "0x6af0",
    "CRC-16-DDS-110": "0x48fc",
    "CRC-16-DECT": "0x2419",
    "CRC-16-DNP": "0x9d58",
    "CRC-16-EN-13757": "0x4d2e",
    "CRC-16-GENIBUS": "0x45fd",
    "CRC-16-MAXIM": "0xb5a7",
    "CRC-16-MCRF4XX": "0x67b3",
    "CRC-16-RIELLO": "0x9ece",
    "CRC-16-T10-DIF": "0xec3c",
    "CRC-16-TELEDISK": "0xc82c",
    "CRC-16-USB": "0x3556",
    "CRC-24": "0x61059d",
    "CRC-24-FLEXRAY-A": "0xf397e7",
    "CRC-24-FLEXRAY-B": "0xdd6f70",
    "CRC-32": "0x9609704aL",
    "CRC-32-BZIP2": "0x50d40806L",
    "CRC-32-MPEG": "0xaf2bf7f9L",
    "CRC-32C": "0xf1dbb20eL",
    "CRC-32D": "0xfcc86807L",
    "CRC-32Q": "0x9c13e09L",
    "CRC-64": "0xb434f60b0a312231L",
    "CRC-64-JONES": "0xc1a828859dc5cca2L",
    "CRC-64-WE": "0xa73a797a702a9d81L",
    "CRC-8": "0xd2",
    "CRC-8-DARC": "0x87",
    "CRC-8-I-CODE": "0x5e",
    "CRC-8-ITU": "0x87",
    "CRC-8-MAXIM": "0xb1",
    "CRC-8-ROHC": "0x4b",
    "CRC-8-WCDMA": "0x44",
    "CRC-AUG-CCITT": "0x643e",
    "CRC-CCITT-FALSE": "0xba02",
    "GIT-BLOB": "623a652aa849645e37e27583b4686eb53727edb1",
    "GIT-COMMIT": "a3c12b0d72a7ba07a99fd069af7c04612999ff8a",
    "GIT-TAG": "1328ff8710ff34f9fef1b982894f44cf81d74d10",
    "JAMCRC": "0x69f68fb5L",
    "KERMIT": "0x4e2e",
    "LENGTH": "91",
    "MD4": "cc6ddaafe37274d514ea0e6026235b02",
    "MD5": "4a254cb1e5a266d44eeb923bf2135e63",
    "MD5-SHA1": "4a254cb1e5a266d44eeb923bf2135e6339cb6d6bf082ad0283b3b07991b50de7c087db8c",
    "MODBUS": "0xcaa9",
    "POSIX": "0xf6273a4fL",
    "RIPEMD160": "511e1ad8a02b04e5a017b1c6250695a999f98399",
    "SHA1": "39cb6d6bf082ad0283b3b07991b50de7c087db8c",
    "SHA224": "ca2de7bcf59bc523af5bfc3d14cfa15e9de732742e20785b5f8e1c0b",
    "SHA256": "821d0319b4d80a89af03ff7df5bb7aac56363c38000273acb7e6a2858d3267b5",
    "SHA3-224": "12785de06107874d20e1b75e3efa367c00e6704b532854720616d45a",
    "SHA3-256": "2836991a2e289d04af9f9366ae0983c23e0b4f6c0597d56caf5525348c1ae51a",
    "SHA3-384": "19542c695041c5acec2ff04fe033536e41f29138a65a12a76d7f122ae5b1a6ce3cbdebc0a44c24c0e2105f7a3435ad1e",
    "SHA3-512": "6accef14e12441918be765b545ba457e9809be1515130d5d7c41df82e976fceb2c3adaba0bee5f5c81fe93ffad9b31a9c3308432d0cec7645e4a3afaf1d7aaf3",
    "SHA384": "e86e0f699f2511e6dd4798762534274204b570a1d6f771b4c9a8715dcab245aaff0a397a905d3625ef1d1d003243a51b",
    "SHA3_224": "12785de06107874d20e1b75e3efa367c00e6704b532854720616d45a",
    "SHA3_256": "2836991a2e289d04af9f9366ae0983c23e0b4f6c0597d56caf5525348c1ae51a",
    "SHA3_384": "19542c695041c5acec2ff04fe033536e41f29138a65a12a76d7f122ae5b1a6ce3cbdebc0a44c24c0e2105f7a3435ad1e",
    "SHA3_512": "6accef14e12441918be765b545ba457e9809be1515130d5d7c41df82e976fceb2c3adaba0bee5f5c81fe93ffad9b31a9c3308432d0cec7645e4a3afaf1d7aaf3",
    "SHA512": "62074634d716800b66386e0e10a601a21eedcc7fcd4d847692cf0cb9d3cdc469dbb7cbd53be4b5d5d91fdc20edf1ab1c2abe8678f04055f3ef450561771f37b1",
    "SHA512-224": "091f4443f53089fbc66bc32caf77be0090a5188a0b9eaf5100057142",
    "SHA512-256": "4b37d93916d0a2e1a0a75481049b43942f127ed33ad58288f3be555b11ae8fb3",
    "SHAKE128": "d7ae67597dc6cd63c303f59aad1151d8",
    "SHAKE256": "7bba948c75cfc3570b76772ea9d6011d150beda285c7a3253ea856253b5a0646",
    "SM3": "d5e3c17e576e22ce7797e4cd946e4f9f3b48ff9da3bf0c94a48235702c1d57cb",
    "WHIRLPOOL": "343a45063c39bf2cb95bc689744c10ce70e740b38df1c985ce5fb610b80bd9ca973d7872278dc92238a90ca2030f3c2c6129127486bb91ce82068cb0a1636e81",
    "X-25": "0x984c",
    "XFER": "0x8244182bL",
    "XMODEM": "0x396"
}

4_solve.py

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

from __future__ import print_function, division

from sage.all import *

import subprocess, json, os
from subprocess import PIPE

if not os.path.exists("cache"):
    os.mkdir("cache")

def tobin(x, n):
    return tuple(ZZ(x).digits(2, padto=n)[::-1])

def frombin(v):
    return int("".join(map(str, v)), 2)

def omnihash(x):
    """All affine funcs concatenated"""
    # cache the result for reruns
    f = "cache/%s" % x.encode("hex")
    if not os.path.exists(f):
        res = subprocess.Popen(['omnihash', '-jcs'], stdin=PIPE, stdout=PIPE)
        res, _ = res.communicate(x)
        with open(f, "w") as fd:
            fd.write(res)
    return parse(open(f).read())

def parse(res):
    res = json.loads(res)
    while not isinstance(res, dict):
        res = res[0]
    h = ""
    for k in sorted(res):
        if k.startswith("CRC") or \
           k in "X-25 XMODEM MODBUS POSIX JAMCRC KERMIT XFER":
            # assume 64-bit value by default
            # just to reduce dimension,
            # we can hint the actual size
            t = res[k].lstrip("0x").rstrip("L").zfill(16)
            if "-8" in k: t = t[-2:]
            if "-16" in k: t = t[-4:]
            if "-24" in k: t = t[-6:]
            if "-32" in k: t = t[-8:]
            if "CIT" in k: t = t[-4:]
            h += t
    return h

# 75 = size(p)
# 91 matches the omnihash Length field
SHA256_HASH = "821d0319b4d80a89af03ff7df5bb7aac56363c38000273acb7e6a2858d3267b5"
FLAG_SHA1 = "3a4a6c4047f9350493cdabcf719d8e4f3b3c1f2f"
MSG_BYTES = 75 + 8 + 8
MSG_BITS = MSG_BYTES * 8
HASHLEN = len(omnihash("qwe")) * 4

def hash2vec(h):
    return vector(GF(2), tobin(int(h, 16), HASHLEN))

def vec2str(vec):
    assert len(vec) % 8 == 0
    s = [chr(frombin(vec[i:i+8])) for i in xrange(0, len(vec), 8)]
    return "".join(s)

def str2vec(s):
    v = ()
    for c in s:
        v += tobin(ord(c), 8)
    return vector(GF(2), v)

def hashvec(vec):
    assert len(vec) == MSG_BITS
    return hash2vec(omnihash(vec2str(vec)))


# iterate DES 10 times on QAQQAQQQ
prefix = "5a208546900315b4".decode("hex")
suffix = "OAOOAOOO"

target_hash = parse(open("hash.json").read())

eqs = []

# the constant part
c0 = hashvec([0] * MSG_BITS)


target = hash2vec(target_hash)
# remove constant part
target += c0
# account suffix
target += hashvec([0] * ((MSG_BYTES - 8) * 8) + list(str2vec(suffix))) + c0
# account prefix
target += hashvec(list(str2vec(prefix)) + [0] * ((MSG_BYTES - 8) * 8)) + c0

# use the black-box oracle to recover the matrix
for i in xrange(len(prefix), MSG_BYTES-len(suffix)):
    for j in xrange(8):
        s = [0] * MSG_BITS
        s[i*8 + j] = 1
        eqs.append(hashvec(s))
    print("byte", i, "done")

mat = matrix(GF(2), eqs).transpose()
print(mat.nrows(), "x", mat.ncols(), ":", mat.rank())
print("kernel dimension:", mat.ncols() - mat.rank())

import hashlib
base = mat.solve_right(target)
# iterate over all solutions
# get the right one by com
for z in mat.right_kernel():
    s = prefix + vec2str(base + z) + suffix
    h = hashlib.sha256(s).hexdigest()
    if h == SHA256_HASH:
        assert omnihash(s) == target_hash
        print("got THE solution!")
        print(repr(s))
        break
else:
    quit(print("Fail"))

# use sage -sh to install pycrypto
from Crypto.Cipher import AES, DES
from Crypto.Util.number import bytes_to_long, long_to_bytes

# invert DES transformations
s = s[8:-8]
k = 'QAQQAQQQ'
ks = []
for _ in range(10):
    k = hashlib.sha256(k[:8]).digest()[:8]
    ks.append(k)
for k in ks[::-1]:
    des = DES.new(k, DES.MODE_CFB, k)
    s = des.decrypt(s)

print(repr(s))

# invert AES transformations
for _ in range(10):
    k = s[-16:]
    s = s[:-16:]
    aes = AES.new(k, AES.MODE_CFB, k)
    s = aes.decrypt(s)
    s = k + s

print(repr(s))

p = 0x6816b2bba5ad70478c1beadb176b9ab17cb172841b10277f538f9d837f22bdd807b970605c63859c739571cc535fd0c6879149b2d2eb676a182fd75ff343e75a22ce75c36a775157c34f17
d = int(inverse_mod(31337, p-1))
s = bytes_to_long(s)
s = pow(s, d, p)
s = long_to_bytes(s)
print("Password hex:", s.encode("hex"), repr(s), sep="\n")
assert hashlib.sha1(s).hexdigest() == FLAG_SHA1

open("password", "w").write(s.encode("hex") + "\n")
os.system("cat password | nc collision.balsnctf.com 5451")