Navigation Menu

Skip to content

Instantly share code, notes, and snippets.

@r98inver
Created November 5, 2023 18:34
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save r98inver/15607feb69f09e511eca38aee6389c75 to your computer and use it in GitHub Desktop.
Save r98inver/15607feb69f09e511eca38aee6389c75 to your computer and use it in GitHub Desktop.
LakeCTF 2023 - Invalid curve attack
from time import time
def get_invalid_point(p, a, known_factors = [], check_point = False):
"""
Input: the prime p, the fixed curve parameter a, and the already know factors
that we do not want to repeat. Optionally we can check how much does it take
to solve the dlp for a point before returning it with check_point=True.
Output: an invalid point Q, the parameter b defining its curve, and the factors
of its order.
"""
while True:
b = randint(1, p)
E_1 = EllipticCurve(GF(p), [a, b])
order = E_1.order()
factors = prime_factors(order)
# Compute the best order we can get from a point
good_factors = []
for f in factors:
if f.nbits() <= 40 and not f in known_factors:
good_factors.append(f)
cof = prod(good_factors)
if cof.nbits() >= 50:
print(f'Found curve')
break
# Now that we have a good curve, we need to find the point
G = E_1.gen(0) * (order // cof)
assert G.order() == cof
if check_point:
# Sanity check that we can actually solve the invalid dlp
r = randint(1, cof)
Q = G*r
print(f'Solving dlog for {cof.nbits()} bits order')
tic = time()
dlog = G.discrete_log(Q)
assert dlog == r, (r, dlog)
print(f'Done in {round(time() - tic, 2)} s')
return G, b, good_factors
if __name__ == '__main__':
p = 0xfffffffffffffffffffffffffffffffeffffffffffffffff
a = 0xfffffffffffffffffffffffffffffffefffffffffffffffc
b = 0x64210519e59c80e70fa7e9ab72243049feb8deecc146b9b1
E = EllipticCurve(GF(p), [a, b])
order = E.order()
assert is_prime(order) # should we trust NSA?
known_factors = []
Gs = []
Bs = []
for i in range(4):
G, b, new_factors = get_invalid_point(p, a, known_factors)
known_factors.extend(new_factors)
print(f'{G = }\n{b = }')
print(f'Got {prod(known_factors).nbits()} total bits')
# Some computed values
p = 0xfffffffffffffffffffffffffffffffeffffffffffffffff
a = 0xfffffffffffffffffffffffffffffffefffffffffffffffc
b = 0x64210519e59c80e70fa7e9ab72243049feb8deecc146b9b1
Bs = [83741891083651463213018945835494413320520449989597215648,3556206473404317281093691979083778944572588872003627559970,132627736693468008571263914981090018160610438249416432561,4353766386870675869823517562355728918310218671450488829638]
Gs = [EllipticCurve(GF(p), [a, Bs[0]])(1428777260646132976198331917216550410517338377336849911092, 3658983833028448009741994042652306163657412286434111440479),EllipticCurve(GF(p), [a, Bs[1]])(3189235510701084020240251273172260904256567493190538416973, 3147050744360070584444363752093634124297717789231789390963),EllipticCurve(GF(p), [a, Bs[2]])(1836055837552433451429707649431552069210777860779533915323, 4080888809128014080938902461081426574934912634479355715692),EllipticCurve(GF(p), [a, Bs[3]])(567148773685333711499991584170987837091585548967120385444, 2945834156539179266918934145900085216962713232769658612995)]
# Server values
pub = EllipticCurve(GF(p), [a, b])(275956366273838645914286744108317970424389601350215013292,1715484665561054570396524612468150066010506001507851259697)
out = [
EllipticCurve(GF(p), [a, Bs[0]])(2520009623362543945986336259874602290571366143015497579774,918209543266182540574220472175145773512397388546557928127),
EllipticCurve(GF(p), [a, Bs[1]])(6114283288101947049456189131219162763629412798424257598888,3337781419281746480460476732287507319887104334435838499559),
EllipticCurve(GF(p), [a, Bs[2]])(4375469479810874253079345013985635396946981387269636176579,3039983122916367530269883045392843677915744087945892387770),
EllipticCurve(GF(p), [a, Bs[3]])(5006251221813189712869553605012565305195873815585805823417,1916349364515225922801955454929707154738727920670355042345)
]
orders = [Gs[i].order() for i in range(4)]
dlogs = []
for i in range(4):
print(f'Solving dlog {i}')
dlog = Gs[i].discrete_log(out[i])
print(f'{dlog = }')
dlogs.append(dlog)
PK = CRT_list(dlogs, orders)
d = inverse_mod(PK, E.order())
G = d*pub
flag = int(G[0]).to_bytes((int(G[0]).bit_length() + 7)//8, 'big')
print(f'{flag = }')
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment