yoshikingのがんばる日記

あたまよくないけどがんばります

Crypto CTF 2020 Writeup

CTF

今回は一人チームUdagawaWhiteBearsでCrypto CTF 2020に参加していました． 結果は(welcome問を含む)計4問を解き、73位でした．

むずい...

CTFtime.org / Crypto CTF 2020

[Crypto] Trailing Bits

The text that includes the flag is transmitted while unfortunately both of its head and tail bits are lost

問題文にかかれているように、与えられるoutput.txtに書かれているものは先頭と末尾がいくつか消されているようです．末尾を0で合わせることで、先頭と末尾以外はうまく文字列に戻せそうです．

from Crypto.Util.number import long_to_bytes

data = open("./output.txt").read().strip()

for _ in range(1000):
    data += "0"
    m = long_to_bytes(int(data, 2))
    if b"CCTF{" in m:
        print("[+] text:", m)
        break

[+] text: b'\x01 basic unit of information in computing and digital communications. The name is a portmanteau of binary digit.[1] The bit represents a logical state with one of two possible values. These values are most commonly represented as either 0or1, but other representations such as true/false, yes/no, +/\xe2\x88\x92, or on/off are common.\nThe flag is CCTF{it5_3n0u9h_jU5T_tO_sH1ft_M3}\nThe correspondence between these values and the physical states of the underlying storage or device is a matter of convention, and different assignments may be used even within the same device or program. It may be physically implemented with a two-st`'

フラグが含まれていました． CCTF{it5_3n0u9h_jU5T_tO_sH1ft_M3}

[Crypto] Amsterdam

Is it normal to have such encoding?

暗号化ファイルとそれを使った暗号文が与えられます． 暗号化処理はかなりややこしそうですが、1つずつ処理をおっていくと大きく分けて2つの処理になりそうです．

  1. msgを組み合わせ {}_nC_k を使って2進数mに変換
  2. そのmの下2桁を見ていき、条件に応じた3のn乗で構成されるcを生成

これらの処理をざっと見る感じ、逆の処理をすることができそうです． 2.の処理からやってみます．

この2.の処理を関数 f(x) とすると、逆関数 f(x)^{-1} を作ることが目標です． 具体的な値を入れて考えてみると、以下の表のようになります．

x bin(x) f(x)
1 1 30
2 10 0+31
3 11 2*30+0+32
4 100 0+0+32
5 101 30+0+32
6 110 0+2*31+0+33
7 111 2*30+0+0+33
8 1000 0+0+0+33

この表から f(x) の3の余りに注目することで1ビットずつ特定していけそうです． 注意する点としては、余りが2のときはその後に続く0の数だけmのビットは1となるのでバグらないようにがんばります．いろいろ値をデバッグしつつ f(x)^{-1} が完成

def inv_f(enc):
    m = ""
    flag = False
    while enc > 0:
        if flag:
            if enc % 3 == 0:
                m = "1" + m
            elif enc % 3 == 1:
                enc -= 1
                m = "0" + m
                flag = False
            elif enc % 3 == 2:
                m = "0" + m
                enc -= 2
        else:
            if enc % 3 == 0:
                m = "0" + m
            elif enc % 3 == 1:
                m = "1" + m
                enc -= 1
            elif enc % 3 == 2:
                m = "1" + m
                enc -= 2
                flag = True
        enc = enc // 3
    if m[0] == "0":
        return m[1:]
    return m

これでmまで復元できたので、あとは1.の処理です． 処理を読むと、もともとmは先頭が1のn配列であることがわかります． そして、msgが {}_{n-i}C_k 以下であれば配列m[i-1]を1にして諸々引きます． この処理を繰り返していった結果が先程手に入れたものです．

mは手に入っているので、どのiで {}_{n-i}C_k が計算されているのかわかります． さらに、mの長さからn=493であることがわかります． 後はkさえわかればmsgを手に入れることができそうです． n=493と大きくないので、総当りで十分計算できそうです．

あとは、該当する {}_{n-i}C_k を足していけばおっけー

full script:

from Crypto.Util.number import long_to_bytes
from functools import reduce
import operator

enc = 5550332817876280162274999855997378479609235817133438293571677699650886802393479724923012712512679874728166741238894341948016359931375508700911359897203801700186950730629587624939700035031277025534500760060328480444149259318830785583493


