RITSEC CTF: CictroHash write-up
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
Mathematical definition of f
Functions
All of them will have as an argument a matrix of 2x4, as defined in the PDF:
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.
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
}