Inshall'hack
Security if God wills it
Inshall'hack

# protation Writeup (ECSC Qualifier Finals 2019/LeHack 2019)

(EDIT 2019/07/12: added an alternative solution from the author of the challenge)

(Note: writeup brought to you by Casimir/SIben and Mathis)

protation was a 200-point challenge at the ECSC Qualifier, worth 600 points once given first blood + presentation points. On the side of LeHack, it was valued at 350 points.

We, Casimir (aka SIben) and Mathis, were flagging for different competitions (but playing for Inshall'hack in both cases), and were pursuing similar approaches, so we ended up joining our efforts.

Although the challenge remained unsolved during the competition, we were about 99% done when it ended. It took us about 30 minutes (after a much needed night of sleep) to figure out what was going wrong and to get the correct solution. While this is a huge disappointment, we had a great time trying to figure out this challenge and we thank its author profusely for that!

# Challenge description

```Can you find the right input that will output the flag?
(Note: no bruteforce needed)
```

# Analysis

The provided file contains the following source code:

```import sys
import binascii
import random
import string
import hashlib
from random import randint
from flag import flag

N = 8

rol = lambda val, r_bits, max_bits:                          \
(val << r_bits%max_bits) & (2**max_bits-1) |               \
((val & (2**max_bits-1)) >> (max_bits-(r_bits%max_bits)))

def p(s):
sys.stdout.write(s)
sys.stdout.flush()

def check(N, S):
assert len(S) == 2**N-1, "Error: the sequence should be of length {}".format(2**N-1)
rotations = [ randint(0, N-1) for _ in range(2**N-1) ]
SS = [ rol(S[i], rotations[i], N) for i in range(2**N-1) ]
values = 
tmp = 0
for i in range(2**N-1):
tmp ^= SS[i]
values += [tmp]
return len(set(values)) == 2**N

def anti_bruteforce_PoW(difficulty):
randstr = ''.join(random.choice(string.ascii_letters) for _ in range(32))
print("Enter a string S such that the {} most signicant bits".format(difficulty))
print("of sha256(P||S) are zeros, with the prefix P is defined as");
print("P = {}".format(randstr))
S = input(">> ")
randstr += S
m = hashlib.sha256()
m.update(randstr.encode())
h = m.digest()
bits = "{:0256b}".format(int(h.hex(), 16))
return bits[:difficulty] == "0"*difficulty

'''
def solve_PoW(prefix, difficulty):
while True:
suffix = ''.join(random.choice(string.ascii_letters) for _ in range(32))
randstr = prefix + suffix
m = hashlib.sha256()
m.update(randstr.encode())
h = m.digest()
bits = "{:0256b}".format(int(h.hex(), 16))
if bits[:difficulty] == "0"*difficulty:
return suffix
break
'''

if __name__== "__main__":

## Welcome
p("Algorithmic challenge\n")
p("---------------------\n")
assert (N!=0) and ((N&(N-1)) == 0), "Error: N must be a power of 2."

## Anti-brutefoce
p("Before starting the actual challenge, we limit the access by a proof-of-work mechanism.\n")
if not anti_bruteforce_PoW(18):
p("Error: Please retry solving the PoW.\n")
exit(1)

## Actual challenge
p("You passed the PoW verification!\n")
p("You can now attempt to solve the challenge:\n")
while True:
s = input(">>> ")
try:
s = list(binascii.unhexlify(s))
if len(s) == 2**N - 1: break
except:
pass

## Check of the solution
if check(N, s):
p("Congrats!! Here is the flag: {}\n".format(flag))
else:
p("Not Good.\n")
```

## High-level summary

The code first asks for some kind of proof of work to discourage bruteforce attacks. Once the right proof has been provided, a hex-encoded string representing 255 (2N-1, N = 8) 8-bit characters is requested. That string is then checked in some way using the appropriately named `check` function. If the check goes through, the flag is printed.

In the following, we always assume N = 8 unless stated otherwise.

## The check function

The check function contains most of the interesting logic of the program.

```def check(N, S):
assert len(S) == 2**N-1, "Error: the sequence should be of length {}".format(2**N-1)
rotations = [ randint(0, N-1) for _ in range(2**N-1) ]
SS = [ rol(S[i], rotations[i], N) for i in range(2**N-1) ]
values = 
tmp = 0
for i in range(2**N-1):
tmp ^= SS[i]
values += [tmp]
return len(set(values)) == 2**N
```

First, a list named `rotations` and containing 255 values between 0 and 7 is generated.

Then, the function `rol` (parameterized with N) is mapped to every byte of the input and a corresponding element within `rotations`, and the result is stored into `SS`

Third, with two variables `values` and `tmp` respectively initialized to `` and `0`, the latter is successively xored with every element of `SS`, and the result of the operation is stored into `values` at each step.

Finally, the function checks that the resulting set of values contains exactly 256 elements.

```rol = lambda val, r_bits, max_bits:                          \
(val << r_bits%max_bits) & (2**max_bits-1) |               \
((val & (2**max_bits-1)) >> (max_bits-(r_bits%max_bits)))
```

As hinted in the code for `check`, `rol` achieves a simple rotation of `val` to the left by `r_bits` assuming a buffer of length `max_bits`.

To get `len(set(values)) = 256`, we need to get a different value for `tmp ^= SS[i]` at each step (since `SS` contains 255 elements), and `SS[i]` must not be `0` (since `values` already contains 0).

## Subtle hints and reducing the search space

First, obviously, we know that there can be no `\x00` in the bytes we send, as any rotation of `\x00` would still be `\x00` and given a starting value `a` of `tmp`, we have `a ^ 0 = a` which makes us automatically fail the "different value at every step" requirement.

Second, we assume that the right input must result in the flag being printed reliably (which is emphasized by the "no bruteforce" indication): this means that, since the rotations are random, we must be able to consider all the possible rotations of a given byte as equivalent (for example, 10101100 and 01011001 would be equivalent). Thus, using the following code

```def is_permutation(x, y, N):
for i in range(8):
if rol(x, i, N) == y:
return True
return False

def make_equivalence_classes(N):
equivalence_classes = []

for i in range(1, 2**N):
for eqc in equivalence_classes:
if is_permutation(i, eqc, N):
break
else:
equivalence_classes.append(i)
return equivalence_classes

equivalence_classes = make_equivalence_classes(8)
```

we reduce our possible input bytes to the following set of 35 equivalence class representatives:

```equivs = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 37, 39, 43, 45, 47, 51, 53, 55, 59, 61, 63, 85, 87, 91, 95, 111, 119, 127, 255]
```

Third, 255 is represented as 0b11111111. Rotating 255 by any value will always result in 255, and xoring any byte with it is the same as obtaining the unsigned byte's bitwise complement. This means that for each new value we have in `tmp` at step i, we will be able to generate its bitwise complement in step i + 1 if `SS[i + 1] = 255`.

We can guess that the solution will have the following pattern:

`[255, byte1, 255, byte3, …, 255, byte253, 255]`

where every other value is one of `equivs \ 255`.

(Note that to make use this pattern, we HAVE to have 255 as our first value, as we will not be able to generate it otherwise.)

While these insights are good, they are not yet sufficient to generate a solution. A good way to tackle this kind of problem is generally to figure out an approach that works for smaller problems and then generalize it.

To pick the size of the smaller problems we'll look into, we benefit from a hint in the source code once more:

```assert (N!=0) and ((N&(N-1)) == 0), "Error: N must be a power of 2."
```

We thus decide that our test cases will be for `N = 2` and `N = 4`.

## N = 2

For the sake of the example, we can generate the two non-zero equivalence classes and their representative for N = 2 by hand:

Representative Class members
10 10 01
11 11

Using our predefined scheme, there is only one sequence over three rounds we can generate: Let's check that we actually generate all the possible values. We need to check that it indeed works in both cases, as `SS` may contain 0b10 or 0b10. On each of the following screenshots, `tmp` always contains the same value as the last element of `values`: Works fine for the first branch. Since 0b11 works as a NOT here, it is trivial to see that it also works in the second case. Nevertheless, let's check: Alright, so our method checks out for N = 2. However, there is no real other insight to extract here. Let's move on to N = 4.

## N = 4

This case is a bit longer to figure out by hand, as there are more equivalence classes and more holes. BUT, it is still a small enough problem that we can solve it easily by bruteforcing it on our machines. We write the following piece of code:

```N = 4

# Taking [:-1] to ignore 0xf, since results are ordered
equivalence_classes = make_equivalence_classes(N)[:-1]

for possible_arrangement in itertools.product(equivalence_classes, repeat=7):
result = [0xf]
for i in range(7):
result.append(possible_arrangement[i])
result.append(0xf)

# Loop to avoid false positives
for _ in range(100):
if not check(N, result):
break
else:
print(result)
```

Running the program, we find two very similar results:

`[15, 5, 15, 3, 15, 5, 15, 1, 15, 5, 15, 3, 15, 5, 15]` and `[15, 5, 15, 3, 15, 5, 15, 7, 15, 5, 15, 3, 15, 5, 15]`.

Only the central number varies between the two. Let's try to represent the first result using a table like before: We can make two interesting observations here:

First, the result can be represented as a binary tree where the two subtrees of every node are always equal, and the number at the center of the resulting list is the root of the tree. This is represented as the following: and can be generated like a Gray (or binary reflected) code:

```values = [15, 5, 3, 1]
tree = []
for v in values:
tree = tree + [v] + tree
```

The second observation is also very important: the result is mostly made up of the solution we found for N = 2: We should therefore be able to reuse this result for N = 8 the same way we could reuse the result for N = 2 here.

# Solving for N = 8

Using our previous result, we can deduce that the first 15 rounds of our result should be the following: which can thus be generated using the reflected binary construction:

```values = [0b11111111, 0b10101010, 0b00110011, 0b00010001]
tree = []
for v in values:
tree = tree + [v] + tree
```

To get the 255 values we need, we have to bruteforce 4 numbers to append them to values. Since we have only 34 possible equivalence class representatives to choose from, we have only 344 = 1336336 possibilities. We write the following code:

```N = 8

# Taking [:-1] to ignore 0xff, since results are ordered
equivalence_classes = make_equivalence_classes(N)[:-1]

# FYI, this is where we failed at copying one value, and why we didn't get the flag in time
starting_values = [0b11111111, 0b10101010, 0b00110011, 0b00010001]

for possible_arrangement in itertools.product(equivalence_classes, repeat=4):

values = starting_values + list(possible_arrangement)
tree = []

for v in values:
tree = tree + [v] + tree

# Loop to avoid false positives
for _ in range(100):
if not check(N, tree):
break
else:
# Converting to the right format for submission
print(''.join(hex(n)[2:].zfill(2) for n in tree))
# We only need one result
break
```

And we get the following string: ffaaff33ffaaff11ffaaff33ffaaff0fffaaff33ffaaff11ffaaff33ffaaff05ffaaff33ffaaff11ffaaff33ffaaff0fffaaff33ffaaff11ffaaff33ffaaff03ffaaff33ffaaff11ffaaff33ffaaff0fffaaff33ffaaff11ffaaff33ffaaff05ffaaff33ffaaff11ffaaff33ffaaff0fffaaff33ffaaff11ffaaff33ffaaff01ffaaff33ffaaff11ffaaff33ffaaff0fffaaff33ffaaff11ffaaff33ffaaff05ffaaff33ffaaff11ffaaff33ffaaff0fffaaff33ffaaff11ffaaff33ffaaff03ffaaff33ffaaff11ffaaff33ffaaff0fffaaff33ffaaff11ffaaff33ffaaff05ffaaff33ffaaff11ffaaff33ffaaff0fffaaff33ffaaff11ffaaff33ffaaff that passes the required checks!

I guess this is the too-late version of flagging:

```\$ python protation.py
You passed the PoW verification!
You can now attempt to solve the challenge:
>>> ffaaff33ffaaff11ffaaff33ffaaff0fffaaff33ffaaff11ffaaff33ffaaff05ffaaff33ffaaff11ffaaff33ffaaff0fffaaff33ffaaff11ffaaff33ffaaff03ffaaff33ffaaff11ffaaff33ffaaff0fffaaff33ffaaff11ffaaff33ffaaff05ffaaff33ffaaff11ffaaff33ffaaff0fffaaff33ffaaff11ffaaff33ffaaff01ffaaff33ffaaff11ffaaff33ffaaff0fffaaff33ffaaff11ffaaff33ffaaff05ffaaff33ffaaff11ffaaff33ffaaff0fffaaff33ffaaff11ffaaff33ffaaff03ffaaff33ffaaff11ffaaff33ffaaff0fffaaff33ffaaff11ffaaff33ffaaff05ffaaff33ffaaff11ffaaff33ffaaff0fffaaff33ffaaff11ffaaff33ffaaff
Traceback (most recent call last):
File "protation.py", line 82, in <module>
p("Congrats!! Here is the flag: {}\n".format(flag))
NameError: name 'flag' is not defined
```

# Alternative solution

The author of the challenge kindly provided us with his solution which showcases the pattern in a more elegant way. With his permission, we share it here with some annotations:

```def solve(N):
assert bin(N).count('1') == 1, "Error: N must be a power of 2."

if N == 1: return 

N_half = N//2
seq_half = solve(N_half)

# This is equivalent to our step describing the first
# 2**(N/2) - 1 rounds of the output using results for N / 2,
# i.e. it takes a N/2-bit pattern s to a N-bit pattern s . s,
# where . describes concatenation.
# The solution for N/2 is being applied to both halves of the
# N output bits.
tmp = [ (x*2**N_half) ^ x for x in seq_half]
seq = []

# This loop interleaves the solution for N/2 applied on both
# halves of the N output bits with it applied on the lower
# half of the N output bits.
# We would also find a solution by applying it on the upper
# half of the N output bits instead.
for s in seq_half:
seq += tmp
# The following line can be replaced by
# `seq += [ s << N_half ]`
# to produce another working solution.
seq += [s]
seq += tmp
return seq
```

This construction can be observed in this illustration from our solution: # Conclusion

Good sleep is underrated.

Thanks again to all the organizers of both ECSC and LeHack for a nice set of challenges!

comments powered by Disqus

ATOM