Posts RITSEC CTF: CictroHash write-up
Post
Cancel

RITSEC CTF: CictroHash write-up

RITSEC CTF: CictroHash write-up

Img

After having a look at the attached pdf file we can clearly see that we need to implement a sponge function, which includes XORs and a function f that is comprised of four composite functions. So I’ll start by writing the four functions first.

Visual representation of the sponge function

Img

Mathematical definition of f

Img

Img

Functions

All of them will have as an argument a matrix of 2x4, as defined in the PDF:

Img

I will not be passing the matrix as an argument and then returning it. Instead, I will be modifying it right from within the functions.

Alpha(w)

The first function was a simple swap, so I just needed to do:

1
2
3
4
5
6
void alpha(unsigned arr[2][4]){
  unsigned x[4];
  for (int i = 0; i<4; i++) x[i] = arr[0][i];
  for (int i = 0; i<4; i++) arr[0][i] = arr[1][i];
  for (int i = 0; i<4; i++) arr[1][i] = x[i];
}

Beta(w)

Beta consisted of XORing one of the elements of the matrix to another:

1
2
3
4
5
void beta(unsigned arr[2][4]){
  for (int i = 0; i<4; i++){
    arr[0][i] ^= arr[1][3-i];
  }
}

Gamma(w)

In gamma we find that we need to do some variable assignations (we need to take into account that a -> b means store a into b, not the other way around).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void gamma(unsigned arr[2][4]){
  unsigned w,x,y,z;
  x = arr[1][3];
  y = arr[1][2];
  z = arr[0][3];
  w = arr[1][1];
  arr[0][3] = arr[0][0];
  arr[1][2] = arr[0][1];
  arr[1][3] = arr[0][2];
  arr[1][1] = z;
  arr[0][1] = arr[1][0];
  arr[1][0] = w;
  arr[0][2] = y;
  arr[0][0] = x;
}

Delta(w)

Finally, in delta there are some bitwise rotations that we can do with right and left shifts and masks (to get only the first byte).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
unsigned rotate_left(unsigned x){
  return 0xff & ((x << 1)|(x >> 7));
}

unsigned rotate_right(unsigned x){
  return 0xff & ((x >> 1)|(x << 7));
}

void delta(unsigned arr[2][4]){
  arr[0][0] = rotate_left(arr[0][0]);
  arr[1][0] = rotate_left(arr[1][0]);
  arr[0][2] = rotate_left(arr[0][2]);
  arr[1][2] = rotate_left(arr[1][2]);
  arr[0][1] = rotate_right(arr[0][1]);
  arr[1][1] = rotate_right(arr[1][1]);
  arr[0][3] = rotate_right(arr[0][3]);
  arr[1][3] = rotate_right(arr[1][3]);
}

The sponge function

After doing the composite function f we need to understand how the sponge function works.

Img

It starts with 8 bytes, 4 in r and 4 in c. What we need to do is divide our message in 4-bit chunks (padding it with 0s at the end if needed) and then XOR each chunk with r. Then, we apply f and start again.

For example, if we had “HELLOWORLD” we would divide our message in “HELL”, “OWOR”, “LD” + 00. They would be P0, P1 and P2 respectively.

I transformed this into code the following way:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void tests(char stri[], int len){
  unsigned w[2][4] = {31,56,156,167,38,240,174,248};
  for (int i=0; i<len/4; i+=1){
    for (int j=0; j<4; j++){
      w[0][j] ^= stri[j+(4*i)];
    }
    f(w);
  }
  if (len%4!=0){
    for (int j=0; j<len%4; j++){
      w[0][j] ^= stri[j+(4*(len/4))];
    }
    for (int j=4-(len%4); j<4; j++){
      w[0][j] ^= 0;
    }
    f(w);
  }
  printf("0x%x%x%x%x\n", w[0][0], w[0][1], w[0][2], w[0][3]);
}

Putting it all together

I ended with the following code, that took 2 arguments when run from the command line: a string and its length. The reason I did this was so that I could pass arguments from another program and then brute-force the solution.

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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include <stdlib.h>
#include <stdio.h>
#include <string.h>

