Zenn
🐊

WaniCTF 2024 Writeup [Crypto全完]

2024/06/23に公開
CTF
crypto
tech

めちゃめちゃ楽しかったです。学びもあってすごくいい回でした。

beginners_rsa [530 solves]

Do you know RSA?

chall.py
from Crypto.Util.number import *

p = getPrime(64)
q = getPrime(64)
r = getPrime(64)
s = getPrime(64)
a = getPrime(64)
n = p*q*r*s*a
e = 0x10001

FLAG = b'FLAG{This_is_a_fake_flag}'
m = bytes_to_long(FLAG)
enc = pow(m, e, n)
print(f'n = {n}')
print(f'e = {e}')
print(f'enc = {enc}')

n = 317903423385943473062528814030345176720578295695512495346444822768171649361480819163749494400347
e = 65537
enc = 127075137729897107295787718796341877071536678034322988535029776806418266591167534816788125330265

n が小さいので素因数分解ができます。SageMath Onlineで素因数分解しました。

from Crypto.Util.number import *

n = 317903423385943473062528814030345176720578295695512495346444822768171649361480819163749494400347
e = 65537
enc = 127075137729897107295787718796341877071536678034322988535029776806418266591167534816788125330265

p = 9953162929836910171
q = 11771834931016130837
r = 12109985960354612149
s = 13079524394617385153
a = 17129880600534041513

phi = (p-1)*(q-1)*(r-1)*(s-1)*(a-1)

d = pow(e, -1, phi)

m = pow(enc, d, n)

print(long_to_bytes(m))

FLAG{S0_3a5y_1254!!}

beginners_aes [453 solves]

AES is one of the most important encryption methods in our daily lives.

chall.py
# https://pycryptodome.readthedocs.io/en/latest/src/cipher/aes.html
from Crypto.Util.Padding import pad
from Crypto.Cipher import AES
from os import urandom
import hashlib

key = b'the_enc_key_is_'
iv = b'my_great_iv_is_'
key += urandom(1)
iv += urandom(1)

cipher = AES.new(key, AES.MODE_CBC, iv)
FLAG = b'FLAG{This_is_a_dummy_flag}'
flag_hash = hashlib.sha256(FLAG).hexdigest()

msg = pad(FLAG, 16)
enc = cipher.encrypt(msg)

print(f'enc = {enc}') # bytes object
print(f'flag_hash = {flag_hash}') # str object

enc = b'\x16\x97,\xa7\xfb_\xf3\x15.\x87jKRaF&"\xb6\xc4x\xf4.K\xd77j\xe5MLI_y\xd96\xf1$\xc5\xa3\x03\x990Q^\xc0\x17M2\x18'
flag_hash = 6a96111d69e015a07e96dcd141d31e7fc81c4420dbbef75aef5201809093210e

key と iv について、考えうるものが 65536 ( = 256 \times 256) 通りしかない。全て試す。

# https://pycryptodome.readthedocs.io/en/latest/src/cipher/aes.html
from Crypto.Util.Padding import pad
from Crypto.Cipher import AES
from os import urandom
import hashlib

key = b'the_enc_key_is_'
iv = b'my_great_iv_is_'
key += urandom(1)
iv += urandom(1)

cipher = AES.new(key, AES.MODE_CBC, iv)
FLAG = b'FLAG{This_is_a_dummy_flag}'
flag_hash = hashlib.sha256(FLAG).hexdigest()

msg = pad(FLAG, 16)
enc = cipher.encrypt(msg)

print(f'enc = {enc}')
print(f'flag_hash = {flag_hash}')

replacement [431 solves]

No one can read my diary!

from secret import cal
import hashlib

enc = []
for char in cal:
    x = ord(char)
    x = hashlib.md5(str(x).encode()).hexdigest()
    enc.append(int(x, 16))
        
with open('my_diary_11_8_Wednesday.txt', 'w') as f:
    f.write(str(enc))

my_diary_11_8_Wednesday.txt は省略。

全ての 1 文字に対して md5.hexdigest() した結果を事前に求めておけばよい。

cs = [] # my_diary_11_8_Wednesday.txt の内容

ms = []

for c in cs:
    for i, h in enumerate(hs):
        if c == h:
            ms.append(i)

