# [pbctf 2020] LeaK

This post originally appeared on the flagbot site, feel free to read it there. It is presented here as a form of archival and to collect all my posts in one place.

Being aware of this paper early on, already when first seeing the challenge, we incorrectly conclude that the bounds for the lattice with 2 unknowns don’t match what we need for this challenge. After postponing trying to deal with lattice-induced headaches for a while, we eventually decide to implement the extended HNP based approach as described e.g. here. After implementing this and finding some minor bugs, it’s unfortunately still not working. Further investigation seems to tell us that the embedding of CVP in SVP we were using is not actually giving us a good result. We’re running out of time, we never really used Babai’s nearest plane algorithm before, what do we do now? Well, you copy an implementation of Babai’s algorithm from some random webpage and hope for the best. After waiting for a while (because apparently the Gram-Schmidt part of the CVP was quite slow), and against our expectations, the flag just appeared, no need to even add more modular reductions or find more hidden bugs. Thanks, internet!

from collections import namedtuple
from ecdsa import SECP256k1
import ast

curve_order = int(SECP256k1.order)

Sig = namedtuple("Sig", "h leak r s".split())
sigs = []
with open("leak.out") as f:
data = t.split("]")[0].strip() + "]"
ciphertext = bytes.fromhex(t.split("]\n")[1].strip())
for h, leak, r, s in ast.literal_eval(data):
sigs.append(Sig(h, leak, r, s))

def Babai_CVP(M, target):
M = Matrix(QQ, M).LLL()
target = vector(QQ, target)
G = M.gram_schmidt()[0]
diff = target
for i in reversed(range(M.nrows())):
diff -=  M[i] * ((diff * G[i]) / (G[i] * G[i])).round()
return target - diff

delta = QQ(1/(10^8))
def EHNP(xbar, N, pis, nus, alphas, rhos, mus, betas):
assert len(pis) == len(nus)
assert len(alphas) == len(rhos) == len(mus) == len(betas)
assert all(len(rho) == len(mu) for rho, mu in zip(rhos, mus))
m = len(pis)
d = len(alphas)
L = sum(len(rho) for rho in rhos)
D = d + m + L
print(f"{D = }, {d = }, {m = }, {L = }")
B = [[0 for _ in range(D)] for _ in range(D)] # +1 for CVP
# N * I_d
for i in range(d):
B[i][i] = N
# A
for j in range(m):
for i in range(d):
B[d + j][i] = alphas[i]*2^pis[j]
# X
for i in range(m):
B[i + d][i + d] = delta / (2^nus[i])
# rhos
c = 0
for i in range(d):
for j, rho in enumerate(rhos[i]):
B[d + m + c][i] = rho
c += 1
# K
c = 0 # quick and dirty way to not have to do math
for mu_arr in mus:
for mu in mu_arr:
B[d + m + c][d + m + c] = delta / (2^mu)
c += 1

kappa = (2^(D / 4) * (m + L)^(1/2) + 1) / 2
print((delta * kappa).n())
assert 0 < delta * kappa < 1
v = [(beta - alpha * xbar) % N for beta, alpha in zip(betas, alphas)] + [delta / 2 for _ in range(L + m)]
W = Babai_CVP(B, v)
xs = [(W[d + j] * 2^(nus[j])) / delta for j in range(m)]
return xbar + sum(xs[j]*2^(pis[j]) for j in range(m))

pis = [0]
nus = [256]
alphas = [sig.r for sig in sigs]
rhos = [[-sig.s % curve_order, (-sig.s * 2^216) % curve_order] for sig in sigs]
mus = [[40, 40] for _ in range(len(sigs))]
betas = [(sig.s * 2^40 * sig.leak - sig.h) % curve_order for sig in sigs]
key = EHNP(0, curve_order, pis, nus, alphas, rhos, mus, betas)

print(f"{key = }")

from hashlib import sha256
from Crypto.Cipher import AES
cipher = AES.new(sha256(str(key).encode()).digest(), AES.MODE_ECB)
print(cipher.decrypt(ciphertext))

Flag: pbctf{!!!_https://eprint.iacr.org/2019/023.pdf_\$}