ISITDTU 2019 Quals CTF Writeups

I had a short look at some challenges from ISITDTU CTF (2019 quals) over the weekend and managed to solve two crypto challs.

Challenges:

Crypto
- decrypt to me
- Easy RSA 2

decrypt to me

Crypto - 395 points (solved)

decrypt to me?????

import binascii
def generate_prg_bit(n):
    state = n
    while True:
        last_bit = state & 1
        yield last_bit
        middle_bit = state >> len(bin(n)[2:])//2 & 1
        state = (state >> 1) | ((last_bit ^ middle_bit) << (len(bin(n)[2:])-1))
flag = '###########'
enc = "OKQI+f9R+tHEJJGcfko7Ahy2AuL9c8hgtYT2k9Ig0QyXUvsj1B9VIGUZVPAP2EVD8VmJBZbF9e17"
flag_bin_text = bin(int(binascii.hexlify(flag), 16))[2:]
prg =  generate_prg_bit(len(flag_bin_text))
ctext = []
flag_bits = [int(i) for i in flag_bin_text]
for i in range(len(flag_bits)):
    ctext.append(flag_bits[i] ^ next(prg))  
ciphertext = '0b' + ''.join(map(str, ctext))
n = int(ciphertext, 2)
print binascii.unhexlify('%x' % n).encode('base64')

Solution

We are given a python program that uses a pseudorandom generator to XOR each bit of the flag with to give us the encrypted flag enc.

The first thing we take note of is that we don't need to understand how the prg works at all. Since it is given to us, we just need to use it to XOR the ciphertext since $(x \oplus y) \oplus y = x$

The second important thing to notice is that the seed being used for the prg is len(flag_bits)), a value which is very feasible to brute force.

With this knowledge, all that's left is implementation:

import binascii
def generate_prg_bit(n):
    state = n
    while True:
        last_bit = state & 1
        yield last_bit
        middle_bit = state >> len(bin(n)[2:])//2 & 1
        state = (state >> 1) | ((last_bit ^ middle_bit) << (len(bin(n)[2:])-1))
enc = "OKQI+f9R+tHEJJGcfko7Ahy2AuL9c8hgtYT2k9Ig0QyXUvsj1B9VIGUZVPAP2EVD8VmJBZbF9e17"
ctext = '0' + bin(int(binascii.hexlify(enc.decode('base64')),16))[2:]
for k in range(7, 1000, 8):
    try:
        prg = generate_prg_bit(k)
        f = ''
        cbits = [int(i) for i in ctext]
        for i in range(len(cbits)):
            f += str(cbits[i] ^ next(prg))
        f = binascii.unhexlify(hex(int(f,2))[2:-1])
        if 'ISITDTU' in f:
            print f, k
            break
    except:
        pass

Also note that we prepend '0' to the ctext variable after reversing the encodings done by the encryption script. This is because bin(n, 2)[2:] will not start with a '0'. We could have also set the script to run through all possible flag lengths, but since the seed is the length of the binary representation of the text, we know it will be of the form $7 + 8n$ since the first letter of the flag is I which is equivalent to 10010010 (7 bits).

Running the script prints the flag.

Flag: ISITDTU{Encrypt_X0r_N0t_Us3_Pseud0_Rand0m_Generat0r!!!!!}

Easy RSA 2

Crypto - 919 points (solved)

Let's continue with RSA

from Crypto.Util.number import *
import gmpy2

flag = '##################################'
p1 = getPrime(512)
p2 = gmpy2.next_prime(p1)
q1 = getPrime(512)
q2 = gmpy2.next_prime(q1)
n = p1*p2*q1*q2
e = 65537
phi = (p1-1)*(p2-1)*(q1-1)*(q2-1)
d = gmpy2.invert(e,phi)
c = pow(bytes_to_long(flag),e,n)