print(''.join(chr(x) for x in ms))

# Wednesday, 11/8, clear skies. This morning, I had breakfast at my favorite cafe. Drinking the freshly brewed coffee and savoring the warm buttery toast is the best. Changing the subject, I received an email today with something rather peculiar in it. It contained a mysterious message that said "This is a secret code, so please don't tell anyone. FLAG{13epl4cem3nt}". How strange!
#
# Gureisya

FLAG{13epl4cem3nt}

Easy calc [95 solves]

😆

chall.py
import os
import random
from hashlib import md5

from Crypto.Cipher import AES
from Crypto.Util.number import long_to_bytes, getPrime

FLAG = os.getenvb(b"FLAG", b"FAKE{THIS_IS_NOT_THE_FLAG!!!!!!}")


def encrypt(m: bytes, key: int) -> bytes:
    iv = os.urandom(16)
    key = long_to_bytes(key)
    key = md5(key).digest()
    cipher = AES.new(key, AES.MODE_CBC, iv=iv)
    return iv + cipher.encrypt(m)


def f(s, p):
    u = 0
    for i in range(p):
        u += p - i
        u *= s
        u %= p

    return u


p = getPrime(1024)
s = random.randint(1, p - 1)

A = f(s, p)
ciphertext = encrypt(FLAG, s).hex()


print(f"{p = }")
print(f"{A = }")
print(f"{ciphertext = }")

f(s, p) は（値を知っていたとしても、p がデカすぎて）愚直に求められないので、どうにかして計算できないかを考える。

f の中身を追っていく。

easy_calc

(1-s)f(s, p) は初項 s, 公比 s の等比数列の総和と等しいことが分かる。

すなわち

A \equiv \frac{s(1-s^p)}{(1-s)^2} \pmod p

ここで、フェルマーの小定理を思い出すと、 s^p \equiv 1 \pmod p であるから、

A \equiv \frac{s}{1-s} \pmod p

となり、これと合致する s を計算すればよい

solve_s.sage
p = 108159532265181242371960862176089900437183046655107822712736597793129430067645352619047923366465213553080964155205008757015024406041606723580700542617009651237415277095236385696694741342539811786180063943404300498027896890240121098409649537982185247548732754713793214557909539077228488668731016501718242238229
A = 60804426023059829529243916100868813693528686280274100232668009387292986893221484159514697867975996653561494260686110180269479231384753818873838897508257692444056934156009244570713404772622837916262561177765724587140931364577707149626116683828625211736898598854127868638686640564102372517526588283709560663960

F = GF(p)

R.<s> = PolynomialRing(F)

numerator = s
denominator = (1 - s)
polynomial = numerator - A * denominator

roots = polynomial.roots()

for root, multiplicity in roots:
    print(f"s = {root}")
solve.py
p = 108159532265181242371960862176089900437183046655107822712736597793129430067645352619047923366465213553080964155205008757015024406041606723580700542617009651237415277095236385696694741342539811786180063943404300498027896890240121098409649537982185247548732754713793214557909539077228488668731016501718242238229
A = 60804426023059829529243916100868813693528686280274100232668009387292986893221484159514697867975996653561494260686110180269479231384753818873838897508257692444056934156009244570713404772622837916262561177765724587140931364577707149626116683828625211736898598854127868638686640564102372517526588283709560663960
ciphertext = '9fb749ef7467a5aff04ec5c751e7dceca4f3386987f252a2fc14a8970ff097a81fcb1a8fbe173465eecb74fb1a843383'

s = 1687413597309293800744215069073564700111464906280803472827126056011788534089081297767956072498777988960765236816249236506915467068679173946738276390422326894133097728262062079690201267739279447117445097896824910096682450843424480831170129071861123241366800056648768192097429858942658575325552357170973141110

import os
from hashlib import md5
from Crypto.Cipher import AES
from Crypto.Util.number import *

def decrypt(c: bytes, key: int) -> bytes:
    iv = c[:16]
    ciphertext = c[16:]
    key = long_to_bytes(key)
    key = md5(key).digest()
    cipher = AES.new(key, AES.MODE_CBC, iv=iv)
    decrypted = cipher.decrypt(ciphertext)
    return decrypted

