チーム zoozer で出ていました！

[crypto] reiwa_rot13

問題

以下のような感じで計算されたn,e,c1,c2が与えられるので、keyを頑張って特定する問題。（本当はこの後にAES暗号化処理が書いてあるのだが、keyを特定する所が本質なので割愛）

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))

解法

まず一番目を引くのはrot13をしている部分。求めたいkeyとkeyをrot13したものに対してRSA暗号をしている。とりあえず、RSA暗号に対する有名攻撃を順番に使えるか使えないかやっていくと、Franklin-Reiter Related Message Attackを見つけることができる。Franklin-Reiter Related Message Attackの形にしたいなーと思いながら整理すると、帰着させることが可能。

keyをrot13したものについて考えてみる。rot13は各文字について文字を13個進める操作のことであるが、13個進めた時にzを超えてしまう場合は頭のaに戻るような動きをする。つまり、普通は+13であるが、文字によっては+13-26、つまり-13されることになる。どちらになるかは初期の文字が最初の13個であるかどうかで決まる。

この操作をkeyに当てはめて考えてみよう。まず、keyは

$\displaystyle k_1 k_2 ... k_{10}$

であれば、

$\displaystyle key = 2^{72} k_{1} + 2^{64} k_2 + ... + k_{10}$

のように計算される。この時、 $k_{1}$ に対するrot13操作、つまり、±13は

$\displaystyle key ± 2^{72} * 13$

と数値の足し引きで表現することができる。

keyは全部で10文字なので、各バイトについて±13のどちらかであるかは2¹⁰通りしかないので全探索でき、それが決まれば先ほどの数値計算を適用して、key + diff = rot13_keyを満たすdiffを求めることができる。そう考えると、今回の問題は

$\displaystyle c_1 = key^e\ mod\ n\ を満たす c_1 が既知 \\ c_2 = (key + diff)^e\ mod\ n\ を満たす c_2 が既知$

という問題に帰着し、これはFranklin-Reiter Related Message Attackが適用可能である。後は、アルゴリズムに従ってやるだけなので、sagemathで以下のようにkeyを求めることができる。

n = [redacted]
e = 137
c1 = [redacted]
c2 = [redacted]

from Crypto.Util.number import *

pgcd = lambda g1, g2: g1.monic() if not g2 else pgcd(g2, g1%g2)
P.<x> = PolynomialRing(Zmod(n))

for mask in range(2**10):
    diff = 0
    for i in range(10):
        if (mask & (2**i)) == 0:
            # x + 13 = y
            diff += 13 * (2**(8 * i))
        else:
            # x - 13 = y
            diff -= 13 * (2**(8 * i))
    f = x^e - c1
    g = (x + diff)^e - c2
    m = -pgcd(f, g).coefficients()[0]
    try:
        print(long_to_bytes(int(m)))
    except:
        pass

あとはkeyをsha256ハッシュにして最終的なkeyを作り、AES-ECB復号化すればフラグが得られる。

[crypto] dual_summon

問題について

問題のソースコードは以下。

from Crypto.Cipher import AES
import secrets
import os
import signal

signal.alarm(300)

flag = os.getenv('flag', "SECCON{sample}")

keys = [secrets.token_bytes(16) for _ in range(2)]
nonce = secrets.token_bytes(16)

def summon(number, plaintext):
    assert len(plaintext) == 16
    aes = AES.new(key=keys[number-1], mode=AES.MODE_GCM, nonce=nonce)
    ct, tag = aes.encrypt_and_digest(plaintext)
    return ct, tag

# When you can exec dual_summon, you will win
def dual_summon(plaintext):
    assert len(plaintext) == 16
    aes1 = AES.new(key=keys[0], mode=AES.MODE_GCM, nonce=nonce)
    aes2 = AES.new(key=keys[1], mode=AES.MODE_GCM, nonce=nonce)
    ct1, tag1 = aes1.encrypt_and_digest(plaintext)
    ct2, tag2 = aes2.encrypt_and_digest(plaintext)
    # When using dual_summon you have to match tags
    assert tag1 == tag2

print("Welcome to summoning circle. Can you dual summon?")
for _ in range(10):
    mode = int(input("[1] summon, [2] dual summon >"))
    if mode == 1:
        number = int(input("summon number (1 or 2) >"))
        name   = bytes.fromhex(input("name of sacrifice (hex) >"))
        ct, tag = summon(number, name)
        print(f"monster name = [---filtered---]")
        print(f"tag(hex) = {tag.hex()}")

    if mode == 2:
        name   = bytes.fromhex(input("name of sacrifice (hex) >"))
        dual_summon(name)
        print("Wow! you could exec dual_summon! you are master of summoner!")
        print(flag)

keys[0]を使うAES-GCMの暗号器0と、keys[1]を使うAES-GCMの暗号器1が用意される。どちらも暗号化復号化の時に使うnonceは共通で固定である。keys, nonceは与えられない。

代わりに2つのmodeの操作が行える。

mode=1: 暗号器を選択して任意の平文を暗号化し、タグだけを得る
mode=2: 任意の平文を入力し、2つの暗号器が出力するタグが一致すればフラグが得られる

最初に

nonceが共通しているので、そこが弱点だろうということはなんとなく分かる。nonceがランダムでないと安全でないのは共通認識なので、タグを頑張って衝突させてねと言うことだろう。AES-GCM、良く知らないので検索するとkurenaif先生の動画が見つかるので、ちゃんと見る。

