UTCTF 2024 writeup
RSA-256
RSA-256 Description:
1
Based on the military-grade encryption offered by AES-256, RSA-256 will usher in a new era of cutting-edge security... or at least, better security than RSA-128.
Challenge code:
1
2
3
N = 77483692467084448965814418730866278616923517800664484047176015901835675610073
e = 65537
c = 11711610210897103123119971051169511511195828365955053549510511595100101100125
This was a really simple RSA challenge. By it’s name and taking a look at the size of N, we can see that N is not that big (it’s only 256 bits long!) You can check it that way:
1
N.bit_length()
Which returns us 256, the size in bits. An alternative to solve it is by factoring N and finding it’s factors. Another one, maybe simpler, is to look at the number on a database and check if we have the values there.
There it is :)
1
2
3
4
5
6
p = 1025252665848145091840062845209085931
q = 75575216771551332467177108987001026743883
phi = (p-1)*(q-1)
d = pow(e, -1, phi)
m = pow(c, d, N)
print(int.to_bytes(m, 32))
Then we find the flag: utflag{just_send_plaintext}
Beginner: Anti-dcode.fr
Beginner: Anti-dcode.fr Description:
1
2
3
4
I've heard that everyone just uses dcode.fr to solve all of their crypto problems. Shameful, really.
This is really just a basic Caesar cipher, with a few extra random characters on either side of the flag. Dcode can handle that, right? >:)
The '{', '}', and '_' characters aren't part of the Caesar cipher, just a-z. As a reminder, all flags start with "utflag{".
The file is huge and it contais more than 250,000 characters. So I won’t be able to put it here. To solve it, I looked for a website that works with Caesar ciphers. I used: https://cryptii.com/pipes/caesar-cipher. But first, we need to save the complete text on the clipboard. If you are using Linux you can try the following command:
1
cat text.txt | xclip -selection c
Finally, with a shift of 18, we can find the flag.
(I looked for the flag at every shift using Ctrl+F)
We then find the flag utflag{rip_dcode}. Very simple :)
numbers go brrr
numbers go brrr Description:
1
I wrote an amazing encryption service. It is definitely flawless, so I'll encrypt the flag and give it to you.
Challenge code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#!/usr/bin/env python3
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
import time
seed = int(time.time() * 1000) % (10 ** 6)
def get_random_number():
global seed
seed = int(str(seed * seed).zfill(12)[3:9])
return seed
def encrypt(message):
key = b''
for i in range(8):
key += (get_random_number() % (2 ** 16)).to_bytes(2, 'big')
cipher = AES.new(key, AES.MODE_ECB)
ciphertext = cipher.encrypt(pad(message, AES.block_size))
return ciphertext.hex()
print("Thanks for using our encryption service! To get the encrypted flag, type 1. To encrypt a message, type 2.")
while True:
print("What would you like to do (1 - get encrypted flag, 2 - encrypt a message)?")
user_input = int(input())
if(user_input == 1):
break
print("What is your message?")
message = input()
print("Here is your encrypted message:", encrypt(message.encode()))
flag = open('./src/flag.txt', 'r').read()
print("Here is the encrypted flag:", encrypt(flag.encode()))
Analyzing the code, we can see that it generates a seed according to the current time and generates an “random” key for an AES scheme. What we need to remember here is that AES is a symmetric-key algorithm. That means that the key used to encrypt is the same used for decrypting. We can get the flag if we find the public key.
But how do we find it?
Take a closer look at how the key is generated:
1
2
3
4
5
6
7
def encrypt(message):
key = b''
for i in range(8):
key += (get_random_number() % (2 ** 16)).to_bytes(2, 'big')
cipher = AES.new(key, AES.MODE_ECB)
ciphertext = cipher.encrypt(pad(message, AES.block_size))
return ciphertext.hex()
Basically, random numbers are generated using the get_random_number function. The number is then calculated (mod 2^16) and concatenated to the key. Now let’s take a look at the function get_random_number:
1
2
3
4
5
seed = int(time.time() * 1000) % (10 ** 6)
def get_random_number():
global seed
seed = int(str(seed * seed).zfill(12)[3:9])
return seed
The function uses the global variable seed and do some operations. What we need to notice here is that, having the generated seed, it’s really easy to calculate the “random numbers” generated by the function.
The seed is calculated based at the time on which the program is runned. On python, time.time() returns a float with a few decimal places of precision, which is something the chall explores. What happens here is that the challenge is multiplying time.time() by 1000. That means the milliseconds are being considered on the number. After thinking for a while on how to consider the milliseconds on my solve, a friend suggested using bruteforce to find the decimal places. There are only 10^3 possibilities, so it should take only a few moments. That’s what I ended up doing:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#!/usr/bin/env python3
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad, unpad
import time
from pwn import *
sh = remote('betta.utctf.live', 7356)
current_time = time.time()
seed = (int(current_time) * 1000) % (10 ** 6)
def get_random_number():
global seed
seed = int(str(seed * seed).zfill(12)[3:9])
return seed
def decrypt(ciphertext_hex, key):
#key = b''
#for i in range(8):
# key += (get_random_number_decrypt(seed) % (2 ** 16)).to_bytes(2, 'big')
cipher = AES.new(key, AES.MODE_ECB)
ciphertext = bytes.fromhex(ciphertext_hex)
decrypted_message = unpad(cipher.decrypt(ciphertext), AES.block_size)
return decrypted_message.decode('utf-8')
sh.recvuntil(b'?')
sh.sendline(b'1')
sh.recvuntil(b'Here is the encrypted flag: ')
encrypted_flag = sh.recvline().decode().strip()
print(f"Encrypted flag is: {encrypted_flag}")
for i in range(1, 1000):
try:
key = b''
for j in range(8):
key += (get_random_number() % (2 ** 16)).to_bytes(2, 'big')
decrypt(encrypted_flag, key)
except ValueError:
print(f"{i} did not work")
seed = ((int(current_time) * 1000) + i) % (10 ** 6)
continue
print(decrypt(encrypted_flag, key))
break
sh.interactive()
Bits and pieces
Bits and pieces Description:
1
2
3
I really really like RSA, so implemented it myself <3.
A two parter.
Challenge code:
1
2
3
4
5
6
7
8
9
10
11
n1= 16895844090302140592659203092326754397916615877156418083775983326567262857434286784352755691231372524046947817027609871339779052340298851455825343914565349651333283551138205456284824077873043013595313773956794816682958706482754685120090750397747015038669047713101397337825418638859770626618854997324831793483659910322937454178396049671348919161991562332828398316094938835561259917841140366936226953293604869404280861112141284704018480497443189808649594222983536682286615023646284397886256209485789545675225329069539408667982428192470430204799653602931007107335558965120815430420898506688511671241705574335613090682013
e1= 65537
c1= 7818321254750334008379589501292325137682074322887683915464861106561934924365660251934320703022566522347141167914364318838415147127470950035180892461318743733126352087505518644388733527228841614726465965063829798897019439281915857574681062185664885100301873341937972872093168047018772766147350521571412432577721606426701002748739547026207569446359265024200993747841661884692928926039185964274224841237045619928248330951699007619244530879692563852129885323775823816451787955743942968401187507702618237082254283484203161006940664144806744142758756632646039371103714891470816121641325719797534020540250766889785919814382
n2= 22160567763948492895090996477047180485455524932702696697570991168736807463988465318899280678030104758714228331712868417831523511943197686617200545714707332594532611440360591874484774459472586464202240208125663048882939144024375040954148333792401257005790372881106262295967972148685076689432551379850079201234407868804450612865472429316169948404048708078383285810578598637431494164050174843806035033795105585543061957794162099125273596995686952118842090801867908842775373362066408634559153339824637727686109642585264413233583449179272399592842009933883647300090091041520319428330663770540635256486617825262149407200317
e2= 65537
c2= 19690520754051173647211685164072637555800784045910293368304706863370317909953687036313142136905145035923461684882237012444470624603324950525342723531350867347220681870482876998144413576696234307889695564386378507641438147676387327512816972488162619290220067572175960616418052216207456516160477378246666363877325851823689429475469383672825775159901117234555363911938490115559955086071530659273866145507400856136591391884526718884267990093630051614232280554396776513566245029154917966361698708629039129727327128483243363394841238956869151344974086425362274696045998136718784402364220587942046822063205137520791363319144
n3= 30411521910612406343993844830038303042143033746292579505901870953143975096282414718336718528037226099433670922614061664943892535514165683437199134278311973454116349060301041910849566746140890727885805721657086881479617492719586633881232556353366139554061188176830768575643015098049227964483233358203790768451798571704097416317067159175992894745746804122229684121275771877235870287805477152050742436672871552080666302532175003523693101768152753770024596485981429603734379784791055870925138803002395176578318147445903935688821423158926063921552282638439035914577171715576836189246536239295484699682522744627111615899081
e3= 65537
c3= 17407076170882273876432597038388758264230617761068651657734759714156681119134231664293550430901872572856333330745780794113236587515588367725879684954488698153571665447141528395185542787913364717776209909588729447283115651585815847333568874548696816813748100515388820080812467785181990042664564706242879424162602753729028187519433639583471983065246575409341038859576101783940398158000236250734758549527625716150775997198493235465480875148169558815498752869321570202908633179473348243670372581519248414555681834596365572626822309814663046580083035403339576751500705695598043247593357230327746709126221695232509039271637
Taking a quick look at the code, the most immediate thing that came to mind was to use a broadcast attack. We take the values of n and c, put them on an array, calculate the Chinese Remainder Theorem and then take it’s root. However, that doesn’t quite work:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
sage: ns = [n1, n2, n3]
sage: cs = [c1, c2, c3]
sage: crt(cs, ns)
-----------------------------------------------------------------------
ValueError Traceback (most recent call last)
Cell In[5], line 1
----> 1 crt(cs, ns)
File /usr/lib/python3.11/site-packages/sage/arith/misc.py:3450, in crt(a, b, m, n)
3329 r"""
3330 Return a solution to a Chinese Remainder Theorem problem.
3331
(...)
3447 58
3448 """
3449 if isinstance(a, list):
-> 3450 return CRT_list(a, b)
3452 try:
3453 f = (b-a).quo_rem
File /usr/lib/python3.11/site-packages/sage/arith/misc.py:3566, in CRT_list(values, moduli)
3564 vs, ms = values[::2], moduli[::2]
3565 for i, (v, m) in enumerate(zip(values[1::2], moduli[1::2])):
-> 3566 vs[i] = CRT(vs[i], v, ms[i], m)
3567 ms[i] = lcm(ms[i], m)
3568 values, moduli = vs, ms
File /usr/lib/python3.11/site-packages/sage/arith/misc.py:3464, in crt(a, b, m, n)
3462 q, r = f(g)
3463 if r != 0:
-> 3464 raise ValueError("no solution to crt problem since gcd(%s,%s) does not divide %s-%s" % (m, n, a, b))
3465 from sage.arith.functions import lcm
3467 x = a + q*alpha*py_scalar_to_element(m)
ValueError: no solution to crt problem since gcd(374421497892249265823794031537470448 ...
We got an exception!
Doing some investigations, I decided to check if the values of n have any factors in common:
1
2
3
4
5
6
sage: gcd(n1, n2)
1
sage: gcd(n1, n3)
1
sage: gcd(n2, n3)
175136386393724074897068211302311758514344898633187862983126380556807924872210372704023620020763131468811275018725481764101835410780850364387004844957680252860643364609959757601263568806626614487575229052115194838589297358422557307359118854093864998895206960681533165623745478696564104830629591040860031236467
And it does have!
If they have a common factor, we can divide both by gcd(n2, n3), which will leave us with the other factors of n2 and n3. That means we already have the primes p2, q2, p3, q3. So what about n1? Trying to factor it on my machine, I realized it would take a while. So I decided to search for it on FactorDB, just like we did on the first challenge.
And we get ourselves the values of p1 and q1 :)
Final solve:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
from Crypto.Util.number import long_to_bytes, getPrime
from sage.all import *
load('vals.sage')
p2 = int(n2 / gcd(n2, n3))
p3 = int(n3 / gcd(n2, n3))
q2 = gcd(n2, n3)
q3 = gcd(n2, n3)
phi2 = (p2-1)*(q2-1)
phi3 = (p3-1)*(q3-1)
e = 65537
d2 = pow(e, -1, phi2)
d3 = pow(e, -1, phi3)
m2 = long_to_bytes(pow(c2, d2, n2))
m3 = long_to_bytes(pow(c3, d3, n3))
p1 = 129984014749130366259742130443330376923069118727641845190136006048911945242427603092160936004682857611235008521722596025476170673607376869837675885556290582081941522328978811710862857253777650447221864279732376499043513950683086803379743964370215090077032772967632331576620201195241241611325672953583711299819
q1 = 129984014749130366259742130443330376923069118727641845190136006048911945242427603092160936004682857611235008521722596025476170673607376869837675885556290582081941522328978811710862857253777650447221864279732376499043513950683086803379743964370215090077032772967632331576620201195241241611325672953583711295127
phi1 = (p1-1)*(q1-1)
d1 = pow(e, -1, phi1)
m1 = long_to_bytes(pow(c1, d1, n1))
print(m1.decode(), m2.decode(), m3.decode())
Running it, we get the flag: utflag{oh_no_it_didnt_work_</3_i_guess_i_can_just_use_standard_libraries_in_the_future}