m = decrypt(bytes.fromhex(ciphertext), s)

print(m)

FLAG{Do_the_math396691ba7d7270a}

dance [85 solves]

step by step

chall.py
from mycipher import MyCipher
import hashlib
import datetime
import random

isLogged = False
current_user = ''
d = {}

def make_token(data1: str, data2: str):
    sha256 = hashlib.sha256()
    sha256.update(data1.encode())
    right = sha256.hexdigest()[:20]
    sha256.update(data2.encode())
    left = sha256.hexdigest()[:12]
    token = left + right
    return token

def main():
    print('Welcome to the super secure encryption service!')
    while True:
        print('Select an option:')
        print('1. Register')
        print('2. Login')
        print('3. Logout')
        print('4. Encrypt')
        print('5. Exit')
        choice = input('> ')
        if choice == '1':
            Register()
        elif choice == '2':
            Login()
        elif choice == '3':
            Logout()
        elif choice == '4':
            Encrypt()
        elif choice == '5':
            print('Goodbye!')
            break
        else:
            print('Invalid choice')

def Register():
    global d
    username = input('Enter username: ')
    if username in d:
        print('Username already exists')
        return
    dt_now = datetime.datetime.now()
    minutes = dt_now.minute
    sec = dt_now.second
    print(minutes, sec)
    data1 = f'user: {username}, {minutes}:{sec}'
    data2 = f'{username}'+str(random.randint(0, 10))
    d[username] = make_token(data1, data2)
    print('Registered successfully!')
    print('Your token is:', d[username])
    return

def Login():
    global isLogged
    global d
    global current_user
    username = input('Enter username: ')
    if username not in d:
        print('Username does not exist')
        return
    token = input('Enter token: ')
    if d[username] != token:
        print('Invalid token')
        return
    isLogged = True
    current_user = username
    print(f'Logged in successfully! Hi {username}!')
    return

def Logout():
    global isLogged
    global current_user
    isLogged = False
    current_user = ''
    print('Logged out successfully!')
    return

def Encrypt():
    global isLogged
    global current_user
    if not isLogged:
        print('You need to login first')
        return
    token = d[current_user]
    sha256 = hashlib.sha256()
    sha256.update(token.encode())
    key = sha256.hexdigest()[:32]
    nonce = token[:12]
    cipher = MyCipher(key.encode(), nonce.encode())
    plaintext = input('Enter plaintext: ')
    ciphertext = cipher.encrypt(plaintext.encode())
    print('username:', current_user)
    print('Ciphertext:', ciphertext.hex())
    return

if __name__ == '__main__':
    main()

username = 'gureisya'
ciphertext = '061ff06da6fbf8efcd2ca0c1d3b236aede3f5d4b6e8ea24179'

MyCipher 等は省略。共通鍵暗号の一種だった。

data1 = f'user: {username}, {minutes}:{sec}'
data2 = f'{username}'+str(random.randint(0, 10))

の部分に着目すると、key や nonce などを生成している data1, data2 としてありうるパターンが 36000 通りしかないことが分かるため、すべて試す。

solve.py
from mycipher import MyCipher
import hashlib
import datetime
import random

username = 'gureisya'
ciphertext = bytes.fromhex('061ff06da6fbf8efcd2ca0c1d3b236aede3f5d4b6e8ea24179')

def make_token(data1: str, data2: str):
    sha256 = hashlib.sha256()
    sha256.update(data1.encode())
    right = sha256.hexdigest()[:20]
    sha256.update(data2.encode())
    left = sha256.hexdigest()[:12]
    token = left + right
    return token

for minutes in range(60):
    for sec in range(60):
        for n in range(10):
            data1 = f'user: {username}, {minutes}:{sec}'
            data2 = f'{username}'+str(random.randint(0, 10))

            token = make_token(data1, data2)

            sha256 = hashlib.sha256()
            sha256.update(token.encode())
            key = sha256.hexdigest()[:32]
            nonce = token[:12]
            cipher = MyCipher(key.encode(), nonce.encode())
            plaintext = cipher.encrypt(ciphertext)

            if plaintext.startswith(b'FLAG'):
                print(plaintext)

FLAG{d4nc3_l0b0t_d4nc3!!}

