InterKosenCTF2019 Kurukuru Shuffle Writeup

InterKosenCTF2019に参加しました。Kurukuru Shuffle のWriteupです。

1. 問題

「kurukuru_shuffle.tar.gz」が与えられます。ジャンルは「crypto」です。

2. 解説

与えられたファイルを展開すると, 「encrypted」「shuffle.py」が出てきます。「encrypted」はテキストファイルとなっており, 暗号化されたフラグが入っています。「shuffle.py」は以下のようになっています。

from secret import flag
from random import randrange


def is_prime(N):
    if N % 2 == 0:
        return False
    i = 3
    while i * i < N:
        if N % i == 0:
            return False
        i += 2
    return True


L = len(flag)
assert is_prime(L)

encrypted = list(flag)
k = randrange(1, L)
while True:
    a = randrange(0, L)
    b = randrange(0, L)

    if a != b:
        break

i = k
for _ in range(L):
    s = (i + a) % L
    t = (i + b) % L
    encrypted[s], encrypted[t] = encrypted[t], encrypted[s]
    i = (i + k) % L

encrypted = "".join(encrypted)
print(encrypted)

ソースコードを読んでいくと, 「for _ in range(L):」のところでひたすらフラグを入れ替えています。また, キーは「k」「a」「b」であるとわかります。したがって, この３つで全数探索を行うと復号ができると考えられます。復号のためのソースコードは以下のようになります。

from random import randrange

encryptedFlag = "1m__s4sk_s3np41m1r_836lly_cut3_34799u14}1osenCTF{5sKm"
L = len(encryptedFlag)

for k in range(1, L):
    for a in range(L):
        for b in range(L):
            if a == b:
                continue
            decrypted = list(encryptedFlag)
            i = k
            for _ in range(L):
                s = (i + a) % L
                t = (i + b) % L
                decrypted[s], decrypted[t] = decrypted[t], decrypted[s]
                i = (i + k) % L
            
            decrypted = "".join(decrypted)
            print(decrypted)

このプログラムを実行すると, 全数探索の結果が出力されます。あとは, 出力結果から「KosenCTF」から始まるものを探せばOKです。