SECCON CTF 13 Quals Writeup

reiwa_rot13 (crypto)

暗号処理の概要は以下の通り。

・p: 512ビット素数
・q: 512ビット素数
・n = p * q
・e = 137
・key: 英小文字から重複なしで10個選択した文字列
・rot13_key: keyをrot13したもの
・nを出力
・eを出力
・pow(keyの数値化したもの, e, n)を出力
・pow(rot13_keyの数値化したもの, e, n)を出力
・key: keyのsha256ダイジェスト
・flagをkeyでAES ECBモード暗号化したものを出力

keyとro13_keyの各文字の間で差を考える。rot13なので、keyの方が小さい場合と大きい場合の2通りで差は決まる。それが10個の文字なので、そのケースは1024(=2**10)通りしかない。
それぞれのパターンでFranklin-Reiter Related Message Attackを行い、英小文字であるかをチェックし、成功すればkeyを復号できる。あとはそれをkeyにしてAESの復号を行えば、フラグが取得できる。

#!/usr/bin/env sage
from Crypto.Util.number import *
import codecs
import string
import hashlib
from Crypto.Cipher import AES

def related_message_attack(c1, c2, diff, e, n):
    PRx.<x> = PolynomialRing(Zmod(n))
    g1 = x ^ e - c1
    g2 = (x + diff) ^ e - c2

    def gcd(g1, g2):
        while g2:
            g1, g2 = g2, g1 % g2
        return g1.monic()

    return - gcd(g1, g2)[0]

def is_all_lower(s):
    try:
        s = s.decode()
    except:
        return False
    for c in s:
        if c not in string.ascii_lowercase:
            return False
    return True

with open('output.txt', 'r') as f:
    params = f.read().splitlines()

n = int(params[0].split(' = ')[1])
e = int(params[1].split(' = ')[1])
c1 = int(params[2].split(' = ')[1])
c2 = int(params[3].split(' = ')[1])
enc_flag = eval(params[4].split(' =  ')[1])


for i in range(1024):
    b = bin(i)[2:]
    diff = 0
    for j in range(len(b)):
        if b[j] == '0':
            diff += 13 * 256 ** j
        else:
            diff -= 13 * 256 ** j

    key = related_message_attack(c1, c2, diff, e, n)
    key = long_to_bytes(int(key))
    if is_all_lower(key):
        key = key.decode()
        break

rot13_key = codecs.encode(key, 'rot13')
print('[+] key =', key)
print('[+] rot13_key =', rot13_key)

key = key.encode()
key = hashlib.sha256(key).digest()
cipher = AES.new(key, AES.MODE_ECB)
flag = cipher.decrypt(enc_flag).decode()
print('[*] flag =', flag)

実行結果は以下の通り。

[+] key = dnjqygbmor
[+] rot13_key = qawdltozbe
[*] flag = SECCON{Vim_has_a_command_to_do_rot13._g?_is_possible_to_do_so!!}

SECCON{Vim_has_a_command_to_do_rot13._g?_is_possible_to_do_so!!}