b01lers CTF 2024 Writeup - よっちんのブログ

この大会は2024/4/13 8:00(JST)～2024/4/15 8:00(JST)に開催されました。
今回もチームで参戦。結果は3112点で393チーム中46位でした。
自分で解けた問題をWriteupとして書いておきます。

sanity-check (misc)

Discordに入り、#announcementsチャネルのメッセージにフラグが書いてあった。

bctf{sanitcheckcomplete}

Annnnnnny Second Now (rev)

Ghidraでデコンパイルする。

undefined8 main(void)

{
  ulong uVar1;
  long in_FS_OFFSET;
  uint local_84;
  uint local_78 [26];
  long local_10;
  
  local_10 = *(long *)(in_FS_OFFSET + 0x28);
  local_78[0] = 0x8bf7;
  local_78[1] = 0x8f;
  local_78[2] = 0x425;
  local_78[3] = 0x36d;
  local_78[4] = 0x1c1928b;
  local_78[5] = 0xe5;
  local_78[6] = 0x70;
  local_78[7] = 0x151;
  local_78[8] = 0x425;
  local_78[9] = 0x2f;
  local_78[10] = 0x739f;
  local_78[11] = 0x91;
  local_78[12] = 0x7f;
  local_78[13] = 0x42517;
  local_78[14] = 0x7f;
  local_78[15] = 0x161;
  local_78[16] = 0xc1;
  local_78[17] = 0xbf;
  local_78[18] = 0x151;
  local_78[19] = 0x425;
  local_78[20] = 0xc1;
  local_78[21] = 0x161;
  local_78[22] = 0x10d;
  local_78[23] = 0x1e7;
  local_78[24] = 0xf5;
  uVar1 = super_optimized_calculation(0x5a);
  for (local_84 = 0; local_84 < 0x19; local_84 = local_84 + 1) {
    putc((int)(uVar1 % (ulong)local_78[(int)local_84]),stdout);
  }
  putc(10,stdout);
  if (local_10 != *(long *)(in_FS_OFFSET + 0x28)) {
                    /* WARNING: Subroutine does not return */
    __stack_chk_fail();
  }
  return 0;
}

long super_optimized_calculation(int param_1)

{
  long lVar1;
  long lVar2;
  
  if (param_1 == 0) {
    lVar1 = 0;
  }
  else if (param_1 == 1) {
    lVar1 = 1;
  }
  else {
    lVar2 = super_optimized_calculation(param_1 + -1);
    lVar1 = super_optimized_calculation(param_1 + -2);
    lVar1 = lVar1 + lVar2;
  }
  return lVar1;
}

super_optimized_calculationはフィボナッチ数列になる関数で、引数をインデックスとして、以下のような配列になる。

[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...]

インデックスが0x5aの値を求める必要がある。Pythonで簡単に求める方法を使ってこの値を求め、あとは上記のコードと同じ処理をして出力する。

#!/usr/bin/env python3
def fib(n):
    global iterations
    new, old = 1, 0
    for i in range(n):
            new, old = old, new + old
            iterations+=1 #keep track of how many times its run
    return old

enc = [0x8bf7, 0x8f, 0x425, 0x36d, 0x1c1928b, 0xe5, 0x70, 0x151, 0x425, 0x2f,
    0x739f, 0x91, 0x7f, 0x42517, 0x7f, 0x161, 0xc1, 0xbf, 0x151, 0x425, 0xc1,
    0x161, 0x10d, 0x1e7, 0xf5]

iterations = 0
v = fib(0x5a)

flag = ''
for c in enc:
    flag += chr(v % c)
print(flag)

