CONFidence Teaser CTF- Crypto Writeups

In this blog post, we will discuss solutions of all the crypto challenges from CONFidence Teaser CTF! The crypto challenges were a bit easy and we could solve all of them within 6 hours, so it was quite fun!

More difficult crypto challenges next time please 😉

Thanks for the amazing challenges in all categories and organising this beautiful CTF!

Count me in

Solved by: v3ct0r

Writeup authored by: v3ct0r

This challenge is a customised version of AES-CTR. Here is the challenge script:

import multiprocessing

from Crypto.Cipher import AES

from secret import key, flag

counter = 0
aes = AES.new(key, AES.MODE_ECB)

def chunk(input_data, size):
    return [input_data[i:i + size] for i in range(0, len(input_data), size)]

def xor(*t):
    from functools import reduce
    from operator import xor
    return [reduce(xor, x, 0) for x in zip(*t)]

def xor_string(t1, t2):
    t1 = map(ord, t1)
    t2 = map(ord, t2)
    return "".join(map(chr, xor(t1, t2)))

def pad(data):
    pad_byte = 16 - len(data) % 16
    return data + (chr(pad_byte) * pad_byte)

def worker_function(block):
    global counter
    key_stream = aes.encrypt(pad(str(counter)))
    result = xor_string(block, key_stream)
    counter += 1
    return result

def distribute_work(worker, data_list, processes=8):
    pool = multiprocessing.Pool(processes=processes)
    result = pool.map(worker, data_list)
    pool.close()
    return result

def encrypt_parallel(plaintext, workers_number):
    chunks = chunk(pad(plaintext), 16)
    results = distribute_work(worker_function, chunks, workers_number)
    return "".join(results)

def main():
    plaintext = """The Song of the Count

You know that I am called the Count
Because I really love to count
I could sit and count all day
Sometimes I get carried away
I count slowly, slowly, slowly getting faster
Once I've started counting it's really hard to stop
Faster, faster. It is so exciting!
I could count forever, count until I drop
1! 2! 3! 4!
1-2-3-4, 1-2-3-4,
1-2, i love couning whatever the ammount haha!
1-2-3-4, heyyayayay heyayayay that's the sound of the count
I count the spiders on the wall...
I count the cobwebs in the hall...
I count the candles on the shelf...
When I'm alone, I count myself!
I count slowly, slowly, slowly getting faster
Once I've started counting it's really hard to stop
Faster, faster. It is so exciting!
I could count forever, count until I drop
1! 2! 3! 4
1-2-3-4, 1-2-3-4, 1,
2 I love counting whatever the
ammount! 1-2-3-4 heyayayay heayayay 1-2-3-4
That's the song of the Count!
""" + flag
    encrypted = encrypt_parallel(plaintext, 32)
    print(encrypted.encode("hex"))

if __name__ == '__main__':
    multiprocessing.freeze_support()
    main()

After observing the script carefully, you can see that the each block has been parallelly encrypted using multithreading , but here lies the vulnerebility!

Since multithreading is used, a few set of blocks are encrypted with the same nonce. Here comes the use of the given plaintext, since we have many plaintext and ciphertext block pairs we can recover the encrypted nonce.

It is basically a xor challenge where the encrypted nonces are the keys which when XORed with the plaintext gives us the ciphertext. So basically the part of the flag maybe XORed with the same key block with which some of the previous blocks have been xored. But we don’t which of these is used so we try all of them.

There are two steps involved in solving this challenge:

Step-1: Recovering the key sets from the known plaintext-ciphertext pairs.
You can get that by XORing the pt-ct pairs and dividing it into chunks of 16 since each block is 16.

Step-2: Getting the flag
Find which key set used to xor with the flag. Just try all of them and there is nothing to do but get the flag.

Here is the exploit script:

from Crypto.Cipher import AES
import string

from count import plaintext as pt
ct = open("output.txt").read().decode('hex')

chars = string.ascii_lowercase+string.digits+"{}_"

def chunk(input_data, size):
    return [input_data[i:i + size] for i in range(0, len(input_data), size)]

def xor(a,b):
    from itertools import cycle
    return ''.join(chr(ord(i)^ord(j)) for i,j in zip(a,cycle(b)))