speedy [60 solves]

I made a super speedy keystream cipher!!

chall.py
from cipher import MyCipher
from Crypto.Util.number import *
from Crypto.Util.Padding import *
import os

s0 = bytes_to_long(os.urandom(8))
s1 = bytes_to_long(os.urandom(8))

cipher = MyCipher(s0, s1)
secret = b'FLAG{'+b'*'*19+b'}'
pt = pad(secret, 8)
ct = cipher.encrypt(pt)
print(f'ct = {ct}')
cipher.py
from Crypto.Util.number import *
from Crypto.Util.Padding import *

def rotl(x, y):
    x &= 0xFFFFFFFFFFFFFFFF
    return ((x << y) | (x >> (64 - y))) & 0xFFFFFFFFFFFFFFFF

class MyCipher:
    def __init__(self, s0, s1):
        self.X = s0
        self.Y = s1
        self.mod = 0xFFFFFFFFFFFFFFFF
        self.BLOCK_SIZE = 8
    
    def get_key_stream(self):
        s0 = self.X
        s1 = self.Y
        sum = (s0 + s1) & self.mod
        s1 ^= s0
        key = []
        for _ in range(8):
            key.append(sum & 0xFF)
            sum >>= 8
        
        self.X = (rotl(s0, 24) ^ s1 ^ (s1 << 16)) & self.mod
        self.Y = rotl(s1, 37) & self.mod
        return key
    
    def encrypt(self, pt: bytes):
        ct = b''
        for i in range(0, len(pt), self.BLOCK_SIZE):
            ct += long_to_bytes(self.X)
            key = self.get_key_stream()
            block = pt[i:i+self.BLOCK_SIZE]
            ct += bytes([block[j] ^ key[j] for j in range(len(block))])
        return ct

8 文字ごとにブロック暗号で暗号化しているようだ。

また、flag の長さはパディングも含めると 28 であり、 get_key_stream() は系4回行われていることが分かる。

そして、毎ラウンドの X についてはわかっている。

どうにかしてそれぞれの key を求めたい。

1回目について、最終的な X を X_{after} とし、self.X = (rotl(s0, 24) ^ s1 ^ (s1 << 16)) & self.mod について式を追ってみると、以下の図のような計算を行っていることが分かる。

speedy

X_{after} さえわかれば、S_1 の下位 2 バイトが復元可能

S_1 の下位 2 バイトさえわかれば、 S_1 の下位 4 バイトが復元可能

というように、順番に 2 バイトずつ求めることができる。

肝心の X_{after} は次のラウンドの X であるため、以上から求めることができた。

最後の 8 バイトについては上のアルゴリズムだと求められないが、}\x07\x07\x07\x07\x07\x07\x07 なのが事前にわかっているため、心配する必要は無い。

solve.py
from Crypto.Util.number import *
ct = b'"G:F\xfe\x8f\xb0<O\xc0\x91\xc8\xa6\x96\xc5\xf7N\xc7n\xaf8\x1c,\xcb\xebY<z\xd7\xd8\xc0-\x08\x8d\xe9\x9e\xd8\xa51\xa8\xfbp\x8f\xd4\x13\xf5m\x8f\x02\xa3\xa9\x9e\xb7\xbb\xaf\xbd\xb9\xdf&Y3\xf3\x80\xb8'

def rotl(x, y):
    x &= 0xFFFFFFFFFFFFFFFF
    return ((x << y) | (x >> (64 - y))) & 0xFFFFFFFFFFFFFFFF

def get_key(X: int, nxt_X: int):
    X_rot24 = rotl(X, 24)
    S1_0 = (X_rot24 & 0x000000000000FFFF)^(nxt_X & 0x000000000000FFFF)
    S1_1 = (X_rot24 & 0x00000000FFFF0000)^(nxt_X & 0x00000000FFFF0000)^(S1_0 << 16)
    S1_2 = (X_rot24 & 0x0000FFFF00000000)^(nxt_X & 0x0000FFFF00000000)^(S1_1 << 16)
    S1_3 = (X_rot24 & 0xFFFF000000000000)^(nxt_X & 0xFFFF000000000000)^(S1_2 << 16)
    S1_new = S1_0 + S1_1 + S1_2 + S1_3
    S1 = S1_new^X
    sum = (X+S1) & 0xFFFFFFFFFFFFFFFF
    key = []
    for _ in range(8):
        key.append(sum & 0xFF)
        sum >>= 8
    return key

