Inshall'hack
Security if God wills it
Inshall'hack

Bitshift Writeup (Sogeti Cyber E-Scape 2019 Qualifier)

Bitshift was the only cryptography challenge of the qualifier (among 8) and one of the least solved of the competition. I personally believe it was the most interesting one, and featured a technique that I never really got to work with before.

There are better solutions than the one I will present in this writeup for this particular challenge. However, I argue that the method I used works in a more generic context and is thus probably worth reading about.

Side note: There was no official Inshall'hack team for the event, and I thus competed with my friends Calin42, Fumik0, Geluchat and GlaCiuS in the team Délicieux et Salé. Although our performance was fairly unimpressive, we [probably] secured a spot in the finals that will take place in Paris at the end of March.

Challenge description (translated from French)

We managed to obtain an account on the Shadow League's message exchange web server available at the following address:
id
http://quals.shadow-league.org:8002

The account, "test:test" (very original), doesn't have many permissions.
Will you be able to escalate your privileges?
Our information also reveals that the developer of the website failed his cryptography exam…

Discovery

The front page of the website consists of the following login page:

Login page

Logging in with the provided credentials redirects us to the following page:

Logged in page

No cookie has been set, and it doesn't seem like we can do much with this. Let's login again while ticking the "Remember me" box this time:

Cookie request

That's more like it! This time, we have two cookies: userid (which is 500, as we can see on the page) and rememberme, which is a 6-letter apparently hex value: DC7AC6.

Incrementing or decrementing the value of the userid cookie (and keeping the rememberme cookie unchanged), we get different results.

For userid=501:

Invalid cookie

For userid=499:

Invalid user id

Interesting! Seems like we can enumerate the ids of all the valid users from this. We whip out this quick'n'dirty script:

for i in `seq 1 1000`;
    do res=`curl -s 'http://quals.shadow-league.org:8002/index.php' -H "Cookie: userid=$i; rememberme=DC7AC6" | grep "Invalid user id"`;
    if [ -z "$res" ]; then
        echo $i;
    fi;
done;

Good! With this, we get the following list of valid ids: 100, 400-412, 500-512 and 600-612. Doesn't seem like we can do much with them for now. Let's check out the rememberme.php page.

We try to call it with other valid userids in the userid parameter, but we're basically told that we are not permitted from getting the cookie. Fair enough, that would have been too easy.

Changing the userid parameter to a random string, however, returns the following error message:

LFSR - number of iterations must be an integer

Now we're getting somewhere! It seems like userid defines the number of iterations to apply on a starting state to generate the rememberme cookie. We can therefore also guess that this LFSR has 24 bits (6 hex characters in the cookie).

Side note: people who never heard anything about LFSR might want to read the first few lines of the Wikipedia page before proceeding to read the rest of this writeup.

Deducing subsequent values of the LFSR

Since we know the state at iteration 500 (the value of the rememberme cookie for userid=500), we are able to restrict the possible values at iteration 501 to only 4, since for the binary state Si of a n-bit LFSR, the next state is calculated in one of those two ways:

1) Si+1 = Si[1:N] + LFSR(Si);

2) Si+1 = LFSR(Si) + Si[0:N-1]

where LFSR(Si) is a bit.

By testing all four possible cookies for userid=501, we find out that the second direction is used.

We then use the following script to retrieve the rememberme cookie value for userids from 501 to 512:

import requests

state = 0xDC7AC6

new_states = {}

for idx in range(501, 513):
    next_state = {0: state >> 1, 1: state >> 1 | (1 << 23)}

    for i in range(len(next_state)):
        headers = {'Cookie': 'Cookie: userid=' + str(idx) + '; rememberme=' + hex(next_state[i])[2:]}
        text = requests.get('http://quals.shadow-league.org:8002/index.php', headers=headers).text

        if not 'Invalid' in text:
            new_states[idx] = hex(next_state[i])[2:]
            state = int(new_states[idx], 16)
            break

print(new_states)

And we end up with this unsorted dictionary of cookies:

{500: 'DC7AC6', 512: '6fbdc7', 501: 'ee3d63', 502: 'f71eb1', 503: '7b8f58',
504: 'bdc7ac', 505: 'dee3d6', 506: 'ef71eb', 507: 'f7b8f5', 508: 'fbdc7a',
509: '7dee3d', 510: 'bef71e', 511: 'df7b8f'}

Now, using these, we're able to navigate all of those user profiles as well. None of them contain anything remotely interesting, except for user 502, that seems to contain some sort of /etc/shadow, with hashes for at least users 600 and 400. We also learn that user 100 is the admin, and that this is probably the account we want to control (at the time of this writeup, the challenge is down, I am therefore unable to provide a screenshot. However, I didn't use the hashes in any way for my solution, so it doesn't matter much).

Cracking the case of the missing polynomial

Now, by cracking the hash for user 600 (which was very much crackable), one would be able to gather enough information to recreate the polynomial used for the LFSR, and therefore to generate a valid cookie for user 100. Unfortunately for me, I didn't really pay attention to the hashes; the reason for that is that the LFSR is already bruteforceable with a reasonable amount of requests.

