SECCON Beginners CTF 2021 crypto 02 Logical_SEESAW Writeup

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])))