pt = b''
for i in range(0, 48, 16):
    X = bytes_to_long(ct[i:i+8])
    nxt_X = bytes_to_long(ct[i+16:i+24])
    key = get_key(X, nxt_X)
    block = ct[i+8:i+16]
    pt += bytes([block[j] ^ key[j] for j in range(8)])

pt += b'}'

print(pt)

FLAG{x013_ro74te_5hif7!!}

Many Xor Shift [29 solves]

はるか昔の記憶
Memories of long long ago.

chall.py
FLAG = b'FAKE{XXXXXXXXXXXXXXXXXXXXXX}'

N = 7
M = 17005450388330379
WORD_SIZE = 32
WORD_MASK = (1 << WORD_SIZE) - 1

def encrypt(m):
    state = [int.from_bytes(m[i:i+4]) for i in range(0, len(m), 4)]
    assert len(state) == N

    def xor_shift():
        nonlocal state
        t = state[0] ^ ((state[0] << 11) & WORD_MASK)
        for i in range(N-1):
            state[i] = state[i+1]
        state[-1] = (state[-1] ^ (state[-1] >> 19)) ^ (t ^ (t >> 8))

    for _ in range(M):
        xor_shift()

    return state

print("N = ", N)
print("M = ", M)
print("WORD_SIZE = ", WORD_SIZE)
print("state = ", encrypt(FLAG))

N = 7
M = 17005450388330379
WORD_SIZE = 32
state = [1927245640, 871031439, 789877080, 4042398809, 3950816575, 2366948739, 935819524]

M 回 特殊な xor_shift を行っている。xor_shift は、あるタイミングの状態が分かれば、それを基に復元をすることができる。

state を列ベクトルとみなし、操作がどのような行列になっているかを考える。

例えば、以下の操作を考えてみる。

for i in range(N-1):
    state[i] = state[i+1]

これは、以下のような行列で表すことができる。

{state}^\prime = \begin{pmatrix} 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ \end{pmatrix} \times {state}

同様に、xor_shift についても、各要素の i ビット目をもった 224 \times 224 行列を用意することで、構築することができる（ややこしいので詳細は実装を見てほしい）

これで行列を準備することができた。逆行列をかけることによって、1 回状態を戻すことができる。

M 回状態を戻す必要があるので M 乗する必要があるが、これは繰り返し二乗法を用いることで高速に計算できる。

solve.sage
N = 7
M = 17005450388330379
WORD_SIZE = 32
state = [1927245640, 871031439, 789877080, 4042398809, 3950816575, 2366948739, 935819524]

import numpy as np

V = np.matrix([[0] for j in range(N*WORD_SIZE)])

for j in range(N):
    for k in range(WORD_SIZE):
        V[WORD_SIZE*j + k] = state[j] >> k & 1

A = np.zeros((N*WORD_SIZE, N*WORD_SIZE))

# shift
for i in range((N-1)*WORD_SIZE):
    A[i][i+WORD_SIZE] += 1

# 0
for i in range(WORD_SIZE):
    A[(N-1)*WORD_SIZE+i][i] = 1
for i in range(11, WORD_SIZE, 1):
    A[(N-1)*WORD_SIZE+i][i-11] = 1

for i in range(8, WORD_SIZE, 1):
      A[(N-1)*WORD_SIZE+i-8][i] = 1
for i in range(11, WORD_SIZE, 1):
     A[(N-1)*WORD_SIZE+i-8][i-11] = 1

# 6
for i in range(WORD_SIZE):
    A[(N-1)*WORD_SIZE+i][(N-1)*WORD_SIZE+i] = 1
for i in range(19, WORD_SIZE, 1):
    A[(N-1)*WORD_SIZE+i-19][(N-1)*WORD_SIZE+i] = 1

MS = MatrixSpace(GF(2), N*WORD_SIZE, N*WORD_SIZE)
A = MS(A)

def power(a, k):
    ret = np.identity(N*WORD_SIZE)
    ret = MS(ret)
    while k:
        if k & 1:
            ret = ret * a
        a = a * a
        k >>= 1
    return ret        

