SECCON Beginners CTF 2023 CoughingFox2 作問者Writeup

この記事は何？

CoughingFox2の作問者Writeup。あくまで解き方の一例に過ぎないので、Twitter等で他の方のWriteupも確認すると良いと思う。

[crypto] CoughingFox2(388 solves)

問題文

暗号問題に初めて挑戦する方向けに独自暗号と暗号化した後の出力を配布します。 ご覧の通り、簡易な暗号方式なので解読は簡単です。 解読をお願いします！

The original cipher for beginners and encrypted text are provided. Needless to say, this cipher is too childish, and that easy to decrypt! So, could you please decrypt it?

配布されたソースコードと暗号化されたテキスト

# coding: utf-8
import random
import os

flag = b"ctf4b{xxx___censored___xxx}"

# Please remove here if you wanna test this code in your environment :)
flag = os.getenv("FLAG").encode()

cipher = []

for i in range(len(flag)-1):
    c = ((flag[i] + flag[i+1]) ** 2 + i)
    cipher.append(c)

random.shuffle(cipher)

print(f"cipher = {cipher}")

cipher = [4396, 22819, 47998, 47995, 40007, 9235, 21625, 25006, 4397, 51534, 46680, 44129, 38055, 18513, 24368, 38451, 46240, 20758, 37257, 40830, 25293, 38845, 22503, 44535, 22210, 39632, 38046, 43687, 48413, 47525, 23718, 51567, 23115, 42461, 26272, 28933, 23726, 48845, 21924, 46225, 20488, 27579, 21636]

解法

配布ファイルを見ると、処理はflagのi文字目とi+1文字目の数字を足して2乗してiを足し、最後に全ての文字をシャッフルであることが分かる。そのため、文字のシャッフル解除、flagの各文字の復元という順番に解けば良い。

まず、シャッフルの解除について。 c = ((flag[i] + flag[i+1]) ** 2 + i) を見た時に、 c-i が必ず自然数の2乗になることが分かる。したがって、以下の通りにcipherを1文字ずつ確認することでシャッフルを解除することができる。

実は昨年にCoughingFoxという類題が出題されていて、そのWriteupを見るとシャッフルは解除できるはず。ググることは大事。

import copy

# from cipher.txt
cipher = [4396, 22819, 47998, 47995, 40007, 9235, 21625, 25006, 4397, 51534, 46680, 44129, 38055, 18513, 24368, 38451, 46240, 20758, 37257, 40830, 25293, 38845, 22503, 44535, 22210, 39632, 38046, 43687, 48413, 47525, 23718, 51567, 23115, 42461, 26272, 28933, 23726, 48845, 21924, 46225, 20488, 27579, 21636]
ordered_cipher = copy.copy(cipher)

# 元の並び順の復元
for i in range(len(cipher)):
    c = cipher[i]
    for j in range(len(cipher)):
        if int(pow(c-j, 1/2)) ** 2 == c-j:
            ordered_cipher[j] = c-j
            break
cipher = ordered_cipher
print(cipher)
# [46225, 47524, 23716, 22500, 48841, 51529, 43681, 40000, 37249, 22201, 23716, 23104, 25281, 48400, 44521, 46225, 21609, 18496, 22801, 9216, 21904, 38025, 20736, 27556, 46656, 42436, 40804, 21609, 26244, 44100, 38025, 39601, 24336, 28900, 47961, 38416, 38809, 47961, 51529, 20449, 4356, 4356, 24964]

次に、flagの各文字の復元について。先ほど求めた数字はi番目とi+1番目の文字を足して2乗したものである。flagのフォーマットはRulesに書かれている通り、ctf4b{[\x20-\x7e]+}なので1文字目がcであることが分かる。そのため、以下の通り1文字目から全ての文字を復元することが可能である。

import sys

cipher = [46225, 47524, 23716, 22500, 48841, 51529, 43681, 40000, 37249, 22201, 23716, 23104, 25281, 48400, 44521, 46225, 21609, 18496, 22801, 9216, 21904, 38025, 20736, 27556, 46656, 42436, 40804, 21609, 26244, 44100, 38025, 39601, 24336, 28900, 47961, 38416, 38809, 47961, 51529, 20449, 4356, 4356, 24964]

# 1文字ずつ復元
flag = b"c"
for i in range(len(cipher)):
    m_i = flag[i]
    for j in range(0x20, 0x7f):
        c = ((m_i + j) ** 2)
        if c == cipher[i]:
            flag += chr(j).encode()
            break
        if j == 0x7e:
            print('not found', file=sys.stderr)
            sys.exit(1)
    print(flag)

# b'ct'
# b'ctf'
# b'ctf4'
# b'ctf4b'
# b'ctf4b{'
# b'ctf4b{h'
# b'ctf4b{hi'
# b'ctf4b{hi_'
# b'ctf4b{hi_b'
# b'ctf4b{hi_b3'
# b'ctf4b{hi_b3g'
# b'ctf4b{hi_b3g1'
# b'ctf4b{hi_b3g1n'
# b'ctf4b{hi_b3g1nn'
# b'ctf4b{hi_b3g1nne'
# b'ctf4b{hi_b3g1nner'
# b'ctf4b{hi_b3g1nner!'
# b'ctf4b{hi_b3g1nner!g'
# b'ctf4b{hi_b3g1nner!g0'
# b'ctf4b{hi_b3g1nner!g00'
# b'ctf4b{hi_b3g1nner!g00d'
# b'ctf4b{hi_b3g1nner!g00d_'
# b'ctf4b{hi_b3g1nner!g00d_1'
# b'ctf4b{hi_b3g1nner!g00d_1u'
# b'ctf4b{hi_b3g1nner!g00d_1uc'
# b'ctf4b{hi_b3g1nner!g00d_1uck'
# b'ctf4b{hi_b3g1nner!g00d_1uck_'
# b'ctf4b{hi_b3g1nner!g00d_1uck_4'
# b'ctf4b{hi_b3g1nner!g00d_1uck_4n'
# b'ctf4b{hi_b3g1nner!g00d_1uck_4nd'
# b'ctf4b{hi_b3g1nner!g00d_1uck_4nd_'
# b'ctf4b{hi_b3g1nner!g00d_1uck_4nd_h'
# b'ctf4b{hi_b3g1nner!g00d_1uck_4nd_h4'
# b'ctf4b{hi_b3g1nner!g00d_1uck_4nd_h4v'
# b'ctf4b{hi_b3g1nner!g00d_1uck_4nd_h4ve'
# b'ctf4b{hi_b3g1nner!g00d_1uck_4nd_h4ve_'
# b'ctf4b{hi_b3g1nner!g00d_1uck_4nd_h4ve_f'
# b'ctf4b{hi_b3g1nner!g00d_1uck_4nd_h4ve_fu'
# b'ctf4b{hi_b3g1nner!g00d_1uck_4nd_h4ve_fun'
# b'ctf4b{hi_b3g1nner!g00d_1uck_4nd_h4ve_fun!'
# b'ctf4b{hi_b3g1nner!g00d_1uck_4nd_h4ve_fun!!'
# b'ctf4b{hi_b3g1nner!g00d_1uck_4nd_h4ve_fun!!!'
# b'ctf4b{hi_b3g1nner!g00d_1uck_4nd_h4ve_fun!!!}'