[cry] Very Serious Cryptography

以下のようなAES-CBCで復号化をするスクリプトが与えられる。

from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
import os

with open("flag.txt", "rb") as f:
    flag = f.read()

key = os.urandom(16)

# Efficient service for pre-generating personal, romantic, deeply heartfelt white day gifts for all the people who sent you valentines gifts
for _ in range(1024):

    # Which special someone should we prepare a truly meaningful gift for? 
    recipient = input("Recipient name: ")

    # whats more romantic than the abstract notion of a securely encrypted flag?
    romantic_message = f'Dear {recipient}, as a token of the depth of my feelings, I gift to you that which is most precious to me. A {flag}'
    
    
    aes = AES.new(key, AES.MODE_CBC, iv=b'preprocessedlove')

    print(f'heres a thoughtful and unique gift for {recipient}: {aes.decrypt(pad(romantic_message.encode(), AES.block_size)).hex()}')

CBCモードではdecrypt([暗号block]) xor [IVか1つ前暗号block]のように復号化を行う点に着目すると解くことができる。とある、i番目のブロックとj番目のブロックについて

$\displaystyle \text{output}[i]) = \operatorname{decrypt}(\text{input}[i]) \oplus \text{input}[i-1] \\ \text{output}[j]) = \operatorname{decrypt}(\text{input}[j]) \oplus \text{input}[j-1]$

のような出力を得ることができ、変形すると

$\displaystyle \operatorname{decrypt}(\text{input}[i]) = \text{output}[i]) \oplus \text{input}[i-1] \\ \operatorname{decrypt}(\text{input}[j]) = \text{output}[j]) \oplus \text{input}[j-1]$

のような感じになる。ここで、decryptはAESで同じ鍵が全体で使う関数なので、同じ入力に対して同じ出力を返すことになる。つまり、この入力と出力から計算可能な各ブロックのdecrypt関数の結果を比較することで特定ブロックの内容が等しいかどうかを判別することが可能になる。

あとは入力を調整しながら、フラグの一部と入力が一緒になるようにブロックを作っていって判別していく。説明が難しいので、一旦、ソルバを置いておく。

from ptrlib import *
import string
from Crypto.Util.strxor import *

sock = Process("python3 chal.py", shell=True)

def get(recipient, flag):
    sock.sendlineafter("Recipient name: ", recipient.encode())
    res = sock.recvlineafter(f"heres a thoughtful and unique gift for {recipient}: ").decode()
    res = [res[i:i+32] for i in range(0, len(res), 32)]

    dummy = 'A' * 100
    estimated = f'Dear {recipient}, as a token of the depth of my feelings, I gift to you that which is most precious to me. A {flag}{dummy}'
    estimated = [estimated[i:i+16] for i in range(0, len(estimated), 16)]

    #for i in range(len(res)):
    #    print(f"{i} {res[i]} {estimated[i]}")
    
    return res, estimated

ans = ""
dic = string.printable
dic = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ!\"#$%&'\\()*+,-./:;<=>?@[]^_`{|}~ "
for j in range(6):
    for i in range(16):
        pre = "A" * 11 # Dear AAAAAAAAAAA
        chall = ""
        for ch in dic:
            chall += ("cious to me. A " + ans)[-15:] + ch
        post = "B" * (18 - i)

        res, estimated = get(pre + chall + post, ans)

        for ch_i in range(len(dic)):
            a = strxor(bytes.fromhex(res[1 + ch_i]), estimated[0 + ch_i].encode())
            b = strxor(bytes.fromhex(res[7 + len(dic) + j]), estimated[6 + len(dic) + j].encode())

            if a == b:
                ans += dic[ch_i]
                break
        print("[+]", ans)

入力として、"A"*11 + "cious to me. A " + [フラグの1文字目候補] + "B" * 18というのを与えてみる。例えば、フラグの1文字目候補としてkを与えてみると以下のような入力ブロックになる。

0 Dear AAAAAAAAAAA
1 cious to me. A k
2 BBBBBBBBBBBBBBBB
3 BB, as a token o
4 f the depth of m
5 y feelings, I gi
6 ft to you that w
7 hich is most pre
8 cious to me. A k

