# ASIS CTF’17

## F4 Phantom

‍‍‍nc 66.172.27.77 54979

We get a key-generation function, as seen below.

def gen_pubkey(e, p):
assert gmpy.is_prime(p) != 0
B = bin(p).strip('0b')
k = random.randrange(len(B))
k, l = min(k, len(B) - k), max(k, len(B) - k)
assert k != l
BB = B[:k] + str(int(B[k]) ^ 1) + B[k+1:l] + str(int(B[l]) ^ 1) + B[l+1:]
q = gmpy.next_prime(int(BB, 2))
assert p != q
n = p*q
key = RSA.construct((long(n), long(e)))
pubkey = key.publickey().exportKey("PEM")
return n, p, q, pubkey


So, $pq = p \cdot (p \pm 2^k \pm 2^l + \Delta)$, where $\Delta = \texttt{next\_prime}(p \pm 2^k \pm 2^l) - (p \pm 2^k \pm 2^l)$. The density of primes (well, asymptotically) is $\pi(n) \sim \frac{x}{log x}$, so we expect $\Delta$ to be quite small.

We define $a := p \pm 2^k \pm 2^l$. Now, we solve the following equation $x \cdot (x \pm 2^k \pm 2^l + \Delta) = N \iff x \cdot (x + a) - N = 0 \iff x = \frac{a}{2} \pm \sqrt{\frac{a^2}{4} + N}$

Now, we know that the roots should be numerically close to $p$ and $q$. So, we may simply call $\texttt{next\_prime}$ on them and check if they divide $N$. Note that we need to do this for different hypotheses (different $k$).

import gmpy, base64
from Crypto.PublicKey import RSA

def solve(a):
a2 = a ** 2/4
L = gmpy.sqrt(a2 + N) # L > a/2
C_1 = gmpy.next_prime(-a/2 + L)
if N % C_1 == 0: return C_1
C_2 = gmpy.next_prime(a/2 + L)
if N % C_2 == 0: return C_2
return False

# just some public key
pem_data1 = '''
zl8xJmCe8eEPGNfDVMFgN7Ll4WdRLYE4T8dOvoMb99Cmjhym7Orb/qfP5q/BpTQy
5hr1w5RZVtYMqQ5I+M4qg7E8kkVhGJh/13bNwqEYvV6VNSCK+bgFWVGMelTQam31
Fiq6wsTLbIBCrLie52Cil1584QIEC8rPFw==
'''

pub =  RSA.importKey(base64.b64decode(pem_data1))
N = pub.n
m = (len(bin(N))+1)/2-2
print '[ ] Solving equations...'

for mm in range(m, m+3):
for j in range(2, m/2+1):
k = mm - j
l = j
retval = solve(2**(k-1) + 2**(l-1))
if retval:
q = retval
break
retval = solve(2**(k-1) - 2**(l-1))
if retval:
q = retval
break

p = N / q
print '[+] Found p = {}... and q = {}...'.format(str(p)[:40], str(q)[:40])

λ python solve.py
[ ] Solving equations...
[+] Found p = 1381282812140256921334162381757305071089... and q = 1381282811302268925712750063033928508701...


Now, it turns out that $\text{gcd}(e, (p-1)(q-1)) \neq 1$. We cannot decrypt the message! If we look closely, we see that $\text{gcd}(e, (p-1)) = 1$. Hmm… so, we can decrypt the message $c^d = m \mod p$. And the message is the flag, which is constant. What if we sample two ciphertexts encrypting the same message but under different keys? Yes… so, basically, we have $m \mod p_1$ and $m \mod p_2$. Then, we can combine it using CRT! This is easy!

import gmpy
from Crypto.Util.number import long_to_bytes

enc1 = 63188108518214820361083256140053967663112132356420859206347143811869148973386950682507343981284848159232100220605963292020722612854139075311063776086523677522160515093598202087755508512714885329251980275085813640578839753523295579661559881983237388178475574713319340090857313275483787001349560782781513895950569634984688753665
q1 = 33452043035349425454164058954054458228134102234436666511159820871022348004023966976017694615018111901825497223286811050478588079083387098695346723120647425399335947
p1 = 33452043035349425454164058954054813129854949698738692548175391185736387867969615080539316436404430573352896343366560167202569408949342999951142479436993639588965567
e1 = 3562731839

