AeroCTF 2021 | horcrux - crypto-writeup-public

#!/usr/bin/env python3.8

from os import urandom
from gmpy2 import next_prime
from random import randrange, getrandbits
from Crypto.Cipher import AES
from fastecdsa.curve import Curve


def bytes_to_long(data):
    return int.from_bytes(data, 'big')


def generate_random_point(p):
    while True:
        a, x, y = (randrange(0, p) for _ in range(3))
        b = (pow(y, 2, p) - pow(x, 3, p) - a * x) % p

        if (4 * pow(a, 3, p) + 27 * pow(b, 2, p)) % p != 0:
            break

    return Curve(None, p, a, b, None, x, y).G


class DarkWizard:
    def __init__(self, age):
        self.power = int(next_prime(getrandbits(age)))
        self.magic = generate_random_point(self.power)
        self.soul = randrange(0, self.power)

    def create_horcrux(self, location, weakness):
        # committing a murder
        murder = self.cast_spell(b'AVADA KEDAVRA')

        # splitting the soul in half
        self.soul = self.soul * pow(2, -1, self.power) % self.power

        # making a horcrux
        horcrux = (self.soul + murder) * self.magic

        # nobody should know location and weakness of the horcrux
        horcrux.x ^= location
        horcrux.y ^= weakness

        return horcrux

    def cast_spell(self, spell_name):
        spell = bytes_to_long(spell_name)

        return spell %~ spell # -1


def encrypt(key, plaintext):
    cipher = AES.new(key=key, mode=AES.MODE_ECB)
    padding = b'\x00' * (AES.block_size - len(plaintext) % AES.block_size)

    return cipher.encrypt(plaintext + padding)