これを見ると、AとBでいい感じにアラインメントが調整されて、1番目と8番目が同じ入力になっていることが分かる。フラグはkalmarから始まっているので、kが正解なのだが、この入力を与えてやってdecryptの1番目と8番目を比較するとフラグの先頭が分かる。実際にはa,b,c,...のように全ての文字を探索する必要があるのだが、それぞれでやると効率が悪いので以下のように一気に送ってやって、decryptをそれぞれ比較することで文字を特定していく。

Dear AAAAAAAAAAA
cious to me. A a
cious to me. A b
cious to me. A c
cious to me. A d
...
cious to me. A @
BBBBBBBBBBBBBBBB
BB, as a token o
f the depth of m
y feelings, I gi
ft to you that w
hich is most pre
cious to me. A k

これで1文字目が特定できたので、次も同様にアラインメントを調整して、

Dear AAAAAAAAAAA
ious to me. A ka
ious to me. A kb
ious to me. A kc
ious to me. A kd
...
ious to me. A k@
BBBBBBBBBBBBBBBB
B, as a token of
 the depth of my
 feelings, I gif
t to you that wh
ich is most prec
ious to me. A ka

のようにして探索を続けていけば全ての文字を特定できる。説明が大変すぎるのでこの辺りでストップ。上の考え方の理解が一番大変な所で、ここが理解できれば、あとはソルバを読めば全体のやり方が分かると思う。

[cry] basic sums

以下のような、問題コード。概要としては、[2,256]の数値baseを入力し、プログラムはフラグを数値化したものをbase進数で表記して、各桁の総和を返してくれる。ここからフラグを求める。

with open("flag.txt", "rb") as f:
    flag = f.read()

# I found this super cool function on stack overflow \o/ https://stackoverflow.com/questions/2267362/how-to-convert-an-integer-to-a-string-in-any-base
def numberToBase(n, b):
    if n == 0:
        return [0]
    digits = []
    while n:
        digits.append(int(n % b))
        n //= b
    #print(digits)
    return digits[::-1]

assert len(flag) <= 45

flag = int.from_bytes(flag, 'big')

base = int(input("Give me a base! "))

if base < 2:
    print("Base is too small")
    quit()
if base > 256:
    print("Base is too big")
    quit()

print(f'Here you go! {sum(numberToBase(flag, base))}')

以下の公式にたどり着ければ解ける。

任意の基数bにおいて、ある数nをb-1で割った余りは、nを基数bで表したときの各桁の合計をb-1で割った余りと等しい

つまり、今回のソルバを使えば、フラグをbase-1で割った余りを得ることができることになる。このように、異なる法の下の計算結果が得られて、もともとの数を計算する方法と言えば… CRT！

base-1として、2,3,5,7,11,13,... を与えて、素数で割った余りを収集して、あとはCRTで戻せばフラグが手に入る。

注意点はフラグの長さが大きいので、素数を与えるのではなく、素数のべき乗を与えることでCRT後の法をなるべく大きくする必要がある。よって、各base-1の素数について、baseが[2,256]に収まるような最大のべき乗数を採用すること。

ソルバを見る方が分かりやすいと思う。

from ptrlib import *
from Crypto.Util.number import *

def ask(base):
    sock = Process("python3 chal.py", shell=True)
    
    sock.sendlineafter("Give me a base! ", str(base))
    res = int(sock.recvlineafter("Here you go! "))
    sock.close()

    return res

ps = []
for p in range(256):
    if isPrime(p):
        pp = p
        while pp * p < 256:
            pp *= p
        ps.append(pp)

mods = []
rs = []
for p in ps:
    res = ask(p+1)
    mods.append(p)
    rs.append(res % p)

flag = long_to_bytes(crt(rs, mods)[0])
print(flag)

[cry] Not-so-complex multiplication

以下のような問題コードが与えられる。

from sage.all import *

FLAG = b"kalmar{???}"

# Generate secret primes of the form x^2 + 7y^2
ps = []
x = randint(0, 2**100)
while gcd(x, 7) > 1:
    x = randint(0, 2**100)
while len(ps) < 10:
    pi = x**2 + 7*randint(0, 2**100)**2
    if is_prime(pi):
        ps.append(pi)

for p in ps:
    F = GF(p)
    E = EllipticCurve_from_j(F(int("ff", 16))**3)
    print(E.order())
print(sum(ps))

# Encrypt the flag
import hashlib
import os
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad, unpad

