May 27

CONFidence CTF 2015 – RSA2 (Crypto 500)

Find the flag
data

Summary: cube attack + recover python’s MersenneTwister state + leak 320/520 LSBs of one of the primes

In the second part of the challenge, we have this code:

def generate_40_bytes_random_number():
   return int(open('/dev/urandom').read(80).encode('hex'), 16)
 
def generate_random_number_bytes(n):
   res = 0
   while res < 2**(8*n):
     res += generate_40_bytes_random_number()
     res *= 2**(40*8)
   return res
 
def get_prime(n):
  while (not check_prime(n)) or (((n-1) % 3) == 0):
    n += random.getrandbits(512)
  return n
 
r = generate_random_number_bytes(1024)
p = get_prime(r % (2**512))
q = get_prime((r >> 512) % (2**512))
 
n = p*q
 
open('out/n1','w').write(str(n))
e=3
 
flag_index = random.getrandbits(10)
 
for i in range(0, 1024):
   if i <> flag_index:
     encryptedFlag = pow(random.getrandbits(32), e, n)
     open('out/flag'+str(i),'w').write(str(encryptedFlag))
r = generate_random_number_bytes(1024)
p = get_prime(r % (2**512))
q = get_prime((r >> 512) % (2**512))
 
n = p*q
 
open('out/n2','w').write(str(n))
e=3
 
encryptedFlag = pow(FLAG, e, n)
open('out/flag'+str(flag_index),'w').write(str(encryptedFlag))

Note that generate_random_number_bytes uses secure random generator, while get_prime uses standard Python’s MersenneTwister. Also note implementation bug in generate_random_number_bytes: 320 LSBs of the result are always zero. This means one of the primes will have 320 LSBs from MT random.

Also 1023 MT random values are given, so we can easily recover the state and predict 320 LSBs of one of the primes. This is enough to factor modulus.

The first stage is to recover the MT random state. Note that due to small public exponent (e=3) and small 32-bit values we can recover them by simply extracting cube root over integers. Script for MersenneTwister::untemper

#!/usr/bin/env python
#-*- coding:utf-8 -*-
 
import gmpy
import random
from mt import untemper
 
n1 = int(open("out/n1").read())
 
values = []
for i in xrange(1024):
    c = int(open("out/flag%d" % i).read())
    r, is_cube = gmpy.root(c, 3)
    if not is_cube:
        print "secret index:", i
        continue
    values.append(int(r))
 
mt_state = tuple(map(untemper, values[:624]) + [0])
random.setstate((3, mt_state, None))
 
for i in xrange(1023):
    r = random.getrandbits(32)
    assert r == values[i], "Fail 1"
 
predicted = [random.getrandbits(512) for _ in xrange(5000)]
 
open("out/predicted", "w").write(str(predicted))

The script found the secret index: 826. Now we can predict 320 LSBs of the prime. Actually we don’t know how many times a random number was generated in get_prime, but the experiments show that it’s usually less than 3000 so we can check them all.

To factor the modulus given LSBs we can use the Coppersmith’s method for finding small roots of polynomials as described in the paper by Boneh-Durfee-Frankel. Here’s the outline:

Assume we know t and r such that p = rx + t. In our case r is 2320. We multiply both sides by inverse of r mod N: r-1p = x + r-1t (mod N). We see that x is a small root of polynomial x + r-1t modulo p and so we can compute it with the Coppersmith’s method. Here’s the code (Sage):

from sage.all import *
 
N = int(open("out/n2").read())
C = int(open("out/flag826").read())
predicted = eval(open("out/predicted").read())
 
PR.<x> = PolynomialRing(Zmod(N))
 
mod = 1 << 320
imod = inverse_mod(mod, N)
t = 0
for i, rnd in enumerate(predicted):
    t += rnd
    t %= mod
 
    f = x + t * imod
    roots = f.small_roots(X=2**(540-320), beta=0.4)
    print "#%d:" % i, roots
    if roots:
        root = int(roots[0])
        kq = root + t * imod
        q = gcd(N, kq)
        assert q != 1, "Fail"
        assert q != N, "Fail"
        p = N / q
        d = inverse_mod(3, (p - 1) * (q - 1))
        msg = pow(C, d, N)
        # convert to str
        h = hex(int(msg))[2:].rstrip("L")
        h = "0" * (len(h) % 2) + h
        print `h.decode("hex")`

On the 151st iteration the flag is revealed: DrgnS{ThisFlagMustBeEnteredVerbally|W_Szczebrzeszynie_chrzaszcz_brzmi_w_trzcinie_I_Szczebrzeszyn_z_tego_slynie}

hellman

3 comments

2 pings

  1. Привет!

    Мы (open-sec.ru) готовим подкаст про CTF. Не хотите принять участие? Несколько вопросов по скайпу, много времени не займет.
    Если интересно, мой скайп: darklen_skype

    Надеюсь на ваше участие!
    Андрей

    • dekhi on April 4, 2016 at 20:30
    • #
    • Reply

    How do you know that roots = f.small_roots(X=2**(540-320), beta=0.4)? I try different number but it did not get the result/

    1. Sage’s manual has description of those parameters. But I remember that I had to play with those parameters on my own values until it worked.

  1. […] [0] http://mslc.ctf.su/wp/confidence-ctf-2015-rsa2-crypto-500/ [1] http://en.wikipedia.org/wiki/Least_significant_bit [2] […]

  2. […] and it is able to recover the state of the Python random generator with 624 32-bit integers. See this link for […]

Leave a Reply

Your email address will not be published.