好奇心の足跡

飽きっぽくすぐ他のことをしてしまうので、忘れないため・形にして頭に残すための備忘録。

SECCON BeginnersCTF 2018 復習 [Crypto] Streaming

SECCON BeginnersCTF 2018 に参加したので wite-upを書いたけど 解けなかった問題が多かったしコンテスト環境しばらく残していただけるそうなので、後追いでやってみる。(ほぼ大会中の話だったりする)

write-upはこちら kusuwada.hatenablog.com

[Crypto] Streaming

問題

問題文なし。下記のスクリプトencryptedバイナリが配布される。

encrypt.py

import os
from flag import flag


class Stream:
    A = 37423
    B = 61781
    C = 34607
    def __init__(self, seed):
        self.seed = seed % self.C

    def __iter__(self):
        return self

    def next(self):
        self.seed = (self.A * self.seed + self.B) % self.C
        return self.seed

g = Stream(int(os.urandom(8).encode('hex'), 16))

encrypted = ''
for i in range(0, len(flag), 2):
    a = int(flag[i:i+2].encode('hex'), 16) ^ g.next()
    encrypted += chr(a % 256)
    encrypted += chr(a / 256)

open('encrypted', 'wb').write(encrypted)

encrypt.py で暗号化された出力が配布された encrypted。このスクリプトから、Stream暗号化がなされているのがわかる。
next を呼ぶと、現在の seed をもとに次の seed が生成されており、そのseedとflag(2バイトずつ処理)のXORで暗号化後の文が生成されている。

encryptedのバイナリから逆にたどっていくのは不可能なので、streamを適当に選択して頭から処理していき、それっぽいものを見つけていくしかない。

seedの処理を見てみると、初期seedは

class Stream:
    def __init__(self, seed):
        self.seed = seed % self.C
    
g = Stream(int(os.urandom(8).encode('hex'), 16))

と与えられており、% self.C が最後に施されているので、seedの範囲は 0~34607 ということがわかる。

ということは、この範囲のseedを片っ端から試していって、flagのフォーマットにあっているやつを見つければOK!!!

findflag.py

#!/usr/bin/env python3
# -*- coding:utf-8 -*-

from encrypt import Stream

encrypted = None
with open('encrypted', 'rb') as f:
    encrypted = f.read()
print(encrypted)

for seed in range(34607):
    g = Stream(seed)
    flag = ''
    for i in range(0, len(encrypted), 2):
        a = encrypted[i+1] * 256 + encrypted[i]
        a ^= g.next()
        flag += chr(a//256) + chr(a%256)
    if flag.startswith('ctf4b{'):
        print(flag)
        break

flag: ctf4b{lcg-is-easily-predictable}

※ python3でencrpyt.pyを動かそうとすると下記を書き換える必要あり。また、flagなど与えられていないimportは適当にごまかす必要あり。

int(os.urandom(8).encode('hex'), 16)

int.from_bytes(os.urandom(8), sys.byteorder)

もしくは必要なの Streamクラス だけなので、import せずに findflag.py にコピペ。

感想

python3で動かないわーってなってそのまま後回しにして解き忘れていた。もったいない。

他の SECCON BeginnersCTF 2018 関連記事リンク

kusuwada.hatenablog.com

kusuwada.hatenablog.com

kusuwada.hatenablog.com

kusuwada.hatenablog.com