SECCON Beginners CTF 2021 writeup（crypto：Logical_SEESAW）

本記事について
crypto（Logical_SEESAW）
SECCON Beginners CTF 2021に関する記事

本記事について

2021年5月22日と2021年5月23日に開催された「SECCON Beginners CTF 2021」の「crypto」の「Logical_SEESAW」問題について、解きましたので、手順を詳細に記載します。

crypto（Logical_SEESAW）

以下の問題文に記載があり、問題文から新しい暗号アルゴリズムを使って暗号化した結果を復号化する問題のようです。

ファイルを解凍すると、以下の2つのファイルがありました。

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)

cipher = ['11000010111010000100110001000000010001001011010000000110000100000100011010111110000010100110000001101110100110100100100010000110001001101000101010000010101000100000001010100010010010001011110001101010110100000010000010111110000010100010100011010010100010001001111001101010011000000101100', '11000110110010000100110001000000010001001111010010000110110000000110011010101110011010100110000010100110101100000100000000001110001001001000101000001010101001100000001010101010010110001001110001101010110100000110011010010110011000000100100011010000110010001001011001101010011000001101100', '11000010110010000100110001101000010001001111001000000110000100000110011000111110010010100110000000101110101101100000000010010110001001101000101010000010101000100000001000101110000010001001111001101010110100000010011010010110011000100000100011010010100010001001111001101010011000001101100', '11000110110010001100110000101000110001000111000000000110000000000110011010101110011000100110000010100110101101100100100010000100101001001000101010000010101000100000001010100110010010001001110001101010110000000110000010110110000000000000100011010010110010001011011001101010001000000111101', '11000110100010001100110000000000010001000111001010000110110100000110011010111110001010100110100011101110101110100010000000110100001001101000101010000010101001101000001000101000010010001001111001101010110000000010000010111110000000000010000011010010100010001001011001101010011000001111101', '11000010110010001100110001001000010001000011000000100110000000000110011010101110000010100110100011100110101110100010000000101100101001101000101010000010101001101000001010100010000010001011111001101010110100000110001010010110001010100100000011010010110010001011111001101010011000000101100', '11000110110010000100110001101000110001001011010000100110110000000110011000101110010000100110100001100110100110000000100010000110101001001000101010000010101001100000001000101110010010001011111001101010110000000010001010110110001010100110000011010000110010001011111001101010011000000101100', '11000010110010000100110000100000010001000111011000100110100000000110011000111110000010100110000001101110101111100100000010111110001001001000101000001010101001101000001000101010000110001011110001101010110000000110001010011110000010100010100011010010110010000011011001101010001000000111100', '11000010101010000100110001001000010001000011000000100110010000000100011000111110011000100110000001100110100101000010000000011100101001101000101000001010101001101000001010101110010110001001110001101010110000000010010010110110011000000010100011010000100010001011111001101010001000000101100', '11000010101010001100110000100000010001001111001010000110000000000100011010101110011000100110000011100110100111100110100000000110001001001000101010000010101000100000001000101100010010001011110001101010110000000110011010010110011010000000000011010010100010001011011001101010011000001101101', '11000010101010001100110001000000010001001011010010000110010100000100011000111110011000100110000010100110100111000100000000000100101001101000101010001010101000100000001000100000000110001001111001101010110000000110011010010110000010000100100011010000110010000011011001101010001000001101100', '11000110101010001100110001000000110001001111001010000110110000000110011010101110011000100110100001100110101111000100100010011110101001001000101010001010101000101000001000101100000110001011111001101010110100000010011010011110001000000100100011010010100010000001011001101010011000001111100', '11000110100010001100110001000000010001001011011010100110000000000100011000101110001000100110100001101110101101000110100010001100101001001000101010000010101000100000001010101100000010001001111001101010110100000110011010010110010000100110100011010010110010001001111001101010011000001101101', '11000110101010000100110000000000010001001111001010100110100100000100011010111110001000100110100001101110101100000000100000111110001001101000101000001010101001101000001010100110010010001011110001101010110100000110000010010110001010000010100011010010110010001001011001101010001000000101100', '11000010101010000100110000000000110001001011011010100110110000000110011000101110010010100110100000100110101111000010000000100100001001001000101000001010101001100000001000100000000010001011110001101010110000000010011010011110001010000000000011010010100010001001011001101010001000000101101', '11000110101010001100110001000000110001001111011000000110010100000100011000101110001010100110000001101110101110000100100000101110101001101000101000000010101000100000001010101010000010001011110001101010110000000010000010010110001000100100100011010000100010000001011001101010001000001111101']

