3rd Crypto CTF Writeup - easy編

1. はじめに

　2021/7/31(土) 01:00 JST ～ 2021/8/1(日) 1:00:00 JST で「3rd Crypto CTF」に参加し、951 点（得点を得た 444 チーム中 35 位）を獲得しました。24 時間ほぼフル稼働でしたが、最後の方は何をやっていたかよく覚えていません。おそらく、ベストコンディションで 8 時間だけプレイした方が結果は良かったはずです。滅びよ、我が精神に染みつきしジャパニーズブラック企業的思考！
　それはさておき、今回の大会の設問にはじっくり復習したい内容が多いので、競技中解けなかった問題も含め少しずつ復習してゆきたいと思います。まずは easy レベルまでの Writeup です。

2. Writeup

2-0. Mic Check (warm-up, 19 points, 440 solves)

☆設問

Read the Rules, check the mic and enter the flag!

☆方針・解法

　いわゆる「Welcome 問」です。
　ここは、愚直に「Rules」のページを熟読します。ページ内を「CCTF{」で検索をするのは野暮というものです（嘘つけ！）。「暗号解読は提示された情報（暗号文）を正しく読み込むところから始まる」というのが我々 N30Z30N のポリシーでもありますので（これは本当）。あと、競技に参加する以上は当然ルールを遵守するというのは言うまでもないことでしょう（それが一番大事）。
　そうこうして読み進めていくと、このページの末尾に以下の一文があります。

The flag for Mic Check task is: CCTF{W3lc0me_t0_The_0ne_&_0nly_Crypt0_CTF_Mad3ـw1th_L0ve_f0r_Crypt0!}

　よっしゃ！

☆フラグ

CCTF{W3lc0me_t0_The_0ne_&_0nly_Crypt0_CTF_Mad3ـw1th_L0ve_f0r_Crypt0!}

　日本のマイクテストは（実際の天候にかかわらず）「本日は晴天なり」とやるようなのですが、この問題を解いたのは夜中だったので、その時晴天であったかどうか定かではありません。

2-1. Farm (easy, 41 points, 149 solves)

☆設問

Explore the Farm very carefully!

　さらに、以下の SageMath のコード（farm.sage）と暗号文（output.txt）が提示されます。

farm.sage

\#!/usr/bin/env sage

from sage.all import *
import string, base64, math
from flag import flag

ALPHABET = string.printable[:62] + '\\='

F = list(GF(64))

def keygen(l):
    key = [F[randint(1, 63)] for _ in range(l)] 
    key = math.prod(key) # Optimization the key length :D
    return key

def maptofarm(c):
    assert c in ALPHABET
    return F[ALPHABET.index(c)]

def encrypt(msg, key):
    m64 = base64.b64encode(msg)
    enc, pkey = '', key**5 + key**3 + key**2 + 1
    for m in m64:
        enc += ALPHABET[F.index(pkey * maptofarm(chr(m)))]
    return enc

# KEEP IT SECRET 
key = keygen(14) # I think 64**14 > 2**64 is not brute-forcible :P

enc = encrypt(flag, key)
print(f'enc = {enc}')

output.txt

enc = 805c9GMYuD5RefTmabUNfS9N9YrkwbAbdZE0df91uCEytcoy9FDSbZ8Ay8jj

☆方針・解法

　突然ですが、我々 N30Z30N には以下のような格言があります。

no Sage, no flag!

　簡単に言うと、「SageMath なくして、Crypto 問のフラグなし」という意味です。実際 Crypto 問の中には、ちょっとした「代数学＋初等整数論」の知識と SageMath の使い方を知っているだけで容易に解けてしまう問題（それらの道具がないとキツい問題）が結構あります（本問もそれに該当します）。
　さて、本問では暗号化キーを「GF(64)」＝ 「位数 64 の有限体」の元（と、その中で閉じた演算）から作っています。ですので、暗号化キーは「64^14通り」など存在し得なくて、「高々 64 通り」しかありません（実際にはもっと絞られます）。「# I think 64*14 > 2*64 is not brute-forcible :P」などという「戯言」は信じてはいけないのです（Crypto問を解くときの鉄則）。
　よって、この暗号化キーについては頑張って求めるのではなく、総当たりで攻めるのが得策です。これまた N30Z30N の行動哲学（？）であるところの、「金（パワー）で解決できることは金（パワー）で解決する（まぁ、でもそんなに持ち合わせてないから程々しか出来んけど）」的な考え方です。
　また、GF(64) での演算ロジックは無論自作するのではなく、提示されたコード同様「SageMath」の力を借ります。ここは「逆らわずして勝つ」というジゴロー・カノー的な発想です。余談ですが、Sage は「セイジ」と発音するそうです。かつての２ちゃんねらー（現：５ちゃんねらー）は「サゲ」、名作「君が望む永遠」にどっぷり浸かった方は「サージュ」と発音してしまう癖があるですのでバレたくなければ「セイジ」と発音する習慣を身に着けたほうが無難です。
　閑話休題。あとは復号処理ですが、提示された encrypt 関数をもとにその逆変換を実装します。但し、不正なキーで復号しようとうしたとき例外が発生し得るので、そこは try ～ except でテキトーにハンドリングします。これでソルバの材料は揃いました。

☆ソルバ

solve.sage

import string, base64

enc = "805c9GMYuD5RefTmabUNfS9N9YrkwbAbdZE0df91uCEytcoy9FDSbZ8Ay8jj"
ALPHABET = string.printable[:62] + '\\='

F = list(GF(64))
R.<x> = PolynomialRing(GF(64))
g = x^5 + x^3 + x^2 + 1

keys = []
for f in F:　#Preparation to Bruteforce 
  if not g(f) in keys:
    keys.append(g(f))

def decrypt(enc, key): #Inverse of function "encrypt"
  dec = ""
  try:
    for m in enc:
      print()
      dec += ALPHABET[F.index(maptofarm(chr(m))/key)]
    dec = base64.b64decode(dec)
  except:
    dec = b""
  return dec

def maptofarm(c):
  assert c in ALPHABET
  return F[ALPHABET.index(c)]

for key in keys: #Bruteforce 
  dec = decrypt(enc.encode(), key)
  if b"CCTF{" in dec:
    print(dec.decode())
    exit()

☆フラグ

CCTF{EnCrYp7I0n_4nD_5u8STitUtIn9_iN_Fi3Ld!}

　競プロでとかで鍛えていればこの程度の実装は「瞬殺」できたかもしれませんが、ここまでに約 50 分を費やしてしまいました。しかしこの時思ったことは

「あと 23 時間以上あるから、頑張れば 20 問くらいはイケるんじゃね？」

・・・滅びよ、我が精神に染みつきしジャパニーズブラック企業的思考！

2-2. KeyBase (easy, 48 points, 111 solves)

☆設問

Recovering secrets is hard, but there is always some easy parts!
（接続先サーバのホスト名・ポート番号）

　サーバのプログラムも示されます。

keybase.py

#!/usr/bin/env python3

from Crypto.Util import number
from Crypto.Cipher import AES
import os, sys, random
from flag import flag

def keygen():
    iv, key = [os.urandom(16) for _ in '01']
    return iv, key

def encrypt(msg, iv, key):
    aes = AES.new(key, AES.MODE_CBC, iv)
    return aes.encrypt(msg)

def decrypt(enc, iv, key):
    aes = AES.new(key, AES.MODE_CBC, iv)
    return aes.decrypt(enc)

def die(*args):
    pr(*args)
    quit()

def pr(*args):
    s = " ".join(map(str, args))
    sys.stdout.write(s + "\n")
    sys.stdout.flush()

def sc():
    return sys.stdin.readline().strip()

def main():
    border = "+"
    pr(border*72)
    pr(border, " hi all, welcome to the simple KEYBASE cryptography task, try to    ", border)
    pr(border, " decrypt the encrypted message and get the flag as a nice prize!    ", border)
    pr(border*72)

    iv, key = keygen()
    flag_enc = encrypt(flag, iv, key).hex()

    while True:
        pr("| Options: \n|\t[G]et the encrypted flag \n|\t[T]est the encryption \n|\t[Q]uit")
        ans = sc().lower()
        if ans == 'g':
            pr("| encrypt(flag) =", flag_enc)
        elif ans == 't':
            pr("| Please send your 32 bytes message to encrypt: ")
            msg_inp = sc()
            if len(msg_inp) == 32:
                enc = encrypt(msg_inp, iv, key).hex()
                r = random.randint(0, 4)
                s = 4 - r
                mask_key = key[:-2].hex() + '*' * 4
                mask_enc = enc[:r] + '*' * 28 + enc[32-s:]
                pr("| enc =", mask_enc)
                pr("| key =", mask_key)
            else:
                die("| SEND 32 BYTES MESSAGE :X")
        elif ans == 'q':
            die("Quitting ...")
        else:
            die("Bye ...")

if __name__ == '__main__':
    main()

☆方針・解法

　まずは、サーバに接続して情報を集めます。key と iv は固定値ではなく接続都度変わるので、途中ウッカリ切断しないよう注意します。

++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
+  hi all, welcome to the simple KEYBASE cryptography task, try to     +
+  decrypt the encrypted message and get the flag as a nice prize!     +
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
| Options: 
|   [G]et the encrypted flag 
|   [T]est the encryption 
|   [Q]uit

　提示されたコードに偽りはないようです。「G」で暗号化フラグの取得、「T」で暗号化の試行が出来ます。

G
| encrypt(flag) = 9a7760e08c90dea6aba5cb7232145cd72b62ce3b81baf21696f97115da567db1
| Options: 
|   [G]et the encrypted flag 
|   [T]est the encryption 
|   [Q]uit

　暗号化フラグは（提示されたコードからもわかりますが） 32 バイトのようです。
　続いて、暗号化試行をやってみます。

T
| Please send your 32 bytes message to encrypt: 

　32 バイトの平文メッセージを要求されるので、とりあえず 「A」×32 でやってみます。

AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
| enc = 7****************************6d9384d662fd8abf19fe06724e36572d145
| key = 21078dd425ac208448ff390b6beb****
| Options: 
|   [G]et the encrypted flag 
|   [T]est the encryption 
|   [Q]uit

　暗号化キーは最後の 2 バイト（HEXで4文字）分がマスクされ、メッセージは a バイト目 ～ a+27バイト目（a=1～4）の28バイトがマスクされます。マスクをできるだけ外すため、暗号化を何回か試行します。

T   
| Please send your 32 bytes message to encrypt: 
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
| enc = ****************************36d9384d662fd8abf19fe06724e36572d145
| key = 21078dd425ac208448ff390b6beb****
| Options: 
|   [G]et the encrypted flag 
|   [T]est the encryption 
|   [Q]uit
T
| Please send your 32 bytes message to encrypt: 
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
| enc = 7****************************6d9384d662fd8abf19fe06724e36572d145
| key = 21078dd425ac208448ff390b6beb****
| Options: 
|   [G]et the encrypted flag 
|   [T]est the encryption 
|   [Q]uit
T
| Please send your 32 bytes message to encrypt: 
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
| enc = 7****************************6d9384d662fd8abf19fe06724e36572d145
| key = 21078dd425ac208448ff390b6beb****
| Options: 
|   [G]et the encrypted flag 
|   [T]est the encryption 
|   [Q]uit
T             
| Please send your 32 bytes message to encrypt: 
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
| enc = 742****************************9384d662fd8abf19fe06724e36572d145
| key = 21078dd425ac208448ff390b6beb****
| Options: 
|   [G]et the encrypted flag 
|   [T]est the encryption 
|   [Q]uit
T
| Please send your 32 bytes message to encrypt: 
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
| enc = 742****************************9384d662fd8abf19fe06724e36572d145
| key = 21078dd425ac208448ff390b6beb****
| Options: 
|   [G]et the encrypted flag 
|   [T]est the encryption 
|   [Q]uit
Q
Quitting ...

　助さん、格さん、もういいでしょう（by 光圀）。

　ここで情報を整理すると、

　・鍵の判明しない部分は 2 バイト分だけなので、総当たりで行ける。

　・鍵の「当たり」判定は、
　　　　　　暗号化試行した際の暗号文の後半 16 バイト分を
　　　　　　　　iv = b"AAAAAAAAAAAAAAAA"
　　　　　として復号した際の値（以下、♧）の hex の先頭・末尾各3文字分が一致しているかどうか
　　　　　　　　742**************************6d9
　　　　　の形をしているかどうか
　　で行えそう（誤検知の可能性はあるが、高々数個なので気にしない）。

　・鍵を推測できれば、本来の iv を判明させてフラグを復号すればよい。
　　⇒ 本来の iv は、CBCモードの性質
　　　　　　ブロック n の暗号文を復号してブロック n の平文と XOR すると
　　　　　　ブロック n-1 の暗号文を得られる
　　　を利用すれば、本来の iv は
　　　　　　前記 ♧ を、
　　　　　　　　iv = b"AAAAAAAAAAAAAAAA"
　　　　　　で復号する
　　　ことで求められる。

　ということがわかります。
　以上をソルバとして実装すると、次のようになりました。

☆ソルバ

solve.py

from Crypto.Cipher import AES
h_flag = "9a7760e08c90dea6aba5cb7232145cd72b62ce3b81baf21696f97115da567db1"
h_key14 = "21078dd425ac208448ff390b6beb"
dummy_iv = b"AAAAAAAAAAAAAAAA"
h_enc0 = "384d662fd8abf19fe06724e36572d145"

enc0 = bytes.fromhex(h_enc0)
key14 = bytes.fromhex(h_key14)
encflag = bytes.fromhex(h_flag)
for i in range(0, 0x10000):
    key = key14 + i.to_bytes(2,"big")
    cipher = AES.new(key, AES.MODE_CBC, dummy_iv)
    enc1 = cipher.decrypt(enc0)
    h_enc1 = enc1.hex()
    if h_enc1[:3] == "742" and h_enc1[-3:] == "6d9":
      print(f"key={key.hex()}")
      cipher = AES.new(key, AES.MODE_CBC, dummy_iv)
      iv = cipher.decrypt(enc1)
      cipher = AES.new(key, AES.MODE_CBC, iv)
      flag = cipher.decrypt(encflag)
      if b"CCTF{" in flag:
        print(flag.decode())
        exit()

☆フラグ

CCTF{h0W_R3cOVER_7He_5eCrET_1V?}
　「暗号文n = 平文n と 暗号文n-1 を XOR して暗号化したもの」という CBC モードの特徴を理解していればすんなり解ける問題だったようです。
　これを解いたのが開始から 1時間40分後。この時思ったことは

「あと 22 時間以上あるから、頑張れば 20 問くらいはイケるんじゃね？」

・・・滅びよ、我が精神に染みつきしジャパニーズブラック企業的思考！

2-3. Symbols (easy, 70 points, 70 solves)

☆設問

Oh, my eyes, my eyes! People still can solve this kind of cryptography? Mathematicians should love this one!

　以下の画像が提示されます。

☆方針・解法

　これは競技開始後ある程度経過してから追加された問題で、気づいたときには「easy キターーーーーー！」と歓喜しながら着手しました。しかし・・・

　出た、記号問題！これ苦手なんだよなぁ。。。

・・・と落ち込み。
　ここは気持ちを切り替えて、「Symbol」というタイトルから Symbol フォントか？と思って試してみることにしました。しかし、見事にハズレorz...
　最初の 4 文字は「CCTF」ですので、これを手掛かりとして仕切り直します。
　といってもヨクワカランので、全体をぼんやりと眺めてみると、「∞」やら「∴」やら、やっぱり数学っぽいニオイがします。3 文字目、ギリシャ文字の「Theta」、1 文字目と 2 文字目は積集合を表す「Cap」、これで 「CCT」となる、ということは。。。

「これ、LaTeXじゃね？」

やってみると、確かにそんな感じでした。

$\Cup$ $\Cup$ $\Theta$ $\Finv$ { $\Pi$ $\ltimes$ $\aleph$ $y$ _ $\wp$ $\infty$ $\therefore$ $\heartsuit$ _ $\Lsh$ $\aleph$ $\Theta$ $\eth$ $\Xi$ }

$\Cup$ $\Cup$ $\Theta$ $\Finv$ { $\Pi$ $\ltimes$ $\aleph$ $y$ _ $\wp$ $\infty$ $\therefore$ $\heartsuit$ _ $\Lsh$ $\aleph$ $\Theta$ $\eth$ $\Xi$ }

　各記号は、その記号を表す LaTex のコマンドで「\」の次の1文字を表すもの（{_}yはそのまま）。そのルールで解読してフラグをゲットできました。

☆フラグ

CCTF{Play_with_LaTeX}

　LaTex を使ったことがある人には嬉しいサービス問題でした。

＃それにしても、Qiita で TeX（MathJax） 使うと時々変なスクロールバー出るのが謎ですね。。。

　ちなみに、この問題を解いたのは終了 2 時間前でした。この後「Elegant Curve」に挑戦して撃沈したのですが、その顛末は次号で紹介したいと思います。

3 おわりに

　次は medium 編を出す予定です。
　ジーク、ジオン！!