inv_A = A^(-1)

inv = power(inv_A, M)

begin_state_v = inv*V

begin_state = [0 for _ in range(N)]

for i in range(N):
    for j in range(WORD_SIZE):
        if begin_state_v[i*WORD_SIZE + j]:
            begin_state[i] += 1 << j

from Crypto.Util.number import *
print(b''.join(long_to_bytes(x) for x in begin_state))

FLAG{m47r1x_!n_8inary_w0rld}

uf [14 solves]

🙄

chall.py
import os
from secrets import randbits
from Crypto.Util.number import bytes_to_long


FLAG = os.environb.get(b"FLAG", b"FAKE{THIS_IS_DUMMY_FLAG}")
m = bytes_to_long(FLAG)
assert m.bit_length() >= 512


def encrypt(m: int, n: int = 512) -> int:
    x = 0
    for i in range(n):
        x <<= 1
        x += m * randbits(1)
        if i >= n // 2:
            x ^= randbits(1)
    return x


X = [encrypt(m) for _ in range(4)]
print(X)
output.txt
[6643852762092641655051592752286380661448697120839285262713138738793179330857521051418707355387198243788554658967735136760757552410466512939791351078152197994352930016306075464400264019640466277732596022216246131141036813931972036259910390741311141390889450882074162723823607552591155184799627590418587536982033939537563823, 4495106960532238798978878322218382764459613684889887356979907395021294655849239390809608204284927849117763119933285899077777162943233437728643056322845118660545730870443735090094400144586494098834221418487123653668703665085461676013454922344247818407399456870636622800919629442727075235809213114639237367651539678560390951, 7622226387024225267485603541284038981214490586915816777231024576546652676746968149372915915975325662783469952634025859954515971134032563991925283958708572235632178937041656690377178266198211581176947491463237398083133658483056792368618417698027992083481412961301906342594056438180675328433412539805240307255787971167535638, 1149407465454162408488208063367931363888120160126632926627929705372269921465081968665764846439238807939361247987642326885758277171318666479752274577607727935160689442316433824450832192798328252739495913920016290902086534688608562545166349970831960156036289570935410160077618096614135121287858428753273136461851339553609896]

「m を足すか足さないかし、1ビットシフト」を 512 回行っているうえに、下位 256 ビットはぐちゃぐちゃにされている。

「m を足すか足さないかし、1ビットシフト」だけならば、最大公約数を計算することによって m を復元できる。

そういえば、誤差込みでの計算が得意な LLL というアルゴリズムがあることを思い出し、いろいろ調査してみると、Approximate Common Divisor Problem というものがあることを知る。今回の問題と合致しているので、これを使ってみる。

頑張って紹介されている論文を見たりしながら、行列を作って計算させた。

solve.py
x = [6643852762092641655051592752286380661448697120839285262713138738793179330857521051418707355387198243788554658967735136760757552410466512939791351078152197994352930016306075464400264019640466277732596022216246131141036813931972036259910390741311141390889450882074162723823607552591155184799627590418587536982033939537563823, 4495106960532238798978878322218382764459613684889887356979907395021294655849239390809608204284927849117763119933285899077777162943233437728643056322845118660545730870443735090094400144586494098834221418487123653668703665085461676013454922344247818407399456870636622800919629442727075235809213114639237367651539678560390951, 7622226387024225267485603541284038981214490586915816777231024576546652676746968149372915915975325662783469952634025859954515971134032563991925283958708572235632178937041656690377178266198211581176947491463237398083133658483056792368618417698027992083481412961301906342594056438180675328433412539805240307255787971167535638, 1149407465454162408488208063367931363888120160126632926627929705372269921465081968665764846439238807939361247987642326885758277171318666479752274577607727935160689442316433824450832192798328252739495913920016290902086534688608562545166349970831960156036289570935410160077618096614135121287858428753273136461851339553609896]

rho = 256

x_zero = x[0]

K = 1 << (rho+1)

M = matrix([
    [K, x[0], x[1], x[2], x[3]],
    [0, -x_zero, 0, 0, 0],
    [0, 0, -x_zero, 0, 0],
    [0, 0, 0, -x_zero, 0],
    [0, 0, 0, 0, -x_zero],
])