# Possible Keys
k = xor(ct,pt)[:len(pt)]
keys = chunk(k,16)

ctflag = ct[-64:]
flag = ''
for key in set(keys):
    out = chunk(xor(ctflag,key),16)
    for i in out:
        if all(char in chars for char in i[:8]):
            flag+=i
print flag

Running the above script gives out the flag as:
p4{at_the_end_of_the_day_you_can_only_count_on_yourself}!

 

Bro do you even lift

Solved by: v4d3r, s0rc3r3r, v3ct0r, 4lph4

Writeup authored by: v4d3r

This challenge was based on a 4th degree univariate polyomial ring. We are provided with lift.sage and outputs.txt. In lift.sage we have:

flag = int(open('flag.txt','r').read().encode("hex"),16)
ranges = int(log(flag,2))
p = next_prime(ZZ.random_element(2^15, 2^16))
k = 100
N = p^k
d = 5
P. = PolynomialRing(Zmod(N), implementation='NTL')
pol = 0
for c in range(d):
    pol += ZZ.random_element(2^ranges, 2^(ranges+1))*x^c
remainder = pol(flag)
pol = pol - remainder
assert pol(flag) == 0

print(p)
print(pol)

Contents of outputs.txt are:

35671
12172655049735206766902704703038559858384636896299329359049381021748*x^4 + 11349632906292428218038992315252727065628405382223597973250830870345*x^3 + 9188725924715231519926481580171897766710554662167067944757835186451*x^2 + 8640134917502441100824547249422817926745071806483482930174015978801*x + 170423096151399242531943631075016082117474571389010646663163733960337669863762406085472678450206495375341400002076986312777537466715254543510453341546006440265217992449199424909061809647640636052570307868161063402607743165324091856116789213643943407874991700761651741114881108492638404942954408505222152223605412516092742190317989684590782541294253512675164049148557663016927886803673382663921583479090048005883115303905133335418178354255826423404513286728

It is clear from the above snippet that the flag is a root of the following polynomial:

, where

Thus, the challenge was to find the root of this polynomial!

To solve this challenge, we can first find a solution for the given polynomial over  and then use Hensel’s lifting lemma to find a solution for the given polynomial over . Hensel’s lifting lemma states that:

If a polynomial equation has a simple root modulo a prime number p, then this root corresponds to a unique root of the same equation modulo any higher power of p, which can be found by iteratively “lifting” the solution modulo successive powers of p.

Step-1: Finding roots of the polynomial over

p = 35671
k = 100
P. = PolynomialRing(Zmod(p), implementation='NTL')
f = 12172655049735206766902704703038559858384636896299329359049381021748*x^4 + 11349632906292428218038992315252727065628405382223597973250830870345*x^3 + 9188725924715231519926481580171897766710554662167067944757835186451*x^2 + 8640134917502441100824547249422817926745071806483482930174015978801*x + 170423096151399242531943631075016082117474571389010646663163733960337669863762406085472678450206495375341400002076986312777537466715254543510453341546006440265217992449199424909061809647640636052570307868161063402607743165324091856116789213643943407874991700761651741114881108492638404942954408505222152223605412516092742190317989684590782541294253512675164049148557663016927886803673382663921583479090048005883115303905133335418178354255826423404513286728
print f.monic().roots()

Cool! This sage script returned the base solutions as `[27020, 25020]`.

Step-2: Use Hensel’s lifting lemma to find a solution over mod N

We primarily used p4’s Hensel’s lifting implementation in their library crypto-commons. v4d3r tweaked it to make it compatible with sagemath.

from sage.all import *
from Crypto.Util.number import * 

def lift(f, p, k, previous):
    result = []
    df = diff(f)
    for lower_solution in previous:
        dfr = Integer(df(lower_solution))
        fr = Integer(f(lower_solution))
        if dfr % p != 0:
            t = (-(xgcd(dfr, p)[1]) * int(fr / p ** (k - 1))) % p
            result.append(lower_solution + t * p ** (k - 1))
        if dfr % p == 0:
            if fr % p ** k == 0:
                for t in range(0, p):
                    result.append(lower_solution + t * p ** (k - 1))
    return result

def hensel_lifting(f, p, k, base_solution):
    solution = base_solution
    for i in range(2, k + 1):
        solution = lift(f, p, i, solution)
    return solution

if __name__=="__main__":
    #base = [27020,25020]
    base = [27020]
    p = 35671
    k = 100
    N = p^k
    P. = PolynomialRing(Zmod(N), implementation='NTL')
    f = 12172655049735206766902704703038559858384636896299329359049381021748*x^4 + 11349632906292428218038992315252727065628405382223597973250830870345*x^3 + 9188725924715231519926481580171897766710554662167067944757835186451*x^2 + 8640134917502441100824547249422817926745071806483482930174015978801*x + 170423096151399242531943631075016082117474571389010646663163733960337669863762406085472678450206495375341400002076986312777537466715254543510453341546006440265217992449199424909061809647640636052570307868161063402607743165324091856116789213643943407874991700761651741114881108492638404942954408505222152223605412516092742190317989684590782541294253512675164049148557663016927886803673382663921583479090048005883115303905133335418178354255826423404513286728
    solutions = hensel_lifting(f,p,k,base)
    for solution in solutions:
        print long_to_bytes(solution)

Running the above script gave the flag as:

p4{Th4t5_50m3_h34vy_l1ft1n9}

Really Suspicious Acronym

Solved by: s0rc3r3r, v4d3r, nsg99, 4lph4

Write-up authored by: s0rc3r3r

The challenge is based on RSA and we are given the following script:

def bytes_to_long(data):
    return int(data.encode("hex"),16)

def rsa(msg,e,n):
    return pow(bytes_to_long(msg),e,n)

flag = open('flag.txt','r').read()
tmp = randint(2**1023, 2**1024)
e = 65537
p = next_prime(0xDEAD*tmp+randint(2, 2**500))
q = next_prime(0xBEEF*tmp+randint(2, 2**500))
N =  p*q
print('msg1 = '+str(rsa("You can't factor the modulus",e,N)))
print('msg2 = '+str(rsa("If you don't know the modulus!",e,N)))
print('flag = '+str(rsa(flag,e,N)))

We are given ciphertext of two plaintext messages  “You can’t factor the modulus” and  “If you don’t know the modulus!”, and encrypted text of the flag in output.txt:

msg1 = 4249729541274832324831915101850978041491970958978013333892918723306168770472089196478720527554982764987079625218029445015042835412969986610407794962546486526768377464483162272541733624521350257458334912357961557141551376502679112069746250223130120067678503609054343306910481618502449487751467838568736395758064426403381068760701434585433915614901796040740316824283643177505677105619002929103619338876322183416750542848507631412106633630984867562243228659040403724671325236096319784525457674398019860558530212905126133378508676777200538275088387251038714220361173376355185449239483472545370043145325106307606431828449482078191
msg2 = 13075855845498384344820257559893309320125843093107442572680776872299102248743866420640323500087788163238819301260173322187978140866718036292385520509724506487692001245730298675731681509412177547061396861961413760298064385526657135656283464759479388590822600747903100354135682624356454872283852822117199641700847558605700370117557855396952083088645477966782338316017387406733063346986224014837246404581562813312855644424128648363175792786282857154624788625411070173092512834181678732914231669616670515512774709315620233482515821178277673737845032672993814500177126048019814877397547310166915188341668439101769932492677363463422
flag = 1325070956009103489249194637347510588506729608784127511926628895543304940415297099207601498626181915901848862854995077315475674257593360012633818395699000501896896712855638114932274873636706679536094148084825113213348693669110684534612150434985589138003619494080556587882502882245480530148296233019306164832959924719530089539412878605051284492900919153291539285764067215954480046474237129247005910958854570936626494664674014970792183182621261776942952172643573955950074108555363333808330455648256916095619261620286120748266415219259665310637340092503523139379869446053982200858497231506892485419429178671743186148288407233657

Some observations:

1. We are not given the public modulus in this challenge.
2. Factors of the modulus n are derived and there exists a relation between them

Based on the above observations, one can say that the challenge can be solved in two steps:

1. Recover the public modulus using the ciphertext-plaintext pairs
2. Since there exists a relation between factors of n, recover factors based on this and decrypt the ciphertext of the flag.

Step-1: Recovering the modulus

Let the ciphertext of message   be  and ciphertext of message  be .

We can write:

This implies:

Hence,

