- 以下の内容を踏まえると、暗号化に用いられたシード値を力技（※）で求められることが分かる。
- 平文の先頭8文字（64ビット）は b'CakeCTF{' 。
- シード値は64ビット。
- LSFRが出力する最初の64ビットはシード値と同じ。
- 平文の先頭1文字目のビット列から順番にLSFRの出力するビットとXORが取られ、暗号化ビットになる。
- 暗号化ビット列（task.pyの変数c）は上位ビットから順番に暗号化ビットが入っている。
- 暗号化ビット列がhex関数で変換される際、先頭から4ビット以上0が続く部分は無視される。
- hex関数で変換された出力は75桁、300ビット分。
- 37文字+4ビット分に相当。hex関数で無視されたビットが無いと仮定すると、4ビット分は制御文字LFと推測できる。
- LFは
0x0a のため、下位4ビットの暗号化が終わった時点で暗号化ビット列を出力するwhileループが終了する。
- ※暗号化ビット列がhex関数で変換される際に無視されたビット数が不明なため、暗号化ビット列の長さを仮置きする必要がある。この問題では無視されたビット数なしのパターンが正解だった。
- 仮にシード値が
0x7b465443656b6143 なら、暗号化ビット列の先頭64ビットは全て0になる。とはいえ、乱数で生成した値がこれと完全に一致する確率は無視できるレベル。
int.from_bytes(b'CakeCTF{', 'little') の値。
- 無視されたビットなし、1ビット無視、2ビット無視……と確率が高いパターン順に試していけば、いずれ当たりを引ける。
- 下記コードのdecrypt関数のoffset_bitsに負数を指定すると解読できるケースがあり、当初は理由が分からなかった。
- 原因）出力ビット列を逆順にする際、元の暗号化ビット列の長さを4で割った余りを4から引いた数だけ、下位ビットに0のビットが余計に追加されるため。
- 補足）元の暗号化ビット列の長さが4の倍数にならないのは、1ビットずつ出力していって0になったらループが終了するため。平文の最後が
} なら 0x7D → 0b0111_1101 なので7ビット出力した時点でループが終了する。
- z3pyを使うと、 LFSRの定義からほぼコピペするだけでシード値を求められる。便利！
import os
import random
from z3 import *
# ビット長を指定してビット列を逆順にする
# reversed_bits(0b0001, 4) #=> 0b1000
def reversed_bits(int_bits, length=8):
r = 0
for _ in range(length):
r = (r << 1) | (int_bits & 1)
int_bits >>= 1
return r
def LFSR(seed=None):
r = random.randrange(1 << 64) if seed is None else seed
while True:
yield r & 1
b = (r & 1) ^\
((r & 2) >> 1) ^\
((r & 8) >> 3) ^\
((r & 16) >> 4)
r = (r >> 1) | (b << 63)
def decrypt(output_int, offset_bits=0):
# シード値の推定 ########
l = len(hex(output_int)[2::]) * 4 + offset_bits
reversed_output = reversed_bits(output_int, l)
known = b'CakeCTF{'
seed = s = BitVec('seed', 64)
solv = Solver()
for i in range(len(known)):
for j in range(8):
lsb = ((reversed_output >> (i * 8 + j)) & 1) ^ ((known[i] >> j) & 1)
solv.add(lsb == (s & 1))
b = (s & 1) ^\
(LShR(s & 2, 1)) ^\
(LShR(s & 8, 3)) ^\
(LShR(s & 16, 4))
s = LShR(s, 1) | (b << 63)
r = solv.check()
if r == sat:
m = solv.model()
solution_seed = m[seed].as_long()
else:
print(r)
return None
# 復号化 ########
lfsr = LFSR(solution_seed)
flag_int = 0
for i in range(len(bin(reversed_output)[2:])):
flag_int |= ((((reversed_output >> i) & 1) ^ next(lfsr)) << i)
flag = ''
i = 0
while True:
c = (flag_int >> (i * 8)) & 0xFF
if c < 0x20 or c > 0x7E:
# フラグ文字列に含まれない文字が見つかったら復号化を停止
break
flag += chr(c)
i += 1
if len(flag) <= 9:
return None
if flag[-1] == '}':
return flag
else:
return None
if __name__ == '__main__':
with open(os.path.join(os.path.dirname(__file__), "output.txt"), "r") as f:
o = int(f.readline(), base=16)
flag = decrypt(o, 0)
if flag:
print(flag)
exit(0)
# ビット列逆転時にビットが増えるケースを想定。
# 例） 0b10011
# hex(0b10011) → '0x12'
# len('0x12'[2::]) * 4 → 8
# reversed_bits(0x12, 8) → 0b11001000
# 0b11001 != 0b11001000
for i in range(-1, -4, -1):
print(i, '', end='')
flag = decrypt(o, i)
if flag:
print()
print(flag)
exit(0)
# 暗号化ビット列の先頭に0が8個以上出力され、
# hexで変換した際に桁が減るケースを想定。
# シード値が b'CakeCTF{' なら64個以上の0が出力される。
for i in range(1, 8 * 10):
print(i,'',end='')
flag = decrypt(o, i)
if flag:
print()
print(flag)
exit(0)
print()
print('flag not found')