AlpacaHack Round 12 (Crypto) Writeup

RSARSARSARSARSARSA

You don't have to say it again and again...

問題は簡潔。

from math import gcd
import os
from Crypto.Util.number import getPrime, bytes_to_long

e = 19
while True:
    p = getPrime(2048)
    q = getPrime(2048)
    if gcd((p - 1) * (q - 1), e) == 1:
        break
n = p * q

flag = os.environ.get("FLAG", "Alpaca{**** REDACTED ****}")
assert len(flag) == 26 and flag.startswith("Alpaca{") and flag.endswith("}")

m = bytes_to_long((flag * 1337).encode())
c = pow(m, e, n)

print(f"{n = }")
print(f"{e = }")
print(f"{c = }")

RSA暗号。e=19と小さいのと、26文字のフラグが1337回繰り返した状態で平文にしてあるのが特徴。フラグはAlpaca{と}で囲われているので不明なバイト数は18bytes。これが繰り返されているので暗号文全体は4096bitsだが、未知変数は18*8bitsしかないので、Coppersmithで解く。

from Crypto.Util.number import *

n = 4342452751297...[redacted]...7965527
e = 19
c = 7833881697699...[redacted]...470920836

prefix = b"Alpaca{"
suffix = b"}"

Z.<x> = PolynomialRing(Zmod(n))

flag_template = prefix + b'\x00' * 18 + suffix
repeated_template = flag_template * 1337
template_int = bytes_to_long(repeated_template)

first_unknown_pos = len(suffix)
coeff = 0

for rep in range(1337):
    pos_in_full = rep * 26 + first_unknown_pos
    byte_coeff = 256 ** pos_in_full
    coeff += byte_coeff

f = (template_int + coeff * x)^e - c

f = f.monic()
roots = f.small_roots(X=2**(8*18), epsilon=1/30)
print(prefix + long_to_bytes(int(roots[0]), 18) + suffix)

このように不明部分を1つの変数としてCoppersmithする。

OTEC

Obliviate!

楕円曲線を使った Oblivious Transfer (OT) プロトコルの実装で、フラグが3つに分割されて暗号化されている。

import os
import signal
import secrets
from fastecdsa.curve import secp256k1
from fastecdsa.point import Point
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from Crypto.Util.number import long_to_bytes

signal.alarm(60)

flag = os.environ.get("FLAG", "Alpaca{**** REDACTED ****}").encode()

# Oblivious Transfer using Elliptic Curves
G = secp256k1.G
a = secrets.randbelow(secp256k1.q)
A = a * G

print(f"{A.x = }")
print(f"{A.y = }")

x, y = map(int, input("B> ").split(","))
B = Point(x, y, secp256k1)

k0 = long_to_bytes((a * B).x, 32)
k1 = long_to_bytes((a * (B - A)).x, 32)

def encrypt(message, key):
    return AES.new(key, AES.MODE_ECB).encrypt(pad(message, 16))

print(encrypt(flag[0::3], k0).hex())
print(encrypt(flag[1::3], k1).hex())
print(encrypt(flag[2::3], bytes(c0 ^ c1 for c0, c1 in zip(k0, k1))).hex())