unsigned rotate_left(unsigned x){
  return 0xff & ((x << 1)|(x >> 7));
}

unsigned rotate_right(unsigned x){
  return 0xff & ((x >> 1)|(x << 7));
}

void alpha(unsigned arr[2][4]){
  unsigned x[4];
  for (int i = 0; i<4; i++) x[i] = arr[0][i];
  for (int i = 0; i<4; i++) arr[0][i] = arr[1][i];
  for (int i = 0; i<4; i++) arr[1][i] = x[i];
}

void beta(unsigned arr[2][4]){
  for (int i = 0; i<4; i++){
    arr[0][i] ^= arr[1][3-i];
  }
}

void gamma(unsigned arr[2][4]){
  unsigned w,x,y,z;
  x = arr[1][3];
  y = arr[1][2];
  z = arr[0][3];
  w = arr[1][1];
  arr[0][3] = arr[0][0];
  arr[1][2] = arr[0][1];
  arr[1][3] = arr[0][2];
  arr[1][1] = z;
  arr[0][1] = arr[1][0];
  arr[1][0] = w;
  arr[0][2] = y;
  arr[0][0] = x;
}

void delta(unsigned arr[2][4]){
  arr[0][0] = rotate_left(arr[0][0]);
  arr[1][0] = rotate_left(arr[1][0]);
  arr[0][2] = rotate_left(arr[0][2]);
  arr[1][2] = rotate_left(arr[1][2]);
  arr[0][1] = rotate_right(arr[0][1]);
  arr[1][1] = rotate_right(arr[1][1]);
  arr[0][3] = rotate_right(arr[0][3]);
  arr[1][3] = rotate_right(arr[1][3]);
}

void f(unsigned arr[2][4]){
  for (int i=0; i<50; i++){
    alpha(arr);
    beta(arr);
    gamma(arr);
    delta(arr);
  }
}

void tests(char stri[], int len){
  unsigned w[2][4] = {31,56,156,167,38,240,174,248};
  for (int i=0; i<len/4; i+=1){
    for (int j=0; j<4; j++){
      w[0][j] ^= stri[j+(4*i)];
    }
    f(w);
  }
  if (len%4!=0){
    for (int j=0; j<len%4; j++){
      w[0][j] ^= stri[j+(4*(len/4))];
    }
    for (int j=4-(len%4); j<4; j++){
      w[0][j] ^= 0;
    }
    f(w);
  }
  printf("0x%x%x%x%x\n", w[0][0], w[0][1], w[0][2], w[0][3]);
}

int main(int argc, char *argv[]){
  int x = strtol(argv[2], NULL, 10);
  char stri[x];
  strcpy(stri, argv[1]);
  tests(stri, x);
}

In order to get the flag I wrote a simple python script to generate permutations of letters, pass them as arguments to the C code and then retrieve the hash for comparisons.

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
from itertools import product
import subprocess, os, sys

li = []

def allwords(chars, length):
    for letters in product(chars, repeat=length):
        yield ''.join(letters)

def main():
    letters = "abcdefghijklmnopqrstuvwxyz"
    global li
    for wordlen in range(1, 26):
        for word in allwords(letters, wordlen):
            print(word)
            hash = subprocess.Popen(["./Citro", word, str(len(word))], stdout=subprocess.PIPE, stderr=subprocess.PIPE).communicate()[0].strip()
            print hash
            if hash in li:
                print li
                print word, hash
                sys.exit()
            else:
                li.append(hash)

if __name__=="__main__":
    main()

After running it for a few seconds we get our output back, a collision was found!

1
2
pa 0xba847264
ap 0xba847264

Therefore, I do the following Curl request and get the flag:

1
curl -X POST http://fun.ritsec.club:8003/checkCollision --header "Content-Type: application/json" --data '{"str1": "pa", "str2": "ap"}'

Output

1
2
3
4
{
  "flag": "RITSEC{I_am_th3_gr3@t3st_h@XOR_3v@}",
  "success": true
}

Diego Bernal Adelantado
This post is licensed under CC BY 4.0 by the author.