www.youtube.com

「nonce固定だとmacを実はバイパスできるんだよね～」と言ってはいるが、肝心な所は教えてくれない… もう少しGCMについて調べると本当は怖いAES-GCMの話という無茶苦茶参考になるブログが見つかる。このブログを読んでいくと方針が立ってくる。

GCMの処理は他のCBCとかに比べると複雑だが、16bytesのみ暗号化するということ、また、特殊な和積を導入すると比較的扱いやすいタグを求める式が立てられる。16bytesを暗号化するAES-GCMは、暗号文をC、’0’*16を暗号化したものをH, 長さのバイト列にしたものをL, nonceを暗号化したものをSと置くと、最終的なタグ T は、

$\displaystyle \begin{equation} T = CH^2 + LH + S \tag{1} \end{equation}$

と書くことができる。

H²を求める

この式をこねくり回すことで、2つの暗号器のH²をそれぞれ求めることができる。平文P、nonce+1を暗号化したものをS’とするとGCMのアルゴリズムにより

$\displaystyle C = P + S'$

と書ける。ここで、平文の最下位ビットをフリップさせた新しい平文P + 1を暗号化することを考えよう。今回使っている「特殊な和積」の和はxorであるため、最下位ビットのフリップは+1として表現できる。よって、P+1を暗号化するときの式は、

$\displaystyle P + 1 + S' = C + 1$

となる。よって、P + 1を暗号化したときの最終的なタグT’は

$\displaystyle \begin{equation} T’ = (C + 1)H^2 + LH + S \tag{2} \end{equation}$

と書ける。ここで、(1)と(2)の両辺を足すと、和がxorであることからA+A=0なので、以下のようにH²のみが残る。

$\displaystyle \begin{equation} T + T' = H^2 \end{equation}$

T + T’は問題環境から得られるのでH²を求めることができる。この方法を使って、2つのAES暗号器におけるH²の値を求めることができた。

Tagの衝突

次に同じ平文を入力したときに、同じTagが出力されるようにする。表記上片方のAESについては大文字、もう片方のAESについては小文字を使って書くことにする。（共通のものについては大文字で統一）すると、2つのAESについてタグの生成はこのようになる。

$\displaystyle T = CH^2 + LH + S \\ t = ch^2 + Lh + s$

次に、2つのAES暗号器に与える平文は同じものである必要があるので、ここから同じ値を両方の平文に足すことを考える。両方の平文に同じ値 k を足すと以下のように式が変形される。

$\displaystyle (C + k)H^2 + LH + S = CH^2 + LH + S + kH^2 = T + kH^2 \\ (c + k)h^2 + Lh + s = ch^2 + Lh + s + kh^2 = t + kh^2$

今回はこの足した結果が等しくなればよいので

$\displaystyle T + kH^2 = t + kh^2$

を満たせばよい。ここで任意の同じ平文 P を2つのAES暗号器に与えて、T,tをmode=1により取得しておく。これにより、T, t, H², h²が既知の状態になるので、

$\displaystyle k = \frac{T + t}{H^2 + h^2}$

でkを求めることができ、P+kをすることで同じタグを生成する平文を作り出すことができる。

PoCコード

以下のようなsagemathコードを用意して、手動でクエリ結果とやり取りしながらフラグを得た。

P.<x> = PolynomialRing(GF(2))
GF2_128 = GF(2**128, name='a', modulus=x^128 + x^7 + x^2 + x + 1)

from Crypto.Util.number import *
from Crypto.Cipher import AES

def bytes_to_poly(b):
    v = int.from_bytes(b, 'big')
    v = int(f"{v:0128b}"[::-1], 2)
    return GF2_128.from_integer(v)

def reverse_bits(num, bit_length):
    bin_rep = format(num, f'0{bit_length}b')
    reversed_bin_rep = bin_rep[::-1]
    reversed_num = int(reversed_bin_rep, 2)
    return reversed_num

def int_to_poly(b):
    return GF2_128.from_integer(reverse_bits(b,128))

def poly_to_bytes(p):
    v = p.integer_representation()
    v = int(f"{v:0128b}"[::-1], 2)
    return v.to_bytes(16, 'big')

tag_a_0 = int_to_poly(0xd39af8a6a972d68f5e0051e40db27366) # 00000000000000000000000000000000
tag_a_1 = int_to_poly(0xaad442977b1d889f17629142a28218e7) # 80000000000000000000000000000000

tag_b_0 = int_to_poly(0x5e4ec2309516675ae6d0bad182a0a787)
tag_b_1 = int_to_poly(0xeeb6e1c5b192f937f9519ad25932fba2)

hh_a = (tag_a_1 + tag_a_0)
hh_b = tag_b_1 + tag_b_0

k = (tag_a_0 - tag_b_0) / (hh_a - hh_b)

ans = 0
for c in k.polynomial():
    ans = ans * 2 + int(c)
print(hex(ans)[2:])

はまやんはまやんはまやん

hamayanhamayan's blog

SECCON CTF 13 Quals Writeups

[crypto] reiwa_rot13

問題

解法

[crypto] dual_summon

問題について

最初に

H²を求める

Tagの衝突

PoCコード

[crypto] reiwa_rot13

問題

解法

[crypto] dual_summon

問題について

最初に

H2を求める

Tagの衝突

PoCコード

H²を求める