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で動かないわーってなってそのまま後回しにして解き忘れていた。もったいない。