def encrypt_flag(secret: int):
    sha1 = hashlib.sha1()
    sha1.update(str(secret).encode('ascii'))
    key = sha1.digest()[:16]
    iv = os.urandom(16)
    cipher = AES.new(key, AES.MODE_CBC, iv)
    ciphertext = cipher.encrypt(pad(FLAG, 16))
    return iv.hex(), ciphertext.hex()

# Good luck! :^)
print(encrypt_flag(prod(ps)))

[0,2¹⁰⁰]の乱数 $x$ を生成し、そこから更に10個の[0,2¹⁰⁰]の乱数 $y_i$ を生成し、そこから、10個の素数 $p_i$ を

$\displaystyle p_i = x^2 + 7y^2$

のように作る。そこから更に10個の楕円曲線を $\mathbb{F}_{p_i}$ 上で作る。

この状態で、各楕円曲線のそれぞれの位数と、素数p_iの総和が与えられるので、素数p_iを復元する問題。

ガチャガチャ考察していると、[tex:p=x²+7y²]の形の素数は虚二次元体Q(sqrt(-7)に関連していてCM楕円曲線でなんたらかんたらというのを見つけたが何を言っているのか全然分からない。更にガチャガチャやっていると、以下の規則性を発見できた。

$\displaystyle \#E(\mathbb{F}_p) - p = 1 \pm 2x$

理由は全く分からない、実験的に得た。（j-不変量が固定だから？分からん）これを見つけるのがこの問題の最も難しいポイント。今得られた式の総和を取ってみる。

$\displaystyle \sum_{i} \#E(\mathbb{F}_{p_i}) - \sum_{i} p_i = \sum_{i}(1 \pm 2x)$

ここで左辺はどちらも既に与えられているので計算可能。よって、全体で使われている乱数xのみの式に帰着させることができる！まだ、式に±が残っているが、与えられている楕円曲線は10個なので、それぞれ+であるか-であるかを全探索すれば2¹⁰通りしかなく、これは全探索可能である。

これによって、xが復元できれば

$\displaystyle \#E(\mathbb{F}_p) - p = 1 \pm 2x$

によって $p_i$ を復元できるので問題を解くことができる。ソルバは以下。

import hashlib
from Crypto.Cipher import AES
from Crypto.Util.Padding import unpad

curve_orders = [
    1666663939089711870041057125344768424484360951424563692520424,
    4214498804406416313644357742112215844134609666200352264374976,
    950976951932444475351136722706487022980266898502474679556504,
    5048806274207110258595094188560360133685255687785741251319368,
    4142798969150438784396041753190730958039397547094083508303744,
    7716551183483230100472669184245125421165202412621941658816464,
    1211022154703627741380322682429241250680916702954339156211848,
    8372297180409222240227656234061485880108900764645861349876656,
    1012946900247163320228586390250288629690910831313171584120024,
    454620832322718928974392262478258736440710084540589920586056
]
sum_of_primes = 34791183189952084033311314285373613514101599321466508943561590

def decrypt_flag(secret: int):
    sha1 = hashlib.sha1()
    sha1.update(str(secret).encode('ascii'))
    key = sha1.digest()[:16]
    iv = bytes.fromhex("5c892056bf8a05e3522c995d8c65835b")
    cipher = AES.new(key, AES.MODE_CBC, iv)
    flag = cipher.decrypt(bytes.fromhex("9e318b989e8a7e04e96473b551313917f03869285aea581900d9c7a9a321e55b841032b40a75ffa4be0cc3f099456c3ed75e16e55711f21b17ee49f862c4ef6fe27efd9dad4e632a3c85df46732162d6"))
    if b"kalmar{" in flag:
        print(flag)

for mask in range(1 << 10):
    total = sum_of_primes
    keisu = 0
    for i in range(10):
        total -= curve_orders[i]
        total += 1
        if mask & (1 << i) == 0: # 
            keisu += 2
        else:
            keisu -= 2
    if keisu == 0:
        continue
    x = total // keisu

    ps = []
    for i in range(10):
        p = curve_orders[i] - 1
        if mask & (1 << i) == 0: # 
            p += 2 * x
        else:
            p -= 2 * x
        ps.append(p)

    if sum(ps) == sum_of_primes:
        decrypt_flag(prod(ps))

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

hamayanhamayan's blog

KalmarCTF 2025 Writeup

[cry] Very Serious Cryptography

[cry] basic sums

[cry] Not-so-complex multiplication