NSEC21 yeswehack - Mon, May 24, 2021 - Jean Privat

Python, maths and dot. | Rev Python | Nsec21

This NSEC21 challenge was contributed by a sponsor|.

Basically, it is a short Python script that validates a flag given by the user.

A python script

import re
from functools import reduce

FLAG_REG = re.compile(r"^\d{0,16}9$")
KEY = 0xC3F80B633F90C6DE
OPS = [
    lambda x: ([print(x), x][1]),
    lambda x: x - ((KEY >> (x - 8 & 56) >> (x & 7) & 1 ^ 1) & x >> 3) * 8 & 56 | x & 7,
    lambda x: x - ((KEY >> (x - 8 & 56) >> (x & 7) & 1 ^ 1) & ~x >> 3) * 8 & 56 | x & 7,
    lambda x: x + ((KEY >> (x + 8 & 56) >> (x & 7) & 1 ^ 1) & x >> 3) * 8 & 56 | x & 7,
    lambda x: x + ((KEY >> (x + 8 & 56) >> (x & 7) & 1 ^ 1) & ~x >> 3) * 8 & 56 | x & 7,
    lambda x: x & 56 | x + ((KEY >> (x & 56) >> (x + 1 & 7) & 1 ^ 1) & ~x) & 7,
    lambda x: x & 56 | x + ((KEY >> (x & 56) >> (x + 1 & 7) & 1 ^ 1) & x) & 7,
    lambda x: x & 56 | x - ((KEY >> (x & 56) >> (x - 1 & 7) & 1 ^ 1) & ~x) & 7,
    lambda x: x & 56 | x - ((KEY >> (x & 56) >> (x - 1 & 7) & 1 ^ 1) & x) & 7,
    lambda x: ["Good flag!", "Bad flag!"][x > 1],
]

if __name__ == "__main__":
    flag = input("FLAG-")
    if not FLAG_REG.match(flag):
        exit(1)
    print(reduce(lambda x, c: OPS[c](x), (int(c) for c in flag), 48))

The regex inform us that the flag is made of up to 16 digits and a final 9.

An interesting part is reduce(lambda x, c: OPS[c](x), (int(c) for c in flag), 48) and the OPS array:

• c is the current digit of the flag (so values are from 0 to 9)
• OPS is an array of 10 lambda functions (from 0 to 9).
• The lambda in the reduce executes the cth function of OPS on a value x.
• the reduce applies its given function in order on a value x. x starts at 48 but is updated on each digit of the flag. Basically, if the digits of the flag are c1, c2, …, cn then the computed value is ops(...(ops(ops(48, c1), c2), ...), cn).
• Digit 9 is the final one and validates the flag if the value x reaches 0.
• Note that the digit 0 is special and just print the value of x. It could be used for debugging.

The math part of OPS is not easy to read, and did force us to check the precedence of operators in Python. Maybe, we should try some flags first to see what are the kind of values we need to deal with.

Lets try it

$ python3 yeswehack.py 
FLAG-009
48
48
Bad flag!

• 0 just displays the current value of x, so 48 each time
• 9 just check if x == 0 (and it wasn’t)

Lets try it more

$ python3 yeswehack.py 
FLAG-10203040506070809
48
48
48
48
49
50
49
48

Oh, the values are quite manageable and not so diverse. Especially, we note that it is unlikely that the flag starts with 1, 2, 3 or 4 since x did not change and stay at 48.

Automaton

Instead of reverse engineering the OPS functions, why not check all the possibilities?

• Start on 48
• Run 8 functions (we do not care about 0 and 9)
• Get possibly some new values
• Run 8 functions on these new values
• Etc. until we visit everything.

# [...]
# Remove the `main` part but keep the rest of the code

todo = [48]
seen = [48]
print("digraph { rankdir=LR")
while todo:
    x = todo.pop(0)
    for c in range(1,9):
        k = OPS[c](x)
        if k != x:
            print(str(x) + " -> " + str(k) + "[label=" + str(c) + "]")
        if k not in seen:
            todo.append(k)
            seen.append(k)
print("}")

Note: the updated script just prints a graph in the graphviz format, so we can see what it looks like.

$ python3 yeswehack.py | xdot -

Et voilà…

No need to hack anymore, just follow the automaton with a finger or a mouse: FLAG-56456534873878219

$ python3 yeswehack.orig.py 
FLAG-56456534873878219
Good flag!

Acknowledgements

The challenge was solved thanks to the invaluable help of Lucas Bajolet.

Back to Home