def comb(n, k):
    if k > n:
        return 0
    k = min(k, n - k)
    u = reduce(operator.mul, range(n, n - k, -1), 1)
    d = reduce(operator.mul, range(1, k + 1), 1)
    return u // d


def f(m):
    m = int(m, 2)
    i = 0
    c = 0
    while (m > 0):
        if m % 4 == 1:
            c += 3 ** i
            m -= 1
        elif m % 4 == 3:
            c += 2 * 3 ** i
            m += 1
        m //= 2
        i += 1
    return c


def inv_f(enc):
    m = ""
    flag = False
    while enc > 0:
        if flag:
            if enc % 3 == 0:
                m = "1" + m
            elif enc % 3 == 1:
                enc -= 1
                m = "0" + m
                flag = False
            elif enc % 3 == 2:
                m = "0" + m
                enc -= 2
        else:
            if enc % 3 == 0:
                m = "0" + m
            elif enc % 3 == 1:
                m = "1" + m
                enc -= 1
            elif enc % 3 == 2:
                m = "1" + m
                enc -= 2
                flag = True
        enc = enc // 3
    if m[0] == "0":
        return m[1:]
    return m


# print("[+] ---------- test ----------")
# for i in range(1, 100):
#     enc = f(bin(i)[2:])
#     print(f"[+] {i}-value({bin(i)[2:]==inv_f(enc)}): f({bin(i)[2:]})={enc} -> {inv_f(enc)}")

m = inv_f(enc)
print(m)
print(f(m) == enc)
n = len(m)
print("[+] n:", n)

for k in range(n, 0, -1):
    msg = 0
    for i in range(2, n + 1):
        if m[i-1] == "1":
            msg += comb(n-i, k)
            k -= 1
    msg = long_to_bytes(msg)
    if b"CCTF{" in msg:
        print("[+] flag:", msg)
        break

$ python solver.py 
1000001010000011110111100000110010110010000000001110111100111010111110100110100000111010111000101100000010111010010011000011010001111101000001101010111110000001000000011000001000110010101000000111111111101101111100000000111101001100001110000110101010101110000100111100100001000101100001011111101001010101010000011010101001001000011010100010000011101011100000110110111101110010011000010111010010111000110110011101001000000110001000000010100000011000000011000010101111001011111111000010000100000
True
[+] n: 493
[+] flag: b'..:: CCTF{With_Re3p3ct_for_Sch4lkwijk_dec3nt_Encoding!} ::..'

CCTF{With_Re3p3ct_for_Sch4lkwijk_dec3nt_Encoding!}

[Crypto] Gambler

Gamble as an ancient Philossepher! nc 05.cr.yp.toc.tf 33371

接続するとproof of workが求められます． proof of workが成功するとこのようなオプションが出てきます．

| Options: 
|   [C]ipher flag! 
|   [E]ncryption function! 
|   [T]ry the encryption 
|   [Q]uit

Eで暗号化処理を見ると、

def encrypt(m, p, a, b):
    assert m < p and isPrime(p)
    return (m ** 3 + a * m + b) % p

となっていることがわかります． Tで任意の数字を暗号化できるので、パラメータ(a, b, p)の特定ができそうです．

bは m=0 を暗号化することで、特定できます． aは bが求まったので、 m=1 を入力し

c = 1^3 + a*1 + b \bmod{p} \\ a = c - b - 1 \bmod{p}

と計算できます． 最後にpですが、modを外し、

c + kp = m^3 + am + b \\ kp = m^3 + am + b - c

としたとき、 k が1となるような m を入力したとき求めることができます． そのような m は小さい値なのですが、小さすぎると k が0になってしまうので、適当に探します．

これでパラメータa, b, pをすべて求めることができたので、後は

enc = x^3 + ax + b \bmod{p}

となるようなxを求めるだけです． この辺りの計算はsagemathが強いので任せると解けます．

from ptrlib import Socket
from Crypto.Util.number import long_to_bytes
from hashlib import md5, sha224, sha512, sha256, sha384, sha1
import string
import re

sock = Socket("05.cr.yp.toc.tf", 33371)