Indeed, by gathering the cookie for users 500-512, we have gathered a starting state and 12 equational constraints on the polynomial. Since we know that the polynomial is 24-bit long, there were 224 = 16777216 possible polynomials to begin with. With 12 equational constraints, that number is reduced to 212 = 4096, which is low enough to actually get a result in a reasonable time.

It's then quite trivial to generate all the possible polynomials using z3:

import requests
from z3 import *

# Polynomial application function
def apply_poly(arr, poly):
    return reduce(lambda x,y: x ^ y, [bool(int(x)) and bool(int(y)) for (x, y) in zip(arr, poly)])

s = Solver()

# Unknown polynomial
polynomial = BoolVector('x', 24)

# Gathering all the known bits information
dic = {500: 'DC7AC6', 512: '6fbdc7', 501: 'ee3d63', 502: 'f71eb1', 503: '7b8f58',
504: 'bdc7ac', 505: 'dee3d6', 506: 'ef71eb', 507: 'f7b8f5', 508: 'fbdc7a',
509: '7dee3d', 510: 'bef71e', 511: 'df7b8f'}

# Using all the known states to recreate the stream
bknown_bits = bin(int(dic[500], 16))[2:].zfill(24)[::-1] + ''.join(bin(int(dic[x], 16))[2:].zfill(24)[0] for x in sorted(dic)[1:])

# Generating a list of booleans from the stream 
known_bits = [True if c == '1' else False for c in bknown_bits]

# Adding the constraints to the solver
for i in range(24, len(known_bits)):
    s.add(reduce(lambda x,y: Xor(x, y), [And(x, y) for (x, y) in zip(polynomial, known_bits[i - 24:i])]) == known_bits[i])

while s.check() == sat:
    # Setting the starting state of the LFSR
    toeval = known_bits[:24]

    # Generate a possible polynomial
    m = s.model()

    # Build the polynomial
    poly = bin(sum(int(bool(m[polynomial[i]])) << i for i in range(24)))[2:].zfill(24)

    # Run the LFSR 100 times starting from state 500 to get to state 600
    for _ in range(100):
        toeval = toeval[1:] + [apply_poly(toeval[::-1], poly)]

    # Building the cookie
    possible_cookie = hex(sum(toeval[i] << i for i in range(24)))[2:]

    # Trying to query the server with the cookie set for user 600
    text = requests.get('http://quals.shadow-league.org:8002/index.php', headers={'Cookie': 'Cookie: userid=600; rememberme=' + possible_cookie}).text

    if not 'Invalid cookie' in text:
        print(possible_cookie)
        print(m)
        print(count)
        exit()

    # Adding a constraint that this polynomial can not be produced again in order to always get different results
    s.add(Not(reduce(lambda x,y: And(x, y), [polynomial[i] == m[polynomial[i]] for i in range(24)])))

Running that script, we get the polynomial [True, False, True, False, True, False, True, False, True, False, True, False, False, True, False, True, True, True, False, True, True, False, False, False], or '101010101010010111011000', in a cleaner way.

Using the polynomial to generate the cookie for user 100

OK, now, we have found the polynomial, but our starting state is set at 500 iterations. How the heck are we going to get to 100 iterations? Well, for starters, the operation is totally invertible, so we can just build the inverse function by mirroring the taps and run it 400 times on the state to generate our cookie.

This is very straightforward to do, but in the spirit of sharing "interesting" stuff, know that we can also do this in a different (though less efficient) way; indeed, LFSRs are periodic. That's right, for a given LFSR of period p, a starting state Si and k a positive integer, we have the following equation:

Si - j = LFSRkp - j(Si)

The maximum possible period for a n-bit LFSR is 2n - 1, which, for our 24-bit LFSR, corresponds to 224 - 1 = 16777215. It is trivial to find the period of any LFSR: just count the number of steps it takes to go from a state to itself.

For our LFSR, the period is maximal, therefore, the following script also generates the cookie:

def apply_poly(arr, poly):
    return reduce(lambda x,y: x ^ y, [bool(int(x)) and bool(int(y)) for (x, y) in zip(arr, poly)])

known_bits = [True if c == '1' else False for c in '011000110101111000111011110111110110']

poly_bits = [True, False, True, False, True, False, True, False, True, False, True, False, False, True, False, True, True, True, False, True, True, False, False, False]

toeval = known_bits[:24]

poly = bin(sum(poly_bits[i] << i for i in range(24)))[2:].zfill(24)
print poly

# 16777215 - 400
for _ in range(16776815):
    toeval = toeval[1:] + [apply_poly(toeval[::-1], poly)]

possible_cookie = hex(sum(toeval[i] << i for i in range(24)))[2:]
print(possible_cookie)

We use the generated cookie to log into the account of user 100 and… Flagged!

Flag: SCE{Ze_Crypt0_Fl4g_H@GHG#FHGVK__JVYDRUFJKHJ9875423}

Conclusion

Definitely a great challenge I'm happy I solved! I can't wait to see what the challenges will be in the finals :)


comments powered by Disqus

Receive Updates

ATOM

Contacts