enc2 = 162331112890791758781057932826106636167735138703054666826574266304486608255768782351247144197937186145526374008317633308191215438756014724244242639042178681790803086016105986729819920057318114565244866632716401408212076926367974085730803964312385570202673351687846963322223962280999264618753873289802828995706526584379102468
q2 = 1381282812140256921334162381757305071089685391539884775199049048751523002134390007428038278188586333291047282664366863789424963612326970767160301759006158962675449
p2 = 1381282811302268925712750063033928508701820008572424411412024462643800411901779755548441592138469189655615818433739872652769585433967353091413641137354055362924329
e2 = 197840663

d1 = gmpy.invert(e1, p1-1)
d2 = gmpy.invert(e2, p2-1)

assert(gmpy.gcd(e1, p1-1) == 1)
assert(gmpy.gcd(e2, p2-1) == 1)

m = (pow(enc1, d1, p1) * p2 * gmpy.invert(p2, p1) + pow(enc2, d2, p2) * p1 * gmpy.invert(p1, p2)) % (p1*p2)
print long_to_bytes(m)


…prints:

********** great job! the flag is: ASIS{Still____We_Can_Solve_Bad_F4!}

Alright!

## A fine OTP server

Connect to OTP generator server, and try to find one OTP.

nc 66.172.27.77 35156

We get the code for generating OTPs:

def gen_otps():
template_phrase = 'Welcome, dear customer, the secret passphrase for today is: '

OTP_1 = template_phrase + gen_passphrase(18)
OTP_2 = template_phrase + gen_passphrase(18)

otp_1 = bytes_to_long(OTP_1)
otp_2 = bytes_to_long(OTP_2)

nbit, e = 2048, 3
privkey = RSA.generate(nbit, e = e)
pubkey  = privkey.publickey().exportKey()
n = getattr(privkey.key, 'n')

r = otp_2 - otp_1
if r < 0:
r = -r
IMP = n - r**(e**2)
if IMP > 0:
c_1 = pow(otp_1, e, n)
c_2 = pow(otp_2, e, n)
return pubkey, OTP_1[-18:], OTP_2[-18:], c_1, c_2


We note that $\texttt{otp\_1}^3 < N$. Because of this, the task is really trivial. We can simply compute the cubic root without taking any modulus into consideration. $\texttt{gmpy2.iroot(arg, 3)}$ can solve this efficiently! This gives us:

ASIS{0f4ae19fefbb44b37f9012b561698d19}

## Secured OTP server

Connect to OTP generator server, and try to find one OTP.
This is secure than first server 🙂

nc 66.172.33.77 12431

This is almost identical to the previous, but the OTP is chosen such that it will overflow the modulus when cubed.

    template_phrase = '*************** Welcome, dear customer, the secret passphrase for today is: '
A = bytes_to_long(template_phrase + '00' * 18)


Note that we can write an OTP as $m = A \cdot 2^k + B$, where $B < 2^k$. So, we have $m^3 = A^3 + 3A^2D + 3AD^2 + D^3$. The observant reader have noticed that if we remove $A^3$, it will not wrap around $N$. Now, we can mod out the terms containing $A$, i.e., find $m - A^3 \mod A$. Now we are back in the scenario of previous challenge… so, we can use the method from before! Hence, $(m - A^3 \bmod A)^{1/3}$. Finally, we get

ASIS{gj____Finally_y0u_have_found_This_is_Franklin-Reiter’s_attack_CongratZ_ZZzZ!_!!!}


## DLP

You should solve a DLP challenge, but how? Of course , you don’t expect us to give you a regular and boring DLP problem!

nc 146.185.143.84 28416

The ciphertext is generated using the following function:

def encrypt(nbit, msg):
msg = bytes_to_long(msg)
p = getPrime(nbit)
q = getPrime(nbit)
n = p*q
s = getPrime(4)
enc = pow(n+1, msg, n**(s+1))
return n, enc


We have that $e = (n+1)^m \mod n^s = n^m + {m \choose {m-1}}n^{m-1} + \cdots + + {m \choose 2}n^2 + {m \choose 1}n + 1$. We can write this as ${m \choose 1}n + 1 + \mathcal{O}(n^2)$. Now, we can eliminate the ordo term by taking $e \mod n^2 = {m \choose 1}n + 1 \iff e - 1 \mod n^2 = mn$. Assuming that $m < n$, we can determine $m$ by simple division. So, $\frac{e - 1 \mod n^2}{n} = m$. In Python, we have that

