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

Challenge Name

Score

Challenge

Solution

Flag

Farm

Challenge

Explore the Farm very carefully!

Attachment:

farm.txz

Code Review

#!/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

#!/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






























































#!/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 containsn3T4Dm1n, 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

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 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 and solving equations, but should be a real mathematician to solve it with a diophantine equation?









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\):





























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












































































#!/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:

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 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





































#!/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










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





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




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




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:

















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]))

Syntax	Example	Reference
# Header	Header	基本排版
- Unordered List	Unordered List
1. Ordered List	Ordered List
- [ ] Todo List	Todo List
> Blockquote	Blockquote
Bold font	Bold font
Italics font	Italics font
~~Strikethrough~~	~~Strikethrough~~
19^th^	19^th
H~2~O	H₂O
++Inserted text++	Inserted text
==Marked text==	Marked text
[link text](https:// "title")	Link
![image alt](https:// "title")	Image
`Code`	`Code`	在筆記中貼入程式碼
```javascript var i = 0; ```	`var i = 0;`	在筆記中貼入程式碼
:smile:		Emoji list
{%youtube youtube_id %}	Externals
$L^aT_eX$	L^aT_eX
:::info This is a alert area. :::	This is a alert area.