With the above equation we can recover a multiple of n, where k' is a small number and can be detected simply by brute force. We wrote the following code (in sage, python took longer time on our laptops to calculate since the messages are quite large) to recover n:

from Crypto.Util.number import *
from sage.all import *

c1 = 4249729541274832324831915101850978041491970958978013333892918723306168770472089196478720527554982764987079625218029445015042835412969986610407794962546486526768377464483162272541733624521350257458334912357961557141551376502679112069746250223130120067678503609054343306910481618502449487751467838568736395758064426403381068760701434585433915614901796040740316824283643177505677105619002929103619338876322183416750542848507631412106633630984867562243228659040403724671325236096319784525457674398019860558530212905126133378508676777200538275088387251038714220361173376355185449239483472545370043145325106307606431828449482078191
c2 = 13075855845498384344820257559893309320125843093107442572680776872299102248743866420640323500087788163238819301260173322187978140866718036292385520509724506487692001245730298675731681509412177547061396861961413760298064385526657135656283464759479388590822600747903100354135682624356454872283852822117199641700847558605700370117557855396952083088645477966782338316017387406733063346986224014837246404581562813312855644424128648363175792786282857154624788625411070173092512834181678732914231669616670515512774709315620233482515821178277673737845032672993814500177126048019814877397547310166915188341668439101769932492677363463422
flag = 1325070956009103489249194637347510588506729608784127511926628895543304940415297099207601498626181915901848862854995077315475674257593360012633818395699000501896896712855638114932274873636706679536094148084825113213348693669110684534612150434985589138003619494080556587882502882245480530148296233019306164832959924719530089539412878605051284492900919153291539285764067215954480046474237129247005910958854570936626494664674014970792183182621261776942952172643573955950074108555363333808330455648256916095619261620286120748266415219259665310637340092503523139379869446053982200858497231506892485419429178671743186148288407233657
m1 = bytes_to_long("You can't factor the modulus")
m2 = bytes_to_long("If you don't know the modulus!")
e = 65537

N = GCD(pow(m1, e) - c1, pow(m2, e) - c2)
print N

Coincidentally, GCD gave us the exact value of n. We can verify this by simply encrypting the given messages  and  with our recovered modulus value and given exponent e, and check if they match with their corresponding given ciphertexts  and .

The above code gives out the value of n as:

N = 34825223743402829383680359547814183240817664070909938698674658390374124787235739502688056639022131897715513587903467527066065545399622834534513631867145432553730850980331789931667370903396032758515681278057031496814054828419443822343986117760958186984521716807347123949922837482460532728350223473430713058522361175980521908817215812291272284241848086260180382693014713901303747444753828636575351349026883294939561001468099252543181336195746032718177937417431101756313823635150129601855358558635996348271242920308406268552606733676301725088348399264293936151662467456410825402303921583389167882090767423931762347825907802328053

Now that we have value of `N`, let’s move to the second and final step in solving the challenge!

Step-2: Factoring N using Coppersmith’s Theorem and getting the flag

This step is almost the same as part-3 of Old-School challenge from Meepwn CTF 2018: https://github.com/p4-team/ctf/tree/master/2018-07-13-meepwn-ctf/crypto_old_school#part3

We are given the following relation between p and q:

tmp = randint(2**1023, 2**1024)
e = 65537
p = next_prime(0xDEAD*tmp+randint(2, 2**500))
q = next_prime(0xBEEF*tmp+randint(2, 2**500))
N =  p*q

We can approximate the value of `tmp` and then try to recover `p` and `q` based on the approximation:

We can take the approximate value of tmp as:

With the above approximation, we can calculate the upper bound of one of the factors of N, let’s say q_approx as:

Note: We still don’t have a strong mathematical explanation of why q_approx is   and not , we deduced the formula based on the writeup for Meepwn CTF challenge mentioned earlier. s0rc3r3r discussed it with Shalom (challenge author) about this, but the reason is still not clear; here is an excerpt from IRC:

So if you have a mathematical explanation, feel free to comment! I would love it!

/EONote

Now that we have q_approx, we can use Coppersmith’s Theorem to recover the actual value of q. I wrote the following script for this:

hidden = 500
tmp = isqrt((N)/(0xdead * 0xbeef))
print "tmp: ", tmp
q_approx = 0xbeef*tmp - 2**500
print q_approx

