April 21st, 2016 · CTF Writeup

Linear-Feedback Shift Register is not Random

Continuing the unnamed CTF write-up series, today I will be presenting my tought process and solution to the last level of a cryptography-oriented challenge. Cracking this challenge took a few days, mostly due to my lack of free time and also because I was unable to find any hints online or people on IRC whose brains to pick in regards to this challenge.

The previous levels of this CTF used a few primitive ciphers, ranging from ROT-13 to Vigenère, however the final level is supposed to get more serious, moving from text-level ciphers to byte-level. The cipher itself is not mentioned, only that hex editors are required beyond this level. A directory is available with a sample key file, an example plain text and its resulting cipher text. Another executable binary is also available, which allows us to encrypt any arbitrary text with the same key which was used to encrypt the password of the next level, thus introducing the element of chosen-plaintext attack.

Fiddling around with the provided files in CrypTool was not going anywhere, therefore I decided to look at the provided HINT2 file, which hints at the encryption method being an 8-bit LFSR.

LFSR just generates a byte stream, which is then XOR'd to the source file, making the encryption same as the decryption process. Given a key, (z1,z2,...,zm)(z_{1}, z_{2}, ..., z_{m}), the byte stream is generated according to the following linear relationship:

zi+m=c0zi+c1zi+1+...+cm1zi+m1z_{i+m} = c_0 z_i + c_1 z_{i+1} + ... + c_{m-1} z_{i+m-1}

where i1i \ge 1 and c0,c1,...,cm1c_0, c_1, ..., c_{m-1} are predetermined constants.

My first thought was to try and use the provided encryption binary on the encrypted password file to perform a decryption. That, however, would've been too simple, and obviously didn't work. There is a known-plaintext attack on LFSR (when applied with XOR), where you can recover the byte stream LFSR generated by simply XOR'ing the known and cipher files, and then using the result to decrypt other encrypted files. As such, the following Python script was born:

with open("plain.txt") as pf, open("cipher.txt") as cf, open("krypton7") as kf:
    while True:
        p = pf.read(1)
        c = cf.read(1)
        k = kf.read(1)

        if not c or not p or not k:
            break

        print(chr(ord(p)^ord(c)^ord(k)), end='')

This should be it:

$ python test.py
TFW_I_T_JJARBMW
$ ssh <censored>
<censored>'s password:
Permission denied, please try again.

Unfortunately, it was not.

Since I ran out of ideas to try, I grabbed the encrypt6 binary from the server (using scp, since network connections are otherwise blocked) and threw it into IDA. As the HINT2 file said, there is an lfsr() function in the binary:

__int64 lfsr()
{
    reg_2690 = (reg_2690 >> 1) | 8 * (reg_2690 & 1 ^ ((reg_2690 & 2) >> 1));
    return reg_2690;
}

However, if this is all it did, then the previous XOR trick should've worked, which suggests that LFSR is only one half of the process. A quick look at where this function is called leads to this function block:

v13 = lfsr(v4, "w");
v11 = 0;
while (!feof(v15))
{
    if (v11 >= v12)
        v11 = 0;
    v5 = fgetc(v15);
    v9 = toupper(v5);
    if (v9 != 32 && isalpha(v9))
    {
        for (i = v9 - 65 + v17[v11] + v13 - 65; i > 25; i -= 26);
        v6 = (i + 65);
        fputc(v6, v16);
        ++v11;
        v13 = lfsr(v6, v16);
    }
}

As we can see, the encryption process consists of subtracting "A" from the character, adding a character to it from the keyfile (v17[v11]) plus the output of the LFSR (v13). The challenge description states that a static key and a random number is used during the encryption, however, as it has no calls to any rand functions, it seems that the LFSR is supposed to be the source of the randomness.

Studying the for loop in the disassembled code leads me to modifying the above Python script with the following changes:

with open("cipher.txt") as cf, open("krypton7") as pf:
    while True:
        c = cf.read(1)
        p = pf.read(1)

        if not c or not p:
            break

        c = ord(c)-<censored>
        p = ord(p)-<censored>
        k = p-c

        if k < 0:
            k += <censored>

        print(chr(k+<censored>), end='')

So, let's give it a try:

$ python test.py
LFSRIS<censored>
$ ssh <censored>
<censored>'s password:
krypton7@melinda:~$ wechall
Registering this level with WeChall...
You gained 0.62% (155 points) on <censored>.

Time for the victory dance.