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.

Super salt

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 = [0]
    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 = [0]
    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 [0] 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:

2-bit example

Let's check that we actually generate all the possible values. We need to check that it indeed works in both cases, as SS[1] may contain 0b10 or 0b10. On each of the following screenshots, tmp always contains the same value as the last element of values:

2-bit branch 1

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:

2-bit branch 2

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:

4-bit branch working example

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:

Binary tree

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:

Reuse of N=2 result for N=4

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:

Deduced first 15 rounds for N = 8

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 [1]

    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:

Reuse of N=2 result for N=4

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

Receive Updates

ATOM

Contacts