HXP 2021 - Gipfel (Crypto)

Summary: Choosing the value of the prime modulus - 1 as the base in a pseudo Diffie Hellman key exchange scheme allows setting a shared value to 1. When this value is used as an exponent for a validation value and the construction of an AES key, it allows us to bypass verification and reduce the search space of AES decryption key.

Challenge Prompt

gipfel
by yyyyyyy
crypto baby
Difficulty estimate: easy - easy

Points: round(1000 · min(1, 10 / (9 + [109 solves]))) = 85 points

Description:
Hey, I heard you’re good with computers! So… Thing is, I forgot my password. Can you help??

Update: Due to popular request, we’ve reduced the proof-of-work difficulty a little bit.

Download:
gipfel-f1733d57c1257d22.tar.xz (2.1 KiB)

Connection (mirrors):
nc 65.108.176.66 1088

Attachment: challenge file

Solution

We are given the following script:

#!/usr/bin/env python3
from Crypto.Hash import SHA256
from Crypto.Cipher import AES
import signal, random
random = random.SystemRandom()

q = 0x3a05ce0b044dade60c9a52fb6a3035fc9117b307ca21ae1b6577fef7acd651c1f1c9c06a644fd82955694af6cd4e88f540010f2e8fdf037c769135dbe29bf16a154b62e614bb441f318a82ccd1e493ffa565e5ffd5a708251a50d145f3159a5

def enc(a):
    f = {str: str.encode, int: int.__str__}.get(type(a))
    return enc(f(a)) if f else a

def H(*args):
    data = b'\0'.join(map(enc, args))
    return SHA256.new(data).digest()

def F(h, x):
    return pow(h, x, q)

################################################################

password = random.randrange(10**6)

def go():
    g = int(H(password).hex(), 16)

    privA = 40*random.randrange(2**999)
    pubA = F(g, privA)
    print(f'{pubA = :#x}')

    pubB = int(input(),0)
    if not 1 < pubB < q:
        exit('nope')

    shared = F(pubB, privA)

    verA = F(g, shared**3)
    print(f'{verA = :#x}')

    verB = int(input(),0)
    if verB == F(g, shared**5):
        key = H(password, shared)
        flag = open('flag.txt').read().strip()
        aes = AES.new(key, AES.MODE_CTR, nonce=b'')
        print(f'flag:', aes.encrypt(flag.encode()).hex())
    else:
        print(f'nope! {shared:#x}')

# three shots, three opportunities
# to seize everything you ever wanted
# would you capture? or just let it slip?
signal.alarm(2021)
go()
go()
go()

The value of q is prime and the body of the go() function appears to implement a variant of the Diffie-Hellman key exchange scheme in which the shared base is randomly generated and not given to us. We are free to choose our own value of pubB as long as it is between 1 and q non-inclusive.

We can modify the script to print shared and F(g, shared**5) to debug this dynamically with some test values. On the first run, we try a random value (‘123’) for pubB, the values of shared looks unpredictable and so it’s not usable.

python gipfel/test.py
pubA = 0x10e3e39fb5da49959753ea84c2fdba763b91527bf1f5d3f21159363c103f5651ec774c6edddd69137afd9e86e84f40d03954aa44112303640c727b2c3c8927603a36f0198f647b8ef58401453764d9898ebae8b239ead0e45a187ff4c839b22
123
shared = 0x33163a2e4566d237dce2b4cbf8e5a94a585a2d16fea44b907a2880552760635f46966af68b2da59ff4611e67706b4a9e3a1c04792a7204c1cdaa35c99bf297841cbe3b85b208d79c133aa81ce2b2d1e0e07ca21215953291ed665f40195386c
verA = 0x4dc1a32b7e5a8232b632de5e25c683bea0fbad8a724324c641a2dcb74446131bd93af5d461a6a8e59d5ca7cf83843fdd6762e9060ae810d6e8fee78854e94f90021f5fb068c13b38ec1c8daa26ee90c4507bf53923ee47c92180d6377a417f
F(g, shared**5) = 0x1f1f7b72cf099141f0eefa19a73113d1e7fdd530be1deb5cc7f963fa887963f5880bd83df5a0ca40c9348f3efed412c504922f67054d339533ad178dc06127cefbb0fb4092de6f5ece1f15d29e81926631b03061dbba09e5c8ff592ff57e717

However, if we try q - 1 as the value for pubB, the shared value will always be computed to be 0x1. This means that the value of F(g, shared**5) will simply be computed to be the value of verA and we can pass verification to get the encrypted flag.