def main():
    wizard_age = 3000
    horcruxes_count = 2

    wizard = DarkWizard(wizard_age)
    print(f'Wizard\'s power:\n{hex(wizard.power)}\n')
    print(f'Wizard\'s magic:\n{wizard.magic}\n')

    key = urandom(AES.key_size[0]) # 16
    horcrux_length = len(key) // horcruxes_count

    for i in range(horcruxes_count):
        key_part = key[i * horcrux_length:(i + 1) * horcrux_length]

        horcrux_location = bytes_to_long(key_part[:horcrux_length // 2])
        horcrux_weakness = bytes_to_long(key_part[horcrux_length // 2:])

        horcrux = wizard.create_horcrux(horcrux_location, horcrux_weakness)
        print(f'Horcrux #{i + 1}:\n{horcrux}\n')

    with open('flag.txt', 'rb') as file:
        flag = file.read().strip()

    ciphertext = encrypt(key, flag)
    print(f'Ciphertext:\n{ciphertext.hex()}')


if __name__ == '__main__':
    main()

やっていることは……

ランダムな曲線のランダムな点 $G$ を作る
ランダムなパラメータ $r \in \lbrack 0, p-1 \rbrack$ (= soul )を作る
$key = key_1 || key_2 || key_3 || key_4$ として
$P_1 = (2^{-1}r - 1) * G$ に対して $Q_1 = (P_1.x \oplus key_1, P_1.y \oplus key_2)$
$P_2 = (2^{-2}r - 1) * G$ に対して $Q_2 = (P_2.x \oplus key_3, P_2.y \oplus key_4)$

として、 $key$ を求める問題

与えられるパラメータは……

$p, G, Q_1, Q_2$ の4つ

パラメータの大きさ

$p, G, Q_1, Q_2$ それぞれ3000bitくらい
$key_i$ 32bit くらい

考察（ボツ）

$2P_2 + G = (2^{-1}r - 2)G + G = (2^{-1}r - 1)G = P_1$
$P_i = (x_i, y_i), G = (x_g, y_g)$ と書いて EllipticCurve の加法公式より
- $2P_2 = (x', y')$ とおきつつ
- $\lambda_1 = \frac{3x_2^2 + a}{2 y_2}$
- $x' = \lambda_1^2 - 2x_2, y' = \lambda_1(x_2 - x') - y_2$
$\lambda_2 = \frac{y' - y_g}{x' - x_g}$
- $x_1 = \lambda_2 ^2 - x' - x_g$
- $y_1 = \lambda_2 (x' - x_1) - y'$
↑で実際には $(x_1, y_1), (x_2, y_2)$ は下位32bitはわからないのでこれを $(x_1 + s_1, y_1 + t_1), (x_2 + s_2, y_2 + t_2)$ と置き直して計算したい

考察

$y_g^2 - y_1^2 = x_g^3 - x_1^3 + a(x_g - x_1)$ と
$y_2^2 - y_1^2 = x_2^3 - x_1^3 + a(x_2 - x_1)$ より、
$a(x_g - x_1) = y_g^2 - y_1^2 - x_g^3 + x_1^3$
$a(x_2 - x_1) = y_2^2 - y_1^2 - x_2^3 + x_1^3$ となるので $a$ を消して

$(y_g^2 - y_1^2 - x_g^3 + x_1^3)(x_2 - x_1) = (y_2^2 - y_1^2 - x_2^3 + x_1^3)(x_g - x_1)$ が成り立つ

$y_g^2 x_2 - y_1^2 x_2 - x_g^3 x_2 + x_1^3 x_2 - y_g^2 x_1 + y_1^2 x_1 + x_g^3 x_1 = y_2^2 x_g - y_1^2 x_g - x_2^3 x_g + x_1^3 x_g - x_1 y_2^2 + x_1 y_1^2 - x_1 x_2^3$

↑で実際には $(x_1, y_1), (x_2, y_2)$ は下位32bitはわからないのでこれを $(x_1 + s_1, y_1 + t_1), (x_2 + s_2, y_2 + t_2)$ と置き直して

solution

これで一応解ける……。要するに、未知数は32bitまでで、↑の等式をみても、最大でも未知数は4乗までにしかならないので、それぞれの項を分解して行列に入れると良い

要するに

$f = k_1x_1 + k_2x_2 + \dots + k_nx_n + c$ （ $x_i$ は最大でも $2^{32*4}$ の未知数）

$f \equiv 0 \mod p$ なので $f - tp = -c$ と置き直して

$\begin{pmatrix} x_1 & x_2 & \cdots & x_n & t\end{pmatrix} \begin{pmatrix} 1 & & \cdots & &k_1 \ & 1 & & & k_2 \ & & \ddots & & \vdots \ & & & 1 & k_n \ & & & & p \end{pmatrix}$

↑という格子を考えて、lb, ubは $2^{32*\alpha}$ とか $-c$ とかになることを考えるとCVPで解ける（解けるのかと思うかもしれないけど、 $f$ のエントロピー（知らないbit数の和）は1000bitくらいであるのに対して、 $p$ は3000bitくらいあるので解ける）

# x1 = (x1 >> 32) << 32
# y1 = (y1 >> 32) << 32
# x2 = (x2 >> 32) << 32
# y2 = (y2 >> 32) << 32

print("[+] Start...")

PR.<s1, t1, s2, t2> = PolynomialRing(GF(p))
# (y_g^2 - y_1^2 - x_g^3 + x_1^3)(x_2 - x_1) = (y_2^2 - y_1^2 - x_2^3 + x_1^3)(x_g - x_1)
f = (gy^2 - (y1 + t1)^2 - gx^3 + (x1 + s1)^3)*((x2 + s2) - (x1 + s1)) - ((y2 + t2)^2 - (y1 + t1)^2 - (x2 + s2)^3 + (x1 + s1)^3)*(gx - (x1 + s1))

print("[+] Make lattice...")
coeffs = f.coefficients()
monomials = f.monomials()
degrees = [monomial.degree() for monomial in monomials]

n = len(monomials)
M = matrix(ZZ, n, n)
M.set_block(0, 0, matrix.identity(n-1))
M[n-1] = coeffs
M[n-1,n-1] = p

lb = [0 for _ in range(n)]
ub = [0 for _ in range(n)]
for i in range(n):
    lb[i] = -(2^(32*degrees[i]))
    ub[i] = 2^(32*degrees[i])

lb[-1] = int((-coeffs[-1]) % p)
ub[-1] = int((-coeffs[-1]) % p)

# target = [(u + l) // 2 for u, l in zip(lb, ub)]
# size = max(target)
# weights = []
# 
# for i in range(len(ub)):
#     w = size // target[i] if target[i] != 0 else size
#     M[i] *= w
#     target[i] *= w
#     weights.append(w)
# 
# print("[+] CVP...")
# closest = Babai_CVP(M.transpose(), vector(target))
# 
# print("[+] done")
# print([closest[i] // weights[i] for i in range(len(closest))])

results, weights = solve(M.transpose(), lb, ub)
print([results[i] // weights[i] for i in range(len(results))])

s1 = closest[-5] // weights[-5]
t1 = closest[-4] // weights[-4]
s2 = closest[-3] // weights[-3]
t2 = closest[-2] // weights[-2]

print(s1, t1, s2, t2)