yoshikingのがんばる日記

あたまよくないけどがんばります

Poseidon CTF Writeup

CTF

24hで開催されていたPoseidon CTFにzer0ptsで参加しました． チームとしては3位でした．

約4か月ぶりのCTFですかね． 個人では1問しか解いてない（しかも簡単なやつ）ですが、初心（writeupを書くまでがCTF）を思い出してWriteupを書こうと思います． zer0ptsの他メンバーマジで強いんでどんどんいい成績を残していきますが、僕自身は強くないので勘違いされないようにもこうやってWriteupを残した方がいいなと思った節もあります．

ctftime.org

チームメンバーのWriteup:

[Crypto 100pts] Triplet Bits Encryption

#!/usr/bin/env python3

from hashlib import sha256
from Crypto.Util.number import long_to_bytes, bytes_to_long
from Crypto.Random import get_random_bytes
from flag import flag

def mixkeybit(keybit1, keybit2, keybit3):
    return int(keybit1 or (not(keybit2) and keybit3))

key1 = get_random_bytes(32)
key2 = get_random_bytes(32)
key3 = get_random_bytes(32)

wfile = open('output.txt', 'w')

for _ in range(256):
    flagbin = bin(bytes_to_long(flag))[2:]
    encbin = ""
    for i in range(len(flagbin)):
        key1 = sha256(key1).digest()
        key2 = sha256(key2).digest()
        key3 = sha256(key3).digest()
        keybit1 = int(bin(bytes_to_long(key1))[2:][-1])
        keybit2 = int(bin(bytes_to_long(key2))[2:][-1])
        keybit3 = int(bin(bytes_to_long(key3))[2:][-1])
        encbin += str(mixkeybit(keybit1, keybit2, keybit3) ^ int(flagbin[i]))
    wfile.write(encbin)
    wfile.write('\n')
wfile.close()

flagを2進数にしたもの(flagbin)を1bitづつランダムな3つのkeyから生成したビットとxorしていて、それを256回繰り返したものがもらえます． 初めにkey1~3をget_random_bytes(32)で生成していて、その後も1回sha256で使うごとに更新しています． ここで使われているget_random_bytes()もsha256()もこれらからビットを復元することは無理そうです． また、mixkeybitで何か演算をしていますが、結局は1bitなのでそこまで気にしなくてよさそうです．

ここでう～んって言っていたら、@st98さんがmixkeybit(keybit1, keybit2, keybit3)に偏りがあることを教えてくれました． 取り敢えず、偏りとフラグのprefixを使ってその関係を見てみます．

from Crypto.Util.number import bytes_to_long
from collections import Counter
data = open("./output.txt", "r").read().strip().split("\n")

flag = b"Poseidon{"
flag = bin(bytes_to_long(flag))[2:]

for i in range(len(flag)):
    bits = []
    for c in data:
        bits.append(c[i])
    print(f"[+] {flag[i]}: {Counter(bits).most_common()}")

$ python solver.py 
[+] 1: [('0', 165), ('1', 91)]
[+] 0: [('1', 166), ('0', 90)]
[+] 1: [('0', 159), ('1', 97)]
[+] 0: [('1', 172), ('0', 84)]
[+] 0: [('1', 160), ('0', 96)]
[+] 0: [('1', 172), ('0', 84)]
[+] 0: [('1', 157), ('0', 99)]
[+] 0: [('1', 151), ('0', 105)]
[+] 1: [('0', 165), ('1', 91)]
[+] 1: [('0', 147), ('1', 109)]
[+] 0: [('1', 173), ('0', 83)]
[+] 1: [('0', 157), ('1', 99)]
[+] 1: [('0', 162), ('1', 94)]
[+] 1: [('0', 156), ('1', 100)]
[+] 1: [('0', 148), ('1', 108)]
[+] 0: [('1', 172), ('0', 84)]
[+] 1: [('0', 153), ('1', 103)]
[+] 1: [('0', 150), ('1', 106)]
[+] 1: [('0', 173), ('1', 83)]
[+] 0: [('1', 163), ('0', 93)]
[+] 0: [('1', 167), ('0', 89)]
[REDACTED]

この結果を見る限り、出現回数が少ない方をフラグのビットにすればうまくいきそうです．

from Crypto.Util.number import long_to_bytes
from collections import Counter

data = open("./output.txt", "r").read().strip().split("\n")

m = ""
for i in range(len(data[0])):
    bits = []
    for c in data:
        bits.append(c[i])
    m += Counter(bits).most_common()[1][0]
print("[+] flag:", long_to_bytes(int(m, 2)))

$ python solver.py 
[+] flag: b'Poseidon{7h3_u53_0f_pr0b4b1l17y_15_57r0n6}'

おわり

ブロック暗号イヤイヤ言ってられない～