SECCON Beginners CTF 2023 作問者Writeup

はじめに

SECCON Beginners CTF 2023のCryptoの作問(&review)を担当させていただきました。
Conquer, switchable_catの作問をしたのでそれぞれの作問者想定解法とお気持ちを書いていきます。
各作問者WriteupはxryuseixさんのWriteupでまとめてあるのでそちらを参照してください。また作問者Writeupは正解というわけではないので、みなさまのWrirteupをぜひお待ちしております！運営一同エゴサします。

• 開催概要
  • スコアサーバURL：https://score.beginners.seccon.jp/
  • 開始時刻：2023/06/03（土）14:00 JST
  • 終了時刻：2023/06/04（日）14:00 JST

[Easy] Conquer ( 84 points / 152 solves )

problem.py

from Crypto.Util.number import *
from random import getrandbits
from flag import flag


def ROL(bits, N):
    for _ in range(N):
        bits = ((bits << 1) & (2**length - 1)) | (bits >> (length - 1))
    return bits


flag = bytes_to_long(flag)
length = flag.bit_length()

key = getrandbits(length)
cipher = flag ^ key

for i in range(32):
    key = ROL(key, pow(cipher, 3, length))
    cipher ^= key

print("key =", key)
print("cipher =", cipher)

暗号化部分に注目すると、

for i in range(32):
    key = ROL(key, pow(cipher, 3, length))
    cipher ^= key

となっています。上のコードは、

