SECCON Beginners CTF 2021 crypto 02 Logical_SEESAW Writeup
pythonを勉強している者として，絶対に勝たなければいけない問題。
解けて，ほっとしている。
入手データ
problem.py
output.txt
problem.py
from Crypto.Util.number import *
from random import random, getrandbits
from flag import flag
flag = bytes_to_long(flag.encode("utf-8"))
length = flag.bit_length()
key = getrandbits(length)
while not length == key.bit_length():
key = getrandbits(length)
flag = list(bin(flag)[2:])
key = list(bin(key)[2:])
cipher_L = []
for _ in range(16):
cipher = flag[:]
m = 0.5
for i in range(length):
n = random()
if n > m:
cipher[i] = str(eval(cipher[i] + "&" + key[i]))
cipher_L.append("".join(cipher))
print("cipher =", cipher_L)
output.txt
cipher = ['11000010111010000100110001000000010001001011010000000110000100000100011010111110000010100110000001101110100110100100100010000110001001101000101010000010101000100000001010100010010010001011110001101010110100000010000010111110000010100010100011010010100010001001111001101010011000000101100', '11000110110010000100110001000000010001001111010010000110110000000110011010101110011010100110000010100110101100000100000000001110001001001000101000001010101001100000001010101010010110001001110001101010110100000110011010010110011000000100100011010000110010001001011001101010011000001101100', '11000010110010000100110001101000010001001111001000000110000100000110011000111110010010100110000000101110101101100000000010010110001001101000101010000010101000100000001000101110000010001001111001101010110100000010011010010110011000100000100011010010100010001001111001101010011000001101100', '11000110110010001100110000101000110001000111000000000110000000000110011010101110011000100110000010100110101101100100100010000100101001001000101010000010101000100000001010100110010010001001110001101010110000000110000010110110000000000000100011010010110010001011011001101010001000000111101', '11000110100010001100110000000000010001000111001010000110110100000110011010111110001010100110100011101110101110100010000000110100001001101000101010000010101001101000001000101000010010001001111001101010110000000010000010111110000000000010000011010010100010001001011001101010011000001111101', '11000010110010001100110001001000010001000011000000100110000000000110011010101110000010100110100011100110101110100010000000101100101001101000101010000010101001101000001010100010000010001011111001101010110100000110001010010110001010100100000011010010110010001011111001101010011000000101100', '11000110110010000100110001101000110001001011010000100110110000000110011000101110010000100110100001100110100110000000100010000110101001001000101010000010101001100000001000101110010010001011111001101010110000000010001010110110001010100110000011010000110010001011111001101010011000000101100', '11000010110010000100110000100000010001000111011000100110100000000110011000111110000010100110000001101110101111100100000010111110001001001000101000001010101001101000001000101010000110001011110001101010110000000110001010011110000010100010100011010010110010000011011001101010001000000111100', '11000010101010000100110001001000010001000011000000100110010000000100011000111110011000100110000001100110100101000010000000011100101001101000101000001010101001101000001010101110010110001001110001101010110000000010010010110110011000000010100011010000100010001011111001101010001000000101100', '11000010101010001100110000100000010001001111001010000110000000000100011010101110011000100110000011100110100111100110100000000110001001001000101010000010101000100000001000101100010010001011110001101010110000000110011010010110011010000000000011010010100010001011011001101010011000001101101', '11000010101010001100110001000000010001001011010010000110010100000100011000111110011000100110000010100110100111000100000000000100101001101000101010001010101000100000001000100000000110001001111001101010110000000110011010010110000010000100100011010000110010000011011001101010001000001101100', '11000110101010001100110001000000110001001111001010000110110000000110011010101110011000100110100001100110101111000100100010011110101001001000101010001010101000101000001000101100000110001011111001101010110100000010011010011110001000000100100011010010100010000001011001101010011000001111100', '11000110100010001100110001000000010001001011011010100110000000000100011000101110001000100110100001101110101101000110100010001100101001001000101010000010101000100000001010101100000010001001111001101010110100000110011010010110010000100110100011010010110010001001111001101010011000001101101', '11000110101010000100110000000000010001001111001010100110100100000100011010111110001000100110100001101110101100000000100000111110001001101000101000001010101001101000001010100110010010001011110001101010110100000110000010010110001010000010100011010010110010001001011001101010001000000101100', '11000010101010000100110000000000110001001011011010100110110000000110011000101110010010100110100000100110101111000010000000100100001001001000101000001010101001100000001000100000000010001011110001101010110000000010011010011110001010000000000011010010100010001001011001101010001000000101101', '11000110101010001100110001000000110001001111011000000110010100000100011000101110001010100110000001101110101110000100100000101110101001101000101000000010101000100000001010101010000010001011110001101010110000000010000010010110001000100100100011010000100010000001011001101010001000001111101']
これを見た第一印象。
とりあえず時間がかかりそうなので後回し。
これを解いたのは２日目の午前中。
歳のせいか，まったく閃きがなく，problem.py を地道に解明することにした。
閃きがある人は，problem.py を見ないで output.txt だけでこの問題を解いたと思う。
problem.py の解明
from flag import flag って何？
problem.pyと同じディレクトリに flag.py というファイルを作成する
flag.py
flag = "ctf4b{AAA}"
problem改.py
from flag import flag
print(flag)
ctf4b{AAA}が出力された。
この状態で python problem.py > test.txt を実行すると
test.txt
ctf4b{AAA}
cipher = ['1100010011101000010011000000100010000100101101101000001010000010000000101011101', '1100010011101000110001000010000010000000101101101000001000000010000000101111101', '1100010011101000000001000010000010000100101101101000001000000010100000101010001', '1100010011101000010011000000000010000100111101101000001000000010100000101110101', '1100010011101000100001000010000010000000101101101000001010000010000000101011001', '1100010011101000010011000000100010000000101101101000001010000010100000101010101', '1100011011101000110001000110000011000000101101101000001000000010100000100010101', '1100011011101000010001000100000010000100101101101000001010000010100000100111001', '1100011011101000110011000100000011000000101101101000001000000010100000100111101', '1100011011101000010011000010000010000000101101101000001000000010100000100111101', '1100011011101000010001000100100011000000101101101000001000000010100000100110001', '1100010011101000010001000000000011000100111101101000001000000010100000100011101', '1100010011101000010011000100100011000000111101101000001000000010100000101110001', '1100010011101000100001000000100010000100101101101000001000000010000000101110001', '1100011011101000000011000010100011000000111101101000001010000010000000100111001', '1100010011101000000001000100000010000100111101101000001000000010000000100111101']
再現できた。
配列が16個できた。
２進数の長さは，output.txtより短い。＝本物のflagはもっと長いはず。
後は，print文を入れまくって謎を解くだけ。
２進数の長さであるが，
problem改.py
print(flag)
flag = bytes_to_long(flag.encode("utf-8"))
print(flag)
print(bin(flag))
の結果を見ると
>python problem2.py
ctf4b{AAA}
469661468736217357042045
0b1100011011101000110011000110100011000100111101101000001010000010100000101111101
test.txtとoutput.txt の分析から，これらの２進数は flagと同じ文字長のデータを long に加工し，さらに２進数にしたものと判明。
flag = list(bin(flag)[2:])って何？
これは bin() で２進数に変換したときに頭につく 0b を除去している
暗号化キー
problem改.py
key = getrandbits(length)
while not length == key.bit_length():
key = getrandbits(length)
print("key= "+str(key))
flagと同じ長さのランダム値
key= 358627437659718300899429
key= 542345662730517676205014
key= 401868384748730272520438
...
規則性なし
keyを特定することは不可能
暗号化ロジック
problem改.py
for _ in range(16):
cipher = flag[:]
m = 0.5
for i in range(length):
n = random()
print(n)
if n > m:
cipher[i] = str(eval(cipher[i] + "&" + key[i]))
cipher_L.append("".join(cipher))
まず random() で求める n であるが規則性はなかった。
n=0.6985737873463962
n=0.06041478251221988
n=0.9172107162824306
...
大きいループは16回で，その中で全ビットを処理するループがある。
フラグとkeyをビット単位で AND してるが，
random() で求める n （ 0.0 ～ 1.0 ）と 0.5 を比べて確率２分の１で
AND して flag のビットを書き換えるか AND しないでそのままとするかを決定している。
なるほど。だから問題名が SEESAW ね。
よく考えてるw
AND される場合（未知のkeyによってenc1は変化する）※この変化は情報が減る
| flag | key | enc1 |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
AND されない場合（enc2 = flag）
| flag | key | enc2 |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
enc1 と enc2 を OR すると必ず flag に戻る
| enc1 | enc2 | flag(OR) |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 1 | 1 |
２分の１の確率でANDが行われず素のflagが残るので，ほぼ確実にするため16回結果を残している。
ちなみに16回やると作問に失敗する（flagに戻らないものが出来る）確率は約0.0016%のはず。
ANDする確率が1/2で ANDしてflagが変わる確率が1/4なので，データ消失率的には1/8
flagに戻らないものが出来る確率は(1/8)**16かな？
solver の作成
最初に言ったように，output.txtを加工( OR )するだけ
solver.py
from Crypto.Util.number import *
# copy from output.txt
cipher = ['11000010111010000100110001000000010001001011010000000110000100000100011010111110000010100110000001101110100110100100100010000110001001101000101010000010101000100000001010100010010010001011110001101010110100000010000010111110000010100010100011010010100010001001111001101010011000000101100', '11000110110010000100110001000000010001001111010010000110110000000110011010101110011010100110000010100110101100000100000000001110001001001000101000001010101001100000001010101010010110001001110001101010110100000110011010010110011000000100100011010000110010001001011001101010011000001101100', '11000010110010000100110001101000010001001111001000000110000100000110011000111110010010100110000000101110101101100000000010010110001001101000101010000010101000100000001000101110000010001001111001101010110100000010011010010110011000100000100011010010100010001001111001101010011000001101100', '11000110110010001100110000101000110001000111000000000110000000000110011010101110011000100110000010100110101101100100100010000100101001001000101010000010101000100000001010100110010010001001110001101010110000000110000010110110000000000000100011010010110010001011011001101010001000000111101', '11000110100010001100110000000000010001000111001010000110110100000110011010111110001010100110100011101110101110100010000000110100001001101000101010000010101001101000001000101000010010001001111001101010110000000010000010111110000000000010000011010010100010001001011001101010011000001111101', '11000010110010001100110001001000010001000011000000100110000000000110011010101110000010100110100011100110101110100010000000101100101001101000101010000010101001101000001010100010000010001011111001101010110100000110001010010110001010100100000011010010110010001011111001101010011000000101100', '11000110110010000100110001101000110001001011010000100110110000000110011000101110010000100110100001100110100110000000100010000110101001001000101010000010101001100000001000101110010010001011111001101010110000000010001010110110001010100110000011010000110010001011111001101010011000000101100', '11000010110010000100110000100000010001000111011000100110100000000110011000111110000010100110000001101110101111100100000010111110001001001000101000001010101001101000001000101010000110001011110001101010110000000110001010011110000010100010100011010010110010000011011001101010001000000111100', '11000010101010000100110001001000010001000011000000100110010000000100011000111110011000100110000001100110100101000010000000011100101001101000101000001010101001101000001010101110010110001001110001101010110000000010010010110110011000000010100011010000100010001011111001101010001000000101100', '11000010101010001100110000100000010001001111001010000110000000000100011010101110011000100110000011100110100111100110100000000110001001001000101010000010101000100000001000101100010010001011110001101010110000000110011010010110011010000000000011010010100010001011011001101010011000001101101', '11000010101010001100110001000000010001001011010010000110010100000100011000111110011000100110000010100110100111000100000000000100101001101000101010001010101000100000001000100000000110001001111001101010110000000110011010010110000010000100100011010000110010000011011001101010001000001101100', '11000110101010001100110001000000110001001111001010000110110000000110011010101110011000100110100001100110101111000100100010011110101001001000101010001010101000101000001000101100000110001011111001101010110100000010011010011110001000000100100011010010100010000001011001101010011000001111100', '11000110100010001100110001000000010001001011011010100110000000000100011000101110001000100110100001101110101101000110100010001100101001001000101010000010101000100000001010101100000010001001111001101010110100000110011010010110010000100110100011010010110010001001111001101010011000001101101', '11000110101010000100110000000000010001001111001010100110100100000100011010111110001000100110100001101110101100000000100000111110001001101000101000001010101001101000001010100110010010001011110001101010110100000110000010010110001010000010100011010010110010001001011001101010001000000101100', '11000010101010000100110000000000110001001011011010100110110000000110011000101110010010100110100000100110101111000010000000100100001001001000101000001010101001100000001000100000000010001011110001101010110000000010011010011110001010000000000011010010100010001001011001101010001000000101101', '11000110101010001100110001000000110001001111011000000110010100000100011000101110001010100110000001101110101110000100100000101110101001101000101000000010101000100000001010101010000010001011110001101010110000000010000010010110001000100100100011010000100010000001011001101010001000001111101']
print(long_to_bytes(eval("0b"+cipher[0]+"|"+"0b"+cipher[1]+"|"+"0b"+cipher[2]+"|"+"0b"+cipher[3]+"|"+"0b"+cipher[4]+"|"+"0b"+cipher[5]+"|"+"0b"+cipher[6]+"|"+"0b"+cipher[7]+"|"+"0b"+cipher[8]+"|"+"0b"+cipher[9]+"|"+"0b"+cipher[10]+"|"+"0b"+cipher[11]+"|"+"0b"+cipher[12]+"|"+"0b"+cipher[13]+"|"+"0b"+cipher[14]+"|"+"0b"+cipher[15])))