実装はこんな感じ。k0,k1,bytes(c0 ^ c1 for c0, c1 in zip(k0, k1)が分かれば解ける。Aが与えられていて、Bを入力できるので良い感じの入力を入れて、これら3つを確定させていく。一気に確定させるのは難しいので別々のセッションで別々に復元してつなげる。

k0

k0 = long_to_bytes((a * B).x, 32)と計算される。aは分からないのだが、Gは分かるので、B=Gとしてやれば、aGのx座標が鍵になり、これは与えられるAのx座標と同じなので、k0が判明する。

これによりprint(encrypt(flag[0::3], k0).hex())を復元できる。

k1

k1 = long_to_bytes((a * (B - A)).x, 32)と計算される。B=Aとしてやれば無限遠のx座標にすることができるが、これはライブラリが取得できずに例外で落ちてしまうので、B=A+GとすることでaGのx座標を鍵にすることができ、これはk0の時と同様に与えられるAのx座標と同じなので、k1が判明する。

これによりprint(encrypt(flag[1::3], k1).hex())を復元できる。

bytes(c0 ^ c1 for c0, c1 in zip(k0, k1))

これが一番難しい。

k0 = long_to_bytes((a * B).x, 32)
k1 = long_to_bytes((a * (B - A)).x, 32)

という計算があり、それを元にbytes(c0 ^ c1 for c0, c1 in zip(k0, k1))を計算している。方向性として計算結果が0になるようにしてみよう。つまり、(a * B).x = (a * (B - A)).xを目指す。x座標が一致すればいいので、点としてはa * B = a * (B - A)かa * B = -(a * (B - A))を満たせばよい。

1つ目はこうなるのでダメ。

2つ目はこうできるので、B=A/2であれば(a * B).x = (a * (B - A)).xとなり、鍵は最終的に0にできる。2で割るのは計算可能なので、これで鍵を0にすることができ、print(encrypt(flag[2::3], bytes(c0 ^ c1 for c0, c1 in zip(k0, k1))).hex())が復元できる。

ソルバ

最終的に以下のようにやればフラグが手に入る。

from ptrlib import *
from fastecdsa.curve import secp256k1
from fastecdsa.point import Point
from Crypto.Cipher import AES
from Crypto.Util.Padding import unpad
from Crypto.Util.number import long_to_bytes, inverse

def get_A(r):
    r.recvuntil(b'A.x = ')
    ax = int(r.recvline().strip())
    r.recvuntil(b'A.y = ')
    ay = int(r.recvline().strip())
    return ax, ay

def get_ciphertexts(r, B_coords):
    r.sendlineafter("B> ", f"{B_coords[0]},{B_coords[1]}".encode())
    
    c0_hex = r.recvline().strip().decode()
    c1_hex = r.recvline().strip().decode()
    c2_hex = r.recvline().strip().decode()
    
    return c0_hex, c1_hex, c2_hex

def decrypt_part(ciphertext_hex, key):
    ciphertext = bytes.fromhex(ciphertext_hex)
    aes = AES.new(key, AES.MODE_ECB)
    return unpad(aes.decrypt(ciphertext), 16)

def get0():
    print("Getting part0...")
    
    r = remote('[redacted]', 62340)
    ax, ay = get_A(r)
    G = secp256k1.G
    c0_hex, c1_hex, c2_hex = get_ciphertexts(r, (G.x, G.y))
    r.close()
    
    k0 = long_to_bytes(ax, 32)
    part0 = decrypt_part(c0_hex, k0)
    
    return part0

def get1():
    print("Getting part1...")
    
    r = remote('[redacted]', 62340)
    ax, ay = get_A(r)
    
    A = Point(ax, ay, secp256k1)
    G = secp256k1.G
    B = A + G
    
    c0_hex, c1_hex, c2_hex = get_ciphertexts(r, (B.x, B.y))
    r.close()
    
    k1 = long_to_bytes(ax, 32)
    part1 = decrypt_part(c1_hex, k1)
    
    return part1

def get2():
    print("Getting part2...")
    
    r = remote('[redacted]', 62340)
    ax, ay = get_A(r)
    
    A = Point(ax, ay, secp256k1)
    inv2 = inverse(2, secp256k1.q)
    B_half = inv2 * A
    
    c0_hex, c1_hex, c2_hex = get_ciphertexts(r, (B_half.x, B_half.y))
    r.close()
    
    k2 = b'\x00' * 32
    part2 = decrypt_part(c2_hex, k2)
    
    return part2

def combine_parts(part0, part1, part2):
    flag = b''
    max_len = max(len(part0), len(part1), len(part2))
    
    for i in range(max_len):
        if i < len(part0):
            flag += part0[i:i+1]
        if i < len(part1):
            flag += part1[i:i+1]
        if i < len(part2):
            flag += part2[i:i+1]
    
    return flag

def main():
    print("=== OTEC Final Clean Solver ===")
    
    part0 = get0()
    part1 = get1()
    part2 = get2()
    
    print(f"part0: {part0}")
    print(f"part1: {part1}")
    print(f"part2: {part2}")
    
    flag = combine_parts(part0, part1, part2)
    print(f"\nFLAG: {flag.decode()}")

if __name__ == "__main__":
    main()