LUDICOLO - squeamishossifrage
Overview
This is one of my favourite challenges ever!
The description says “We have a bunch of certificates and a flag that is encrypted for one of these certificates. All RSA parameters underlying these certificates were generated by the same source.”
We then have a folder of 1000 certificates which contains 1000 RSA moduli.
Each modulus is of the form (for unknown g, M and random k’s, a’s):
\[n = (k_1 \cdot M + (g^{a_1} \text{ (mod } M \text{)})) \cdot (k_2 \cdot M + (g^{a_2} \text{ (mod } M \text{)}))\]Reading the certs
git clone https://github.com/zerosumsecurity/squeamishossifrage && mv ./squeamishossifrage/LUDICOLO ./LUDICOLO
There’s 2 non-unicode filenames, we’ll just rename them:
cd ./LUDICOLO/certificates && mv 'NO'$'\353''LLE.crt' 'NOELLE.crt' && mv 'DANI'$'\353''LLE.crt' 'DANIELLE.crt' && cd ..
Then we can read them:
from Crypto.PublicKey import RSA
from os import listdir
for cert in listdir("certificates"):
key = RSA.import_key(open(f"certificates/{cert}", "rb").read())
print(f"{cert}\n{key.n = }\n{key.e = }\n\n")
You can observe that e = 21558488234539889837938770635971330903489839146766895224490179041465516193145582266963154883831707522081140734421052039099233464837201660281606980530249
for every cert, but e won’t be used to factor any of the moduli.
Handling unknown g and M
The code used to create the vulnerable primes is not given to us so it’s basically impossible to bruteforce what the real value of g is.
So, we’ll have to create our own new valid g.
Expanding our equation for n yields:
\[n \equiv g^{a_1 + a_2} \text{ (mod } M \text{)}\]As such, testing whether or not the discrete log Zmod(M)(n).log(g) exists is a good way to test if the paramaters are suitable.
All the n’s are 1024 bits, so M is some primorial 0 < M < 2**512. For now let’s just set M as primorial(44) which is 257 bits,
(it’s probably bigger but meh we’re just going to use it to find a good g and then we’ll come back to M).
Now since we’ve shown n is a power of g mod M, we can choose g to be one of the n’s!
The ideal g will have the highest order mod M and pass the discrete log test for all n’s:
from Crypto.PublicKey import RSA
from os import listdir
ns = []
for cert in listdir("certificates"):
key = RSA.import_key(open(f"certificates/{cert}", "rb").read())
ns.append(key.n)
M = prod(Primes()[:44])
orders = [(Zmod(M)(g).multiplicative_order(), g) for g in ns]
g = max(orders)[1]
print(f"{g = }")
This spits out: g = 124487484906862841716197271099288982418112339712300503532811587529290282070741393095312005224387582755588498588422611085050656924777128366585922973222106128294698530803880136848394814736494132569717601758206266058059480149764779347375471688251307463397885640587176752552571821368775747843170717099871242658691
Now let’s go back to M, we’ll try increasing primorials until the discrete log test fails:
g = 124487484906862841716197271099288982418112339712300503532811587529290282070741393095312005224387582755588498588422611085050656924777128366585922973222106128294698530803880136848394814736494132569717601758206266058059480149764779347375471688251307463397885640587176752552571821368775747843170717099871242658691
i = 44
while True:
M = prod(Primes()[:i])
try:
for n in ns:
_ = Zmod(M)(n).log(g)
except:
break
i += 1
print(i)
It fails on primorial(75), making me guess the author used M = primorial(74).
Optimising M’
To reduce the search space for the ROCA attack, we can choose M’ = some divisor of M.
The ideal M’ will have a small order (for a smaller searchspace to brute) but also be big enough
for coppersmith to succeed.
Additionally, a bigger lattice dimension (m) is necessary for smaller M’, but will cause
LLL to take longer to complete, so there is a tradeoff between searchspace and LLL computation time to consider.
p_size = 512
pp = 1
rs = []
for p in Primes():
pp *= p
if pp > 2**p_size:
break
o = 1
for n in ns:
o = lcm(o, Mod(n, p).multiplicative_order())
rs.append((o, p))
ps = []
for _, p in sorted(rs):
ps.append(p)
if prod(ps) > 2**(p_size * 0.6):
break
M = prod(ps)
print(M)
from tqdm import tqdm
import time
def coppersmith(f, X, beta=1.0, m=None):
N = f.parent().characteristic()
delta = f.degree()
if m is None:
epsilon = RR(beta^2/f.degree() - log(2*X, N))
m = max(beta**2/(delta * epsilon), 7*beta/delta).ceil()
t = int((delta*m*(1/beta - 1)).floor())
f = f.monic().change_ring(ZZ)
P,(x,) = f.parent().objgens()
g = [x**j * N**(m-i) * f**i for i in range(m) for j in range(delta)]
g.extend([x**i * f**m for i in range(t)])
B = Matrix(ZZ, len(g), delta*m + max(delta,t))
for i in range(B.nrows()):
for j in range(g[i].degree()+1):
B[i,j] = g[i][j]*X**j
B = B.LLL()
f = sum([ZZ(B[0,i]//X**i)*x**i for i in range(B.ncols())])
roots = set([f.base_ring()(r) for r,m in f.roots() if abs(r) <= X])
return [root for root in roots if N.gcd(ZZ(f(root))) >= N**beta]
def get_test_prime(p_size, M, g):
o = Zmod(M)(g).multiplicative_order()
k_size = p_size - M.nbits()
a_size = o.nbits()
while True:
k = randint(1, 2**k_size-1)
a = randint(1, 2**a_size-1)
if a % o == 0:
continue
p = k * M + pow(g, a, M)
if is_prime(p):
return p, a
def roca_attack(n, g, M, m=1, a=None):
order_M = Zmod(M)(g).multiplicative_order()
c_prime = Zmod(M)(n).log(g)
P.<k> = PolynomialRing(Zmod(n))
if a: # cheat
r = range(a, a+1)
else:
r = range(c_prime//2, (c_prime + order_M)//2)
for a in r:
f = k*M + int(pow(g, a, M))
X = 2**(n.nbits()//2 - M.nbits() + 1)
t_start = time.time()
roots = coppersmith(f, X=X, beta=0.4, m=m)
t_end = time.time()
if roots != []:
k = roots[0]
p = int(f(k))
if is_prime(p):
return p, t_end - t_start
def primorial(n):
M = 1
p = 1
for i in range(n):
p = next_prime(p)
M *= p
return M
def maximal_divisor_M(M, order_M_prime, g):
M_prime = M
for P, e in factor(M):
order_P = Zmod(P)(g).multiplicative_order()
if order_M_prime % order_P != 0:
M_prime //= P
return M_prime
def optimal_M_prime(M, g, p_size, ntrials=20, nn=20, reliability=0.8, t=0, m_range=range(3,8)):
bit_threshold = p_size//2 + t
order_M = Zmod(M)(g).multiplicative_order()
print('search space: ', len(divisors(order_M)))
M_primes = []
for order_M_divisor in tqdm(reversed(divisors(order_M))):
M_prime = maximal_divisor_M(M, order_M_divisor, g)
if M_prime.nbits() >= bit_threshold:
o = Zmod(M_prime)(g).multiplicative_order()
M_primes.append((o, M_prime))
M_primes = list(set(M_primes))
M_primes.sort()
print(M_primes[:nn])
best_time = 2**999999999 # inf
for i in range(nn):
M_prime = Integer(M_primes[i][1])
o = Zmod(M_prime)(g).multiplicative_order()
print(f'### {i} {M_prime.nbits()} {o.nbits()}')
for m in m_range:
success = 0
for _ in range(ntrials):
tst_p, tst_a = get_test_prime(p_size, M_prime, g)
tst_q, _ = get_test_prime(p_size, M_prime, g)
tst_n = tst_p*tst_q
out = roca_attack(tst_n, g, M_prime, m=m, a=tst_a%o)
if out is not None:
_, duration = out
success += 1
if success > 0:
apprx_time = duration * (o/2)
print(f"{m=}: {float(success/ntrials):.1%}, approx time: {apprx_time:.2f} seconds")
if success/ntrials >= reliability and apprx_time < best_time:
best_M = M_prime
best_m = m
best_time = apprx_time
print(f"M_prime = {best_M}")
print(f"m = {best_m}")
return best_M, best_m
g = 124487484906862841716197271099288982418112339712300503532811587529290282070741393095312005224387582755588498588422611085050656924777128366585922973222106128294698530803880136848394814736494132569717601758206266058059480149764779347375471688251307463397885640587176752552571821368775747843170717099871242658691
M = 2562050762925653677328453030125662986159243532827792161255140060416517133784758421124051417870
optimal_M_prime(M, g, 512, nn=5, t=15)
This finds:
M_prime = 180537903712182739447634935500952314074429576908277933036643046670837592164271750889410
m = 4
Final solve script
from Crypto.PublicKey import RSA
from Crypto.Cipher import AES
from os import listdir
from tqdm import tqdm
def coppersmith(f, X, beta=1.0, m=None):
N = f.parent().characteristic()
delta = f.degree()
if m is None:
epsilon = RR(beta^2/f.degree() - log(2*X, N))
m = max(beta**2/(delta * epsilon), 7*beta/delta).ceil()
t = int((delta*m*(1/beta - 1)).floor())
f = f.monic().change_ring(ZZ)
P,(x,) = f.parent().objgens()
g = [x**j * N**(m-i) * f**i for i in range(m) for j in range(delta)]
g.extend([x**i * f**m for i in range(t)])
B = Matrix(ZZ, len(g), delta*m + max(delta,t))
for i in range(B.nrows()):
for j in range(g[i].degree()+1):
B[i,j] = g[i][j]*X**j
B = B.LLL()
f = sum([ZZ(B[0,i]//X**i)*x**i for i in range(B.ncols())])
roots = set([f.base_ring()(r) for r,m in f.roots() if abs(r) <= X])
return [root for root in roots if N.gcd(ZZ(f(root))) >= N**beta]
def roca_attack(n, g, M, m=1):
order_M = Zmod(M)(g).multiplicative_order()
c_prime = Zmod(M)(n).log(g)
P.<k> = PolynomialRing(Zmod(n))
for a in range(c_prime//2, (c_prime + order_M)//2):
f = k*M + int(pow(g, a, M))
X = 2**(n.nbits()//2 - M.nbits() + 1)
roots = coppersmith(f, X=X, beta=0.4, m=m)
if roots != []:
k = roots[0]
p = int(f(k))
if is_prime(p):
return p, n//p
def decrypt(d, n):
enc_key = 0x63cd3cc036a3059eaba99faa4d295c1ad826f018c62d405c19c6149e826f7a1ba488534a52fa0647427d67efdbe1620fa13729d584bd193715b88c5013b1c8df084b16fad33b3a60f1c946228d27fa0260a06dcf8d032d7d92acea43e897f37df7cc917b30ad37c2de49edb1ce40ecb7f435db4dbad20671b9c6465a1cdbfd43
enc_data = bytes.fromhex("379fb5383b1c35c774a45b13148cc7cea90f27e78150540be8a292024e5cec2cd0ebd7bfe92c9c452402777297d155fb")
iv = bytes.fromhex("b789660c2ba7f7d7b77fa480a7a70bf6")
key = bytes.fromhex(hex(pow(enc_key, d, n))[-64:])
cipher = AES.new(key, AES.MODE_CBC, iv)
try:
print(cipher.decrypt(enc_data).decode().strip())
except:
pass
def main():
g = 124487484906862841716197271099288982418112339712300503532811587529290282070741393095312005224387582755588498588422611085050656924777128366585922973222106128294698530803880136848394814736494132569717601758206266058059480149764779347375471688251307463397885640587176752552571821368775747843170717099871242658691
M_prime = 180537903712182739447634935500952314074429576908277933036643046670837592164271750889410
for cert in tqdm(listdir("certificates")):
if cert != "LUC.crt":
continue
key = RSA.import_key(open(f"certificates/{cert}", "rb").read())
n = Integer(key.n)
e = key.e
f = roca_attack(n, g, M_prime, m=4)
if f is not None:
p, q = f
d = pow(e, -1, (p-1)*(q-1))
decrypt(d, n)
if __name__ == "__main__":
main()