A = M.LLL()

guess_m = []

for i in range(5):
    q_zero = A[i][0] // K
    if q_zero == 0:
        continue
    r_zero = x_zero % q_zero
    p = (x_zero-r_zero) // q_zero
    p = abs(p)
    guess_m.append(p)

from Crypto.Util.number import *

for x in guess_m:
    print(long_to_bytes(x))

FLAG{hope_this_chal_is_not_automatically_solved_by_AI_c14ef1732e87a6c}

初めて LLL を使った問題が解けて、とっても嬉しい。

Cheat Code [44 solves]

チートがあれば何でもできる
You can do anything with cheats.

server.py
from hashlib import sha256
import os
from secrets import randbelow
from secret import flag, cheat_code
import re

challenge_times = 100
hash_strength = int(os.environ.get("HASH_STRENGTH", 10000))

def super_strong_hash(s: str) -> bytes:
    sb = s.encode()
    for _ in range(hash_strength):
        sb = sha256(sb).digest()
    return sb

cheat_code_hash = super_strong_hash(cheat_code)
print(f"hash of cheat code: {cheat_code_hash.hex()}")
print("If you know the cheat code, you will always be accepted!")

secret_number = randbelow(10**10)
secret_code = f"{secret_number:010d}"
print(f"Find the secret code of 10 digits in {challenge_times} challenges!")

def check_code(given_secret_code, given_cheat_code):
    def check_cheat_code(given_cheat_code):
        return super_strong_hash(given_cheat_code) == cheat_code_hash

    digit_is_correct = []
    for i in range(10):
        digit_is_correct.append(given_secret_code[i] == secret_code[i] or check_cheat_code(given_cheat_code))
    return all(digit_is_correct)

given_cheat_code = input("Enter the cheat code: ")
if len(given_cheat_code) > 50:
    print("Too long!")
    exit(1)
for i in range(challenge_times):
    print(f"=====Challenge {i+1:03d}=====")
    given_secret_code = input("Enter the secret code: ")
    if not re.match(r"^\d{10}$", given_secret_code):
        print("Wrong format!")
        exit(1)
    if check_code(given_secret_code, given_cheat_code):
        print("Correct!")
        print(flag)
        exit(0)
    else:
        print("Wrong!")
print("Game over!")

10^{10} 択を 100 回以内に当てる問題（ではなくってよ）

怪しい計算をしているところを探してみると

for i in range(10):
    digit_is_correct.append(given_secret_code[i] == secret_code[i] or check_cheat_code(given_cheat_code))

わざわざ 1 回判定すればいい check_cheat_code() を 10 回も求めている。そして、この関数の実行に時間がかかることも考えると、サイドチャネル攻撃ができそうだと分かる（python における X or Y は、 X が True の時にわざわざ Y を見ないため、 Xが True の時は素早く実行が終わる）。

各桁について 0 から 9 まで試し、確定させていく。

※プログラムはチームメイトに作ってもらいました。

solve.py
from pwn import *
import time

server = 'chal-lz56g6.wanictf.org'
port = 5000

def find_correct_digit(current_code, position):
    fastest_time = float('inf')
    correct_digit = 0
    for i in range(10):
        test_code = current_code[:position] + str(i) + current_code[position+1:]
        conn.recvuntil(b"Enter the secret code: ")
        
        start_time = time.time()
        conn.sendline(test_code.encode())
        response = conn.recvline()
        elapsed_time = time.time() - start_time
        
        if b"Correct" in response:
            print(conn.recvuntil(b"}").decode())
            conn.close()
            return test_code, True
        
        if elapsed_time < fastest_time:
            fastest_time = elapsed_time
            correct_digit = i
        
    
    return current_code[:position] + str(correct_digit) + current_code[position+1:], False

code = "0000000000"
conn = remote(server, port)
print(conn.recvuntil(b"Enter the cheat code: "))
conn.sendline(b"pwn")

for position in range(10):
    code, found = find_correct_digit(code, position)
    print(f"{position}: {code}")
    if found:
        break

print(f"Found code: {code}")

FLAG{t1m!ng_a774ck_1s_f34rfu1}

Discussion