def search(h, ans, length):
    gomi = "a" * (length - 4)
    for a in string.printable:
        for b in string.printable:
            for c in string.printable:
                for d in string.printable:
                    pattern = gomi + a+b+c+d
                    if h(pattern.encode()).hexdigest()[-6:] == ans:
                        print("[+] found")
                        return pattern
    print("[-] not found")
    exit()


def PoW():
    chall = sock.recvline().strip().decode()
    algo, ans, length = re.compile(r"that (.+)\(X\)\[-6:\] = (.+) and len\(X\) = (\d+)").findall(chall)[0]
    length = int(length)
    print(f"[*] searching... : {algo}(X)[-6:] == {ans}")

    if algo == "sha224":
        pattern = search(sha224, ans, length)
    elif algo == "md5":
        pattern = search(md5, ans, length)
    elif algo == "sha512":
        pattern = search(sha512, ans, length)
    elif algo == "sha256":
        pattern = search(sha256, ans, length)
    elif algo == "sha384":
        pattern = search(sha384, ans, length)
    elif algo == "sha1":
        pattern = search(sha1, ans, length)
    else:
        print("[-] not implementation:", algo)
        exit()

    sock.sendline(pattern)
    return


def get_cipher():
    _ = sock.recvuntil(b"[Q]uit")
    sock.recvline()
    sock.sendline("C")
    _ = sock.recvline().decode()
    c = int(re.compile(r" = (\d+)").findall(_)[0])
    print("[+] get c:", c)
    return c


def get_params():
    # b
    sock.recvuntil(b"[Q]uit")
    sock.recvline()
    sock.sendline("T")
    sock.recvline()
    sock.sendline("0")
    _ = sock.recvline().decode()
    b = int(re.compile(r" = (\d+)").findall(_)[0])
    print("[+] get b:", b)

    # a
    sock.recvuntil(b"[Q]uit")
    sock.recvline()
    sock.sendline("T")
    sock.recvline()
    sock.sendline("1")
    _ = sock.recvline().decode()
    a = int(re.compile(r" = (\d+)").findall(_)[0]) - 1 - b
    print("[+] get a:", a)
    
    # p
    for i in range(10):
        sock.recvuntil(b"[Q]uit")
        sock.recvline()
        sock.sendline("T")
        sock.recvline()
        sock.sendline(str(i))
        _ = sock.recvline().decode()
        p = i**3 + i*a + b - int(re.compile(r" = (\d+)").findall(_)[0])
        if p > 0:
            break
    else:
        print("[-] not found")
        exit()
    print("[+] get p:", p)
    assert is_prime(p)
    return a, b, p


def check(a, b, p):
    for _ in range(10):
        r = getrandbits(128)
        sock.recvuntil(b"[Q]uit")
        sock.recvline()
        sock.sendline("T")
        sock.recvline()
        sock.sendline(str(r))
        _ = sock.recvline().decode()
        y = int(re.compile(r" = (\d+)").findall(_)[0])
        if y != ((r**3 + r*a + b) % p):
            print("[-] wrong params")
            return False
    return True


PoW()
c = get_cipher()
a, b, p = get_params()
print("[+] are correct params:", check(a, b, p))

P.<x> = PolynomialRing(GF(p))
f = x**3 + x*a + b - c
roots = f.roots()
for root in roots:
    flag = root[0]
    print("[+] flag:", long_to_bytes(flag))
sock.interactive()

$ sage solver.sage
(略：sagemathとptrlibの相性が悪くてでるwarning)
[+] __init__: Successfully connected to 05.cr.yp.toc.tf:33371
[*] searching... : md5(X)[-6:] == 365ba8
[+] found
[+] get c: 5559433512100849646163801822363147471799647059884469936581676712456869716405938761762973357988630322690672658212279634116923469389813550588814966311722740
[+] get b: 5364996546250843540612698151302006342127122164550782648949333861832104060296837287034068448262315264086872260891752901764522267986387800874586423501347756
[+] get a: 1589357201947293289217348943897691999156055896095369337267124522547405603922969230557823542621118657825886580392095003411984279701435924546250009517976524
[+] get p: 7247680499368253875836887341257334769994143457647895605143405456928625719556640851017744624352480158224707014821066507651670786857927408626704171185058231
[+] are correct params: True
[+] flag: b'CCTF{__Gerolamo__Cardano_4N_itaLi4N_p0lYma7H}'

さいごに

全然解けなかった！！！けどcryptoたのしいいいい