# LIT CTF

## The Oracle's Prophecy
In this challenge, we're given an implementation of AES, which is remarkably similar to CBC mode. We're allowed to encrypt a string with some flavor text that contains the flag and then the user input. A MAC is appended at the end of the message before encryption, a SHA1 hash of a substring of the message from 223-239.

The message's padding is key to solving the problem. Rather than the traditional method of padding following a message, in this implementation, our padding precedes the message.

Secondly, there is a decryption oracle which allows you to decrypt a string, and see if the decrypted ciphertext has a valid MAC and valid padding.

def decrypt(self,ct):
    if(len(ct) % (2 * self.BLOCK_SIZE) != 0):
        print("Something went wrong while fulfilling the prophecy D:");
        return;
    iv = ct[:32];
    c = ct[32:];
    msg = self.decryptHex(iv,c);
    msg = self.check_padding(msg);
    if(msg):
        if self.check_MAC(msg):
            print("The prophecy is fulfilled!");
        else:
            print("Something went wrong while fulfilling the prophecy D:");
    else:
        print("Something went wrong while fulfilling the prophecy D:");
    return;

The check padding function checks the first byte of the message. It uses PKCS#7 padding, but doesn't actually check every byte. So, it simply removes the first n bytes of the message, if n is the first byte.

So, let's get into the specifics of what type of AES this is, if not CBC. Here's a diagram (THE diagram) that shows the encryption and decryption process of AES CBC:



The only difference between CBC and the implementation version is that ```prevXOR```, i.e. the IV that's used for a given block in the chain, is the ciphertext of the previous block in the chain for AES CBC, but ```ct ^ pt``` for our implementation.

So how do we do this decryption shtick. Well normally, in AES CBC, you alter the inputted IV, and as you can see in the diagram, that only affects the plaintext for the first block. That all changes in this implementation version, however. You'll notice that the final plaintext of every block is fed into the IV for the next one. So, if we take our original IV, and xor it with a new value, our entire outputted decrypted plaintext would be xorred by the new value as well.

That doesn't actually help us much, for two reasons. Firstly, the only way to leak the flag would be for it to be the very first block, so you can do some kind of padding oracle (which only operates on the first block). However, the flag isn't the first block yet, and we can't really put it there yet. Not to mention, xorring the whole message would ruin the outputted plaintext, since the SHA1 output would be ruined.

Somehow, we need to change our ciphertext to get the flag at the beginning, while also preserving the message from 223-239, and preserving the end of the message, the SHA1 hash. We achieve this with one key observation. Any permutation of the first n blocks, in this scheme, doesn't affect the decryption of any of the blocks after the first n.

To be exact, the final effective IV after the n blocks is the xor of $D(c_i), 0\leq i \leq n$, where c_i is the ith block of the ciphertext xored further with the initial IV. You can verify this yourself, and since xor is commutative and all that shit, it works out.

So yay we have a plan! We can move the flag block to the very beginning, and that doesn't affect the decryption of 223-239 or the SHA1 hash. We notice two things that can solve this whole problem! Firstly, we know the effective IV of the flag, namely the xor of the plaintext block that preceded it and its encryption. We have both since we encrypted the plaintext and got the ciphertext.

Of course, we also have the initial IV, which was chosen randomly at encryption but returned to us along with the ciphertext. So, if we move the flag block to the beginning, even though the later blocks stay the same, the flag block would now change. To be precise, looking at our diagram, its initial decryption would be xored with the effective IV and the initial IV. So, if the xor of two knowns and the flag block gives the right first byte to pass the padding, we can deduce what the initial decryption of the first byte of the flag block was. Which is what we want!

So what final bytes pass the padding? Well, if there used to be 3 bytes of padding, then the only first byte that works is 3. You might think, at first glance, that any number from 1 to 16 would work. However, the padding bytes are removed before the MAC is verified. And the MAC is verified with an indexed substring! The index changes if the padding byte is different.

Anyway, good news is, if we get 256 oracle decryptions on average, we can get one byte of the flag! Moreover, we can choose a specific flag byte, by varying the block of the plaintext that we bump to the beginning, as well as the number of padding bytes that are added to the beginning of the message (which we control with our arbitrary input).

Tada! That's all!

def leak_byte(input_length, block_index):
    input_str ='a'*input_length
    spell = 'f'*25 ## The length of the flag
    temp_message = 'Double, double toil and trouble;\nFire burn and caldron bubble.\nWhen midnight strikes and the god dislikes,\nI swear on my soul that\n{0}\n{1}\nIn thunder, lightning, and in rain.\nFather of omens! Give me blood beyond sight!\n'.format(spell,input_str)

    h = hashlib.sha1()
    h.update(temp_message[2*223:2*239].encode("utf-8"));
    temp_message = pad(temp_message.encode("utf-8").hex() + h.digest().hex())

    r = remote('oracleprophecy.litctf.live', 1337)
    r.recv()

    input_str = bytes(input_str, encoding='utf-8')


    while True:
        out = encrypt(r, input_str) ## Encrypts our message of choice

        iv, ct = out[:32], out[32:]

        in_b = block(temp_message, 32)
        xor_byte = int(temp_message[:2], 16)
        out_b = block(ct, 32)
        if not counter:
            print(len(ct))

        new_out_b = [out_b[block_index+1]] + out_b[:block_index+1] + out_b[block_index+2:]


        old_iv = xorHex(in_b[block_index],out_b[block_index])
        if decrypt(r, iv+''.join(new_out_b)): ## Decryption is true if padding and MAC verification succeed
            return chr(int(xorHex(old_iv, iv)[:2], 16) ^ xor_byte)
            break

Yeah so this does the thing. About actually getting the flag in order and all that, I didn't automate it. But I'm sure you can :).

This flag references the fact that this implementation is actually called AES-PCBC. Ajacent. :)