Cool CTF with a bunch of wicked challenges. Of course as usual, limited time for me so I only attempted some basic challenges but even these basic challenges were not a pushover. Let’s talk about these that I solved:
Crypto
Reversing
Minigen - Crypto - 100 Points
This challenge reads:
A stream cipher in only 122 bytes!
Note: This has been tested on python versions 3.8 and 3.9
(141 solves)
With the challenge we get these files:
minigen.pyoutput.txt
The output.txt contains a list of numbers, judging by the clue and filename I assumed these were the encrypted bytes that are the result of the given stream cipher:
281 547 54 380 392 98 158 440 724 218 406 672 193 457 694 208 455 745 196 450 724
The python script is the entire stream cipher algorithm:
exec('def f(x):'+'yield((x:=-~x)*x+-~-x)%727;'*100)
g=f(id(f));print(*map(lambda c:ord(c)^next(g),list(open('f').read())))
The python is written in a mildly obtuse way but its fairly easy to reconcile into re-usable code which I did for purposes of understanding how it worked better. Re-written the code looks like this:
flag = [281,547,54,380,392,98,158,440,724,218,406,672,193,457,694,208,455,745,196,450,724]
def enc(plaintext, key):
def f(x):
yield((x:=-~x)*x+-~-x)%727;yield((x:=-~x)*x+-~-x)%727;yield((x:=-~x)*x+-~-x)%727;yield((x:=-~x)*x+-~-x)%727;yield((x:=-~x)*x+-~-x)%727;yield((x:=-~x)*x+-~-x)%727;yield((x:=-~x)*x+-~-x)%727;yield((x:=-~x)*x+-~-x)%727;yield((x:=-~x)*x+-~-x)%727;yield((x:=-~x)*x+-~-x)%727;yield((x:=-~x)*x+-~-x)%727;yield((x:=-~x)*x+-~-x)%727;yield((x:=-~x)*x+-~-x)%727;yield((x:=-~x)*x+-~-x)%727;yield((x:=-~x)*x+-~-x)%727;yield((x:=-~x)*x+-~-x)%727;yield((x:=-~x)*x+-~-x)%727;yield((x:=-~x)*x+-~-x)%727;yield((x:=-~x)*x+-~-x)%727;yield((x:=-~x)*x+-~-x)%727;yield((x:=-~x)*x+-~-x)%727
# g is a generator with the key == id(f), f will yield one integer per next call.
g=f(key)
return map(lambda c:ord(c)^next(g),list(plaintext))
Useful to note here is the following observations:
gis a generator used with a seed that will return key bytes. In the default code the key generator is seeded with the keyid(f).- In python the
id()built-in is used to return the memory address of the object referenced. In our case in the code provided it will return the memory address of the functionf. - This means the seed to the key generator is always random and there’s too many possible memory addresses to brute-force.
- The constraint that helps us though is that every call to the generator returns a number modulo 727. So there are really only 727 possible seed values reducing the keyspace a huge amount.
- There were originally 100 x
yieldstatements in theencfunction but the flag is only 21 bytes long so we’re only ever going to ask it for 21 key bytes so we just need 21 yields.
Now we know how the key is generated we need to know how the encryption happens. In our case it simply XORs the bytes of the plaintext by the bytes of the key generator. In order to figure out what seed was used to generate the key in our output.txt we can conduct a known plaintext attack against it since we know the flag format is always rarctf{...}
flag = [281,547,54,380,392,98,158,440,724,218,406,672,193,457,694,208,455,745,196,450,724]
known_pt_start = "rarctf{"
print("Known Plaintext: %s" % known_pt_start)
known_flag_bytes = []
for i in range(len(known_pt_start)):
known_flag_bytes.append(ord(known_pt_start[i])^flag[i])
print("Known flag bytes: %s" % known_flag_bytes)
def check(key):
def f(x):
yield((x:=-~x)*x+-~-x)%727;yield((x:=-~x)*x+-~-x)%727;yield((x:=-~x)*x+-~-x)%727;yield((x:=-~x)*x+-~-x)%727;yield((x:=-~x)*x+-~-x)%727;yield((x:=-~x)*x+-~-x)%727;yield((x:=-~x)*x+-~-x)%727;yield((x:=-~x)*x+-~-x)%727;yield((x:=-~x)*x+-~-x)%727;yield((x:=-~x)*x+-~-x)%727;yield((x:=-~x)*x+-~-x)%727;yield((x:=-~x)*x+-~-x)%727;yield((x:=-~x)*x+-~-x)%727;yield((x:=-~x)*x+-~-x)%727;yield((x:=-~x)*x+-~-x)%727;yield((x:=-~x)*x+-~-x)%727;yield((x:=-~x)*x+-~-x)%727;yield((x:=-~x)*x+-~-x)%727;yield((x:=-~x)*x+-~-x)%727;yield((x:=-~x)*x+-~-x)%727;yield((x:=-~x)*x+-~-x)%727
g=f(key)
return map(lambda c:next(g), known_flag_bytes)
# Since we can guess what the generator will return based on the known plaintext we can find a
# number < 727 that will yield the same series. We dont need to search past 727 since all
# generator results are modulo 727
enckey = 0
for t in range(0,727):
res = list(check(t))
if res == known_flag_bytes:
enckey = t
print("Suitable key found: %d" % enckey)
continue
This finds a suitable seed value of 470 which yields the flag bytes in the correct order so will likely be enough to illuminate the entire flag.
$ python3 getkey.py
Known Plaintext: rarctf{
Known flag bytes: [363, 578, 68, 287, 508, 4, 229]
Suitable key found: 470
We know the cipher is a stream cipher and we know the seed used to generate the key, so we can now go ahead brute force the plaintext and compare against the known ciphertext (encrypted flag). Once the two are equal we have our plaintext flag. The following code gets the job done.
import string
flag = [281,547,54,380,392,98,158,440,724,218,406,672,193,457,694,208,455,745,196,450,724]
def enc(plaintext, key):
def f(x):
yield((x:=-~x)*x+-~-x)%727;yield((x:=-~x)*x+-~-x)%727;yield((x:=-~x)*x+-~-x)%727;yield((x:=-~x)*x+-~-x)%727;yield((x:=-~x)*x+-~-x)%727;yield((x:=-~x)*x+-~-x)%727;yield((x:=-~x)*x+-~-x)%727;yield((x:=-~x)*x+-~-x)%727;yield((x:=-~x)*x+-~-x)%727;yield((x:=-~x)*x+-~-x)%727;yield((x:=-~x)*x+-~-x)%727;yield((x:=-~x)*x+-~-x)%727;yield((x:=-~x)*x+-~-x)%727;yield((x:=-~x)*x+-~-x)%727;yield((x:=-~x)*x+-~-x)%727;yield((x:=-~x)*x+-~-x)%727;yield((x:=-~x)*x+-~-x)%727;yield((x:=-~x)*x+-~-x)%727;yield((x:=-~x)*x+-~-x)%727;yield((x:=-~x)*x+-~-x)%727;yield((x:=-~x)*x+-~-x)%727
g=f(key)
return map(lambda c:ord(c)^next(g),list(plaintext))
# brute force encrypt byte by byte with the key we just found comparing the encrypted byte
# with the known output.txt. If its the same then we know the flag byte in the position.
def inner(ptflag):
for char in string.printable:
test = ptflag + char
ct = list(enc(test, 470))
if ct[i] == flag[i]:
ptflag = ptflag + char
return ptflag
ptflag = ''
for i in range(len(flag)):
ptflag = inner(ptflag)
print("%s" % ptflag)
Which finds our flag very quickly:
$ python solve.py
rarctf{pyg01f_1s_fun}
sRSA - Crypto - 100 Points
This challenge, again in the Crypto category reads:
we have created the securest possible rsa algorithm!
(209 solves)
With the challenge we get these files:
script.pyoutput.txt
The output.txt contains the typical components of an RSA public key (n, e) and a ciphertext (ct).
n = 5496273377454199065242669248583423666922734652724977923256519661692097814683426757178129328854814879115976202924927868808744465886633837487140240744798219
e = 431136
ct = 3258949841055516264978851602001574678758659990591377418619956168981354029697501692633419406607677808798749678532871833190946495336912907920485168329153735
The python script is the crypto algorithm used to get us the ct ciphertext and looks like this:
from Crypto.Util.number import *
p = getPrime(256)
q = getPrime(256)
n = p * q
e = 0x69420
flag = bytes_to_long(open("flag.txt", "rb").read())
print("n =",n)
print("e =", e)
print("ct =",(flag * e) % n)
Initially I went down weak PRNG or small prime avenue but neither of these worked out. 256 bits is small for an RSA prime but not small enough to factor for a CTF challenge usually. The Crypto.Util.number.getPrime()method uses Random.new().read()as a RNG and so isn’t considered weak like the random standard library is as far as I could see.
Careful reading of the clue after some time and the solution stuck out at me. The encryption is performed incorrectly. In the script we have: c = me mod n whereas RSA is supposed to be c = m^e mod n. The result is a much weaker ciphertext as m * e is a much smaller number than m ^ e and so we can simply brute force the solution.
I wrote the following code to get it done:
from libnum import *
n = 5496273377454199065242669248583423666922734652724977923256519661692097814683426757178129328854814879115976202924927868808744465886633837487140240744798219
e = 431136
ct = 3258949841055516264978851602001574678758659990591377418619956168981354029697501692633419406607677808798749678532871833190946495336912907920485168329153735
for i in range(e):
pt = ct // e
pts = n2s(pt)
if pts.startswith(b'rar'):
print(pts)
break
ct += n
On the 1185th iteration we got the solution:
$ python3 solve.py
b'rarctf{ST3GL0LS_ju5t_k1dd1ng_th1s_w4s_n0t_st3g_L0L!_83b7e829d9}'
babycrypt - Crypto - 200 Points
Another RSA challenge because they’re fun and because it has the word baby in the title, it must be easy! This one was a bit trickier but didn’t take too long. The clue in this one didn’t really help but read:
It's not a CTF without a baby RSA challenge right?
(96 solves)
Along with this challenge we had an IP / port combination and a script called server.py which was the source code of the server side.
When connecting to the IP / port we got a rotating set of RSA components indicating they were being dynamically generated as well as a hint each time:
$ nc 193.57.159.27 60123
pubkey: (65537, 13270653513439795763627171945828613191250000443606228399379603067250688403699237128740951712728492912391584550540871347431757533342466011505284225929826417)
hint: 1084571559040510950218059110411552212418708488675523435665337327790351579385
c: 12513373888589593411416979785356971382512837163558244538922006707704435809536228095019882307674030696767932143444868700363408982707690169514418959463481954
The souce code of the server illuminated how the hint was generated:
from Crypto.Util.number import getPrime, bytes_to_long
flag = bytes_to_long(open("/challenge/flag.txt", "rb").read())
def genkey():
e = 0x10001
p, q = getPrime(256), getPrime(256)
if p <= q:
p, q = q, p
n = p * q
pubkey = (e, n)
privkey = (p, q)
return pubkey, privkey
def encrypt(m, pubkey):
e, n = pubkey
c = pow(m, e, n)
return c
pubkey, privkey = genkey()
c = encrypt(flag, pubkey)
hint = pubkey[1] % (privkey[1] - 1)
print('pubkey:', pubkey)
print('hint:', hint)
print('c:', c)
So here’s what we knew:
- RSA looks solid, no simple attacks there.
- The
hintis generated asn mod (q -1)
This hint really is a hint then as it leaks information about one of the primes, even if it is in an obtuse manner. I am not a math expert so I wrote some of my own code to understand how hint related to p and / or q and how I can use it. My exploratory code using much smaller primes looked like this:
import random
# Sample some primes from https://primes.utm.edu/lists/small/millions/primes2.zip
primes = [int(z[0]) for z in [y.split() for y in [x.strip() for x in open('primes2.txt').readlines()] if y != '']]
def genkey():
e = 0x10001
p, q = random.choice(primes), random.choice(primes)
if p <= q:
p, q = q, p
n = p * q
pubkey = (e, n)
privkey = (p, q)
return pubkey, privkey
pubkey, privkey = genkey()
n = pubkey[1]
q = privkey[1]
p = privkey[0]
hint = n % (q - 1)
pmhint = p - hint
qmhint = q - hint
res1 = q - pmhint
res2 = p - qmhint
print('hint:', hint)
print('n: %d' % n)
print('q: %d' % q)
print('p: %d' % p)
print('p - hint = %d' % pmhint)
print('q - hint = %d' % qmhint)
print('q - (p - hint) = %d' % res1)
print('p - (q - hint) = %d' % res2)
When I ran it I found an interesting relationship:
$ python3 testbehav.py
hint: 6935833
n: 693267725507569
q: 23089459
p: 30025291
p - hint = 23089458
q - hint = 16153626
q - (p - hint) = 1
p - (q - hint) = 13871665
This q - (p - hint) = 1 result is interesting, if we re-arrange the terms we can say q = (p - hint) + 1. Given we know hint = n % (q-1) and we know n = p*q, and hint we have a set of equations that we may be able to solve together.
To do this I relied on SAGE because of it’s simple equation solver interface and because we can usually use most Python libraries like pwntools within it:
#!/usr/bin/env sage
import sys
from pwn import *
from Crypto.Util.number import long_to_bytes
host, port = "193.57.159.27:60123".split(':')
conn = remote(host, port)
e, n = [int(c) for c in conn.readline().decode('utf-8')[9:-2].split(',')]
hint = int(conn.readline().decode('utf-8').split()[1])
c = int(conn.readline().decode('utf-8').split()[1])
conn.close()
print('e %d' % e)
print('n %d' % n)
print('hint: %d' % hint)
print('c %d' % c)
print('solving for p...')
# Solve for these...
# n = p * q
# q = (p - hint) + 1
p, q = var('p q')
eq1 = p*q==n
eq2 = q==(p-hint)+1
solutions = solve([eq1, eq2], p, q)
P = abs(int(solutions[0][0].rhs()))
if n % P != 0:
print('solution not found')
quit()
Q = n // P
t = (P-1)*(Q-1)
d = inverse_mod(e, t)
m = int(pow(c, d, n))
print('flag: %s' % long_to_bytes(m, 2).decode('utf-8'))
Which worked surprisingly fast to get the flag:
$ ./solve.sage
[*] Closed connection to 193.57.159.27 port 60123
e 65537
n 9392576813698903065278469812753466259035349694524358966003588543714395953008211955671129615385917416048418900705217378644458776242738509000319371167253959
hint: 28397963005209799410205482864121374264565557001403938358856145871774888309191
c 5028988423707586193976465257582570625999188342022011650996945341765554081390500916730468999102762227041707069861158162047603258697942660825207789039218618
solving for p...
flag: rarctf{g3n3r1c_m4th5_equ4t10n_th1ng_ch4ll3ng3_5a174f54e6}
verybabyrev - Reversing - 100 Points
Very baby rev seems pretty promising for an easy 100 points. So I gave it a look while taking a break from the crypto category. It turned out to be more crypto sort of. Anyway the challenge read:
fun fact: verybabyrev backwards is verybabyrev
(217 solves)
With this clue there was a binary verybabyrev (sha1sum = 2939af5e0a6016c4fa44b027f739a80f77509848)
The first things I always do is just check the file out with file and strings but there was nothing exciting there:
$ file verybabyrev
verybabyrev: ELF 64-bit LSB pie executable, x86-64, version 1 (SYSV), dynamically linked, interpreter /lib64/ld-linux-x86-64.so.2, for GNU/Linux 3.2.0, BuildID[sha1]=276af40b2393e3013daafb8acfc000ab3e0d1ab8, not stripped
Next I loaded it in Ghidra and opened the main function and checked the decompiler. It did a fantastic job to be honest and the resulting code snippet was very illuminating:
// Ciphertext.
local_108 = 0x45481d1217111313;
local_100 = 0x95f422c260b4145;
local_f8 = 0x541b56563d6c5f0b;
local_f0 = 0x585c0b3c2945415f;
local_e8 = 0x402a6c54095d5f00;
local_e0 = 0x4b5f4248276a0606;
local_d8 = 0x6c5e5d432c2d4256;
local_d0 = 0x6b315e434707412d;
local_c8 = 0x5e54491c6e3b0a5a;
local_c0 = 0x2828475e05342b1a;
local_b8 = 0x60450073b26111f;
local_b0 = 0xa774803050b0d04;
local_a8 = 0;
// Get the flag from the user.
printf("Enter your flag: ");
fgets((char *)&flag_input,0x80,stdin);
// It must begin with 'r' as in 'rarctf...'
if ((char)flag_input != 'r') {
puts("Nope!");
exit(0);
}
// XOR each byte in the plaintext with the subsequent byte.
counter = 0;
while (counter < 0x7f) {
*(byte *)((long)&flag_input + counter) =
*(byte *)((long)&flag_input + counter) ^
*(byte *)((long)&flag_input + (counter + 1));
counter++;
}
// If the result looks like the ciphertext then you win.
success = memcmp(&local_108,&flag_input,0x61);
if (success == 0) {
puts("Correct!");
Firstly, thanks Ghidra for resolving the constants and making them as plain as day. Nice work.
Next the algorithm is straightforward, whatever you type will be XOR‘d byte by byte with each subsequent byte and the resulting 0x61 bytes compared with the data stored from local_108 onwards. We even know the first byte of the flag must be r because its hard coded in the binary. It’s safe to assume the first bytes are probably the standard flag format rarctf{.
So the solution is roughly similar to minigen. We conduct a known plaintext attack against the bytes stored in local_108 onward. Starting with rarctf{ we write an encoder in Python that does the same thing the C code does and solve. The following code does the trick:
import string
local_108 = 0x45481d1217111313
local_100 = 0x095f422c260b4145
local_f8 = 0x541b56563d6c5f0b
local_f0 = 0x585c0b3c2945415f
local_e8 = 0x402a6c54095d5f00
local_e0 = 0x4b5f4248276a0606
local_d8 = 0x6c5e5d432c2d4256
local_d0 = 0x6b315e434707412d
local_c8 = 0x5e54491c6e3b0a5a
local_c0 = 0x2828475e05342b1a
local_b8 = 0x060450073b26111f
local_b0 = 0x0a774803050b0d04
blocks = [local_108, local_100, local_f8, local_f0, local_e8, local_e0, local_d8, local_d0, local_c8, local_c0, local_b8, local_b0]
rawdata = b''
for b in blocks:
rawdata += b.to_bytes(8, 'little')
def encode(plaintext):
out = b''
local_c = 0
while True:
if local_c + 1 == len(plaintext):
break
out += (plaintext[local_c] ^ plaintext[local_c+1]).to_bytes(1, 'little')
local_c += 1
return out
knownpt = b'rarctf{'
start = len(knownpt)
for i in range(start, 0x61, 1):
for j in string.printable:
res = encode(knownpt + j.encode('utf-8'))
if res == rawdata[:i]:
knownpt += j.encode('utf-8')
print('flag: %s' % knownpt.decode('utf-8'))
Which when we run, drops us the flag:
$ python3 solve4.py
flag: rarctf{3v3ry_s1ngl3_b4by-r3v_ch4ll3ng3_u535_x0r-f0r_s0m3_r34s0n_4nd_1-d0nt_kn0w_why_dc37158365}