F. = PolynomialRing(Zmod(N), implementation='NTL')
f = x - q_approx

roots = f.small_roots(X=2**hidden, beta=0.1)
for delta in roots:
    print('delta', delta)
    print('q_approx - delta', q_approx-delta)
    q = q_approx-delta
    p = int(N)/int(q)
    d = inverse_mod(65537, (p-1)*(q-1))
    print("d", d)
    decrypted = hex(int(pow(c,d,N)))
    print('flag =', decrypted[2:-1].decode("hex"))

Let us see how the above script works:
We know that q_approx is basically the upper bound for possible value of `q`. To get the actual value we need to subtract a value x from q_approx such that the result becomes a factor of modulus N.
Hence we wrote the script implementing the above idea!

If you want to learn about Coppersmith’s Attack in detail you can refer to this article from Crypton library: https://github.com/ashutosh1206/Crypton/tree/master/RSA-encryption/Attack-Coppersmith

The full script (Make sure you have sagemath installed on your system since this script is written in sagemath):

from Crypto.Util.number import *
from sage.all import *

c1 = 4249729541274832324831915101850978041491970958978013333892918723306168770472089196478720527554982764987079625218029445015042835412969986610407794962546486526768377464483162272541733624521350257458334912357961557141551376502679112069746250223130120067678503609054343306910481618502449487751467838568736395758064426403381068760701434585433915614901796040740316824283643177505677105619002929103619338876322183416750542848507631412106633630984867562243228659040403724671325236096319784525457674398019860558530212905126133378508676777200538275088387251038714220361173376355185449239483472545370043145325106307606431828449482078191
c2 = 13075855845498384344820257559893309320125843093107442572680776872299102248743866420640323500087788163238819301260173322187978140866718036292385520509724506487692001245730298675731681509412177547061396861961413760298064385526657135656283464759479388590822600747903100354135682624356454872283852822117199641700847558605700370117557855396952083088645477966782338316017387406733063346986224014837246404581562813312855644424128648363175792786282857154624788625411070173092512834181678732914231669616670515512774709315620233482515821178277673737845032672993814500177126048019814877397547310166915188341668439101769932492677363463422
flag = 1325070956009103489249194637347510588506729608784127511926628895543304940415297099207601498626181915901848862854995077315475674257593360012633818395699000501896896712855638114932274873636706679536094148084825113213348693669110684534612150434985589138003619494080556587882502882245480530148296233019306164832959924719530089539412878605051284492900919153291539285764067215954480046474237129247005910958854570936626494664674014970792183182621261776942952172643573955950074108555363333808330455648256916095619261620286120748266415219259665310637340092503523139379869446053982200858497231506892485419429178671743186148288407233657
m1 = bytes_to_long("You can't factor the modulus")
m2 = bytes_to_long("If you don't know the modulus!")
e = 65537

N = 34825223743402829383680359547814183240817664070909938698674658390374124787235739502688056639022131897715513587903467527066065545399622834534513631867145432553730850980331789931667370903396032758515681278057031496814054828419443822343986117760958186984521716807347123949922837482460532728350223473430713058522361175980521908817215812291272284241848086260180382693014713901303747444753828636575351349026883294939561001468099252543181336195746032718177937417431101756313823635150129601855358558635996348271242920308406268552606733676301725088348399264293936151662467456410825402303921583389167882090767423931762347825907802328053

c = flag

hidden = 500
tmp = isqrt((N)/(0xdead * 0xbeef))
print "tmp: ", tmp
q_approx = 0xbeef*tmp - 2**500
print q_approx

F. = PolynomialRing(Zmod(N), implementation='NTL')
f = x - q_approx

roots = f.small_roots(X=2**hidden, beta=0.1)
for delta in roots:
    print('delta', delta)
    print('q_approx - delta', q_approx-delta)
    q = q_approx-delta
    p = int(N)/int(q)
    d = inverse_mod(65537, (p-1)*(q-1))
    print("d", d)
    decrypted = hex(int(pow(c,d,N)))
    print('flag =', decrypted[2:-1].decode("hex"))

Running the above script gives us the flag: p4{S3cur1ty_th0ru9h_0b5cur1ty_4t_i7s_fin3s7}

Advertisement