# CryptoCTF 2021
| Challenge | Category | Solved by |
| -------- | --------- | ---------- |
| Farm | Finite Field | EvilMuffinHa |
| KeyBase | B | UnblvR |
| Maid | B | defund |
| Salt and Pepper | Hash length extension | willwam845 |
| RSAphantine | Diophantine equations | UnblvR, AC |
| Triplet | RSA | willwam845 |
| Rami | Encoding | willwam845, randomdude999 |
| A | B | C |
<!-- Template for writeup -->
## Challenge Name
##### Score
### Challenge
### Solution
##### Flag
## Farm
### Challenge
Explore the Farm very carefully!
Attachment:
- [farm.txz](https://cryp.toc.tf/tasks/farm_0a16ef99ff1f979039cda1a685ac0344b927eee6.txz)
### Code Review
```python
#!/usr/bin/env sage
from sage.all import *
import string, base64, math
from flag import flag
ALPHABET = string.printable[:62] + '\\='
F = list(GF(64))
def keygen(l):
key = [F[randint(1, 63)] for _ in range(l)]
key = math.prod(key) # Optimization the key length :D
return key
def maptofarm(c):
assert c in ALPHABET
return F[ALPHABET.index(c)]
def encrypt(msg, key):
m64 = base64.b64encode(msg)
enc, pkey = '', key**5 + key**3 + key**2 + 1
for m in m64:
enc += ALPHABET[F.index(pkey * maptofarm(chr(m)))]
return enc
# KEEP IT SECRET
key = keygen(14) # I think 64**14 > 2**64 is not brute-forcible :P
enc = encrypt(flag, key)
print(f'enc = {enc}')
```
The key is the product of 14 random elements selected from $GF(64)$.
### Solution
Note that the product of two elements of $GF(64)$ is still an element of $GF(64)$. Inductively, the key lies in $GF(64)$. That is, the key space is just 64 and hence we are able to brute-force the key.
### Implementation
```python
#!/usr/bin/env sage
import string
import base64
enc = "805c9GMYuD5RefTmabUNfS9N9YrkwbAbdZE0df91uCEytcoy9FDSbZ8Ay8jj"
ALPHABET = string.printable[:62] + '\\='
F = list(GF(64))
def farmtomap(f):
assert f in F
return ALPHABET[F.index(f)]
def decrypt(msg, key):
dec, pkey = '', key**5 + key**3 + key**2 + 1
for m in msg:
dec += farmtomap(F[ALPHABET.index(m)] / pkey)
return base64.b64decode(dec)
for possible_key in F:
try:
plaintext = decrypt(enc, possible_key)
if b"CCTF{" in plaintext:
print(plaintext.decode())
except:
continue
```
## Salt and Pepper
### Challenge
```python=
#!/usr/bin/env python3
from hashlib import md5, sha1
import sys
from secret import salt, pepper
from flag import flag
assert len(salt) == len(pepper) == 19
assert md5(salt).hexdigest() == '5f72c4360a2287bc269e0ccba6fc24ba'
assert sha1(pepper).hexdigest() == '3e0d000a4b0bd712999d730bc331f400221008e0'
def auth_check(salt, pepper, username, password, h):
return sha1(pepper + password + md5(salt + username).hexdigest().encode('utf-8')).hexdigest() == h
def die(*args):
pr(*args)
quit()
def pr(*args):
s = " ".join(map(str, args))
sys.stdout.write(s + "\n")
sys.stdout.flush()
def sc():
return sys.stdin.readline().strip()
def main():
border = "+"
pr(border*72)
pr(border, " welcome to hash killers battle, your mission is to login into the ", border)
pr(border, " ultra secure authentication server with provided information!! ", border)
pr(border*72)
USERNAME = b'n3T4Dm1n'
PASSWORD = b'P4s5W0rd'
while True:
pr("| Options: \n|\t[L]ogin to server \n|\t[Q]uit")
ans = sc().lower()
if ans == 'l':
pr('| send your username, password as hex string separated with comma: ')
inp = sc()
try:
inp_username, inp_password = [bytes.fromhex(s) for s in inp.split(',')]
except:
die('| your input is not valid, bye!!')
pr('| send your authentication hash: ')
inp_hash = sc()
if USERNAME in inp_username and PASSWORD in inp_password:
if auth_check(salt, pepper, inp_username, inp_password, inp_hash):
die(f'| Congrats, you are master in hash killing, and it is the flag: {flag}')
else:
die('| your credential is not valid, Bye!!!')
else:
die('| Kidding me?! Bye!!!')
elif ans == 'q':
die("Quitting ...")
else:
die("Bye ...")
if __name__ == '__main__':
main()
```
We send a username and password to the server, along with an authentication hash. These are all passed as parameters to the `auth_check` function, and the username contains`n3T4Dm1n`, the password contains `P4s5W0rd`, and the function returns true, we get the flag.
### Solution
The `check_auth` function uses two secrets, `salt` and `pepper`, which we know the length of, however we don't know the value of.
The `check_auth` function calculates the authentication hash using the following line
```py
sha1(pepper + password + md5(salt + username).hexdigest().encode('utf-8')).hexdigest()
```
Since these two secrets are hashed as well as our username and password, we cannot directly work out the authentication hash. However, we get given the MD5 hash of `salt`, and the SHA1 hash of `pepper`. Since both of the secret values are put as prefixes to our input, we can perform a hash length extension attack.
[HashPump](https://github.com/bwall/HashPump) is a useful tool to do this, as all we need to do is provide the parameters and the tool does most of the work for us. One thing that needed to be changed however is that since we get the raw hashes, we don't have any data to give to the tool, and Hashpump complains when we do that.
To get around this, I simply removed this check in the `main.cpp` file (line 255) and recompiled it.
First, we will create a MD5 of (`salt` + `padding` + `n3T4Dm1n`) using the tool:
```
hashpump -s "5f72c4360a2287bc269e0ccba6fc24ba" -d "" -a "n3T4Dm1n" -k 19
```
giving an output of
```
95623660d3d04c7680a52679e35f041c
\x80\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x98\x00\x00\x00\x00\x00\x00\x00n3T4Dm1n
```
Then, we will create our authentication hash by creating a SHA1 of (`pepper` + `padding` + `P4s5W0rd` + `95623660d3d04c7680a52679e35f041c`)
```
hashpump -s "3e0d000a4b0bd712999d730bc331f400221008e0" -d "" -a "P4s5W0rd95623660d3d04c7680a52679e35f041c" -k 19
```
giving an output of
```
83875efbe020ced3e2c5ecc908edc98481eba47f
\x80\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x98P4s5W0rd95623660d3d04c7680a52679e35f041c
```
**83875efbe020ced3e2c5ecc908edc98481eba47f** should now be our authentication hash when we use `\x80\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x98\x00\x00\x00\x00\x00\x00\x00n3T4Dm1n` as our username and `\x80\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x98P4s5W0rd` as our password (note that we remove the MD5 hash at the end as it gets added when the `auth_check` function is called).
Submitting these to the server gives us the flag.
## RSAphantine
### Challenge
[RSA](https://cryp.toc.tf/tasks/RSAphantine_b1f2e30c7e90cfacb9ef4d0b5ce80abe33d1eb08.txz) and solving equations, but should be a real mathematician to solve it with a diophantine equation?
```python=
2*z**5 - x**3 + y*z = 47769864706750161581152919266942014884728504309791272300873440765010405681123224050402253883248571746202060439521835359010439155922618613520747411963822349374260144229698759495359592287331083229572369186844312169397998958687629858407857496154424105344376591742814310010312178029414792153520127354594349356721
x**4 + y**5 + x*y*z = 89701863794494741579279495149280970802005356650985500935516314994149482802770873012891936617235883383779949043375656934782512958529863426837860653654512392603575042842591799236152988759047643602681210429449595866940656449163014827637584123867198437888098961323599436457342203222948370386342070941174587735051
y**6 + 2*z**5 + z*y = 47769864706750161581152919266942014884728504309791272300873440765010405681123224050402253883248571746202060439521835359010439155922618613609786612391835856376321085593999733543104760294208916442207908167085574197779179315081994735796390000652436258333943257231020011932605906567086908226693333446521506911058
p = nextPrime(x**2 + z**2 + y**2 << 76)
q = nextPrime(z**2 + y**3 - y*x*z ^ 67)
n, e = p * q, 31337
m = bytes_to_long(FLAG)
c = pow(m, e, n)
c = 486675922771716096231737399040548486325658137529857293201278143425470143429646265649376948017991651364539656238516890519597468182912015548139675971112490154510727743335620826075143903361868438931223801236515950567326769413127995861265368340866053590373839051019268657129382281794222269715218496547178894867320406378387056032984394810093686367691759705672
```
### Solution
This challenge gives us the following set of three equations and three unknowns $x$, $y$, and $z$; it then generates parameters for RSA encryption using the following equations:
$$p = nextPrime(\frac{x^2+y^2+z^2}{2^{76}})\\
q = nextPrime(z^2+y^3- (xyz \oplus 67))$$
It doesn't look like we can attack the equations for $p$ or $q$ directly, so we solve the diophantine equations first:
$$2z^5-x^3+yz=47769... = a\\
x^4+y^5+xyz=89701... = b\\
y^6+2z^5+yz=47769... = c$$
Note that while the right hand side of the first and third equations appear to be the same, they are different numbers. We first compute $c-a = x^3+y^6 = (x+y^2)(x^2-xy^2+y^4)$ by sum of cubes; factoring $c-a$, we recover the factors $3133713317731333$ and $28413320364759425...$.
Plugging the equations into z3, we solve for $x$, $y$, and $z$:
```python=
from z3 import *
from sympy import *
A = 3133713317731333
B = 28413320364759425177418147555143516002041291710972733253944530195017276664069717887927099709630886727522090965378073004342203980057853092114878433424202989
c = 486675922771716096231737399040548486325658137529857293201278143425470143429646265649376948017991651364539656238516890519597468182912015548139675971112490154510727743335620826075143903361868438931223801236515950567326769413127995861265368340866053590373839051019268657129382281794222269715218496547178894867320406378387056032984394810093686367691759705672
x = Int("x")
y = Int("y")
z = Int("z")
s = Solver()
s.add(y**2 + x == A)
s.add(y**4 - x*y**2 + x**2 == B)
s.add(y>0)
s.add(2*z**5 - x**3 + y*z == 47769864706750161581152919266942014884728504309791272300873440765010405681123224050402253883248571746202060439521835359010439155922618613520747411963822349374260144229698759495359592287331083229572369186844312169397998958687629858407857496154424105344376591742814310010312178029414792153520127354594349356721)
s.add(x**4 + y**5 + x*y*z == 89701863794494741579279495149280970802005356650985500935516314994149482802770873012891936617235883383779949043375656934782512958529863426837860653654512392603575042842591799236152988759047643602681210429449595866940656449163014827637584123867198437888098961323599436457342203222948370386342070941174587735051)
s.add(y**6 + 2*z**5 + z*y == 47769864706750161581152919266942014884728504309791272300873440765010405681123224050402253883248571746202060439521835359010439155922618613609786612391835856376321085593999733543104760294208916442207908167085574197779179315081994735796390000652436258333943257231020011932605906567086908226693333446521506911058)
if s.check() == sat:
m = s.model()
x = m[x].as_long()
y = m[y].as_long()
z = m[z].as_long()
p = nextprime(x**2 + z**2 + y**2 << 76)
q = nextprime(z**2 + y**3 - y*x*z ^ 67)
d = pow(31337, -1, (p-1)*(q-1))
print(bytes.fromhex(hex(pow(c, d, p*q))[2:]).decode())
```
##### Flag
CCTF{y0Ur_jO8_C4l13D_Diophantine_An4LySI5!}
## Triplet
### Challenge
```python=
#!/usr/bin/env python3
from Crypto.Util.number import *
from random import randint
import sys
from flag import FLAG
def die(*args):
pr(*args)
quit()
def pr(*args):
s = " ".join(map(str, args))
sys.stdout.write(s + "\n")
sys.stdout.flush()
def sc():
return sys.stdin.readline().strip()
def main():
border = "+"
pr(border*72)
pr(border, " hi talented cryptographers, the mission is to find the three RSA ", border)
pr(border, " modulus with the same public and private exponent! Try your chance!", border)
pr(border*72)
nbit = 160
while True:
pr("| Options: \n|\t[S]end the three nbit prime pairs \n|\t[Q]uit")
ans = sc().lower()
order = ['first', 'second', 'third']
if ans == 's':
P, N = [], []
for i in range(3):
pr("| Send the " + order[i] + " RSA primes such that nbit >= " + str(nbit) + ": p_" + str(i+1) + ", q_" + str(i+1) + " ")
params = sc()
try:
p, q = params.split(',')
p, q = int(p), int(q)
except:
die("| your primes are not valid!!")
if isPrime(p) and isPrime(q) and len(bin(p)[2:]) >= nbit and len(bin(q)[2:]) >= nbit:
P.append((p, q))
n = p * q
N.append(n)
else:
die("| your input is not desired prime, Bye!")
if len(set(N)) == 3:
pr("| Send the public and private exponent: e, d ")
params = sc()
try:
e, d = params.split(',')
e, d = int(e), int(d)
except:
die("| your parameters are not valid!! Bye!!!")
phi_1 = (P[0][0] - 1)*(P[0][1] - 1)
phi_2 = (P[1][0] - 1)*(P[1][1] - 1)
phi_3 = (P[2][0] - 1)*(P[2][1] - 1)
if 1 < e < min([phi_1, phi_2, phi_3]) and 1 < d < min([phi_1, phi_2, phi_3]):
b = (e * d % phi_1 == 1) and (e * d % phi_2 == 1) and (e * d % phi_3 == 1)
if b:
die("| You got the flag:", FLAG)
else:
die("| invalid exponents, bye!!!")
else:
die("| the exponents are too small or too large!")
else:
die("| kidding me?!!, bye!")
elif ans == 'q':
die("Quitting ...")
else:
die("Bye ...")
if __name__ == '__main__':
main()
```
We need to send 3 pairs of primes followed by a keypair `e,d` so that `e,d` is a valid keypair for each modulus generated by each pair.
Most easy solutions are patched out, as `e` and `d` both have to be less than the lowest phi and greater than 1.
### Solution
Our main idea for this problem is to generate `phi_1`, `phi_2` and `phi_3` in a way so that `phi_2` is a multiple of `phi_1`, and `phi_3` is a multiple of `phi_2`. In this way, any valid keypair for `phi_3` (that also satisfies the length requirement) will also be a valid keypair for `phi_1` and `phi_2` and can be used to get the flag.
We can generate primes as follows:
```py
def phi(p,q):
return (p-1) * (q-1)
from random import randrange
def genprime(baseprime):
while True:
k = randrange(2, 1000)
p = baseprime * k + 1
if is_prime(p):
return p
p = random_prime(2^160)
q = random_prime(2^160)
r = genprime(p)
s = genprime(q)
t = genprime(r)
u = genprime(s)
phi_1 = phi(p,q)
phi_2 = phi(r,s)
phi_3 = phi(t,u)
```
Now all we need to do is generate a valid keypair for `phi_3`. To do this, recall that the values $e$ and $d$ satisfy the following equation:
$$e * d \equiv 1 \mod \phi(n)$$
therefore
$$e * d = 1 + k * \phi(n)$$
If we find factors of $1 + phi(n3)$, we should be able to find two numbers that are small enough to satisfy the length requirements, as the value $k$ in the equation
$$\phi(n3) = k * \phi(n1)$$
should be small. We can just use something like [factordb](http://factordb.com/) for this.
Once we do that, we submit everything to the server and get our flag.
Example input:
```
1016528131013635090619361217720494946552931485213,1429584882448210886669728733194710184148915763157
6211546314237476302579971345731015750127038990912821,8860059189914843449838352373651833954155350825107793
9404281119755539122106076617436757845692337032242009481,24063920759808714809760965046838381019485932840992763073
43589288709210633359625764026901174390804401096987086682930362519465081895858044399533,5191731325979249818708517
```
## Rami
### Challenge
```python=
#!/usr/bin/env python3
from Crypto.Util.number import *
from flag import FLAG
def nextPrime(n):
while True:
n += (n % 2) + 1
if isPrime(n):
return n
f = [int(x) for x in bin(int(FLAG.hex(), 16))[2:]]
f.insert(0, 0)
for i in range(len(f)-1): f[i] += f[i+1]
a = nextPrime(len(f))
b = nextPrime(a)
g, h = [[_ for i in range(x) for _ in f] for x in [a, b]]
c = nextPrime(len(f) >> 2)
for _ in [g, h]:
for __ in range(c): _.insert(0, 0)
for i in range(len(_) - c): _[i] += _[i+c]
g, h = [int(''.join([str(_) for _ in __]), 5) for __ in [g, h]]
for _ in [g, h]:
if _ == g:
fname = 'g'
else:
fname = 'h'
of = open(f'{fname}.enc', 'wb')
of.write(long_to_bytes(_))
of.close()
```
The flag is encoded using a bunch of weird looking operations, and then we get the two files `g.enc` and `h.enc`
### Solution
Firstly, we can deduce the flag length as 32 bytes by simply testing some letter repeated some number of times as the flag, then checking the length of the output and comparing it to the size of `g.enc`.
We will work through the steps in reverse order.
#### Step 1
```python=
g, h = [int(''.join([str(_) for _ in __]), 5) for __ in [g, h]]
for _ in [g, h]:
if _ == g:
fname = 'g'
else:
fname = 'h'
of = open(f'{fname}.enc', 'wb')
of.write(long_to_bytes(_))
of.close()
```
Firstly, each file contains bytes, which we need to convert to a base 10 integer. Then, we need to convert this base 10 integer into a base 5 integer. We can do this quite easily with `gmpy2`'s `digits` function.
#### Step 2
```python=
c = nextPrime(len(f) >> 2)
for _ in [g, h]:
for __ in range(c): _.insert(0, 0)
for i in range(len(_) - c): _[i] += _[i+c]
```
These next steps add some elements of the list to other elements of the list. We can work out the value of `len(_) - c` by just running the program with a random 32 byte flag, and then to reverse it, we just need to ensure that we change the addition to subtraction, and work in reverse order, as the later elements of the list are not affected by the earlier ones (but not vice versa).
We also then need to trim $c$ amound of 0's from the start of the list at the end. $c$ can again be worked out by just running the program.
#### Step 3
```python=
a = nextPrime(len(f))
b = nextPrime(a)
g, h = [[_ for i in range(x) for _ in f] for x in [a, b]]
```
This step simply takes the list $f$ and duplicates it $a$ and $b$ times, storing them in $g$ and $h$. We can either manually find the repeating sequence, work out the values of $a$ and $b$ and simply split $g$ into $a$ chunks (or $h$ into $b$ chunks), or we can simply know the length of $f$, and take the first $len(f)$ elements of $g$ to get the original $f$.
#### Step 4
```python=
f = [int(x) for x in bin(int(FLAG.hex(), 16))[2:]]
f.insert(0, 0)
for i in range(len(f)-1): f[i] += f[i+1]
```
Our last step is again quite similar to step 2, we work out the length of $f$ by running the program, and then going in reverse order, changing the addition to a subtraction instead. We can then obtain the flag by converting the list into a string, which should be the binary string of the flag.
### Implementation
Putting this all together, this looks like this:
```python=
from gmpy2 import digits
# Step 1
g = list(digits(bytes_to_long(open("g.enc","rb").read()) ,5))
g = [int(x) for x in g]
# Step 2
for _ in [g]:
for i in range(65791,-1,-1): _[i] -= _[i+c]
# Step 3
f = g[67:67+256]
f = [int(x) for x in f]
# Step 4
for i in range(len(f)-2, -1, -1):f[i] -= f[i+1]
print("".join([str(x) for x in f]))
```
Google Drive
Gist
Clipboard
Sign in with Wallet