Turns out this is the case, and, hence, we obtain

ASIS{Congratz_You_are_Discrete_Logarithm_Problem_Solver!!!}

## unsecure ASIS sub-d

ASIS has many insecure sub-domains, but we think they are over HTTPS and attackers can’t leak the private data, what do you think?

So, we get a PCAP. The first thing we do is to extract data binwalk -e a.pcap. This generates a folder with all the certificates used.

Then, we look at the moduli.

#!/bin/bash
FILES=*.crt
for f in $FILES do openssl x509 -inform der -in$f -noout -text -modulus
done


This generates a file with all moduli. Let us try something simple! Common moduli! For each pair, we check if $\text{gcd}(N_i, N_j) \neq 1$. If so, we have found a factor. Turns out two moduli have a common factor, so we can factor each of them and decrypt their traffic:

p1 = 146249784329547545035308340930254364245288876297216562424333141770088412298746469906286182066615379476873056564980833858661100965014105001127214232254190717336849507023311015581633824409415804327604469563409224081177802788427063672849867055266789932844073948974256061777120104371422363305077674127139401263621
q1 = 136417036410264428599995771571898945930186573023163480671956484856375945728848790966971207515506078266840020356163911542099310863126768355608704677724047001480085295885211298435966986319962418547256435839380570361886915753122740558506761054514911316828252552919954185397609637064869903969124281568548845615791

p2 = 159072931658024851342797833315280546154939430450467231353206540935062751955081790412036356161220775514065486129401808837362613958280183385111112210138741783544387138997362535026057272682680165251507521692992632284864412443528183142162915484975972665950649788745756668511286191684172614506875951907023988325767
q2 = 136417036410264428599995771571898945930186573023163480671956484856375945728848790966971207515506078266840020356163911542099310863126768355608704677724047001480085295885211298435966986319962418547256435839380570361886915753122740558506761054514911316828252552919954185397609637064869903969124281568548845615791


We can now generate two PEM-keys

d1 = gmpy.invert(e, (p1 - 1)*(q1 - 1))
key = RSA.construct((long(p1*q1), long(e), long(d1)))
f = open('privkey.pem','w')
f.write(key.exportKey('PEM'))
f.close()


Putting it into Wireshark, we obtain two images:  I totally agree.

## Alice, Bob and Rob

We have developed a miniature of a crypto-system. Can you break it?
We only want to break it, don’t get so hard on our system!

This is McElice PKC. The ciphertexts are generated by splitting each byte in blocks of four bits. The following matrix is used as public key: $G = \begin{pmatrix}1& 1& 0& 0& 0& 1& 1& 0\\ 1& 1& 1& 1& 1& 1& 1& 1\\ 0& 1& 1& 0& 1& 1& 0& 0 \\ 0& 1& 1& 1& 0& 0& 1& 0 \end{pmatrix}$

The ciphertext is generated as $\mathbf{m}G + \mathbf{e}$, which is a function from 4 bits to a byte. $\mathbf{e}$ is an error (or pertubation) vector with only one bit set. This defines a map $f: \mathbb{F}_4 \rightarrow \mathbb{F}_8$. So, each plaintext byte is two ciphertext bytes.

We can first create a set of codewords

P = numpy.matrix([[1, 1, 0, 0, 0, 1, 1, 0], [1, 1, 1, 1, 1, 1, 1, 1], [0, 1, 1, 0, 1, 1, 0, 0],[0, 1, 1, 1, 0, 0, 1, 0]])
image = {} # set of codewords
for i in range(0, 2**4):
C = (numpy.array([int(b) for b in (bin(i))[2:].zfill(4)]) * P % 2).tolist()
image[int(''.join([str(c) for c in C]), 2)] = i


Then, go through each symbol in the ciphertext, flip all possible bits (corresponding to zeroing out $\mathbf{e}$) and perform lookup in the set of codewords $P$ (compute the intersection between the Hamming ball of the ciperhext block and $P$).

f = open('flag.enc','r')
out = ''
for i in xrange(18730/2):
j = ord(blocks)
C1 = 0
C2 = 0
for i in range(0, 8):
if j ^ 2**i in image:
C1 = image[j ^ 2**i] << 4
j = ord(blocks)
for i in range(0, 8):
if j ^ 2**i in image:
C2 = image[j ^ 2**i]
out += chr(C1+C2)
f=open('decrypted','w')
f.write(out)


Turns out it is a PNG: 