ASIS CTF Finals 2020 - Coffeehouse writeup

crypto
,

Coffehouse

We are given a small python code, here’s the relevant part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
d = 0xf00d

def genkey():
	key = []
	r, s = random.randint(1, 1<<16), random.randint(1, 1<<16)
	return [r, s, r ^ s, r & s]

def encrypt(u, v, key, d):
	assert u < 2**16 and v < 2**16
	s = 0
	for i in range(32):
		s = (s + d) % 2**16
		w = ((v<<4) + key[0]) ^ (v + s) ^ ((v>>5) + key[1]) % 2**16
		u = (u + w) % 2**16
		x = ((u<<4) + key[2]) ^ (u + s) ^ ((u>>5) + key[3]) % 2**16
		v = (v + x) % 2**16
	return (u, v)

The flag is then splitted into blocks of 2 bytes and encrypted using the encrypt function. We can recognize the encrypt as the Tiny Encryption Algorithm, a very simple ARX block cipher.

We can also see that the key generation is done using 32 bit of randoms, so without trying to break the algorithm itself we wrote a bruteforce in C++ using the C code of TEA available on wikipedia. The only things to notice are that the round constant (d in the code) is not the standard one and that all the computations are done on 16-bit integers instead of the standard 32-bit integers used in TEA. The following non-optimized C++ code retrieves the flag in 2 minutes on a 32 core machine, with almost zero memory usage.

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
#include <bits/stdc++.h>

using namespace std;

void decrypt (uint16_t* v, uint16_t* k) {
    uint16_t v0=v[0], v1=v[1], sum=416, i;
    uint16_t delta=0xf00d;
    uint16_t k0=k[0], k1=k[1], k2=k[2], k3=k[3];
    for (i=0; i<32; i++) {
        v1 -= ((v0<<4) + k2) ^ (v0 + sum) ^ ((v0>>5) + k3);
        v0 -= ((v1<<4) + k0) ^ (v1 + sum) ^ ((v1>>5) + k1);
        sum -= delta;
    }
    v[0]=v0; v[1]=v1;
}

int main() {
  uint16_t encrypted[] = {12263, 64385, 17263, 21844, 59059, 40727, 12495, 21699, 58982, 30941, 52310, 2067, 52933, 47229, 28811, 45010, 3549, 61620};
  #pragma omp parallel for
  for(int i = 0;i<65536;i++){
    for(int j = 0;j<65536;j++){
      uint16_t ii = uint16_t(i);
      uint16_t jj = uint16_t(j);
      uint16_t key[] = {ii, jj, ii^jj, ii&jj};
      string s;
      for(int k = 0; k<18; k+=2){
        uint16_t v[] = {encrypted[k], encrypted[k+1]};
        decrypt(v,key);
        s += char(v[0]>>8);
        s += char(v[0]%256);
        s += char(v[1]>>8);
        s += char(v[1]%256);
      }
      if(s.find("ASIS{") != string::npos) cout<<s<<endl;
    }
  }

	return 0;
}