solving futuretran 2019@ctf@hack.lu (original URL: https://fluxfingersforfuture.fluxfingers.net/challenges/35)

The task

Complex, unsafe languages are the past. We’ve built a new programming language for the future that uses only a fraction of the instructions of RISC. This should be easy, right?
In addition we have 2 files, flag.ftb and interpreter.py

Initial analysis of the interpreter.py

Gets 2 parameters, code (flag.ftb) and flag to check
Extracts from the code file the following parameters
- primes – list of prime numbers sorted starting from 2
- out – one more prime number
- state – one more prime number
- code – list of tuples of 2 mostly not prime numbers formatted as x/y
Expands initial state:
- multiplies the “state” by prime from the primes list power ord(corresponding character from the flag from command line)
Starts to excecute the “code”:

for each tuple in the “code” list of tuples in the order as defined in the input file it tries to multiply the current state by the first member,
if the result is divisible by the second number – it divides the state, stores it, and returns to the start of the tuples
if no successfull division occured for all the tuples the function returns the current state

Checks result:

if the state from the previous stage is not divisible by “out” parameter from the input file – we won

Initial observations on flag.ftb

The list of primes from the file contains 37 first primes
“state” and “out” are also prime numbers, but they are not in the first list of primes
tuples in the code are mostly not primes
after factorization of all the numbers in the flags.ftb we see at all 217 prime numbers (this includes primes list, state and out), from 2 to 1327.
the “out” from flag.ftb is not in the “prime” list from the same file. This means that the only way to mix it into the “state” is successfull multiplication during “code” execution

Work log

It took for me some time to understand what exactly the interpreter.py does but after that the first thing I did was inserting some logging into the “code” execution and looking to the order of executed “code” tuples while analysing obviously false flags like flag{xxxxxxxxxxxx}. In addition I marked prime numbers associated with flag letters as FL_{num}, where num is a number of the letter in the flag and prime number associated with “out” parameter as “INDICATOR”.

Here is what I saw:

There are a long sequences of instructions where primes associated with flag letters are removed from state one by one and factor 257 is added in same quantities.
After each long sequence like this 257 is removed from the state by portions with sizes 64, 32, 16, 8, 4, 2 and 1 and different other primes added each time
After this we have something not too much understandable
Somewhere in the middle of the execution the “out” prime starts to appear in the “state”, which probably means that the flag is incorrect.
Sometimes it is cleared from the “state”, but after that it always returns.

Then I had the first aha moment: whatever RISC program we are running, the “state” is its memory. It looks like that primes in the “state” are similar to variable names, and amount of these primes inside the “state” are these variable values. This actually means that every successful multiplication means addition to all its factors related variables, and division is actually subtraction correspondingly.

Let’s see it on the following example:

if state equals to 30 (235) it can be represented as 3 variables labeled v2, v3, and v5, and their values are {1,1,1} correspondingly.
if we want to multiply it by 3 and divide it by 5, the resulting state will look like {1, 2, 0} correspondingly and so on.

After understanding that I updated the logging and started to see there more understandable logs like this:

96 { FL_1:1,svc601:1,} { CNT:1,svc599:1,} # number of current “instruction” in the “code” {factorized first number of the tuple} {factorized second number of the tuple}
[ FL_1 ]: 64 –> 63 # amount of primes associated with 2nd letter of the flag decremented by 1
[ CNT ]: 44 –> 45 # a variable associated with prime 257 incremented by 1
[ svc599 ]: 0 –> 1 # service variable associated with 599 decremented
[ svc601 ]: 1 –> 0 # service variable associated with 601 incremented
95 { svc599:1,} { svc601:1,}
[ svc599 ]: 1 –> 0
[ svc601 ]: 0 –> 1
96 { FL_1:1,svc601:1,} { CNT:1,svc599:1,}
[ FL_1 ]: 63 –> 62
[ CNT ]: 45 –> 46
[ svc599 ]: 0 –> 1
[ svc601 ]: 1 –> 0
95 { svc599:1,} { svc601:1,}
[ svc599 ]: 1 –> 0
[ svc601 ]: 0 –> 1
96 { FL_1:1,svc601:1,} { CNT:1,svc601:1,}
[ FL_1 ]: 62 –> 61
[ CNT ]: 46 –> 47
[ svc599 ]: 0 –> 1
[ svc601 ]: 1 –> 0
95 { svc599:1,} { svc601:1,}
[ svc599 ]: 1 –> 0
[ svc601 ]: 0 –> 1

OK, stores and loads of our RISC program are understood.

And then (after a lot of staring into the logs in order to find control flow instructions and mapping service variables)
I had the second aha moment:
I don’t need the program. I don’t need to understand the meaning of each specific variable. I probably don’t need to reverse the “program” at all.
Traces are probably enough. We just need to avoid appearance of “out” as a factor in state.

After that I started to analyze the loads and stores of execution order. And then I understood
that the full log of the execution looks like following:

do something not clear
decrease FL_0 and increase CNT
do something with CNT
do something not clear
decrease FL_1 and increase CNT
do something with CNT
do something not clear
decrease FL_2 and increase CNT
do something with CNT
do something not clear
decrease FL_3 and increase CNT
do something with CNT
do something not clear
decrease FL_4 and increase CNT
do something with CNT
do something not clear
decrease FL_5 and increase CNT <– it looks like that here we are checking the first letter in the flag that we don’t know (the start of flag is known: flag{ )
- do something with CNT
- do something not clear
- INDICATOR starts to change <– here we see evidence of the problem
- do something not clear
- decrease FL_6 and increase CNT
- do something with CNT
- do something not clear
- INDICATOR starts to change <– problem persists
- do something not clear
- decrease FL_7 and increase CNT
- do something with CNT
- do something not clear
- INDICATOR starts to change <– problem persists
  ………
- return wrong value

I checked it with “fla” instead of “flag{” in the start of the flag. The problem started to appear earlier in trace. Understanding this allowed me to build the brute force which actually does the following:

    for c in flag_alphabet:
        current_flag += c
        for (a,b) in "code":
            store last letter index we worked with
            return the last letter if we see that "INDICATOR" is in
        if we see advance in letter index, remember the flag and break

The script is attached, here is the partial log of its run, and as you can see it runs around 20 minutes only:

╰─$ date; ./brute.py flag.ftb sss
Thu Oct 24 16:52:03 IDT 2019
Starting … {2: 10, 3: 1}
primes
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157]
out
163 {163: 1}
state
269 {269: 1}
code
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997, 1009, 1013, 1019, 1021, 1031, 1033, 1039, 1049, 1051, 1061, 1063, 1069, 1087, 1091, 1093, 1097, 1103, 1109, 1117, 1123, 1129, 1151, 1153, 1163, 1171, 1181, 1187, 1193, 1201, 1213, 1217, 1223, 1229, 1231, 1237, 1249, 1259, 1277, 1279, 1283, 1289, 1291, 1297, 1301, 1303, 1307, 1319, 1321, 1327] 217
flag{o} FL_6
Thu Oct 24 16:52:06 IDT 2019
flag{on} FL_7
Thu Oct 24 16:52:10 IDT 2019
flag{onl} FL_8
Thu Oct 24 16:52:14 IDT 2019
flag{only} FL_9
Thu Oct 24 16:52:25 IDT 2019
… skipped …
… skipped …
… skipped …
… skipped …
flag{only_a_fraction_find_this_} FL_31
Thu Oct 24 17:01:47 IDT 2019
flag{only_a_fraction_find_this_f} FL_32
Thu Oct 24 17:02:32 IDT 2019
flag{only_a_fraction_find_this_fu} FL_33
Thu Oct 24 17:04:51 IDT 2019
flag{only_a_fraction_find_this_fun} FL_34
Thu Oct 24 17:06:35 IDT 2019
flag{only_a_fraction_find_this_funn} FL_35
Thu Oct 24 17:08:26 IDT 2019
flag{only_a_fraction_find_this_funny} 1327
Thu Oct 24 17:11:50 IDT 2019