print pow(p1+q2,65537,n)
#5043622010330564722783560796388733110223192234657313797979729183216316602247790170027393145104828283812158304519218370476380897023249898720267053051908498011845198383126598688185743313040451851234309071530873683667360872515868401870834371902623509762498919172464493397284930232415029297203698778851121422456149280629701148108649396642433199634388011535777204188207597427548981195309015900421249473588077922607729093939587454170211363784480831197764238579460361668878037335596700513382133341370374840639374005225742007557272153800433699784092511039693877686425832957477808359462507401596842526527374816943302475357302
print pow(p2+q1,65537,n)
#7919283184559406259028604751155413696993375814336862337694645459367829841130544291770103966362177145582007048754925168845793555136985754996486596987205043932984314934297789456823769422776642272151478021108135062833657996366160688598742804847633068533451034898357435150319123770512604358033881809960916484049603490477616900480883862825416570459592254659007024761917196293369565486538943942938968226701375668351560376904094935919442322484791587819687743780031411339960372463937311578960714219580981945254129150844798674023932645363519148439092971133029751088847668041720574694350298717079140377388740434213791727288722
print n 
#8573641536164485111081609341110540574423426701587222458588002464807917555910942077276167528046769327390058096169685188870928286845342631974847171845103806710768418462668311621275704636581042137915505959767806384415314024549489538717607173007829067492516776714817262226691787436227002924225311861164296655909746846329870548266285498682510415418053656271623482202491805513797215793596385014264449282551352796096361524482384994633912515104414237252657058698433260597636367614328512751722615849959987780969423318207123668118325176544879335267439096589035064596631756303300860315257404427016819145298919974287174103934503
print c 
#8436043641135865531308468859210199431445831063674810351906331674115825605849862045115409554309732867926457428348729196827592921108183774070414343257409618631078896543782150761081732376735501920417229787663210936174854000594130785353102718054331606096192133481536724402629697019651921188121029927710787682993814748802295545306899075962041017278877203965796981792702098381465051289581518257202127401748725944229037078896857591660248467597356051123218945757343652461844056927461929195427880969904210166880623689090977714615839624798930450630919330253477634839161931755642681718034910946900928731231093352169252474939674

Solution

This was an interesting RSA problem based around the modulus $n$ having multiple prime factors. The things that stand out immediately are the ways the primes p2 and q2 are generated. Since p2 is the next prime after p1 and q2 is the next prime after q1 we can write them as such:

\begin{aligned} p_2 &= p_1 + \epsilon \cr q_2 &= q_1 + \delta \end{aligned}

For small integers $\epsilon$ and $\delta$

From this, we can further observe that $p_1q_2 - p_2q_1$ will be small since:

\begin{aligned} p_1q_2 - p_2q_1 &= p_1(q_1 + \delta) - (p_1 + \epsilon)q_1 \cr &= p_1q_1 + p_1\delta - p_1q_1 - q_1\epsilon \cr &= p_1\delta - q_1\epsilon \end{aligned}

Thus, $n$ can be easily factorised into the two factors $p_1q_2$ and $p_2q_1$ . We can use Alpertron's Integer Factorization Calculator to do this for us in seconds. Then we get:

n1 = 92593960581478990492272892082797582837598460722110672289472622026362327649808629839901870926342611079306340852878894165246912369940368199994436453135377198629507140256023102013131493810077402487620597574150419252484604398426042348936643985371724093575122287222535733709825807203222224632574777263054682547849
n2 = 92593960581478990492272892082797582837598460722110672289472622026362327649808629839901870926342611079306340852878894165246912369940368199994436453135375408481531310003733935540422655297910944762679239039783193372674051452613244254750117673971732027355424665752849172881712190463569600293779394868475158854447

with n1 = p1*q2 and n2 = p2*q1.

From these two equations, it turns out we can derive a simple quadratic equation in terms of $\epsilon$ , $\delta$ , $n_1$ and $n_2$ to solve for any one of $p_1$ , $p_2$ , $q_1$ or $q_2$ :

\begin{aligned} n_1 &= p_1q_2 \cr &= p_1(q_1 + \delta) \cr \implies p_1 &= \frac{n_1}{q_1 + \delta} \end{aligned}

\begin{aligned} n_2 &= q_1p_2 \cr &= q_1(p_1 + \epsilon) \cr \implies p_1 &= \frac{n_2 - q_1\epsilon}{q_1} \end{aligned}

