PicoCTF 2018 - KeyGen 2 WriteUp

This is a more advanced version of KeyGen 1.

In order to make this writeUp shorter, I will skip parts equal to keyGen 1.

So please, have a look at that before:

https://pwnthemole.github.io/reverse/2018/10/18/PicoCTF2018-KeyGen1.html

Here we have the same “check_valid_key” function
which check if the key is 16 chars long and it has only chars in range (0:9 and A:Z)

But the “validate_key” is different.

AltText

as you can see, there are several checks on the strings (12).
If the string respect all the constraint we get the flag.

constraints are quite easy, here is an example:

AltText

it uses the same ord function of KeyGen 1 and a mod function (that perform a simple mod operation).
in this first example, the constraint is

1
ord(string[0])+ord(string[1])%36 == 14

reversing all the functions, here we have all the constraints

1
2
3
4
5
6
7
8
9
10
11
12
1) return ((sol[0]+sol[1])%36)==14;
2) return ((sol[2]+sol[3])%36)==24;
3) return ((sol[2]-sol[0])%36)==6;
4) return ((sol[1]+sol[3]+sol[5])%36)==4;
5) return ((sol[2]+sol[4]+sol[6])%36)==13;
6) return ((sol[3]+sol[4]+sol[5])%36)==22;
7) return ((sol[6]+sol[8]+sol[10])%36)==31;
8) return ((sol[1]+sol[4]+sol[7])%36)==7;
9) return ((sol[9]+sol[12]+sol[15])%36)==20;
10) return ((sol[13]+sol[14]+sol[15])%36)==12;
11) return ((sol[8]+sol[9]+sol[10])%36)==27;
12) return ((sol[7]+sol[12]+sol[13])%36)==23;

Due to the simplicity of constraints, it’s quite easy to use them in a brute-force with enough pruning.

Here is the link of the script I used:

https://github.com/pwnthemole/ctfs/blob/master/PicoCTF2018-KeyGen2/main.cpp

It produces the key in less than 1 second: 0E6IW8BX07K**Q9D

I also tried to implement this with a z3 script.

here is the script:

https://github.com/pwnthemole/ctfs/blob/master/PicoCTF2018-KeyGen2/z3_script.smt2

it produced a different (but still correct) key, but it took 1 night

XxcoralloxX