SECCON 13 quals: reiwa_rot13 Upsolve

reiwa_rot13

authored by kurenaif

Reiwa is latest era name in Japanese(from 2019). it's latest rot13 challenge!

from Crypto.Util.number import *
import codecs
import string
import random
import hashlib
from Crypto.Cipher import AES
from Crypto.Random import get_random_bytes
from flag import flag

p = getStrongPrime(512)
q = getStrongPrime(512)
n = p*q
e = 137

key = ''.join(random.sample(string.ascii_lowercase, 10))
rot13_key = codecs.encode(key, 'rot13')

key = key.encode()
rot13_key = rot13_key.encode()

print("n =", n)
print("e =", e)
print("c1 =", pow(bytes_to_long(key), e, n))
print("c2 =", pow(bytes_to_long(rot13_key), e, n))

key = hashlib.sha256(key).digest()
cipher = AES.new(key, AES.MODE_ECB)
print("encyprted_flag = ", cipher.encrypt(flag))

$c1, c2$はkey, rot13_keyのみが違いとなって生成されています。
どうにかして、ROT13の仕組みをうまく利用して解けないでしょうか？

解法

ここで重要なのは、ROT13のアルゴリズムです。
小文字bで考えてみましょう。ROT13はまず、ある文字を0~25に直します。つまり
$$
t = b - a
$$
となり、$t=1$です。
これに13を足して剰余を取ります。ということは、
$$
t' = (t + 13) \pmod {26}
$$
と表すことができ、最後にこれを文字に戻すと、$t=14$より、oとなります。
さて、ここで、oをROT13することを考えてみましょう。先ほどと同様にやると、cに戻ります。
つまり、0~12文字、つまりa~mは13文字先に進み、13~26文字、つまりn~zは13文字前に戻ることがわかります。

この考えをrot13_keyで考えてみます。rot13_keyはkeyの各バイトが$\pm 13$だけ変化したものであるといえます。
また、keyはkey = ''.join(random.sample(string.ascii_lowercase, 10))で生成されるため、小文字10文字に限られます。したがって各文字について差分が$\pm 13$になるかの2択しかなく、差分パターンは高々$2^10$通りです。つまり、このパターンを全探索すればkeyとrot13_keyの関係を当てられます。

次に、$c_1, c_2$を見ます。$c_1,c_2$を生成した平文$m_1, m_2$は
$$
m_1 = \text{bytes_to_long(key)}, m_2 = \text{bytes_to_long(rot13_key)}
$$
であるため、ある差分$r$に対して
$$
m_2 \equiv m_1 + r \pmod n
$$
が成立するはずです。

ここで、bytes_to_longは、バイト列を256進数とみなして整数化をするため、10バイトをb[0], ..., b[9]とすると、
$$
m = \sum_{i=0}^9 b[i] \cdot 256^{9-i}
$$
と表せます。

