angstrom CTF 2021 | Circle of Trust - crypto-writeup-public

#angstromctf2021

import random
import secrets
from decimal import Decimal, getcontext
from Crypto.Cipher import AES

BOUND = 2 ** 128
MULT = 10 ** 10

getcontext().prec = 50

def nums(a):
    b = Decimal(random.randint(-a * MULT, a * MULT)) / MULT
    c = (a ** 2 - b ** 2).sqrt()
    if random.randrange(2):
        c *= -1
    return (b, c)


with open("flag", "r") as f:
    flag = f.read().strip().encode("utf8")

diff = len(flag) % 16
if diff:
    flag += b"\x00" * (16 - diff)

keynum = secrets.randbits(128)
ivnum = secrets.randbits(128)

key = int.to_bytes(keynum, 16, "big")
iv = int.to_bytes(ivnum, 16, "big")

x = Decimal(random.randint(1, BOUND * MULT)) / MULT
for _ in range(3):
    (a, b) = nums(x)
    print(f"({keynum + a}, {ivnum + b})")

cipher = AES.new(key, AES.MODE_CBC, iv=iv)
enc = cipher.encrypt(flag)
print(enc.hex())

AESのkey, ivを当てるのが目的

$x \leftarrow \lbrack \frac{1}{10^{10}}, \frac{2^{128}10^{10}}{10^{10}} \rbrack$

という広い範囲でランダムに選んで

$a = \lbrack -\frac{x 10^{10}}{10^{10}}, \frac{x 10^{10}}{10^{10}} \rbrack, b = \pm \sqrt{x^2 - a^2}$

で $key + a, iv + b$ が3回与えられる

考察

$X_i = key + a, Y_i = iv + b$ として $a = X_i - key$ をもう一方に代入すると

$Y_i = iv \pm \sqrt{x^2 - (X_i - key)^2}$

$Y_i - iv = \pm \sqrt{x^2 - (X_i - key)^2}$

$(Y_i - iv)^2 = x^2 - (X_i - key)^2$

$(X_i - key)^2 + (Y_i - iv)^2 = x^2 \quad \quad\tag{1}$

になる。これは円の公式から $(key, iv)$ 座標を中心とした半径 $x$ の円だとわかる。

その円上の3点 $(X_i, Y_i)$ から、円の中心座標をもとめてという題意

ただ、 $b$ の生成時に無理やり平方根を取っているので、無理数のため誤差が生じる

そのせいで、 $Y_i$ の値は誤差を含む（はず…）

解法

似た問題としてgoogle ctf 2019 quals | realityがある( $\mathbb{R}$ 上の Shamir's Secret Sharing

https://colab.research.google.com/github/nguyenduyhieukma/CTF-Writeups/blob/master/Google%20CTF%20Quals/2019/reality/reality-solution.ipynb

ここにあるやり方と同じようにCVPをやると解ける

使う式は(1)を2つ使って $x^2$ を消した後、展開すると、

$(-2X_i + 2X_j)key + (-2Y_i + 2Y_j)iv = -Y_i^2 + Y_j^2 - X_i^2 + X_j^2$

となるので、右辺をtarget vectorの値としてCVPで誤差を持っていくといい

from Crypto.Cipher import AES

def solve_cvp(B, t, verbose=False):
    t_ = t - B.stack(t).gram_schmidt()[0].row(-1)
    if verbose:
        print("Target vector projection:")
        print(numerical_approx(t_, digits=4))

    B_ = B.LLL()
    if verbose:
        print("\nLLL-reduced basis:")
        print(numerical_approx(B_, digits=4))

    c = B_.solve_left(t_)

    c_ = vector(map(round, c))
    if verbose:
        print("\nRound-off errors:")
        print(numerical_approx(vector(map(abs, c - c_)), digits=4))

    return c_ * B_

def solve_cvp2(B, t, scale_factors=None, verbose=False):
    if not scale_factors:
        scale_factors = 1 * B.ncols()

    if verbose:
        print("Scale factors:")
        print(numerical_approx(vector(scale_factors), digits=4))

    scale_matrix = diagonal_matrix(vector(scale_factors))
    return solve_cvp(B*scale_matrix, t*scale_matrix, verbose) * scale_matrix^-1

x0, y0 = (45702021340126875800050711292004769456.2582161398, 310206344424042763368205389299416142157.00357571144)
x1, y1 = (55221733168602409780894163074078708423.359152279, 347884965613808962474866448418347671739.70270575362)
x2, y2 = (14782966793385517905459300160069667177.5906950984, 340240003941651543345074540559426291101.69490484699)
enc = bytes.fromhex("838371cd89ad72662eea41f79cb481c9bb5d6fa33a6808ce954441a2990261decadf3c62221d4df514841e18c0b47a76")

A0 = -2*y0 + 2*y1
A1 = -2*y0 + 2*y2
A2 = -2*y1 + 2*y2
B0 = -2*x0 + 2*x1
B1 = -2*x0 + 2*x2
B2 = -2*x1 + 2*x2
C0 = -y0^2 + y1^2 - x0^2 + x1^2
C1 = -y0^2 + y2^2 - x0^2 + x2^2
C2 = -y1^2 + y2^2 - x1^2 + x2^2

B = matrix(QQ, [
    [A0, A1, A2, 1, 0],
    [B0, B1, B2, 0, 1],
])

t = vector(QQ, [C0, C1, C2, 2^127, 2^127])
scale_factors = [10^20, 10^20, 10^20, 2^-128, 2^-128]
closest_vector = solve_cvp2(B, t, scale_factors, verbose=True)

D0, D1, D2, iv, key = closest_vector
print(int(iv).bit_length(), iv)
print(int(key).bit_length(), key)

iv = int.to_bytes(int(iv), 16, "big")
key = int.to_bytes(int(key), 16, "big")

cipher = AES.new(key, AES.MODE_CBC, iv=iv)
flag = cipher.decrypt(enc)
print(flag)