SharifCTF 7 – Unterscheide

This was an unusual sort of crypto challenge, and it probably gave us more trouble than it should have (partially because we failed at understanding an assert statement in the code; oops!).

In this challenge, they give us the python implementation of an algorithm that encrypts the flag as follows:

#!/usr/bin/python

import gmpy
import random, os
from Crypto.Util.number import *
from Crypto.Cipher import AES

from secret import flag, q, p1, p2, h

assert (gmpy.is_prime(q) == 0) + (q-1) % p1 + (q-1) % p2 + (p2 - p1 > 10**8) + (pow(h, 1023*p1*p2, q) == 1) == 0

key = os.urandom(128)
IV = key[16:32]
mode = AES.MODE_CBC
aes = AES.new(key[:16], mode, IV=IV)
flag_enc = aes.encrypt(flag)

rand = bytes_to_long(key)
benc = bin(bytes_to_long(flag_enc))[2:]

A = []
for b in benc:
	try:
		r = gmpy.next_prime(random.randint(3, q-2))
		s = gmpy.invert(r, q-1)
		if b == '0':
			a = pow(h, r*r*p1, q)*q*rand + rand + 1
		else:
			a = pow(h, s*s*p2, q)*q*rand + rand + 1
		A.append(str(int(a)))
		rand += 1
	except:
		print 'Failed'

fenc = open('enc.txt', 'w')
fenc.write('\n'.join(A))
fenc.close()
  1. Generates a random key R, and encrypts the flag f via AES using this key (and a similarly random IV, also part of R) to get the encrypted flag f_{enc}.
  2. The encryption algorithm also has access to a secret prime q; we are told in the assertion that the totient \phi(q) = q-1 of q has two prime factors p_1 and p_2, who are within 10^8 of each other (we originally misread this assertion as asserting that they are at least 10^8 far away from each other; this cost us some time.). The algorithm is also given an element h of \mathbb{Z}/q\mathbb{Z} whose order is not divisible by p_1 or p_2.
  3. For the ith bit b_i in f_{enc}, output a number of the form (h^{r^2p_1} \bmod q)q(R+i) + (R+i) + 1 if b=0 and a number of the form (h^{s^2p_2} \bmod q)q(R+i) + (R+i) + 1 if b=1, where r and s are a randomly generated prime and its inverse (really, all that matters is that they are relatively prime to p_1 and p_2, though). Let m_i equal the power of h modulo q generated in this step.

To break this cryptosystem, we’ll try to recover the many parameters one by one.

  1. To start, note that a_{i} - a_{i-1} - 1 = (k_i(R+i) - k_{i-1}(R+(i-1))q is divisible by q. Therefore, q divides (and probably equals) the GCD of all of these numbers. We can check that we have the correct q by checking that q is prime.
  2. Next, note that if we have q, we can recover R modulo q by computing (a_0 - 1) \bmod q. It turns out that R < q, so this is the true value of R; we can check this by verifying that (R+i) divides a_i - 1 for all i.
  3. To find p_1 and p_2, we first factor out all small primes from q-1; it turns out the only small prime dividing q-1 is 2, and in fact q = 2p_1p_2 + 1. We are left with a semiprime whose two factors p_1 and p_2 are within 10^8 of each other; we can factor this and retrieve these primes by doing trial division starting at the integer square root of this semiprime.
  4. Finally, instead of finding h (which would require solving some tricky discrete log problem), we will directly compute which of the two cases a_i was generated in via the following observation; if b_i = 0 and m_i = h^{r^2p_1} \bmod q, then m_i^{2p_2} \equiv h^{r^2\phi(q)} \equiv 1 \bmod q; likewise, if b_i = 1, then m_i^{2p_1} \equiv h^{s^2\phi(q)} \equiv 1 \bmod q (by Fermat’s little theorem). We can therefore compute b_i by raising m_i to both of these powers modulo q and seeing which computation results in 1. Note that we don’t know which of p_1 or p_2 was originally which, so we may have to invert the bits b_i that we get.
  5. From the b_is and R, we can decrypt the AES encoded flag, and obtain the original flag.

Here is some python code implementing this solution:

from Crypto.Util.number import *
from Crypto.Cipher import AES

def isqrt(n):
    x = n
    y = (x + 1) // 2
    while y < x:
        x = y
        y = (x + n // x) // 2
    return x

A = map(int, [line for line in open('enc.txt')])

# find q

qmults = [A[i]-A[i-1]-1 for i in xrange(1, len(A))]
q = qmults[0]
for qmult in qmults[1:]:
    q = GCD(q, qmult)

assert isPrime(q)

# find initial value of rand
rand = A[0]%q - 1
assert all([(A[i]-1)%(rand+i) == 0 for i in xrange(len(A))])

# find p1 and p2
semip = (q-1)/2   # turns out phi(q) has no small prime factors besides 2

ind = 1
st = isqrt(semip)
while ind < 10**8:
    if semip%(st+ind) == 0:
        p1, p2 = st+ind, semip/(st+ind)
        ind = 10**8
    ind += 1

# distinguish b=0 case from b=1 case
modpows = [(a-rand-i-1)/(q*(rand+i)) for i, a in enumerate(A)]
def get_bit(mpow):
    if pow(mpow, 2*p1, q) == 1:
        return 0
    elif pow(mpow, 2*p2, q) == 1:
        return 1
    else:
        assert False

benc = [get_bit(mpow) for mpow in modpows]

# decrypt everything
lenc = sum([b*(2**i) for i, b in enumerate(reversed(benc))])
flag_enc = long_to_bytes(lenc)

key = long_to_bytes(rand)
aes = AES.new(key[:16], AES.MODE_CBC, IV=key[16:32])
flag_dec = aes.decrypt(flag_enc)

print flag_dec
# ** SharifCTF{10ED2D76BCC417D9C48BE67F6790AF70}**
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s