さて、同様にrot13_keyをb'[0], ..., b'[9]とすると、$m2-m1$の差は
$$
m_2 - m_1 = \sum_{i=0}^9 (b'[i]-b[i]) \cdot 256^{9-i}
$$
となります。ここで各$(b'[i]-b[i])$は$\pm 13$なので、$r$は各桁の重み$256^{9-i}$に$\pm 13$をかけて足し合わせたものとして、先ほどの$2^10$通りの全探索で求まります。

あとは、$m_2 \equiv m_1 + r$という一次関係がわかったので、これを使って解けないでしょうか？
ということで、いつものサイトを見てみると、記載されてました。いつもありがとう。
https://zenn.dev/anko/articles/ctf-crypto-rsa

上位ビットが共通する二つの平文に対する暗号文を知られてはいけない (Franklin-Reiter Related Message Attack)

今回はこれに該当すると考えると、$m_2 - m_1$の差$r$を用いてFranklin-Reiter Related Message Attackを行い、SECCON{となるような文字列を探せばフラグを求められるでしょう。

import hashlib
from Crypto.Cipher import AES
from Crypto.Util.number import long_to_bytes
from itertools import product

n = 105270965659728963158005445847489568338624133794432049687688451306125971661031124713900002127418051522303660944175125387034394970179832138699578691141567745433869339567075081508781037210053642143165403433797282755555668756795483577896703080883972479419729546081868838801222887486792028810888791562604036658927
e = 137
c1 = 16725879353360743225730316963034204726319861040005120594887234855326369831320755783193769090051590949825166249781272646922803585636193915974651774390260491016720214140633640783231543045598365485211028668510203305809438787364463227009966174262553328694926283315238194084123468757122106412580182773221207234679
c2 = 54707765286024193032187360617061494734604811486186903189763791054142827180860557148652470696909890077875431762633703093692649645204708548602818564932535214931099060428833400560189627416590019522535730804324469881327808667775412214400027813470331712844449900828912439270590227229668374597433444897899112329233
encyprted_flag =  b"\xdb'\x0bL\x0f\xca\x16\xf5\x17>\xad\xfc\xe2\x10$(DVsDS~\xd3v\xe2\x86T\xb1{xL\xe53s\x90\x14\xfd\xe7\xdb\xddf\x1fx\xa3\xfc3\xcb\xb5~\x01\x9c\x91w\xa6\x03\x80&\xdb\x19xu\xedh\xe4"
prefix = b"SECCON{"


def franklinReiter(n, e, r, c1, c2):
    R.<x> = Zmod(n)[]
    f1 = x**e - c1
    f2 = (x + r)**e - c2
    return int(- polygcd(f1, f2).coefficients()[0])

def polygcd(a, b):
    if(b == 0):
        return a.monic()
    else:
        return polygcd(b, a % b)

for sign_bits in product([+1, -1], repeat=10):
    r = sum(sign_bits[i] * 13 * 256**i for i in range(10))
    m = franklinReiter(n, e, r, c1, c2)
    key = hashlib.sha256(long_to_bytes(m)).digest()
    c = AES.new(key, AES.MODE_ECB)
    res = c.decrypt(encyprted_flag)
    if res.startswith(prefix):
        print(res.decode())
        break

Flag: SECCON{Vim_has_a_command_to_do_rot13._g?_is_possible_to_do_so!!}

おまけ

解き終わった後に、作問者のWriteupを見てみるとtqdmライブラリ使ってました。
https://zenn.dev/kurenaif/articles/c2d123f22d081d

(sage) pppp@DESKTOP-ND9HH7A:~$ sage check.sage 
 77%|█████████████████████████████████████████████████████████████████████████████████████████████▏                           | 789/1024 [00:07<00:02, 108.14it/s]
 SECCON{Vim_has_a_command_to_do_rot13._g?_is_possible_to_do_so!!}
 78%|█████████████████████████████████████████████████████████████████████████████████████████████▊                           | 794/1024 [00:07<00:02, 102.36it/s]

実行コード

import hashlib
from tqdm import tqdm
from Crypto.Cipher import AES
from Crypto.Util.number import long_to_bytes
from itertools import product

n = 105270965659728963158005445847489568338624133794432049687688451306125971661031124713900002127418051522303660944175125387034394970179832138699578691141567745433869339567075081508781037210053642143165403433797282755555668756795483577896703080883972479419729546081868838801222887486792028810888791562604036658927
e = 137
c1 = 16725879353360743225730316963034204726319861040005120594887234855326369831320755783193769090051590949825166249781272646922803585636193915974651774390260491016720214140633640783231543045598365485211028668510203305809438787364463227009966174262553328694926283315238194084123468757122106412580182773221207234679
c2 = 54707765286024193032187360617061494734604811486186903189763791054142827180860557148652470696909890077875431762633703093692649645204708548602818564932535214931099060428833400560189627416590019522535730804324469881327808667775412214400027813470331712844449900828912439270590227229668374597433444897899112329233
encyprted_flag =  b"\xdb'\x0bL\x0f\xca\x16\xf5\x17>\xad\xfc\xe2\x10$(DVsDS~\xd3v\xe2\x86T\xb1{xL\xe53s\x90\x14\xfd\xe7\xdb\xddf\x1fx\xa3\xfc3\xcb\xb5~\x01\x9c\x91w\xa6\x03\x80&\xdb\x19xu\xedh\xe4"
prefix = b"SECCON{"


def franklinReiter(n, e, r, c1, c2):
    R.<x> = Zmod(n)[]
    f1 = x**e - c1
    f2 = (x + r)**e - c2
    return int(- polygcd(f1, f2).coefficients()[0])

def polygcd(a, b):
    if(b == 0):
        return a.monic()
    else:
        return polygcd(b, a % b)

for sign_bits in tqdm(product([+1, -1], repeat=10), total=int(1024)):
    r = sum(sign_bits[i] * 13 * 256**i for i in range(10))
    m = franklinReiter(n, e, r, c1, c2)
    key = hashlib.sha256(long_to_bytes(m)).digest()
    c = AES.new(key, AES.MODE_ECB)
    res = c.decrypt(encyprted_flag)
    if res.startswith(prefix):
        print(res.decode())
        break