**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:

Logging in with the provided credentials redirects us to the following 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:

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**:

For **userid=499**:

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 S

_{i}of a n-bit LFSR, the next state is calculated in one of those two ways:

1) S_{i+1} = S_{i}[1:N] + LFSR(S_{i});

2) S_{i+1} = LFSR(S_{i}) + S_{i}[0:N-1]

where **LFSR(S _{i}) 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 **2 ^{24} = 16777216 possible polynomials** to begin with.

**With 12 equational constraints, that number is reduced to 2**, which is low enough to actually get a result in a reasonable time.

^{12}= 4096It'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 S _{i}** and

**k a positive integer**, we have the following equation:

S_{i - j} = LFSR^{kp - j}(S_{i})

The maximum possible period for a n-bit LFSR is 2^{n} - 1, which, for our 24-bit LFSR, corresponds to **2 ^{24} - 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 :)