CONFidence CTF 2015 – RSA1 (Crypto 400)

Find the flag

Summary: Coppersmith’s short pad attack

In this challenge we are given a python script and a set of files generated by it. Here’s the main part:

r = generate_random_number_bytes(1024)
p = get_prime(r % (2**512))
q = get_prime((r << 512) % (2**512))
n = p*q
flag_index = random.getrandbits(10)
for i in range(0, 1024):
   if i <> flag_index:
     encryptedFlag = pow(FLAG * 2**32 + random.getrandbits(32), e, n)
r = generate_random_number_bytes(1024)
p = get_prime(r % (2**512))
q = get_prime((r >> 512) % (2**512))

Flag is also encrypted under another random modulus (n2) but it is not relevant for this challenge (the author confirmed it was added to make the tasks rsa1 and rsa2 look similar).

Here we have 1023 messages encrypted. Each message is the flag padded with 32 random least significant bits. There is a classic attack for this setting – Coppersmith’s Short Pad attack. The description on Wikipedia is enough to implement the attack in Sage, though there is a little problem: Sage doesn’t want to compute the so called resultant of two polynomials modulo composite number:

ValueError: Resultants require base fields or integer base ring.

We can overcome this issue by switching the ring to ZZ and back.

The first phase of the attack is to take some two of the encrypted messages and recover the small difference between them:

from sage.all import *
n1 = long(open("out/n1").read())
e = 3
C1 = long(open("out/flag0").read())
C2 = long(open("out/flag1").read())
PRxy.<x,y> = PolynomialRing(Zmod(n1))
PRx.<xn> = PolynomialRing(Zmod(n1))
PRZZ.<xz,yz> = PolynomialRing(Zmod(n1))
g1 = x**e - C1
g2 = (x + y)**e - C2
q1 = g1.change_ring(PRZZ)
q2 = g2.change_ring(PRZZ)
h = q2.resultant(q1)
# need to switch to univariate polynomial ring
# because .small_roots is implemented only for univariate
h = h.univariate_polynomial() # x is hopefully eliminated
h = h.change_ring(PRx).subs(y=xn)
h = h.monic()
roots = h.small_roots(X=2**40, beta=0.3)
assert roots, "Failed1"
diff = roots[0]
if diff > 2**32:
    diff = -diff
    C1, C2 = C2, C1
print "Difference:", diff

The second stage is to apply Franklin-Reiter related messages attack to recover the message:

x = PRx.gen() # otherwise write xn
g1 = x**e - C1
g2 = (x + diff)**e - C2
# gcd
while g2:
    g1, g2 = g2, g1 % g2
g = g1.monic()
assert g.degree() == 1, "Failed 2"
# g = xn - msg
msg = -g[0]
# convert to str
h = hex(int(msg))[2:].rstrip("L")
h = "0" * (len(h) % 2) + h
print `h.decode("hex")`

The flag: Drgns{She’s_playin’_dumb_all_the_timeJust_to_keep_it_funTo_get_you_on_like_ahh!Be_careful_amigoShe_talkin’_and_walkin}

Leave a Reply

Your email address will not be published.

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>