# BCACTF 2021 writeup
https://play.bcactf.com/
チーム`m1z0r3`のメンバーとして参加して**24位/6125pt**でした。
今回はチームのみなさんが強くてかなり点数が伸びました。ありがとうございました！！！
解いた問題に関してwriteupを書きます。
# Crypto
Easy RSA、Slightly Harder RSA、little eに関しては省略
## [75pt]
文字化けなのでエンコード方式を色々試してみたんですが、どれも上手く行かなかったです。
冷静になると、flagっぽい文字列の前に文章が沢山あるので換字式暗号として解けばよさそう
頻度解析とかはせず、地道に単語をエスパーしてひたすら変換しました。
:::spoiler before
```
" " , 27 1987. , ' , (1987). - , 1987, - . 25 , .[6] 1988 .
"" . 2008, , , .[7] ' .
2019, '' , .[8]
[' ](://..//____)
{______}
```
:::
:::spoiler after
```
"never gonna give you up" is the debut single recorded by english singer and songwriter rick astley, released on 27 july 1987. it was written and produced by stock aitken waterman, and was released as the first single from astley's debut album, whenever you need somebody (1987). the song was a worldwide number-one hit, initially in the united kingdom in 1987, where it stayed at the top of the chart for five weeks and was the best-selling single of that year. it eventually topped the charts in 25 countries, including the united states and west germany.[6] the song won best british single at the 1988 brit awards.
the music video for the song has become the basis for the "rickrolling" internet meme. in 2008, astley won the mtv europe music award for best act ever with the song, as a result of collective voting from thousands of people on the internet, due to the popular phenomenon of rickrolling.[7] the song is considered astley's signature song and it is often played at the end of his live concerts.
in 2019, astley recorded and released a 'pianoforte' version of the song for his album the best of me, which features a new piano arrangement.[8]
shamelessly copied from [wikipedia's article on the subject](https://en.wikipedia.org/wiki/never_gonna_give_you_up)
bcactf{sorry_we_ran_out_of_runes_sjrhwbg}
```
:::
## Cipher Mishup [75pt]
:::spoiler text.txt
```
126-Y,113-N,122-N,130-N,117-N,107-N,137,114-N,127-Y,137,113-Y,104-N,131-N,110-N,137,105-Y,110-N,110-N,121-Y,137,131-Y,114-N,112-N,110-N,121-N,110-N,125-N,110-N,137,114-Y,121-N,126-N,127-N,110-N,104-N,107-N
```
:::
とりあえず数字だけを変換してもasciiにはなってないです。hintに「His sister hates base 10.」と書いてあるので、baseをいくつか試していると8進数でそれっぽくなります。
後はCaesar暗号っぽくrotateするとrot23で意味のある文字列になり、「Y」がついているものだけ大文字にするとフラグが出てきます
`bcactf{Should_iT_Have_BeeN_Vigenere_Instead}`
:::spoiler solver.py
```python=
with open('text.txt', 'r') as f:
a = f.readline().strip().split(',')
flg = 0
ans = ''
for s in a:
L = s.split('-')
n = int(L[0], 8)
if len(L) == 2:
n -= ord('A')
n = (n + 23) % 26
n += ord('A')
if L[1] == 'N':
n -= ord('A')
n += ord('a')
ans += chr(n)
ans = 'bcactf{' + ans + '}'
print(ans)
```
:::
## RSAtrix2[200pt]
:::spoiler rt2.sage
```python=
p = 94653748632775872562206813156858988240379536044871601072940225022186828970998253
q = 47982815420210848939631963090916124891858755590019708758250635504732488148835047
n = p * q
e = 3
N = 23
R = Zmod(n) # Z/nZ
MS = MatrixSpace(R, N, N) # N*N、Z/nZの正方行列クラス
s = PermutationGroupElement('(1,6,8)(2,3,4,5,7)(9,11,13,15,17,19,21,23)(10,12,14,16,18,20,22)')
P = MS(s.matrix()) # 置換行列
with seed(1): C = MS([randrange(100) for i in range(N*N)]) # Cは乱数の行列
G = C * P * C^-1
def encrypt(m):
M = m * G
return (M^e).list()
```
:::
enc.txtは$M^e$を出力した結果が入っていました。
$M = m * G(mは平文で、整数)$であり、$M^e = (m * I)^e * G^e$になります。
よって、右から$G^e$の逆行列を掛けてあげれば、対角成分が$m^e$で、他が0の行列が得られます。seedが1であると分かっているので、$G$は手元で求められます。
あとは$p, q$が分かっているので普通にRSAを解けばOKです。
`bcactf{permutation-conjugation-magic-3x876oeu}`
## RSAtrix3[300pt]、RSAtrix4[400pt]
:::spoiler rt3.sage
```python=
#!/usr/bin/env -S sage --nodotsage
import binascii
p = 2118785735523620955301512231868734231925640292462405499978976981762557161416662496081983014179663
q = 1243737700428927574598968208586995066861594665591025213691894901887737529628559457923362470874703
n = p * q
e = 3
N = 31
R = Zmod(n)
MS = MatrixSpace(R, N, N)
s = PermutationGroupElement('(1,8,18)(2,24,14,22,25,6,9,13,31,15,21)(3,16,27,26,12,10,7,5,20,23)(4,29,28,11,19,17,30)')
P = MS(s.matrix())
with seed(1): C = MS([randrange(100) for i in range(N*N)])
G = C * P * C^-1
def encrypt(m):
M = m * G
return (M^e).list()
with open("flag.txt", "r") as f:
flag = f.read().strip().encode("ascii")
m = int(binascii.hexlify(flag), 16)
mats = {"I": MS.identity_matrix(), "G": G, "E": MS(encrypt(m))}
print("""
Welcome to the RSAtrix demo calculator!
Here, you can define matrix variables in terms of sums, products, or powers of matrices.
You can also multiply a matrix by a constant.
There's only one catch: you can only receive the trace of the resulting matrices!
""", flush=True)
while True:
print("Would you like to print the traces of your stored matrices (P), add two matrices (A), \nmultiply two matrices (M), multiply a matrix by a constant (C), take a matrix power (X), or quit (Q)?", flush=True)
try:
l = input(">>> ").strip().upper()
if (len(l) > 1):
print("You inputted more than one character...", flush=True)
elif (l == "Q"):
print("We hope you enjoyed!", flush=True)
exit()
elif (l == "P"): # I, G, Meのトレースがわかる
print("Here the traces of your matrices:", flush=True)
for k in mats:
print(k + ": " + str(mats[k].trace()), flush=True)
elif (l == "A"):
print("What is the name of the first matrix you would like to add?", flush=True)
A = input(">>> ").strip()
print("What is the name of the second matrix you would like to add?", flush=True)
B = input(">>> ").strip()
C = mats[A]+mats[B]
print("The trace of their sum is: " + str(C.trace()), flush=True)
print("Would you like to save this matrix? (Y/N)", flush=True)
I = input(">>> ").strip().upper()
if I == "N":
continue
print("What would you like the name of the matrix to be?", flush=True)
N = input(">>> ").strip()
mats[N] = C
print("Matrix saved.", flush=True)
elif (l == "M"):
print("What is the name of the first matrix you would like to multiply?", flush=True)
A = input(">>> ").strip()
print("What is the name of the second matrix you would like to multiply?", flush=True)
B = input(">>> ").strip()
C = mats[A]*mats[B]
print("The trace of their product is: " + str(C.trace()), flush=True)
print("Would you like to save this matrix? (Y/N)", flush=True)
I = input(">>> ").strip().upper()
if I == "N":
continue
print("What would you like the name of the matrix to be?", flush=True)
N = input(">>> ").strip()
mats[N] = C
print("Matrix saved.", flush=True)
elif (l == "C"):
print("What is the name of the matrix you would like to multiply?", flush=True)
A = input(">>> ").strip()
print("What is the value of the constant you would like to multiply it by?", flush=True)
B = int(input(">>> ").strip())
C = B * mats[A]
print("The trace of the product is: " + str(C.trace()), flush=True)
print("Would you like to save this matrix? (Y/N)", flush=True)
I = input(">>> ").strip().upper()
if I == "N":
continue
print("What would you like the name of the matrix to be?", flush=True)
N = input(">>> ").strip()
mats[N] = C
print("Matrix saved.", flush=True)
elif (l == "X"):
print("What is the name of the matrix you would like to exponentiate?", flush=True)
A = input(">>> ").strip()
print("What is the value of the exponent you would like to use?", flush=True)
B = int(input(">>> ").strip())
C = mats[A]^B
print("The trace of the matrix power is is: " + str(C.trace()), flush=True)
print("Would you like to save this matrix? (Y/N)", flush=True)
I = input(">>> ").strip().upper()
if I == "N":
continue
print("What would you like the name of the matrix to be?", flush=True)
N = input(">>> ").strip()
mats[N] = C
print("Matrix saved.", flush=True)
except:
print("Your input caused an error.", flush=True)
```
:::
serverのコードが大分長いですが、要約すると、Q, P, A, M, C, Xの5つのコマンドがあります。
始めは`mats`というdictに$I, G, E(=M^e)$が登録されています。コマンドの内訳は以下のとおりです。
- `Q`
- exitする
- `P`
- 登録している行列のトレースが分かる
- `A`
- 登録している行列の中から2つ選んで足し算する
- 新たにできた行列を登録できる
- その行列のトレースもわかる
- `M`
- 登録している行列の中から2つ選んで掛け算する
- 新たにできた行列を登録できる
- その行列のトレースもわかる
- `C`
- 登録している行列の中から1つ選んで、その行列に自分で指定した定数を掛け算できる
- 新たにできた行列を登録できる
- その行列のトレースもわかる
- `X`
- 登録している行列から1つ選んで、自分で指定した定数をBとすると、B乗してくれる
- 逆行列はこれで求められる
- 新たにできた行列を登録できる
- その行列のトレースもわかる
$G$が登録されていて、コマンドCで-1乗、すなわち$G^e$の逆行列を求めるだけなので、RSAtrix2でやったことをインタラクティブにRSAtrix3でもやるだけで解けてしまいます。
少し違う点は、行列を直接知ることはできないので、行列のトレースを$N$で割った値が$m^e$であることからRSAを解く必要があります。
作問者によるとコマンド`C`によって素直に逆行列が求められてしまうのは非想定だったようです。チェックが甘かったようですね...
- RSAtrix3：`bcactf{did-your-solution-generalize-or-not?-oe09k7xd}`
- RSAtrix4：`bcactf{did-you-use-the-eigendecomposition-or-do-something-else?-dm-eiis-490f2}`
## RSAtrix5[450pt]
:::spoiler rt5.sage
```python=
import binascii
# future server implementer (todo ed delete this): all of these should be regenerated on every server connection
# also todo, you probably want to put a POW on this problem
# nc crypto.bcactf.com 49159
print("Starting...")
e = 65537
p = 65538
while (p-1) % e == 0:
p = random_prime(2^401, false, 2^400)
q = 65538
while (q-1) % e == 0:
q = random_prime(2^401, false, 2^400)
n = p * q
d = int(Zmod((p-1)*(q-1))(e)^-1)
N = 64
R = Zmod(n) # Z/nZ
MS = MatrixSpace(R, N, N)
S = SymmetricGroup(N) # N次対称群
running = True
while running:
try:
s = 0
while s.order() < 2000: # 位数は2000以上
s = S.random_element() # S_N からランダムに1つ選ぶ
P = MS(s.matrix())
running = false
except:
continue
C = MS([randrange(n) for i in range(N*N)])
print("Calculating G...")
G = C * P * C^-1
def encrypt(m):
M = m * G
return (M^e).list()
with open("flag.txt", "r") as f:
flag = f.read().strip().encode("ascii")
m = int(binascii.hexlify(flag), 16)
print("Encrypting...")
mats = {"G" : G, "E" : MS(encrypt(m))}
vals = {"e" : e, "d" : d, "n" : n}
done = {"A" : False, "M" : False, "X" : False, "D" : False, "U" : False, "N" : False, "T" : False}
print("""
Our calculator demo has gotten pretty expensive.
Given you're not a paying customer or anything, we decided it was fair to
only allow one of each type of operation per connection.
Try them all for the full experience!
Also, d is secret now. Oops! We've added integer operations to compensate.
""")
print(f"n = {n}")
while True:
print("Would you like to print the traces of your stored matrices (P), list your stored integers (L), \nadd two matrices (A), multiply two matrices (M), take a matrix power (X), \nadd two integers (D), multiply two integers (U), exponentiate two integers mod n (N), \nsave the trace of a matrix (T), or quit (Q)?")
try:
l = input(">>> ").strip().upper()
if len(l) > 1:
print("You inputted more than one character...")
elif l == "Q":
print("We hope you enjoyed!")
exit()
elif l == "P":
print("Here the traces of your matrices:")
for k in mats:
print(k + ": " + str(mats[k].trace()))
elif l == "L":
print("Here is your list of integers:")
print(list(vals.keys()))
elif l == "A" and not done["A"]:
print("What is the name of the first matrix you would like to add?")
A = input(">>> ").strip()
print("What is the name of the second matrix you would like to add?")
B = input(">>> ").strip()
C = mats[A]+mats[B]
done["A"] = True
print("The trace of their sum is: " + str(C.trace()))
print("Would you like to save this matrix? (Y/N)")
I = input(">>> ").strip().upper()
if I == "N":
continue
print("What would you like the name of the matrix to be?")
N = input(">>> ").strip()
mats[N] = C
print("Matrix saved.")
elif l == "M" and not done["M"]:
print("What is the name of the first matrix you would like to multiply?")
A = input(">>> ").strip()
print("What is the name of the second matrix you would like to multiply?")
B = input(">>> ").strip()
C = mats[A]*mats[B]
done["M"] = True
print("The trace of their product is: " + str(C.trace()))
print("Would you like to save this matrix? (Y/N)")
I = input(">>> ").strip().upper()
if I == "N":
continue
print("What would you like the name of the matrix to be?")
N = input(">>> ").strip()
mats[N] = C
print("Matrix saved.")
elif l == "X" and not done["X"]:
print("What is the name of the matrix you would like to exponentiate?")
A = input(">>> ").strip()
print("What is the name or value of the exponent you would like to use?")
B = input(">>> ").strip()
if B in vals:
B = vals[B]
else:
B = int(B)
if B <= 0:
print("Positive powers only.")
continue
C = mats[A]^B
print("The trace of the matrix power is is: " + str(C.trace()))
done["X"] = True
print("Would you like to save this matrix? (Y/N)")
I = input(">>> ").strip().upper()
if I == "N":
continue
print("What would you like the name of the matrix to be?")
N = input(">>> ").strip()
mats[N] = C
print("Matrix saved.")
elif l == "D" and not done["D"]:
print("What is the name or value of the first number you would like to add?")
A = input(">>> ").strip()
if A in vals:
A = vals[A]
else:
A = int(A)
print("What is the name or value of the second number you would like to add?")
B = input(">>> ").strip()
if B in vals:
B = vals[B]
else:
B = int(B)
C = A + B
done["D"] = True
print("Sum calculated. Do you want to save the result (S), or print and quit (Q)?")
I = input(">>> ").strip().upper()
if I == "Q":
print(C)
print("We hope you enjoyed!")
exit()
print("What would you like the name of the variable to be?")
N = input(">>> ").strip()
vals[N] = C
elif l == "U" and not done["U"]:
print("What is the name or value of the first number you would like to multiply?")
A = input(">>> ").strip()
if A in vals:
A = vals[A]
else:
A = int(A)
print("What is the name or value of the second number you would like to multiply?")
B = input(">>> ").strip()
if B in vals:
B = vals[B]
else:
B = int(B)
C = A * B
done["U"] = True
print("Product calculated. Do you want to save the result (S), or print and quit (Q)?")
I = input(">>> ").strip().upper()
if I == "Q":
print(C)
print("We hope you enjoyed!")
exit()
print("What would you like the name of the variable to be?")
N = input(">>> ").strip()
vals[N] = C
elif l == "N" and not done["N"]:
print("What is the name or value of the exponent base?")
A = input(">>> ").strip()
if A in vals:
A = vals[A]
else:
A = int(A)
print("What is the name or value of the exponent base?")
B = input(">>> ").strip()
if B in vals:
B = vals[B]
else:
B = int(B)
C = int(R(A) ^ B)
done["N"] = True
print("Power calculated. Do you want to save the result (S), or print and quit (Q)?")
I = input(">>> ").strip().upper()
if I == "Q":
print(C)
print("We hope you enjoyed!")
exit()
print("What would you like the name of the variable to be?")
N = input(">>> ").strip()
vals[N] = C
elif l == "T" and not done["T"]:
print("What is the name of the matrix whose trace you would like to save?")
A = input(">>> ").strip()
C = mats[A].trace()
done["T"] = True
print("Trace calculated. We will make the brash assumption you'd like to save the result.")
print("What would you like the name of the variable to be?")
N = input(">>> ").strip()
vals[N] = C
else:
print("Either that wasn't an option, or you already used up your trial!")
except:
print("Your input caused an error.")
```
:::
RSAtrix4が非想定で通されまくってしまったことにより急遽作成され追加された問題。
急いで作ったからか、配布コードに1箇所typoがありますね...
今回は指数として`-1`を入力すると弾かれてしまうため、負の数を入力せずに$G^e$の逆行列を求める必要があります。また、各コマンドは1回ずつしか使えません。
まず、行列$P$が$N$次対称群の元(数学分からないので正しい言い方なのか分からない)であり、$P$は置換行列であることに着目します。
置換行列ということは、位数を$n$とすると、$n$回自分自身を掛けると自分自身に戻ってきます(巡回置換)。つまり、$P^n = P$が成り立ちます。
よって、$P^{-1} = P^{n-1}$となります。
また、$G = CPC^{-1}$より、$G^e = CP^{e}C^{-1}$が成り立ちます。
よって、$(G^e)^{-1} = CP^{e+n-1}C^{-1}$となります。
以上より、置換行列$P$の位数が分かれば、今回の場合は逆行列が求められることになります。
しかし、今回$P$はランダムに選ばれ、位数を直接求める手段がないため、もう1段階工夫が必要になります。
先程$P$の逆行列が$P^n$に一致すると言いましたが、$n$周すると自分自身に戻ってくる(サイクルになっている)というのが本質で、より一般的に言えば$P^{kn-1}\space (kは正整数) = P^{-1}$が成り立ちます。
つまり、$N$次の置換行列の全ての位数(今回は2000以上のみでよい)のLCMを求めればよいことになります。
まず、$N=64$での全ての2000以上の位数を求めてみます。これは、$N=64$の分割の仕方を全て列挙することで求められます。これは$N$次対称群が共役類で分割でき、共役類の数はN=64の分割数(N=64の場合は1741630)に一致することにより求められます。
計算すると、N=64での全ての2000以上の位数のLCMは3099044504245996706400になります。
これを使えば$G^e$の逆行列が求まり、後はRSAtrix3, 4と同じように解くことができます。
`bcactf{I-really-hope-you-solved-it-the-right-way-this-time-90ao87d}`
:::spoiler 位数のLCMを求めるコード
```python=
import copy
from math import gcd
def lcm(a, b):
return (a * b) // gcd(a, b)
ms = []
a = []
def dfs(n, ma): # 分割数全列挙
if n == 0:
ms.append(copy.deepcopy(a))
return
for i in reversed(range(1, min(n, ma)+1)):
a.append(i)
dfs(n-i, i)
del a[-1]
n = int(input('input n : '))
dfs(n, n)
# print(ms)
se = set()
# 位数の種類すべて求める
for vals in ms:
g = 1
for val in vals:
g = lcm(g, val)
if g >= 2000: se.add(g)
res = list(se)
print(res)
V = 1
for i in range(0, len(res)):
V = lcm(V, res[i])
print(V)
```
:::
:::spoiler solver.py
```python=
import binascii
from Crypto.Util.number import long_to_bytes
from pwn import *
e = 65537
N = 64
def main():
# nc crypto.bcactf.com 49159
r = remote("crypto.bcactf.com", 49159)
print(r.recvline()) # Starting...
print(r.recvline()) # Calculating G...
print(r.recvline()) # Encrypting...
for _ in range(7): print(r.recvline()) # Our calclator...
n = int(r.recvline().decode('utf-8').strip().split()[-1])
print(f'n = {n}')
print(r.recvline()) # コマンド押す前の最初のメッセージ
# まずG^eの逆行列 "rGe"を登録する
# これは(G^e)^order = G^(e*((orderのLCM)-1))を登録すればOK
# コマンドXを使う
r.sendlineafter('>>> ', 'X')
print(r.recvline())
r.sendlineafter('>>> ', 'G') # A
print(r.recvline())
r.sendlineafter('>>> ', str(e*(3099044504245996706400-1))) # B
print(r.recvline())
print(r.recvline())
r.sendlineafter('>>> ', 'Y')
print(r.recvline())
r.sendlineafter('>>> ', 'rGe')
print(r.recvline())
print(r.recvline()) # コマンド押す前の最初のメッセージ
# 次にE * rGeを計算する
# コマンドMを使う
r.sendlineafter('>>> ', 'M')
print(r.recvline())
r.sendlineafter('>>> ', 'E')
print(r.recvline())
r.sendlineafter('>>> ', 'rGe')
trace = int(r.recvline().decode('utf-8').strip().split()[-1])
print(r.recvline())
r.sendlineafter('>>> ', 'Y')
print(r.recvline())
r.sendlineafter('>>> ', 'ans')
print(r.recvline())
cipher = trace * pow(N, -1, n) % n
print(r.recvline()) # コマンド押す前の最初のメッセージ
# dを受け取る
# ciper^dを計算して、出力して終了
r.sendlineafter('>>> ', 'N')
print(r.recvline())
r.sendlineafter('>>> ', str(cipher))
print(r.recvline())
r.sendlineafter('>>> ', 'd')
print(r.recvline())
r.sendlineafter('>>> ', 'Q')
m = int(r.recvline().decode('utf-8').strip())
print(r.recvline())
m %= n
ans = binascii.unhexlify(hex(m)[2:].encode())
print(ans)
#r.interactive()
r.close()
if __name__ == '__main__':
main()
```
:::
## Rainbow Passage [225pt]
:::spoiler rp.py
```python=
#!/usr/bin/env python3
import math
import binascii
from Crypto.Util.Padding import pad, unpad
print("""
Welcome to the official communication encryption system for rainbow bridges.
Input the encryption password given to you by your sponsor diety to encode messages,
and use the decryption password given to you to decode messages.
""")
def encode_block(m, pm):
m = [i for i in m] # 平文を1文字ずつに分解
c = [0] * 16
for i, w in enumerate(pm): # passwordを2文字ずつに分解して2進数(16bit)にしたやつ
for j, l in enumerate(w): # を1文字ずつ見る
if l == '1': # pwdが'1'だったら
c[j] ^= m[i] # 平文のi番目の要素をxor
print(len(binascii.hexlify(bytes(c))))
return binascii.hexlify(bytes(c))
def encode(m, pwd):
pm = []
while pwd: # passwordを2文字ずつに分解
a = '0'*8 + bin(ord(pwd[0]))[2:]
a = a[-8:] # 後ろから8文字、つまり無理やり8bitにしている
b = '0'*8 + bin(ord(pwd[1]))[2:]
b = b[-8:]
pm.append(a + b)
pwd = pwd[2:]
c = b""
while m: # 平文を16文字ずつに分解し、encode
c += encode_block(m[:16], pm)
m = m[16:]
return c
# たぶんpwdがflag
while True:
print("Would you like to encrypt (E), decrypt (D), or quit (Q)?")
l = input(">>> ").strip().upper()
if (len(l) > 1):
print("You inputted more than one character...")
elif (l == "Q"):
print("Don't forget to perform sacrifices for your sponsor diety daily!")
exit()
elif (l == "E"):
print("What is your encryption password?")
pwd = input(">>> ").strip()
assert len(pwd) == 32
print("What would you like to encrypt?")
m = input(">>> ").strip()
# paddingしてbytesの長さを16の倍数にする
c = encode(pad(m.encode('ascii'), 16), pwd)
print("Here's your encoded message:")
print(c)
elif (l == "D"):
print("Oops, for now, that feature is reserved for your sponsor diety.")
```
:::
:::spoiler enc.txt
```
0074252538126d030056257867484f6400070806330a06660078081c5d571a140018081064105e28006d0841101c4c43000e0408364f1122003f04005b48541d00040b4169050e60007c0b5c471a531600647a4e002d7d2600587a5319391b6c001e054f2e5a502d002405445f1f0c47005a594531575d2d006559555e064947001b06116f0305770076060c4c18501a007076444a470217000f761b61633b2d00160d11230a417d007d0d1b07111f12000c004d715a5776002a004a0d121f140047085b25531c77007708150f074f40004900587211403000210041475f181b000b551c7842142d00365558180f4f1a0011095434135e7200740944134b401a00411a562519037800321a564d5649110023606e780d214b0018607065191c75005e17402c101729006f17015b154a5c004a0a5475440661006f0a13570d530f0011100235135d6e003a104c0e590b540073676a235c304a000067675d3c131a004a00517a0f0d2a006000521c415d4d00317d1f6e164f0700447d67574c3217005e554c2d064c340038550249011e480003151a790950630073155950054e1e00091b527953123f00631b150f0e1c48000206036a001f71003906504616564200155954770e1072006e590a474c5c09000f111c2a1c537c002d11454e52424800130b442a43183e00230b12451e1e4a0076540d2e590d580058540d373a2237
```
:::
言葉で説明するのが辛くて諦めました。
要約すると、平文の各ブロックには同じpwd(これがflag)を使って暗号化していることを利用して、pwdを特定できます(連立方程式を解きます)
掃き出し法を実装したくなかったので、pwdの各ブロックを2^16通り全探索して候補を絞り込みました。実行時間はとても長いですが、フラグが出てきます。
デコードに失敗して途方に暮れていたので、先輩の助けをお借りしてなんとかフラグをゲットできました...
`bcactf{system-of-linear-equations-273de}`
:::spoiler solver.py
```python=
import math
from tqdm import tqdm
import binascii
from Crypto.Util.Padding import pad, unpad
def encode_block(m, pm):
m = [i for i in m] # 平文を1文字ずつに分解
c = [0] * 16
# passwordを2文字ずつに分解して2進数(16bit)にしたやつ
# len(pm) == 32
for i, w in enumerate(pm):
for j, l in enumerate(w): # を1文字ずつ見る
if l == '1':
c[j] ^= m[i]
return binascii.hexlify(bytes(c))
pwd_kouho = [set([i for i in range(2**16)]) for _ in range(16)]
def decode_block(enc, m):
m = [i for i in m]
c = list(binascii.unhexlify(enc))
assert len(m) == 16
assert len(c) == 16
for j in tqdm(range(len(c))):
kouho = set()
for mask in range(1 << 16):
res = 0
S = 0
for i in range(16):
if ((mask >> i) & 1) == 1:
res ^= m[i]
S |= (1 << (15-i))
if c[j] == res:
# print(s)
kouho.add(S)
# print(len(kouho))
pwd_kouho[j] = pwd_kouho[j] & kouho
with open('enc.txt', 'r') as f:
enc = f.read().strip()
with open('message.txt', 'r') as f:
plain_text = f.read().strip()
m = pad(plain_text.encode('ascii'), 16)
print(len(enc), len(m))
while enc:
decode_block(enc[:32], m[:16])
enc = enc[32:]
m = m[16:]
print(pwd_kouho)
pre = []
for se in pwd_kouho:
aa = list(se)
pre.append(aa[0])
ans = [0] * 16
for i in range(16):
for j in range(16):
if pre[i] >> j & 1:
ans[15-j] |= (1 << (15-i))
res = ''
for i in range(16):
x = ans[i] >> 8
y = ans[i] - (x << 8)
print(chr(x)+chr(y), end="")
print()
```
:::
# foren
## Infinite Zip [75pt]
flag.zipが与えられます。解凍してみると1000.zipが出てきて、それを解凍すると999.zipが出てきて...という風になっています。
まず、pythonで1000回unzipするコードを書き解凍します。
```python=
import zipfile
for n in reversed(range(1001)):
with zipfile.ZipFile(f'{n}.zip') as f:
f.extractall('.')
```
最後まで解凍するとflag.pngが出てきて、画像にflagが書いてありました...
と思ったらincorrectでした。どうやらダミーだったようです。
pngの中に隠されていると思い、[tweakpng](http://entropymine.com/jason/tweakpng/)を使って中の構成を見るとtextデータが埋まっていて、その中にフラグがありました。
## Zstegosaurus [75pt]
pngが与えられます。ステガノグラフィー解析する問題です。
ステガノグラフィー解析系はすごく苦手なのですが、とりあえずうさみみハリケーンを起動します...
とりあえず赤、緑、青のみを取り出して怪しいところがないか調べていたら、赤色のLSBのみ抽出したときにフラグっぽい文字列が先頭に見えました。
こういう系、どういうところに着目して探せばよいのか全くわからない...
`bcactf{h15_n@m3_i5nt_g3rard}`
## Gerald's New Job [100pt]
pdfが与えられます。開くとフラグっぽい文字列がありますが、これがフラグなわけはないので、とりあえずpdfに怪しいものが隠れていないかbinwalkで探します。
するとzipが挟まっていて、zipの中にGeraldFlag.pngがあることも分かります。`binwalk -e gerald.pdf`でextractするとpngの中にフラグがありました。
## More than Meets the Eye [100pt]
:::spoiler zwsp.txt
Pretty empty over here.
:::
一見「Pretty empty over here.」という文字列しか無いように見えるが、実は「ゼロ幅スペース文字」が隠されています。
ゼロ幅スペースステガノグラフィーというものがあるらしく、[これ](http://330k.github.io/misc_tools/unicode_steganography.js)を使ってhidden textを2進数に変換し、long_to_bytesして解きました。
後から知りましたが、`\u200b`を0、`\u200c`を1に対応させて01の2進数としてあげればよかっただけでした。
`bcactf{z3r0_w1dth_jungl3_j82axH4}`
# rev
## Digitally Encrypted 1 [75pt]
頑張ってググると、.digファイルは[これ](https://github.com/hneemann/Digital)を使って開けばよいことが分かりました。
開いてみると論理回路が表示されます。
中身は平文をブロックごとにKeyとXORしているだけなので、暗号文をブロックごとにKeyとXORすればもとに戻せました。
`bcactf{that_was_pretty_simple1239152735}`
Sign in with Wallet
Connect another wallet