Zenn
🔥

TAMUctf 2023 に参加しました

2023/05/03に公開
CTF
idea

結果

チーム参加。147位/609チーム

解けた問題

crypto

  • Numbers :pensive: (121 solves)
  • MD5 (114 solves)
  • PRNG (78 solves)

Numbers :pensive: (121 solves)

It wouldn't be a real CTF without some contrived RSA challenge, right?

chall.py
from Crypto.Util.number import getPrime
from Crypto.Random.random import getrandbits, randint
from pathlib import Path
from math import gcd

flag = Path("flag.txt").read_text()

e = 65537

while True:
    p = getPrime(1024)
    q = getPrime(1024)
    n = p * q
    phi = (p - 1) * (q - 1)
    if gcd(e, phi) == 1:
        break

print(f"n = {n}")
print(f"e = {e}")

while True:
    chosen_e = int(input("Give me an `e`, and I'll give you a `d`: "))
    if chosen_e == e:
        print("Nice try!")
        break
    try:
        print(pow(chosen_e, -1, phi))
    except:
        print("That's not invertible :pensive:")
        continue
    m = getrandbits(1024)
    c = pow(m, e, n)
    print("If you can decrypt this, I'll give you a flag!")
    print(c)
    ans = int(input("Your answer: "))
    if ans == m:
        print(flag)
        break
    else:
        print("Numbers, am I right :pensive:")

整数を送信すると、 \pmod N 上での逆元を返してくれるプログラムが動いている。これを利用して、 c を復号化する問題。

送信した数を X 、受け取った数を Y とすると、 XY \equiv 1 + k \phi が成立する。複数の数を送信したのち、 X_iY_i - 1 の最大公約数を求めることによって、 \phi を求めることができる。

gigem{h4h4_numb3rs_ar3_s0_qu1rky}

MD5 (114 solves)

MD5 jail?!?!?!?!

chall.py
import hashlib
import subprocess

def md5sum(b: bytes):
    return hashlib.md5(b).digest()[:3]


whitelisted_cmd = b'echo lmao'
whitelisted_hash = md5sum(whitelisted_cmd)

def main():
    while True:
        cmd = input('> ').encode()
        if cmd == b'exit':
            print('Goodbye')
            exit()

        if md5sum(cmd) != whitelisted_hash:
            print(f'Invalid command, try "{whitelisted_cmd.decode()}"')
            continue

        try:
            out = subprocess.check_output(['/bin/bash', '-c', cmd])
            print(out.decode())
        except subprocess.CalledProcessError as e:
            print(f'Command returned non-zero exit status {e.returncode}')

if __name__ == "__main__":
    main()

subprocess.check_out() の部分が明らかに怪しい。また、 echo (任意の文字列) | (本当に打ちたいコマンド) のような形を送信することによって、任意のハッシュ値のコマンドを送信できる。結果として、 echo tVJu3dCT016T2AvyS | cat ./flag.txt が有効なコマンドだということが分かった。

make_command.py
import hashlib
import random
import string

def randomname(n):
    randlst = [random.choice(string.ascii_letters + string.digits) for i in range(n)]
    return ''.join(randlst)

def md5sum(b: bytes):
    return hashlib.md5(b).digest()[:3]

whitelisted_cmd = b'echo lmao'
whitelisted_hash = md5sum(whitelisted_cmd)

test = ""

while True:
    s = 'echo ' + randomname(random.randint(1, 20)) + ' | cat ./flag.txt'

    s = s.encode('utf-8')

    if md5sum(s) == whitelisted_hash:
        test = s
        break

print(test)

PRNG

I know they say don't roll your own crypto, but secure RNG should be easy. How hard could it be?

chall.py
import secrets
from flag import flag, m, a, c

class Rand:
    def __init__(self, seed):
        self.m = m
        self.a = a
        self.c = c
        self.seed = seed
        if seed % 2 == 0: # initial state must be odd
            self.seed += 1

    def rand(self):
        self.seed = (self.a * self.seed + self.c) % self.m
        return self.seed

def main():
    seed = secrets.choice(range(0, 0x7fffffffffffffff))
    rng = Rand(seed)
    
    chall = []
    for _ in range(10):
        chall.append(rng.rand())

    print(f"Authenticate. Provide the next 10 numbers following")
    for c in chall:
        print(c)

    for _ in range(10):
        x = int(input('> '))
        if x != rng.rand():
            print("Access denied.")
            exit()
    
    print("Access granted.")
    print(flag)


if __name__ == "__main__":
    main()

線形合同法の何もわからないパターンの問題。このリンク が大いに参考になった（というかこれの 3 パターン目が問題そのもの）

gigem{D0nt_r0ll_y0uR_oWn_RnG}

upsolve した問題

  • 今のところなし

upsolve したい問題

  • [crypto]Vigenot (15 solved)
    • 頻度分析っぽい問題だったけどうまくいかず
    • よさげなWriteupを見つけたのでしっかりと理解したい

感想

けっこう難しいセットだった気がしたけど、半分くらいのcryptoを通せたので満足。

Discussion