python gipfel/test.py
pubA = 0x3150f41b8a94bab0e11ee4c3a9e03f099fa4430814c4d7636376b20f599264c211d1042380c766b2fcd55ac3bddd3eb1a5033d840020a4706772fb5a559be27397584b7a2c337b27680ddf85f2c2f54eec674e1425b8b20405bacd9f7799189
0x3a05ce0b044dade60c9a52fb6a3035fc9117b307ca21ae1b6577fef7acd651c1f1c9c06a644fd82955694af6cd4e88f540010f2e8fdf037c769135dbe29bf16a154b62e614bb441f318a82ccd1e493ffa565e5ffd5a708251a50d145f3159a4
shared = 0x1
verA = 0x3ea37cda503d1d63aee5728f36225109431f193d5d6dd290a8f3e0280d83f355
F(g, shared**5) = 0x3ea37cda503d1d63aee5728f36225109431f193d5d6dd290a8f3e0280d83f355

The encryption key for the flag will be a random number between 0 and 1000000 will be prepended to the byte \x01. Thus, we can search for the right flag pattern hxp{ after obtaining the encrypted data locally.

A proof-of-work solver was provided so we simply utilised it in the exploit:

#!/usr/bin/env python

from pwn import *
import re

from Crypto.Hash import SHA256
from Crypto.Cipher import AES

# context.log_level = 'debug'

def enc(a):
    f = {str: str.encode, int: int.__str__}.get(type(a))
    return enc(f(a)) if f else a

def H(*args):
    data = b'\0'.join(map(enc, args))
    return SHA256.new(data).digest()

q = 0x3a05ce0b044dade60c9a52fb6a3035fc9117b307ca21ae1b6577fef7acd651c1f1c9c06a644fd82955694af6cd4e88f540010f2e8fdf037c769135dbe29bf16a154b62e614bb441f318a82ccd1e493ffa565e5ffd5a708251a50d145f3159a5


def brute_flag(fb):
    for password in range(10**6):
        key = H(password, 1)
        aes = AES.new(key, AES.MODE_CTR, nonce=b'')
        decrypt = aes.decrypt(fb)
        if b'hxp{' in decrypt:
            return decrypt
        if password % 100000 == 0 and password > 0:
            log.info('{}%'.format((password / 10**6) * 100))

pow_re = re.compile(r'^please give S such that sha256\(unhex\("(\w+)" \+ S\)\) ends with (\d+) zero bits \(see pow-solver\.cpp\)\.$')


def solve_pow(p):
    line = p.recvline().decode().strip()
    m = pow_re.match(line)
    prefix, bits = m.groups()

    log.info("Solving pow for prefix {} and {} bits.".format(prefix, bits))
    solver = process(["./gipfel/pow-solver", bits, prefix])
    suffix = solver.recvall().strip()
    log.success("Got suffix: {}".format(suffix))
    solver.close()
    p.sendline(suffix)


def main():
    # p = process(["python", "gipfel/vuln.py"])
    p = remote("65.108.176.66", 1088)
    solve_pow(p)

    pubA_line = p.recvline().decode()
    log.info(pubA_line)
    p.sendline(hex(q - 1).encode())

    verA_line = p.recvline().decode()
    verA = verA_line.split("=")[1].strip()
    log.info(verA_line)
    p.sendline(verA.encode())

    flag_line = p.recvline().decode()
    flag_bytes = bytes.fromhex(flag_line.split(":")[1].strip())
    log.success(flag_line)

    log.info("Bruteforcing key...")
    flag = brute_flag(flag_bytes)
    log.success("Flag: {}".format(flag.decode()))

    p.close()


if __name__ == '__main__':
    main()

Running the exploit gives us the flag after awhile. The longest time bottlenecks were the proof-of-work computation and the search for the right key.

vagrant@ubuntu-xenial:/vagrant/hxp/gipfel$ python exploit.py
[+] Opening connection to 65.108.176.66 on port 1088: Done
[*] Solving pow for prefix 37f3d460d77c3dd6 and 32 bits.
[+] Starting local process './gipfel/pow-solver': pid 3117
[+] Receiving all data: Done (17B)
[*] Process './gipfel/pow-solver' stopped with exit code 0 (pid 3117)
[+] Got suffix: b'0200000003f2a41a'
[*] pubA = 0x74498994c446fb5673b5a941f0cda711ef22c8b228eeaec6c7a1c315c948aeebfd8cadd1c3352c05e751be139807389430649f1db4a3bc75edecb91706df5427719544344108ab2dbea513cf202fe70d8dae2636d4709b126aa727b4997d98
[*] verA = 0x18eeaff89770d1771299a47e45562162f0ebb60a0297a1f3c3ce4eb431e3cb70
[+] flag: 929bc92d8abb3528be57d2c237aab1ab241c91df6a48a65e79cc509fdabf771d3a07e9a48dacbfa5
[*] Bruteforcing key...
[+] Flag: hxp{ju5T_k1ddIn9_w3_aLl_kn0w_iT's_12345}
[*] Closed connection to 65.108.176.66 port 1088
vagrant@ubuntu-xenial:/vagrant/hxp/gipfel$

Flag: hxp{ju5T_k1ddIn9_w3_aLl_kn0w_iT's_12345}