# ångstromCTF 2021 writeup
ångstromCTF 2021 に1人チーム iab として参加しました。Crypto だけ最後の問題以外を解いて 231 位でした。Crypto だけだとなかなか順位上がらないですね…。次回は Crypto 以外もがんばります。
## Relatively Simple Algorithm (Crypto 40pts)
```python=
n = 113138904645172037883970365829067951997230612719077573521906183509830180342554841790268134999423971247602095979484887092205889453631416247856139838680189062511282674134361726455828113825651055263796576482555849771303361415911103661873954509376979834006775895197929252775133737380642752081153063469135950168223
p = 11556895667671057477200219387242513875610589005594481832449286005570409920461121505578566298354611080750154513073654150580136639937876904687126793459819369
q = 9789731420840260962289569924638041579833494812169162102854947552459243338614590024836083625245719375467053459789947717068410632082598060778090631475194567
e = 65537
c = 108644851584756918977851425216398363307810002101894230112870917234519516101802838576315116490794790271121303531868519534061050530562981420826020638383979983010271660175506402389504477695184339442431370630019572693659580322499801215041535132565595864123113626239232420183378765229045037108065155299178074809432
```
$p, q$ が与えられているので `modinv` を計算するだけですね。
```python=
from crypto_commons.rsa.rsa_commons import modinv
n = 113138904645172037883970365829067951997230612719077573521906183509830180342554841790268134999423971247602095979484887092205889453631416247856139838680189062511282674134361726455828113825651055263796576482555849771303361415911103661873954509376979834006775895197929252775133737380642752081153063469135950168223
p = 11556895667671057477200219387242513875610589005594481832449286005570409920461121505578566298354611080750154513073654150580136639937876904687126793459819369
q = 9789731420840260962289569924638041579833494812169162102854947552459243338614590024836083625245719375467053459789947717068410632082598060778090631475194567
e = 65537
c = 108644851584756918977851425216398363307810002101894230112870917234519516101802838576315116490794790271121303531868519534061050530562981420826020638383979983010271660175506402389504477695184339442431370630019572693659580322499801215041535132565595864123113626239232420183378765229045037108065155299178074809432
d = modinv(e, (p - 1) * (q - 1))
m = pow(c, d, n)
print(int.to_bytes(m, 100, 'big'))
```
flag:`actf{old_but_still_good_well_at_least_until_quantum_computing}`
## Exclusive Cipher (Crypto 40pts)
> Clam decided to return to classic cryptography and revisit the XOR cipher! Here's some hex encoded ciphertext:
> `ae27eb3a148c3cf031079921ea3315cd27eb7d02882bf724169921eb3a469920e07d0b883bf63c018869a5090e8868e331078a68ec2e468c2bf13b1d9a20ea0208882de12e398c2df60211852deb021f823dda35079b2dda25099f35ab7d218227e17d0a982bee7d098368f13503cd27f135039f68e62f1f9d3cea7c`
> The key is 5 bytes long and the flag is somewhere in the message.
鍵長5で xor 暗号化されているようです。`actf{` がフラグに含まれているのが保証されているので、暗号文の各インデックスについてそこから始まる長さ5の文字列と`actf{` を xor したものを鍵の候補として全部試せば解けます。
```python=
import string
cipher = 'ae27eb3a148c3cf031079921ea3315cd27eb7d02882bf724169921eb3a469920e07d0b883bf63c018869a5090e8868e331078a68ec2e468c2bf13b1d9a20ea0208882de12e398c2df60211852deb021f823dda35079b2dda25099f35ab7d218227e17d0a982bee7d098368f13503cd27f135039f68e62f1f9d3cea7c'
cipher = bytes.fromhex(cipher)
plain = b'actf{'
for i in range(len(cipher) - 5):
key = bytes([plain[j] ^ cipher[i + j] for j in range(5)])
s = b''.join([bytes([key[j] ^ cipher[b + j] for j in range(min(len(cipher) - b, 5))]) for b in range(0, len(cipher), 5)])
if all(chr(c) in string.printable for c in s):
print(s)
```
flag: `actf{who_needs_aes_when_you_have_xor}`
## Keysar v2 (Crypto 40pts)
単一換字暗号です。https://www.guballa.de/substitution-solver に投げたら解けました。
## sosig (Crypto 70pts)
脆弱性がある鍵の RSA です。https://github.com/Ganapati/RsaCtfTool に投げたら解けました。
## Home Rolled Crypto (Crypto 70pts)
```python: chall.py
#!/usr/bin/python
import binascii
from random import choice
class Cipher:
BLOCK_SIZE = 16
ROUNDS = 3
def __init__(self, key):
assert(len(key) == self.BLOCK_SIZE*self.ROUNDS)
self.key = key
def __block_encrypt(self, block):
enc = int.from_bytes(block, "big")
for i in range(self.ROUNDS):
k = int.from_bytes(self.key[i*self.BLOCK_SIZE:(i+1)*self.BLOCK_SIZE], "big")
enc &= k
enc ^= k
return hex(enc)[2:].rjust(self.BLOCK_SIZE*2, "0")
def __pad(self, msg):
if len(msg) % self.BLOCK_SIZE != 0:
return msg + (bytes([0]) * (self.BLOCK_SIZE - (len(msg) % self.BLOCK_SIZE)))
else:
return msg
def encrypt(self, msg):
m = self.__pad(msg)
e = ""
for i in range(0, len(m), self.BLOCK_SIZE):
e += self.__block_encrypt(m[i:i+self.BLOCK_SIZE])
return e.encode()
key = binascii.unhexlify("".join([choice(list("abcdef0123456789")) for a in range(Cipher.BLOCK_SIZE*Cipher.ROUNDS*2)]))
with open("flag", "rb") as f:
flag = f.read()
cipher = Cipher(key)
while True:
a = input("Would you like to encrypt [1], or try encrypting [2]? ")
if a == "1":
p = input("What would you like to encrypt: ")
try:
print(cipher.encrypt(binascii.unhexlify(p)).decode())
except:
print("Invalid input. ")
elif a == "2":
for i in range(10):
p = "".join([choice(list("abcdef0123456789")) for a in range(64)])
print("Encrypt this:", p)
e = cipher.encrypt(binascii.unhexlify(p)).decode()
c = input()
if e != c:
print("L")
exit()
print("W")
print(flag.decode())
elif a.lower() == "quit":
print("Bye")
exit()
else:
print("Invalid input. ")
```
1 を選んで平文を与えると暗号化した文字列を返し、2を選ぶと平文を出力するのでそれを暗号化した文字列を返すのに10回正解すればフラグが手に入るようです。
暗号化は秘密鍵 k を使って `e = m ^ k & k` を5ラウンド繰り返して暗号化するようです。各ビットは独立に暗号化されるので、各ビットが0のときと1のときに暗号化した結果が何になるかが分かれば暗号化できます。
最初に`0x0` と`0xffff...` を投げて各ビットの暗号化結果を求めて、それを使って暗号化するようにしました。
```python
from chall import Cipher
from pwn import *
if 'LOGLEVEL' in os.environ:
context.log_level = os.environ['LOGLEVEL']
context.terminal=['tmux', 'splitw', '-h']
if 'REMOTE' in os.environ:
p = remote('crypto.2021.chall.actf.co', 21602)
else:
p = process('./chall.py', env = {'LD_LIBRARY_PATH': '.'})
def encrypt(msg):
p.sendlineafter('? ', '1')
p.sendlineafter(': ', bytes.hex(msg))
return bytes.fromhex(p.recvline().strip().decode('utf-8'))
def solve():
e0 = encrypt(b'\x00' * 16)
e1 = encrypt(b'\xff' * 16)
p.sendlineafter('? ', '2')
for _ in range(10):
p.recvuntil(':')
msg = bytes.fromhex(p.recvline().strip().decode('utf-8'))
enc = []
print(msg)
for i in range(len(msg)):
enc_byte = 0
for j in range(8):
mb = (msg[i] >> j) & 1
b0 = (e0[i % 16] >> j) & 1
b1 = (e1[i % 16] >> j) & 1
if mb == 0:
eb = b0
else:
eb = b1
enc_byte = enc_byte | (eb << j)
enc.append(enc_byte)
p.sendline(bytes.hex(bytes(enc)))
p.interactive()
if __name__ == '__main__':
solve()
```
flag: `actf{no_bit_shuffling_is_trivial}`
そうですね。
## Follow the Currents
```python
import os
import zlib
def keystream():
key = os.urandom(2)
index = 0
while 1:
index+=1
if index >= len(key):
key += zlib.crc32(key).to_bytes(4,'big')
yield key[index]
ciphertext = []
with open("plain","rb") as f:
plain = f.read()
assert b"actf{" in plain
k = keystream()
for i in plain:
ciphertext.append(i ^ next(k))
with open("enc","wb") as g:
g.write(bytes(ciphertext))
```
初期値が2バイトの鍵に crc32 符号を付け加えて鍵ストリームを作るようです。初期値が2バイトしか無いので全探索できます。
```python
import os
import zlib
def keystream(key):
index = 0
while 1:
index+=1
if index >= len(key):
key += zlib.crc32(key).to_bytes(4,'big')
yield key[index]
with open('enc', 'rb') as f:
cipher = f.read()
key = None
for i in range(2**16):
key = int.to_bytes(i, 2, 'little')
print(key)
ks = keystream(key)
if b'actf{' in bytes([next(ks) ^ c for c in cipher]):
found = True
break
else:
raise ValueError("Cannot find key")
ks = keystream(key)
print(bytes([c ^ next(ks) for c in cipher]))
```
正しい平分には `actf{` が含まれるはずというのを使っています。
flag: `actf{low_entropy_keystream}`
## I'm so Random
```python3
import time
import random
import os
class Generator():
DIGITS = 8
def __init__(self, seed):
self.seed = seed
assert(len(str(self.seed)) == self.DIGITS)
def getNum(self):
self.seed = int(str(self.seed**2).rjust(self.DIGITS*2, "0")[self.DIGITS//2:self.DIGITS + self.DIGITS//2])
return self.seed
r1 = Generator(random.randint(10000000, 99999999))
r2 = Generator(random.randint(10000000, 99999999))
query_counter = 0
while True:
query = input("Would you like to get a random output [r], or guess the next random number [g]? ")
if query.lower() not in ["r", "g"]:
print("Invalid input.")
break
else:
if query.lower() == "r" and query_counter < 3:
print(r1.getNum() * r2.getNum())
query_counter += 1;
elif query_counter >= 3 and query.lower() == "r":
print("You don't get more random numbers!")
else:
for i in range(2):
guess = int(input("What is your guess to the next value generated? "))
if guess != r1.getNum() * r2.getNum():
print("Incorrect!")
exit()
with open("flag", "r") as f:
fleg = f.read()
print("Congrats! Here's your flag: ")
print(fleg)
exit()
```
任意の長さの乱数列を生成するのでその続き2つを推論してねという問題です。乱数列は2つの乱数生成器から生成された乱数の積になっていて、乱数生成器は内部状態と返す乱数が一致しているようです。
以下のようにすれば乱数生成器の内部状態が得られます。
1. 乱数を3つ取得
2. 1つ目の乱数を素因数分解して各乱数生成器が返した乱数の候補を列挙
3. 各候補が 1. で取得した乱数列を生成するかを確認
あとはそれを使って推論します。
```python3
from pwn import *
from math import prod
from sympy.ntheory import factorint
from chall import Generator
if 'LOGLEVEL' in os.environ:
context.log_level = os.environ['LOGLEVEL']
if 'REMOTE' in os.environ:
p = remote('crypto.2021.chall.actf.co', 21600)
else:
p = process('chall.py')
def get_number():
p.recvuntil('? ')
p.sendline('r')
n = int(p.recvline().strip())
return n
def guess(ans):
p.recvuntil('? ')
p.sendline('g')
for n in ans:
p.recvuntil('? ')
p.sendline(str(n))
numbers = [get_number() for _ in range(3)]
primes = list(factorint(numbers[0]).items())
debug(f'primes: {primes}')
def enum_cand(i):
if i == len(primes):
return [[]]
else:
p, n = primes[i]
tails = enum_cand(i + 1)
ret = []
for j in range(n + 1):
ret += [[(p, j)]+ tl for tl in tails]
return ret
cands = enum_cand(0)
debug(f'cands: {len(cands)}')
r1 = r2 = None
for prime in cands:
seed1 = prod([p ** n for p, n in prime])
seed2 = numbers[0] // seed1
debug(f'Candidate: {seed1}, {seed2}')
r1 = Generator(seed1)
r2 = Generator(seed2)
n1 = r1.getNum() * r2.getNum()
n2 = r1.getNum() * r2.getNum()
if n1 == numbers[1] and n2 == numbers[2]:
debug(f'Found correct pair: {seed1}, {seed2}')
break
ans = [r1.getNum() * r2.getNum() for _ in range(2)]
guess(ans)
p.interactive()
```
flag: `actf{middle_square_method_more_like_middle_fail_method}`
## Circle of Trust
```python
import random
import secrets
import math
from decimal import Decimal, getcontext
from Crypto.Cipher import AES
BOUND = 2 ** 128
MULT = 10 ** 10
getcontext().prec = 50
def nums(a):
b = Decimal(random.randint(-a * MULT, a * MULT)) / MULT
c = (a ** 2 - b ** 2).sqrt()
if random.randrange(2):
c *= -1
return (b, c)
with open("flag", "r") as f:
flag = f.read().strip().encode("utf8")
diff = len(flag) % 16
if diff:
flag += b"\x00" * (16 - diff)
keynum = secrets.randbits(128)
ivnum = secrets.randbits(128)
key = int.to_bytes(keynum, 16, "big")
iv = int.to_bytes(ivnum, 16, "big")
x = Decimal(random.randint(1, BOUND * MULT)) / MULT
for _ in range(3):
(a, b) = nums(x)
print(f"({keynum + a}, {ivnum + b})")
cipher = AES.new(key, AES.MODE_CBC, iv=iv)
enc = cipher.encrypt(flag)
print(enc.hex())
```
```
(45702021340126875800050711292004769456.2582161398, 310206344424042763368205389299416142157.00357571144)
(55221733168602409780894163074078708423.359152279, 347884965613808962474866448418347671739.70270575362)
(14782966793385517905459300160069667177.5906950984, 340240003941651543345074540559426291101.69490484699)
838371cd89ad72662eea41f79cb481c9bb5d6fa33a6808ce954441a2990261decadf3c62221d4df514841e18c0b47a76
```
AES暗号文と暗号化鍵 `keynum` と IV `ivnum` に対して実数 `a_i, b_i (i=0,1,2)` を足した値 `(keynum + a_i, ivnum + b_i)`が公開されます。上のコードをよく読むと共通の値 `x` があって各`i` は`a_i ** 2 + b_i ** 2 = x ** 2` を満たします。ということは `(keynum + a_i, ivnum + b_i)` は半径`x`、中心 `(keynum, ivnum)` の円周上の点になります。円の方程式 $x^2 + y^2 + ax + by + c = 0$ に代入すると、未知数3つ ($a, b, c$) で方程式も3つなので解けます。
```sage
from sage.all import *
from Crypto.Cipher import AES
import math
import string
import tqdm
import sys
R = RealField(10000)
points = []
with open('output.txt', 'r') as f:
for _ in range(3):
line = f.readline()
n1, n2 = line.strip().lstrip('(').rstrip(')').split(', ')
print((n1, n2))
n1, n2 = QQ(R(n1)), QQ(R(n2))
points.append((n1, n2))
cipher = bytes.fromhex(f.readline().strip())
def decrypt(key, iv):
iv_bytes = int.to_bytes(int(iv), 16, 'big')
key_bytes = int.to_bytes(int(key), 16, 'big')
flag = AES.new(key_bytes, AES.MODE_CBC, iv=iv_bytes).decrypt(cipher)
return flag
# print(points)
def solve1():
a, b, c = var('a,b,c')
alpha = 10 ** 28
def f(x, y):
return x ^ 2 + y ^ 2 + a * x + b * y + c
eqs = []
for x, y in points:
eqs.append(f(x, y) == 0)
s1 = solve(eqs, [a, b, c], solution_dict=True)[0]
k = - s1[a] / 2
v = - s1[b] / 2
key = int(k)
iv = int(v)
print(math.ceil(math.log2(key)))
print(math.ceil(math.log2(iv)))
iv_bytes = int.to_bytes(int(iv), 16, 'big')
# print(key_bytes, iv_bytes)
for i in range(-50, 50):
key_bytes = int.to_bytes(int(key) + i, 16, 'big')
flag = AES.new(key_bytes, AES.MODE_CBC, iv=iv_bytes).decrypt(cipher)
if b'actf{' in flag:
print(flag)
if __name__ == '__main__':
solve1()
```
求めた解だと誤差があって正しいフラグが出てこなかったので -50~50 あたりを適当に探索しています。
flag: `actf{elliptical_curve_minus_the_curve}`
## Substitution (Crypto 130pts)
```python
#!/usr/bin/python
from functools import reduce
with open("flag", "r") as f:
key = [ord(x) for x in f.read().strip()]
def substitute(value):
return (reduce(lambda x, y: x*value+y, key))%691
print("Enter a number and it will be returned with our super secret synthetic substitution technique")
while True:
try:
value = input("> ")
if value == 'quit':
quit()
value = int(value)
enc = substitute(value)
print(">> ", end="")
print(enc)
except ValueError:
print("Invalid input. ")
```
フラグを $f[0], \dots, f[n-1]$ とすると、入力の整数 $x$ に対して、
$$
\sum_{i=0}^{n-1} x^i f[n-1-i] \mod 691
$$
を教えてもらえるようです。$x$ を固定すると上の式は $\mathbb{Z/691Z}$ 上の線形式になるので、$x=0,\dots, n-1$ を入力すれば $n$ 個の線形方程式 (合同式) が得られます。sage を使えば$\mathbb{Z}/n\mathbb{Z}$の連立線形方程式を解くことができるので $f$ を求めることができます。$n$ は未知なので適当に小さい方から探索しました。
```sage
from sage.all import *
from pwn import *
from sympy import Matrix
import numpy as np
if 'LOGLEVEL' in os.environ:
context.log_level = os.environ['LOGLEVEL']
context.terminal=['tmux', 'splitw', '-h']
if 'REMOTE' in os.environ:
p = remote('crypto.2021.chall.actf.co', 21601)
else:
p = process('chall.py')
N = 691
def get_enc(n):
p.recvuntil('> ')
p.sendline(str(n))
p.recvuntil('>> ')
enc = int(p.recvline().strip())
return enc
encs = [get_enc(i) for i in range(70)]
R = IntegerModRing(N)
for keylen in range(6, 100):
debug(f'keylen: {keylen}')
# for avoiding 0^0
# vals = [[1 if i == keylen - 1 else 0 for i in range(keylen)]]
vals = [[pow(i, keylen - j - 1, N) for j in range(keylen)] for i in range(0, keylen)]
V = matrix(R, vals)
E = vector(R, encs[:keylen])
keys = V.solve_right(E)
debug(f'keys: {keys}')
if all([0x20 <= x and x <= 0x7e for x in keys]):
debug(f'Found flag: {"".join([chr(x) for x in keys])}')
break
```
flag: `actf{polynomials_20a829322766642530cf69}`
## Oracle of Blair (Crypto 160pts)
```python
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
import os
key = os.urandom(32)
flag = open("flag","rb").read()
while 1:
try:
i = bytes.fromhex(input("give input: "))
if not i:
break
except:
break
iv = os.urandom(16)
inp = i.replace(b"{}", flag)
if len(inp) % 16:
inp = pad(inp, 16)
print(
AES.new(key, AES.MODE_CBC, iv=iv).decrypt(inp).hex()
)
```
文字列`i`を与えると `i` 中の `"{}"` をフラグに置き換えて CBC モード AES で **復号** した文字列を返してくれるようです。
CBCモードの復号処理を思い出すと、入力ブロック群 `c0, c1, ...` に対して復号されたブロック `m0, m1, m2, ...` は
```
m0 = AES.decrypt(c0, key, iv)
m1 = AES.decrypt(c1, key, c0)
m2 = AES.decrypt(c2, key, c1)
...
```
のようになるため、c0 に好きな IV を入れて復号して最初のブロックを捨てれば任意の IV での復号ができます。
フラグの先頭 $n$ 文字が既知だとします。ここで `{}` に適当な個数のプリフィックスを付け加えることで、プレフィックスとフラグの先頭$n+1$ 文字がちょうど先頭 $k$ 個のブロックに収まるようにできます。
```python
pref = '\x00' * 0x10 + '\x00' + (0x10 - (n + 1) % 0x10) + '{}'
```
これを復号した結果と同じプリフィックスに既知文字列と文字 $c$ を付け加えた結果を比較することで、$c$ が正しい $n+1$ 文字目かを決定することができます。あとはこれを繰り返すことですべてのフラグ文字列を復元することができます。
```python3
keylen = 57
from pwn import *
if 'LOGLEVEL' in os.environ:
context.log_level = os.environ['LOGLEVEL']
context.terminal=['tmux', 'splitw', '-h']
if 'REMOTE' in os.environ:
p = remote('crypto.2021.chall.actf.co', 21112)
else:
p = process('server.py')
def decrypt(msg):
p.sendlineafter('input: ', msg)
return bytes.fromhex(p.recvline().strip().decode('utf-8'))
# '.......i|.....'
# ^-- 16 byte align
def solve():
known = b'actf{'
for i in range(len(known), keylen):
pref = b'\x00' * 16 + b'\x00' * (16 - (i + 1) % 16)
msg1 = pref + b'{}'
for c in range(0x20, 0x7f):
msg2 = pref + known + bytes([c])
dec1 = decrypt(bytes.hex(msg1))
dec2 = decrypt(bytes.hex(msg2))
if dec1[16:].startswith(dec2[16:]):
known += bytes([c])
print(f'Current key: {known}')
break
else:
raise ValueError('Cannot find correct byte')
if __name__ == '__main__':
solve()
```
フラグの長さ `keylen=57` は '{}' に文字を加えていって、どこで復号文字列の長さが変わるかを見ることで求めました
flag: actf{cbc_more_like_ecb_c}
## Thunderbolt (Crypto 200pts)
ELF バイナリが与えられます。実行して文字列を入力すると何やら暗号化した結果が得られるようです。
```
> ./chall
Enter a string to encrypt: flag
13656c1fc5eb6bf5
```
Ghidra を使って頑張って解析して Python に起こした結果が以下です。
```python
f = [0] * 0x100
s = 0
def fgen(k1, k2):
global f
global s
for i in range(0x100):
f[i] = i
state = s
for i in range(0x300):
idx = i & 0xff
t1 = k1[i % len(k1)] + state + f[idx]
state = f[t1 & 0xff]
# XOR swap
f[idx] ^= f[state]
f[state] ^= f[idx]
f[idx] ^= f[state]
# print(states)
for i in range(0x300):
idx = i & 0xff
t1 = k2[i % len(k2)] + state + f[idx]
s = f[t1 & 0xff]
state = s
# XOR swap
f[idx] ^= f[state]
f[state] ^= f[idx]
f[idx] ^= f[state]
def enc(inp):
global s
global f
state = s
out = [0] * len(inp)
for i in range(len(inp)):
i2 = i & 0xff
tmp = state + f[i2]
s = f[tmp & 0xff]
out[i] = f[(f[f[s]] + 1) & 0xff] ^ inp[i]
state = s
# XOR swap
f[i2] ^= f[state]
f[state] ^= f[i2]
f[i2] ^= f[state]
return bytes(out)
def main():
inp = input("Enter a string to encrypt: ").strip()
inp = inp.encode('utf-8')
with open('flag', 'rb') as file:
flag = file.readline().strip()
inp = inp + flag
print(inp)
# Dummy random key
with open('k1.txt', 'r') as file:
k1 = bytes.fromhex(file.readline().strip())
with open('k2.txt', 'r') as file:
k2 = bytes.fromhex(file.readline().strip())
assert(len(k1) == len(inp))
assert(len(k2) == 16)
fgen(k1, k2)
# Checking correctness of key generation
with open('f.txt', 'r') as file:
f_expect = bytes.fromhex(file.readline().strip())
with open('s.txt', 'r') as file:
s_expect = bytes.fromhex(file.readline().strip())
assert(bytes(f).hex() == bytes(f_expect).hex())
assert(bytes([s]).hex() == bytes(s_expect).hex())
res = enc(inp)
print(res.hex())
if __name__ == '__main__':
main()
```
ELF バイナリ版では `k1, k2` は `/dev/urandom` から取得していますが、動作確認のためにテキストファイルで値を与えています。ELF で実装されているのは `res.hex()` の出力までで、あとは動作確認用のコードです。`k1.txt, k2.txt, f.txt, s.txt` は以下の gdb python スクリプトで生成しました。
```python
def to_bytes(k1):
bytes = ''.join([''.join([byte[2:].rjust(2, '0') for byte in line.split('\t')[1:]]) for line in k1.split('\n')])
return bytes
gdb.execute('b fgen')
gdb.execute('run < inp.txt')
flag = gdb.execute('printf "%s\n", $r14', to_string=True).strip()
# print('flag = {}'.format(flag))
# flag = flag.split('\"')[1]
print('flag = {}'.format(flag))
k1 = gdb.execute('x/{}c $rdi'.format(len(flag)), to_string=True)
k1 = to_bytes(k1)
k2 = gdb.execute('x/16c $rsi', to_string=True)
k2 = to_bytes(k2)
with open('k1.txt', 'w') as f:
f.write(k1 + '\n')
with open('k2.txt', 'w') as f:
f.write(k2 + '\n')
# gdb.execute('b *(fgen+0x5f)')
# gdb.execute('c')
# states = []
# fs = []
# for i in range(0x300):
# idx = int(gdb.execute('p $rax', to_string=True).split()[-1], 16)
# states.append(idx)
# f = gdb.execute('x/256w (int*)(0x001040c0 + fgen - 0x001013d0)', to_string=True)
# f = list(bytes.fromhex(to_bytes(f)))
# fs.append(f)
# gdb.execute('c')
# with open('a.txt', 'w') as file:
# file.write('\n'.join([str(s) + '\n' + str(f) for s, f in zip(states, fs)]))
gdb.execute('fin')
f = gdb.execute('x/256w (int*)(0x001040c0 + fgen - 0x001013d0)', to_string=True)
f = to_bytes(f)
print('f = {}'.format(f))
with open('f.txt', 'w') as file:
file.write(f + '\n')
s = gdb.execute('x/w (int*)(0x001044c0 + fgen - 0x001013d0)', to_string=True)
s = to_bytes(s)
print('s = {}'.format(s))
with open('s.txt', 'w') as file:
file.write(s + '\n')
```
暗号化処理でやっていることは、
1. 入力を取得してフラグと結合 (`inp`)
2. 鍵テーブルの生成 (`fgen`)
- 鍵は 256 要素のテーブル `f` と状態 `s` からなる
- 各 `i in range(0x300)` に対して `s` を `k1` (`k2`) を使って更新して `f[i & 0xff]` と `f[s]` を swap することで f をシャッフルする
3. 暗号化 (`enc`)
- 生成した `f` と `s` 使って `s` を更新しながら平文と `f[s]` の XOR を取っていく
- ここでも 2と同じようなシャッフルをする
この暗号化には脆弱性があって、`fgen`, `enc` において `xor` を用いて swap をするときに `state==idx` が成り立っていると `f[state] = f[idx] = 0` になってしまいます。十分長い文字列 (10000文字くらい) に対して暗号化を行うと `state == idx` となるケースが頻発するため、最終的に`f` のすべての要素を 0 にすることができます。結果フラグは0とのXORが取られるだけなので、そのまま出力されます。
```
> perl -e 'print "A"x10000, "\n"' > inp.txt
> nc crypto.2021.chall.actf.co 21603 < inp.txt
414141......
414141616374667b77617463685f7468655f656467655f63617365735f333162326562373434306536393932633333663365356262643138347d
> echo -n 616374667b77617463685f7468655f656467655f63617365735f333162326562373434306536393932633333663365356262643138347d | xxd -r -p
actf{watch_the_edge_cases_31b2eb7440e6992c33f3e5bbd184}
```
これなにも考えずに大量の文字列流し込んだら解けたという人もいそう。
あと別の方の writeup を見ると頻度見るだけでも解けるみたい [^1] で真面目に rev しなくてもよかったらしい。
[^1]: https://y011d4.netlify.app/20210408-angstromctf-writeup/#thunderbolt
Sign in with Wallet
Connect another wallet