bctf{what's_memoization?}

choose_the_param (crypto)

サーバの処理概要は以下の通り。

・padded_flag: ランダム200バイト文字列 + flag + ランダム200バイト文字列
・m: padded_flagの数値化したもの
・以下繰り返し
　・bits: 数値入力
　・bit_len: bitsの数値
　・p1: bit_lenビット素数
　・p2: bit_lenビット素数
　・n = p1 * p2
　・e = 65537
　・c = pow(m, e, n)
　・n, e, cを表示

小さいビット数にして、素因数分解できるものにし、復号できるようにする。flagの数値を複数のnで割った余りの情報（復号した値）を集め、CRTでフラグを復元する。

#!/usr/bin/env python3
import socket
from sympy import factorint
from sympy.ntheory.modular import crt
from Crypto.Util.number import *

def recvuntil(s, tail):
    data = b''
    while True:
        if tail in data:
            return data.decode()
        data += s.recv(1)

s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
s.connect(('gold.b01le.rs', 5001))

for _ in range(4):
    data = recvuntil(s, b'\n').rstrip()
    print(data)

bits = 32
ms = []
ns = []
for _ in range(64):
    data = recvuntil(s, b'> ')
    print(data + str(bits))
    s.sendall(str(bits).encode() + b'\n')
    data = recvuntil(s, b'\n').rstrip()
    print(data)
    n = int(data.split(' ')[-1], 16)
    data = recvuntil(s, b'\n').rstrip()
    print(data)
    e = int(data.split(' ')[-1], 16)
    data = recvuntil(s, b'\n').rstrip()
    print(data)
    c = int(data.split(' ')[-1], 16)

    fac = factorint(n)
    phi = 1
    for p in fac:
        phi *= p - 1
    d = inverse(e, phi)
    m = pow(c, d, n)
    assert(pow(m, e, n) == c)

    ns.append(n)
    ms.append(m)

m, _ = crt(ns, ms)
padded_flag = long_to_bytes(m)

flag = padded_flag[200:-200].decode()
print(flag)

実行結果は以下の通り。

Choose your parameter
Enter the bit length of the prime!
I'll choose two prime of that length, and encrypt the flag using rsa.
Try decrypt the flag!

Enter the bit length of your primes> 32
n = 91d27d967eaeae2b
e = 10001
c = 498d0427b8cc519d
Enter the bit length of your primes> 32
n = 670f80b17178b50b
e = 10001
c = b6e4aaae745a4d7
Enter the bit length of your primes> 32
n = a4d6eaa111d76175
e = 10001
c = f880af323415c15
Enter the bit length of your primes> 32
n = 7421e8915f92f5c7
e = 10001
c = 13bdaa178c61d4d2
Enter the bit length of your primes> 32
n = 580d9539ab4661e3
e = 10001
c = 1b33de83ec441b3e
Enter the bit length of your primes> 32
n = 6fc3312abe99fe63
e = 10001
c = 2ee82f73ff2c6807
Enter the bit length of your primes> 32
n = 828c5f9fc01151d5
e = 10001
c = 61bb4ea6af3cdcf4
Enter the bit length of your primes> 32
n = 914cc5936cbec0b7
e = 10001
c = 552aba347203ff5
Enter the bit length of your primes> 32
n = c2cc58f3ef13d547
e = 10001
c = 1fcbf90c60c838d
Enter the bit length of your primes> 32
n = 9aaba815dcada10d
e = 10001
c = 10a27cd2bcdc83f8
Enter the bit length of your primes> 32
n = 800aa96fe575173d
e = 10001
c = 7c4beed2815a6ba1
Enter the bit length of your primes> 32
n = cb2d723bae1dbdb3
e = 10001
c = 1d4f53e89437ffa3
Enter the bit length of your primes> 32
n = 6236605304244a8d
e = 10001
c = 46b39bb1f63ad5bb
Enter the bit length of your primes> 32
n = ab8ba59649024711
e = 10001
c = 3f7f3be8dcf3f881
Enter the bit length of your primes> 32
n = 84f03cd87cc37d07
e = 10001
c = 5e2a967169b5ffb5
Enter the bit length of your primes> 32
n = 95925865cb75f845
e = 10001
c = 1d93190429366366
Enter the bit length of your primes> 32
n = 763ecff63a14183b
e = 10001
c = 16f7b7f59ccb3ef3
Enter the bit length of your primes> 32
n = ba80511a830e6b6f
e = 10001
c = 60fba2d0b219893f
Enter the bit length of your primes> 32
n = e5d1de8cb98fd957
e = 10001
c = 6b32e0f73f0ef84
Enter the bit length of your primes> 32
n = c609e6406a0e55f7
e = 10001
c = 1d842d61c342357b
Enter the bit length of your primes> 32
n = 7ebb37c7d2e90321
e = 10001
c = 62eaf78696352f25
Enter the bit length of your primes> 32
n = 6db238c7c046dfcf
e = 10001
c = 494c1b28d9d10680
Enter the bit length of your primes> 32
n = 991439410ed9986d
e = 10001
c = 2f52671eee8c09cc
Enter the bit length of your primes> 32
n = 98e2bd7c91f9efc7
e = 10001
c = 19960b1ab2361059
Enter the bit length of your primes> 32
n = 8ea579a17de9f3fb
e = 10001
c = f45c6b1d18a527d
Enter the bit length of your primes> 32
n = 97993eae7ea671a3
e = 10001
c = 6788616b32bfbc05
Enter the bit length of your primes> 32
n = 997ded2f7c733575
e = 10001
c = 52a21bce335c2496
Enter the bit length of your primes> 32
n = 5806f99758ae659b
e = 10001
c = 3c797e477aa9d5be
Enter the bit length of your primes> 32
n = 61183d3587d99e31
e = 10001
c = 19715b42fd82f77d
Enter the bit length of your primes> 32
n = ba9150172ef173a5
e = 10001
c = 547958a7ac2b88a7
Enter the bit length of your primes> 32
n = 56757ff450b7f079
e = 10001
c = 4a7fe9fb2fa71042
Enter the bit length of your primes> 32
n = 76ef126ba18a7515
e = 10001
c = 637d21c3206b3629
Enter the bit length of your primes> 32
n = ba84ff7ed8d57459
e = 10001
c = 32efee37045153b9
Enter the bit length of your primes> 32
n = 56f680bb40ff9d91
e = 10001
c = 433b64850907b5b8
Enter the bit length of your primes> 32
n = 84b6ff421161c021
e = 10001
c = de4d96d8e702c5d
Enter the bit length of your primes> 32
n = 6ad39973299b2107
e = 10001
c = 229174ed7f7494b9
Enter the bit length of your primes> 32
n = cbf0d754baba2ce9
e = 10001
c = 540bd531a0b53376
Enter the bit length of your primes> 32
n = 6d26e457b179e2e9
e = 10001
c = 3a161e89459d673c
Enter the bit length of your primes> 32
n = 86327cf39c6d75f1
e = 10001
c = 225eca92ac57d93a
Enter the bit length of your primes> 32
n = 6061d7c484d0a35f
e = 10001
c = 47881d12904a6912
Enter the bit length of your primes> 32
n = 8e8adac3cf3b965f
e = 10001
c = 2d01f953e4c3b060
Enter the bit length of your primes> 32
n = c1d908c5ad780ea9
e = 10001
c = 9ea0b4a02b7a9e0b
Enter the bit length of your primes> 32
n = a138d51079b95d8f
e = 10001
c = 7ae89bf18f1983e1
Enter the bit length of your primes> 32
n = 5e34e66cdd61211b
e = 10001
c = 581aa9ceac0d8997
Enter the bit length of your primes> 32
n = bc62ce84c0034897
e = 10001
c = 3e96df0ccadcc199
Enter the bit length of your primes> 32
n = 695f931d5812f8f7
e = 10001
c = 5a0320e540b301d0
Enter the bit length of your primes> 32
n = 9311fe636cd33c87
e = 10001
c = 56b17ecafb623d6e
Enter the bit length of your primes> 32
n = 5cf62e28077105d7
e = 10001
c = 198af292d61fb1d4
Enter the bit length of your primes> 32
n = 75e999f95bacadcd
e = 10001
c = 1ee23dc316401f2f
Enter the bit length of your primes> 32
n = ac6acdab4b1374bb
e = 10001
c = a443ac99946b846b
Enter the bit length of your primes> 32
n = 5346b02ba42d4185
e = 10001
c = 3f77144bf2b19d4c
Enter the bit length of your primes> 32
n = 66e9948966033f59
e = 10001
c = 4becf921a6ed329f
Enter the bit length of your primes> 32
n = ccfb36b3afff7d55
e = 10001
c = ab23a1114bb401da
Enter the bit length of your primes> 32
n = cb8b4744fb4d8997
e = 10001
c = 584905532a8499c6
Enter the bit length of your primes> 32
n = 98dea46cf2711a8b
e = 10001
c = 8e395a8761ff6f0f
Enter the bit length of your primes> 32
n = 80f82dd7ab90108d
e = 10001
c = 2fc52300fe35409e
Enter the bit length of your primes> 32
n = bf97553c0372463b
e = 10001
c = 6f9d1cd29874b9fd
Enter the bit length of your primes> 32
n = 7062e9e6430f349b
e = 10001
c = 5b440e4a8225442e
Enter the bit length of your primes> 32
n = 858a91396893208f
e = 10001
c = 3049d3bb4507e8b0
Enter the bit length of your primes> 32
n = 4d926b549f81dad1
e = 10001
c = 39e9dbd5c29d43b6
Enter the bit length of your primes> 32
n = 6b12b1e746dff909
e = 10001
c = 50a2e32286ef36de
Enter the bit length of your primes> 32
n = 838ad22052610149
e = 10001
c = 32cbbacad70ed43b
Enter the bit length of your primes> 32
n = 6325f18027971b65
e = 10001
c = 99a7db737ed6723
Enter the bit length of your primes> 32
n = 766a8ce181ffde93
e = 10001
c = 74d1222474735238
bctf{dont_let_the_user_choose_the_prime_length_>w<}

bctf{dont_let_the_user_choose_the_prime_length_>w<}

Fetus-RSA (crypto)

topGはフラグを5バイトずつに分割し、5×5の行列にしたもの。bottomGの値からtopGを求める問題ということになる。

bottomG = topG ** e

bottomG = P * J * inverse(P)となるJ(=ジョルダン標準形), Pを求める。

topG * ... * topG = P * J * inverse(P)
　　　　　　　　↓
(inverse(P) * topG * P) ** e = J

nは2分探索で素因数分解できる。上記の計算を素因数分解した素数のp1について行い、Jを算出する。Jの斜めの要素について、RSA暗号の復号でinverse(P) * topG * Pを求める。
inverse(P) * topG * PをBとすると、以下の計算でtopGを算出できる。

topG = P * B * inverse(P)

topGがわかれば、各要素を文字にし、結合すればフラグになる。

#!/usr/bin/sage
from Crypto.Util.number import *
from sympy import nextprime

with open('output.txt', 'r') as f:
    params = f.read().splitlines()

n = int(params[0].split(' ')[-1])
M = []
for i in range(4, 14, 2):
    row = [int(v) for v in params[i].split(' ')[:-1]]
    M.append(row)

bounds = [2**127, 2**128]
while True:
    base = (bounds[0] + bounds[1]) // 2
    p1 = nextprime(base)
    p2 = nextprime(p1 * 1 - 1)
    p3 = nextprime(p2 * 3 - 1)
    p4 = nextprime(p3 * 3 - 1)
    p5 = nextprime(p4 * 7 - 1)
    tmp_n = p1 * p2 * p3 * p4 * p5
    if tmp_n > n:
        bounds[1] = base
    elif tmp_n < n:
        bounds[0] = base
    else:
        break

bottomG = Matrix(GF(p1), M)
J, P = bottomG.jordan_form(transformation=True)

e = 31337
phi = p1 - 1
d = inverse(e, phi)
B = []
for i in range(5):
    c = J[i][i]
    m = pow(c, d, p1)
    row = [0, 0, 0, 0]
    row.insert(i, m)
    B.append(row)
B = Matrix(GF(p1), B)

topG = P * B * ~P

flag = ''
for i in range(5):
    for j in range(5):
        flag += long_to_bytes(int(topG[i][j])).decode()
print(flag)

bctf{c0ngr4ts_y0u_35c4p3d_th3_m4tr1c3s, but really how? what color is your honda civic? sorry i just need to make this long.}

survey (misc)

アンケートの最後の質問の選択肢にフラグが書いてあった。

bctf{thanks_for_playing_see_you_next_year}