\begin{equation}
\left\{ \,
    \begin{aligned}
        & key_1 = ROL(key_0, cipher_{0}^3 \ \mathbb{mod} \ length) \\
        & cipher_1 = cipher_{0} \oplus key_{1}
    \end{aligned}
\right.
\\ \vdots \\
\left\{ \,
    \begin{aligned}
        & key_{32} = ROL(key_{31}, cipher_{31}^3 \ \mathbb{mod} \ length) \\
        & cipher_{32} = cipher_{31} \oplus key_{32}
    \end{aligned}
\right.
\end{equation}

と表すことができます。ここの$key_i$はROL()で更新されているので、その関数について考えてみます。関数内のワンライナーで書かれている処理は以下のように分割できます。

def ROL(bits, N):
    for _ in range(N):
        a = (bits << 1) & (2**length - 1)
        b = bits >> (length - 1)
        bits = a | b
    return bits

aにはbitsを1回左シフトして下位lengthbit分を抽出した値が代入され、bにはbitsのMSB(最高位bit)を抽出した値が代入されています。次の行のa | bでは一番下に持ってきたMSBと、MSBを消して1bit左シフトした値を結合しています。それらの処理がN回ループしているのでROL()はbitsをNbit左に循環させる関数となっています。

例えばlength=6でROL(0b110101, 3)を計算させると返り値は二進数で10111となります。この処理のことをビットローテーションや循環シフトといい、実際googleで「ROL 演算」と検索していただくとその解説記事が出てくるかと思います。

このROL()は不可逆の処理ではなく例えばlength=10でROL(x, 4)の返り値が二進数で10101100だった場合、変数xは二進数で1100001010となります。ところでROLとはRotate Leftの略で、逆の処理はROR(Rotate Right)といいます。

ここで与えられている情報は$cipher_{32}$, $key_{32}$なので、それらからXOR演算で$cipher_{31}$を復元しRORで$key_{31}$を復元、$cipher_{31}$, $key_{31}$から$cipher_{30}$, $key_{30}$を……と復元していけば$cipher_{0}$を復元できると考えられます。これを実装すると次のようになります。

for i in range(32):
    cipher ^= key
    key = ROR(key, pow(cipher, 3, length))

あとの未知情報はlengthだけですが、key.bit_length()やcipher.bit_length()ではビット演算の性質上必ずしもMSBが1とは限らないので、cipher,key,flagのビット長が同じとは限りません。ただkeyがgetrandbits()で初期化されていることから、頭のbitが連続して0で欠損している数は多くないと考えられるので、適宜手動でインクリメントさせるだけで十分特定可能です。

これらの考察を踏まえて以降にソルバを示します。

solve.py

from Crypto.Util.number import *

def ROR(bits, N):
    for _ in range(N):
        bits = (bits >> 1) | ((bits & 1) << (length - 1))
    return bits

key = 364765105385226228888267246885507128079813677318333502635464281930855331056070734926401965510936356014326979260977790597194503012948
cipher = 92499232109251162138344223189844914420326826743556872876639400853892198641955596900058352490329330224967987380962193017044830636379
length = cipher.bit_length() + 3

for i in range(32):
    cipher ^= key
    key = ROR(key, pow(cipher, 3, length))

cipher ^= key

print(long_to_bytes(cipher))

[Medium] switchable_cat ( 179 points / 27 solves )

problem.py

from Crypto.Util.number import *
from secret import seed, flag
from random import getrandbits
from os import urandom


class LFSR:
    def __init__(self):
        self.bits = 128
        self.rr = seed
        self.switch = 0
    def next(self):
        r = self.rr
        if self.switch == 0:
            b = ((r >> 0) & 1) ^ \
                ((r >> 2) & 1) ^ \
                ((r >> 4) & 1) ^ \
                ((r >> 6) & 1) ^ \
                ((r >> 9) & 1)
        if self.switch == 1:
            b = ((r >> 1) & 1) ^ \
                ((r >> 5) & 1) ^ \
                ((r >> 7) & 1) ^ \
                ((r >> 8) & 1)
        r = (r >> 1) + (b << (self.bits - 1))
        self.rr = r
        self.switch = 1 - self.switch
        return r & 1
    
    def gen_randbits(self, bits):
        key = 0
        for i in range(bits):
            key <<= 1
            key += self.next()
        return key


lfsr = LFSR()

neko = urandom(ord("🐈")*ord("🐈")*ord("🐈"))
key = lfsr.gen_randbits(len(neko) * 8)
cipher = bytes_to_long(neko) ^ key

#   📄🐈💨💨💨💨
# ╭─^────────╮
# │  cipher  │
# ╰──────────╯

key = lfsr.gen_randbits(len(flag) * 8)
cipher = bytes_to_long(flag) ^ key

print("seed =", seed)
print("cipher =", cipher)

class名で定義されている通りこれは線形帰還シフトレジスタ(LFSR:Linear Feedback Shift Registerというアルゴリズムをベースに作成した乱数生成器です。一見するとseedが与えられているのでproblem.pyをそのまま実行することでフラグの暗号化に使用した乱数がそのまま手に入るように見えます。しかし、ねこちゃんの平文nekoを暗号化するのに使用した乱数の大きさは2097545240576512*8bitなのでそのまま実行しても実行は終わりません。なのでLFSRの高速化を行列累乗により実装して復号します。

LFSRの行列累乗による高速化とは何か、簡単のために6bitで帰還多項式が以下のようなLFSRを考えます。

b = ((r >> 1) & 1) ^ \
    ((r >> 2) & 1) ^ \
    ((r >> 3) & 1)

この乱数生成器から返される$n$番目の乱数$a_n$は初期シード$seed=s_0|s_1|s_2|s_3|s_4|s_5$を与えて

\begin{pmatrix}
   a_n \\
   a_{n-1} \\
   a_{n-2} \\
   a_{n-3} \\
   a_{n-4} \\
   a_{n-5}
\end{pmatrix}
=
\begin{pmatrix}
   0 & 0 & 0 & 1 & 1 & 1 \\
   1 & 0 & 0 & 0 & 0 & 0 \\
   0 & 1 & 0 & 0 & 0 & 0 \\
   0 & 0 & 1 & 0 & 0 & 0 \\
   0 & 0 & 0 & 1 & 0 & 0 \\
   0 & 0 & 0 & 0 & 1 & 0
\end{pmatrix}^n
\cdot
\begin{pmatrix}
   s_{0} \\
   s_{1} \\
   s_{2} \\
   s_{3} \\
   s_{4} \\
   s_{5}
\end{pmatrix}

と計算することができます。問題文の帰還多項式はswitchによって変わるのでswitch == 0, switch == 1の部分をそれぞれsagemathのMatrixSpace()を使用すると、

bits = 128
M = MatrixSpace(GF(2), bits, bits)
vec1, vec2 = [], []
v1, v2 = [0] * (bits - 10), [0] * (bits - 10)
vec1 += v1 + [1, 0, 0, 1, 0, 1, 0, 1, 0, 1]
vec2 += v2 + [0, 1, 1, 0, 1, 0, 0, 0, 1, 0]
for i in range(bits - 1):
    v = [0] * bits
    v[i] = 1
    vec1 += v[:]
    vec2 += v[:]

A1, A2 = M(vec1), M(vec2)

と定義することができます。flagを暗号化し始めた乱数すなわち、2097545240576512*8+1番目の乱数key_0は前のA,Bを使用して以下のように求めることができます。

seed = 219857298424504813337494024829602082766
neko = 8*ord("🐈")*ord("🐈")*ord("🐈")

A = (A1*A2)^(neko // 2)*A1
B = vector(list(map(int, list(bin(seed)[2:]))))
B = A * B

key_0 = int(list(B)[-1])

あとはswitchの値に気を付けながら内部状態を更新してflagの長さだけkeyを復元していけばいいので最終的なソルバは以下のようになります。

solve.sage

from Crypto.Util.number import *
from random import getrandbits


seed = 219857298424504813337494024829602082766
cipher = int(38366804914662571886103192955255674055487701488717997084670307464411166461113108822142059)

neko = 8*ord("🐈")*ord("🐈")*ord("🐈")
human = cipher.bit_length()+1
bits = 128
M = MatrixSpace(GF(2), bits, bits)
vec1, vec2 = [], []
v1, v2 = [0] * (bits - 10), [0] * (bits - 10)
vec1 += v1 + [1, 0, 0, 1, 0, 1, 0, 1, 0, 1]
vec2 += v2 + [0, 1, 1, 0, 1, 0, 0, 0, 1, 0]
for i in range(bits - 1):
    v = [0] * bits
    v[i] = 1
    vec1 += v[:]
    vec2 += v[:]

A1, A2 = M(vec1), M(vec2)
A = (A1*A2)^(neko // 2)*A1
B = vector(list(map(int, list(bin(seed)[2:]))))
B = A * B

switch = 1
key = 0
for i in range(human):
    key <<= 1
    key += int(list(B)[-1])
    if switch == 0:
        B = A1 * B
    if switch == 1:
        B = A2 * B
    switch = 1 - switch

flag = cipher ^^ key
print(long_to_bytes(flag))