Combining these two results:

\begin{aligned} \frac{n_2-q_1\epsilon}{q_1} = \frac{n_1}{q_1+\delta} \cr \implies (n_2-q_1\epsilon)(q_1+\delta) = n_1q_1 \cr \implies n_2q_1 + \delta n_2 - q_1^2 \epsilon - q_1 \epsilon \delta = n_1q_1 \cr \implies q_1^2 \epsilon + q_1(\epsilon \delta+n_1-n_2) - \delta n_2 = 0 \end{aligned}

Now all that's left is to bruteforce solve for $q_1$ with small $\epsilon$ and $\delta$ . We should be able to comfortably find a solution for $(\epsilon , \delta) \in \{(x, y) \mid 0 \leq x \leq 5000, 0 \leq y \leq 5000\}$ . We should also note that we require $q_1$ to be prime. Script to solve for $q_1$ :

n1 = 92593960581478990492272892082797582837598460722110672289472622026362327649808629839901870926342611079306340852878894165246912369940368199994436453135377198629507140256023102013131493810077402487620597574150419252484604398426042348936643985371724093575122287222535733709825807203222224632574777263054682547849
n2 = 92593960581478990492272892082797582837598460722110672289472622026362327649808629839901870926342611079306340852878894165246912369940368199994436453135375408481531310003733935540422655297910944762679239039783193372674051452613244254750117673971732027355424665752849172881712190463569600293779394868475158854447

from gmpy2 import iroot
from Crypto.Util.number import isPrime

def quadratic(a, b, c):
    try:
        (d, _) = iroot(b*b - (4*a*c),2)
        return ((-b-d)//(2*a), (-b+d)//(2*a))
    except:
        return 0

for (e, d) in ((e, d) for e in range(1, 5000) for d in range(1, 5000)):
    q1 = quadratic(e, e*d+n1-n2, -d*n2)
    if q1 != 0:
        q1 = q1[1]
    res = q1*q1*e + q1*(e*d+n1-n2)-d*n2
    if res == 0 and isPrime(q1):
        print(q1, e, d)

Which after a couple of seconds after being executed, prints: 9171763103475238155920017905180080637957026348805819229558633463083231168099582814700421044911191638619215776932495855800737116252367554545053545527516011 386 528 which gives us the value for q1.

Using this, we can calculate the rest of the primes that make up n and proceed to decrypt RSA as usual.

from Crypto.Util.number import inverse, long_to_bytes

c = 8436043641135865531308468859210199431445831063674810351906331674115825605849862045115409554309732867926457428348729196827592921108183774070414343257409618631078896543782150761081732376735501920417229787663210936174854000594130785353102718054331606096192133481536724402629697019651921188121029927710787682993814748802295545306899075962041017278877203965796981792702098381465051289581518257202127401748725944229037078896857591660248467597356051123218945757343652461844056927461929195427880969904210166880623689090977714615839624798930450630919330253477634839161931755642681718034910946900928731231093352169252474939674
n1 = 92593960581478990492272892082797582837598460722110672289472622026362327649808629839901870926342611079306340852878894165246912369940368199994436453135377198629507140256023102013131493810077402487620597574150419252484604398426042348936643985371724093575122287222535733709825807203222224632574777263054682547849
n2 = 92593960581478990492272892082797582837598460722110672289472622026362327649808629839901870926342611079306340852878894165246912369940368199994436453135375408481531310003733935540422655297910944762679239039783193372674051452613244254750117673971732027355424665752849172881712190463569600293779394868475158854447
q1 = 9171763103475238155920017905180080637957026348805819229558633463083231168099582814700421044911191638619215776932495855800737116252367554545053545527516011
epsilon = 386
delta = 528
q2 = q1 + delta
p1 = n1//q2
p2 = p1 + epsilon
n = n1*n2
phi = (p1-1)*(p2-1)*(q1-1)*(q2-1)
d = inverse(0x10001, phi)
m = pow(c, d, n)
print(long_to_bytes(m).decode())

Which executing, prints the flag.

Flag: ISITDTU{C0ngratu1ati0ns_Attack_RSA_Multi_prim3!!!!}