3時くらいに思い出し子をあやしながらXorshiftStreamの解法について考えていたが一問も解けず・・・

XorshiftStream (コンテスト終了後にAC)

64-bit Xorshift RNGが与えられる。パラメータ(13,7,17)。 keyの16進値アスキー文字列バイト列と (flag ^ key) した文字列を結合したバイト列に対して8byte毎にxorした結果が与えられるので解読してください。

考えたこと - パラメータは(a,b,c)=(13, 7, 17)でなかなか周期的な欠点を突くのは難しそう。 - 'Alpaca{'が7文字なので1文字全探索すれば8バイトの完全なstateがわかり、それを軸に何か頑張れるかな...などを考えつつ、そもそもRNGの出力が生で1つも得られなさそうなので困っていた。 - Xorshiftってs->s'の遷移をs'->sに逆演算できるんだっけ...と考えてみたがあんまり良い方法を思いつかないし無理そう。

Xorshiftの出力列が得られている時にseedを復元する方法をググると以下の記事が出てくる。この記事では下位16bitの出力結果から復元しているよう

burion.net

何かしらの方法で出力列の全部でなくとも一部を見つける方法はないか?

と考えていたら、keyを16進値の"アスキー"(超重要)でバイト列にしていることに今更気づく(5:30)。アスキーなので8ビット目が常に0なことを考えれば、ここの値だけに着目して連立合同式を解けないかz3のライブラリについて調べてみる。

Claudeさんありがとう。詳しいことはさておきまあどうもそういうことは可能っぽいのでやってみる。

とりあえず64bit乱数列の8,16,24,32,40,48,56,64ビット目はそのままリークしているという条件で書いてみるがUnsat!と言われまくり、もしかしてより多くの情報が必要なんじゃないか?と焦りhexなら上位4ビットが0110になるのでは...と断定したコードを書くもまたUnsatと言われ撃沈。そのまま時間切れ

結局色々なミスをやらかしていた。

そもそも上位桁は0110(a~f)もしくは0011(0~9)になるというのが正しい
そもそも出力列を8バイトずつ区切ってbytes_to_longで出力していたがBig Endianなので逆になっちゃっている。int.from_bytes(*,'little')を使うべき

あとでTwitterで色々指摘され、ASCIIであることからわかるのは1バイトが"0x1xxxxx"であることだけなので(2bitわかる!)、結局「64bit乱数列の6,8,14,16,22,24,30,32,38,40,46,48,54,56,62,64ビット目がリークしている」という条件で書き上げればseed=13077903722997275345がわかり、あとは頑張って復元して

Alpaca{I'v3_n3v3r_seen_4_c1ient_51d3_CryptoWeb_ch4ll3ng3_0nce!}

となった。コード

import struct
from Crypto.Util.strxor import strxor
from z3 import z3, BitVecVal

class XorshiftStream:
    def __init__(self, key: int):
        self.state = key % 2 ** 64

    def _next(self):
        self.state = (self.state ^ (self.state << 13)) % 2 ** 64
        self.state = (self.state ^ (self.state >> 7)) % 2 ** 64
        self.state = (self.state ^ (self.state << 17)) % 2 ** 64
        return self.state

    def encrypt(self, data: bytes):
        ct = b""
        for i in range(0, len(data), 8):
            pt_block = data[i: i + 8]
            ct += (int.from_bytes(pt_block, "little") ^ self._next()).to_bytes(
                8, "little"
            )[: len(pt_block)]
        return ct

    def decrypt(self, data: bytes):
        # 実はencryptとdecryptは全く同じ挙動
        return self.encrypt(data)


def reconstruct_seed_by_z3(encrypted_int64s):
    solver = z3.Solver()
    and_bit_mask = 0
    xor_bit_mask = 0
    for i in range(0, 64, 8):
        # ASCIIの8ビット目(0)と6ビット目(1)がリークしているはず
        and_bit_mask |= int("10100000", 2) << i
        xor_bit_mask |= int("00100000", 2) << i

    s = z3.BitVec("s", 64)
    for i in encrypted_int64s:
        s = s ^ (s << 13)
        s = s ^ z3.LShR(s, 7)
        s = s ^ (s << 17)
        t = BitVecVal(i, 64)
        # 8ビット目と6ビット目だけに着目してる
        solver.append((s & and_bit_mask) == ((t ^ xor_bit_mask) & and_bit_mask))

    if solver.check() != z3.sat:
        raise Exception("unsat !!!")
    model = solver.model()
    states = {str(s): model[s] for s in model}
    seed = states["s"].as_long()
    print("Predicted initial seed", seed)
    return seed


# From output.txt
c = "142d35c86db4e4bb82ca5965ca1d6bd55c0ffeb35c8a5825f00819821cd775c4c091391f5eb5671b251f5722f1b47e539122f7e5eadc00eee8a6a631928a0c14c57c7e05b6575067c336090f85618c8e181eeddbb3c6e177ad0f9b16d23c777b313e62b877148f06014e8bf3bc156bf88eedd123ba513dfd6fcb32446e41a5b719412939f5b98ffd54c2b5e44f4f7a927ecaff337cddf19fa4e38cbe01162a1b54bb43b0678adf2801d893655a74c656779f9a807c3125b5a30f4800a8"
assert len(c) % 3 == 0
key_length = len(c) // 3
assert key_length == 126

bs = bytes.fromhex(c)

# keyの長さは126バイトなので120バイト分=15だけ
encrypted_key_part_int64s = struct.unpack_from("<QQQQQQQQQQQQQQQ", bs)
assert len(encrypted_key_part_int64s) == 15
# encrypted_key_part = struct.unpack_from("<QQQQQ", bs)  # ちなみにこれでも80ビットリークしており、十分みたい

seed = reconstruct_seed_by_z3(encrypted_key_part_int64s)


# (org code) xss = XorshiftStream(secrets.randbelow(2 ** 64))
xss = XorshiftStream(seed)

# (org code) key = secrets.token_bytes(len(FLAG))
decrypted = xss.decrypt(bs)

key_part = decrypted[:key_length]
print("Encoded key: ", key_part)

key = bytes.fromhex(key_part.decode())
print("Byte key", key)


# (org code) FLAG = os.environ.get("FLAG", "fakeflag").encode()
FLAG_before_xor = decrypted[key_length:]

# (org code) c = xss.encrypt(key.hex().encode() + strxor(key, FLAG))
print(strxor(key, FLAG_before_xor))
# 出力: b"Alpaca{I'v3_n3v3r_seen_4_c1ient_51d3_CryptoWeb_ch4ll3ng3_0nce!}"

他の問題

やる時間なかった。アルパカハック難しいよ〜

kyuridenamidaのブログ

AlpacaHack Round5 Writeup

XorshiftStream (コンテスト終了後にAC)

他の問題