参考までに、上記のプログラムの以下の関数を使用しています。

関数	概要
bit_length()	整数を符号と先頭の 0 は除いて二進法で表すために必要なビットの数を返します。
getrandbits(k)	k個のランダムビットを持つ正の数のPython整数を返します。

暗号化処理している「for _ in range(16):」配下のプログラムの動作は以下の通りです。

約50%の確率で平文（フラグ）のビットと乱数で生成したビットをand条件暗号化する
約50%の確率で平文（フラグ）のビットがそのまま出力される
上記の何れかの処理を16回実施して、文字列連結する

平文（フラグ）を「10111000」で、暗号化を「00101110」とすると以下のイメージ図のように暗号化します。
暗号文の結果が提供されているため、16個の暗号文のOR条件を計算したら平文（フラグ）が出力されます。
しかし、「平文：1」で「暗号鍵：0」のANDを16回とってしまった場合は、復号化できません。そのような場合になるのは50%の確率で実施するAND条件の算出が16回連続で実施させる確率ですので、かなり低い可能性です。

上記の条件をもとに、暗号文16回のOR条件を算出して、文字列に変換する以下のプログラムを作成します。
プログラムを実行すると、フラグ（ctf4b{Sh3_54w_4_SEESAW,_5h3_54id_50}）が出力されました。

from Crypto.Util.number import *

# 提供されたoutput.txtの値
cipher=(中略)

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"+ciph
er[14]+"|"+"0b"+cipher[15])))

SECCON Beginners CTF 2021に関する記事

SECCON Beginners CTF 2021についての関連記事は以下の通りです。
必要に応じて、ご確認ください。

No	タイトル	記事の概要
1	SECCON Beginners CTF 2021 writeup	以下のカテゴリの問題のwriteupを記載します。【カテゴリ：welcome】　　・welcome 【カテゴリ：crypto】　　・imple_RSA 【カテゴリ：reversing】　　・only_read 　　・children 【カテゴリ：pwnable】　　・rewriter 【カテゴリ：web】　　・osoba 【カテゴリ：misc】　　・git-leak 　　・Mail_Address_Validator
2	SECCON Beginners CTF 2021 writeup （crypto：simple_RSA）	cryptカテゴリのsimple_RSAの問題の writeupを記載します。
3	SECCON Beginners CTF 2021 writeup （crypto：Logical_SEESAW）	cryptカテゴリのLogical_SEESAWの問題の writeupを記載します。
4	SECCON Beginners CTF 2021 writeup （crypto：GFM）	cryptカテゴリのGFMの問題の writeupを記載します。
5	SECCON Beginners CTF 2021 writeup （crypto：Imaginary）	cryptカテゴリのImaginaryの問題の writeupを記載します。
6	SECCON Beginners CTF 2021 writeup （web：Werewolf）	webカテゴリのWerewolfの問題の writeupを記載します。
7	SECCON Beginners CTF 2021 writeup （web：check_url）	webカテゴリのcheck_urlの問題の writeupを記載します。
8	SECCON Beginners CTF 2021 writeup （web：json）	webカテゴリのjsonの問題の writeupを記載します。
9	SECCON Beginners CTF 2021 writeup （web：cant_use_db）	webカテゴリのcant_use_dbの問題の writeupを記載します。