<- CRYPTO

Fibopadcci

13 minutes to read

We are given the Python source code of the server:

import socketserver
from Crypto.Cipher import AES
import os
from secret import flag, key

fib = [1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 121, 98, 219, 61]

wlc_msg = """
-------------------------------------------------------------------------
|           Welcome to my Super Secure Encryption service!              |
|        We use AES along with custom padding for authentication        |
|         for extra security, so only admins should be able to          |
|          decrypt the flag with the key I have provided them!          |
|       Admins: Feel free to send me messages that you have             |
|       encrypted with my key, but make sure they are padded            |
|       correctly with my custom padding I showed you (fibopadcci)      |
|          Also, please use the a value I gave you last time,           |
|   if you need it, ask a fellow admin, I don't want some random        |
|               outsiders decrypting our secret flag.                   |
-------------------------------------------------------------------------
"""[1:]

menu_msg = """\n
-------------------------
| Menu                  |
-------------------------
|[0] Encrypt flag.      |
|[1] Send me a message! |
-------------------------
"""[1:]

def xor(a, b):
    return bytes([_a ^ _b for _a, _b in zip(a, b)])


def pad(data): #Custom padding, should be fine!
    c = 0
    while len(data) % 16:
        pad = str(hex(fib[c] % 255))[2:]
        data += unhex("0" * (2-len(pad)) + pad)
        c += 1
    return data


def checkpad(data):
    if len(data) % 16 != 0:
        return 0
    char = data[-1]

    try:
        start = fib.index(char)
    except ValueError:
        return 0
    
    newfib = fib[:start][::-1]

    for i in range(len(newfib)):
        char = data[-(i+2)]
        if char != newfib[i]:
            return 0

    return 1

def unhex(data):
    return bytes.fromhex(data)

class SuperSecureEncryption: # This should be unbreakable!
    def __init__(self, key):
        self.cipher = AES.new(key, AES.MODE_ECB)

    def encrypt(self, data):
        data = pad(data)
        
        a = os.urandom(16).replace(b'\x00', b'\xff') 
        b = os.urandom(16).replace(b'\x00', b'\xff')

        lb_plain = a
        lb_cipher = b
        output = b''

        data  = [data[i:i+16] for i in range(0, len(data), 16)]

        for block in data:
    
            enc = self.cipher.encrypt(xor(lb_cipher, block))
            enc = xor(enc, lb_plain)
            output += enc
            lb_plain = block
            lb_cipher = enc
        return output, a.hex(), b.hex()

    def decrypt(self, data, a, b):
        lb_plain = a
        lb_cipher = b
        output = b''
        data = [data[i:i+16] for i in range(0, len(data), 16)]
        for block in data:
            dec = self.cipher.decrypt(xor(block, lb_plain))
            dec = xor(dec, lb_cipher)
            output += dec
            lb_plain = dec
            lb_cipher = block
        if checkpad(output):
            return output
        else:
            return None

def encryptFlag():
    encrypted, a, b = SuperSecureEncryption(key).encrypt(flag)
    return f'encrypted_flag: {encrypted.hex()}\na: {a}\nb: {b}'

def sendMessage(ct, a, b):
    if len(ct) % 16:
        return "Error: Ciphertext length must be a multiple of the block length (16)!"
    if len(a) != 16 or len(b) != 16:
        return "Error: a and b must have lengths of 16 bytes!"
    decrypted = SuperSecureEncryption(key).decrypt(ct, a, b)
    if decrypted != None:
        return "Message successfully sent!"
    else:
        return "Error: Message padding incorrect, not sent."

def handle(self):
    self.write(wlc_msg)
    while True:
        self.write(menu_msg)
        option = self.query("Your option: ")
        if option == "0":
            self.write(encryptFlag())
        elif option == "1":
            try:
                ct = unhex(self.query("Enter your ciphertext in hex: "))
                b = unhex(self.query("Enter the B used during encryption in hex: "))
                a = b'HTB{th3_s3crt_A}' # My secret A! Only admins know it, and plus, other people won't be able to work out my key anyway!  
                self.write(sendMessage(ct,a,b))
            except ValueError as e:
              self.write("Provided input is not hex!")
        else:
            self.write("Invalid input, please try again.")


class RequestHandler(socketserver.BaseRequestHandler):
    handle = handle

    def read(self, until='\n'):
        out = ''
        while not out.endswith(until):
            out += self.request.recv(1).decode()
        return out[:-len(until)]

    def query(self, string=''):
        self.write(string, newline=False)
        return self.read()

    def write(self, string, newline=True):
        self.request.sendall(str.encode(string))
        if newline:
            self.request.sendall(b'\n')

    def close(self):
        self.request.close()

class Server(socketserver.ForkingTCPServer):

    allow_reuse_address = True

    def handle_error(self, request, client_address):
        self.request.close()

port = 1337
server = Server(('0.0.0.0', port), RequestHandler)
server.serve_forever()

Cipher analysis

We are given two options:

$ nc 206.189.114.209 31967
-------------------------------------------------------------------------  
|           Welcome to my Super Secure Encryption service!              |
|        We use AES along with custom padding for authentication        |
|         for extra security, so only admins should be able to          |
|          decrypt the flag with the key I have provided them!          |
|       Admins: Feel free to send me messages that you have             |
|       encrypted with my key, but make sure they are padded            |
|       correctly with my custom padding I showed you (fibopadcci)      |
|          Also, please use the a value I gave you last time,           |
|   if you need it, ask a fellow admin, I don't want some random        |
|               outsiders decrypting our secret flag.                   |
-------------------------------------------------------------------------


-------------------------
| Menu                  |
-------------------------
|[0] Encrypt flag.      |
|[1] Send me a message! |
-------------------------

Your option:

The first one just send out the encrypted flag and two values a and b.

Your option: 0
encrypted_flag: 18a6cae6493d67b7d35180499b9db145e33abdfb5a265dc6f5cf257ac6dfde78211ff6bc21399f605790cc6a0b67c9bc  
a: ae9b722fd54f1a40526252a1d8f2da17
b: c304b05b0725ce2e93f6ef2b4bd0a73f

The second option tries to decrypt the encrypted message but it shows an error:

-------------------------
| Menu                  |
-------------------------
|[0] Encrypt flag.      |
|[1] Send me a message! |
-------------------------

Your option: 1
Enter your ciphertext in hex: 18a6cae6493d67b7d35180499b9db145e33abdfb5a265dc6f5cf257ac6dfde78211ff6bc21399f605790cc6a0b67c9bc  
Enter the B used during encryption in hex: c304b05b0725ce2e93f6ef2b4bd0a73f
Error: Message padding incorrect, not sent.

The error says “padding incorrect”, so probably we will be performing a Padding Oracle Attack. This is the class that implements the encryption algorithm:

class SuperSecureEncryption: # This should be unbreakable!
    def __init__(self, key):
        self.cipher = AES.new(key, AES.MODE_ECB)

    def encrypt(self, data):
        data = pad(data)
        
        a = os.urandom(16).replace(b'\x00', b'\xff') 
        b = os.urandom(16).replace(b'\x00', b'\xff')

        lb_plain = a
        lb_cipher = b
        output = b''

        data  = [data[i:i+16] for i in range(0, len(data), 16)]  

        for block in data:
            enc = self.cipher.encrypt(xor(lb_cipher, block))
            enc = xor(enc, lb_plain)
            output += enc
            lb_plain = block
            lb_cipher = enc

        return output, a.hex(), b.hex()

    def decrypt(self, data, a, b):
        lb_plain = a
        lb_cipher = b
        output = b''

        data = [data[i:i+16] for i in range(0, len(data), 16)]

        for block in data:
            dec = self.cipher.decrypt(xor(block, lb_plain))
            dec = xor(dec, lb_cipher)
            output += dec
            lb_plain = dec
            lb_cipher = block

        if checkpad(output):
            return output
        else:
            return None

It is worth drawing the encryption and decryption processes in block diagrams:

  • Encryption:

Fibopadcci 1

  • Decryption:

Fibopadcci 2

Actually, this cipher scheme is known as Infinite Garble Extension (so it is not actually a custom block cipher).

First of all, we will retrieve the encrypted flag, which sends the ciphertexts and the two values a and b used for that (they are random).

We are not able to decrypt the message ourselves because we don’t have the AES key for the decryption blocks… And we can’t tell the server to decrypt it because the server uses a fixed a value:

        elif option == "1":
            try:
                ct = unhex(self.query("Enter your ciphertext in hex: "))
                b = unhex(self.query("Enter the B used during encryption in hex: "))
                a = b'HTB{th3_s3crt_A}' # My secret A! Only admins know it, and plus, other people won't be able to work out my key anyway!  
                self.write(sendMessage(ct,a,b))
            except ValueError as e:
              self.write("Provided input is not hex!")

Moreover, the server does not send back the plaintext:

def sendMessage(ct, a, b):
    if len(ct) % 16:
        return "Error: Ciphertext length must be a multiple of the block length (16)!"  
    if len(a) != 16 or len(b) != 16:
        return "Error: a and b must have lengths of 16 bytes!"
    decrypted = SuperSecureEncryption(key).decrypt(ct, a, b)
    if decrypted != None:
        return "Message successfully sent!"
    else:
        return "Error: Message padding incorrect, not sent."

Padding Oracle Attack

If the padding of the decrypted message is correct, it shows "Message successfully sent!". Otherwise, the server returns "Error: Message padding incorrect, not sent.". That’s the (padding) oracle we have.

The padding implementation is custom (related to the Fibonacci sequence), but that is not a problem:

fib = [1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 121, 98, 219, 61]  

# ...

def pad(data): #Custom padding, should be fine!
    c = 0
    while len(data) % 16:
        pad = str(hex(fib[c] % 255))[2:]
        data += unhex("0" * (2-len(pad)) + pad)
        c += 1
    return data

Let’s try it just in case:

$ python3 -q
>>> fib = [1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 121, 98, 219, 61]  
>>>
>>> def unhex(data):
...     return bytes.fromhex(data)
...
>>> def pad(data): #Custom padding, should be fine!
...     c = 0
...     while len(data) % 16:
...         pad = str(hex(fib[c] % 255))[2:]
...         data += unhex("0" * (2-len(pad)) + pad)
...         c += 1
...     return data
...
>>> pad(b'A')
b'A\x01\x02\x03\x05\x08\r\x15"7Y\x90\xe9yb\xdb'
>>> pad(b'ABCD')
b'ABCD\x01\x02\x03\x05\x08\r\x15"7Y\x90\xe9'
>>> pad(b'ABCDEFGHI')
b'ABCDEFGHI\x01\x02\x03\x05\x08\r\x15'
>>> pad(b'ABCDEFGHIJKLM')
b'ABCDEFGHIJKLM\x01\x02\x03'
>>> pad(b'ABCDEFGHIJKLMNO')
b'ABCDEFGHIJKLMNO\x01'
>>> pad(b'ABCDEFGHIJKLMNOP')
b'ABCDEFGHIJKLMNOP'

The padding is checked in checkpad:

def checkpad(data):
    if len(data) % 16 != 0:
        return 0
    char = data[-1]

    try:
        start = fib.index(char)
    except ValueError:
        return 0
    
    newfib = fib[:start][::-1]

    for i in range(len(newfib)):  
        char = data[-(i+2)]
        if char != newfib[i]:
            return 0

    return 1

Basically, it takes the last byte and checks that the padding sequence is correct. There is a minor mistake, because messages with length a multiple of 16 are not padded and will return padding error:

>>> def checkpad(data):
...     if len(data) % 16 != 0:
...         return 0
...     char = data[-1]
...     try:
...         start = fib.index(char)
...     except ValueError:
...         return 0
...     newfib = fib[:start][::-1]
...     for i in range(len(newfib)):  
...         char = data[-(i+2)]
...         if char != newfib[i]:
...             return 0
...     return 1
...
>>> pad(b'A' * 16)
b'AAAAAAAAAAAAAAAA'
>>> pad(b'A' * 15)
b'AAAAAAAAAAAAAAA\x01'
>>> checkpad(pad(b'A' * 16))
0
>>> checkpad(pad(b'A' * 15))
1
>>> checkpad(pad(b'A' * 32))
0

Padding Oracle Attack works as follows:

Fibopadcci 3

We are able to tweak the second to last ciphertext block, which affects directly to the last plaintext block. The idea is to iterate the last byte from 0x00 to 0xff until we find one that results in 0x01 (the first padding byte of the sequence). At this point, the server will show a successful message.

However, this is not a typical Padding Oracle Attack on AES CBC. In such a case, we would find that “magic” byte ($B_i$) that gives no padding error and these conditions hold:

$$ B_i \oplus \mathrm{pt}_i = \mathrm{pad}_i \iff B_i \oplus \mathrm{AES.dec}(\mathrm{ct}_i) = \mathrm{pad}_i $$

Then, the plaintext byte $\mathrm{pt}_i$ is computed as follows:

$$ \mathrm{pt}_i = \mathrm{AES.dec}(\mathrm{ct}_i) = \mathrm{pad}_i \oplus B_i $$

This time, the ciphertext is not sent directly to the decryptor, there is a XOR operation with the previous plaintext block. Nevertheless, understanding the concepts behind the classic Padding Oracle Attack is needed to understand the process to solve this challenge. We will do the following:

Fibopadcci 4

With this setup, if we used the provided b, the message would decrypt correctly. So, if we force the last byte to be 0x01 (in this specific example), the server will not error out and we can do the above computations to find the plaintext byte.

Testing

Let’s show how this works locally:

$ cat > secret.py
from os import urandom
flag = b'HTB{ABCDEFGHIJKLM}'  
key = urandom(16)
^C

$ python3 server.py

Now, we will use the following Python script:

#!/usr/bin env python3

from pwn import remote, sys, xor

fib = [1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 121, 98, 219, 61]


def main():
    host, port = sys.argv[1].split(':')
    io = remote(host, port)

    io.sendlineafter(b'Your option: ', b'0')
    io.recvuntil(b'encrypted_flag: ')
    encrypted_flag = bytes.fromhex(io.recvline().strip().decode())
    io.recvuntil(b'a: ')
    flag_a = bytes.fromhex(io.recvline().strip().decode())
    io.recvuntil(b'b: ')
    flag_b = bytes.fromhex(io.recvline().strip().decode())

    print(encrypted_flag.hex(), flag_a.hex(), flag_b.hex())

    secret_a = b'HTB{th3_s3crt_A}'

    ct_block = xor(encrypted_flag[:16], secret_a, flag_a)

    for b_byte in range(256):
        io.sendlineafter(b'Your option: ', b'1')
        io.sendlineafter(b'Enter your ciphertext in hex: ', ct_block.hex().encode())
        b = bytes([0] * 15 + [b_byte])

        io.sendlineafter(b'Enter the B used during encryption in hex: ', b.hex().encode())  

        if io.recvline() == b'Message successfully sent!\n':
            dec = [b_byte ^ fib[0] ^ flag_b[15]]
            print(bytes(dec))
            break


if __name__ == '__main__':
    main()

$ python3 solve.py 127.0.0.1:1337
[+] Opening connection to 127.0.0.1 on port 1337: Done
3aafe4279ec56dee1235644f384574877fb67096164ee5e5b65b44c937dff0ba 50d773e13822ea33ae90049f27c5836f f973da5793d1143b3c59c54fa14bf882  
b'L'
[*] Closed connection to 127.0.0.1 port 1337

$ python3 solve.py 127.0.0.1:1337
[+] Opening connection to 127.0.0.1 on port 1337: Done
ca4789bffdb992e84441b81a99b072488d55466a133f5ed28b762cab27b9e85f 5d4ba3db381b3b4818251fa763302bbf 6d53ac073b59a7402f9f6e74beb1ff20
b'L'
[*] Closed connection to 127.0.0.1 port 1337

$ python3 solve.py 127.0.0.1:1337
[+] Opening connection to 127.0.0.1 on port 1337: Done
5a683e63568c6cdcc37604da5c5f2415f42129d6fc7c730986121f6dcf16a7f1 6e86d0b25520672f6db8bf8dc133aba9 30635516c74992dd35b08bb363727da3
b'L'
[*] Closed connection to 127.0.0.1 port 1337

As can be seen, we are getting L, which is the character at position 16 of the plaintext flag (HTB{ABCDEFGHIJKLM}). Let’s update the script to extract the byte at position 15:

def main():
    # ...

    ct_block = xor(encrypted_flag[:16], secret_a, flag_a)
    pt = b''
    dec = []

    for b_byte in range(256):
        io.sendlineafter(b'Your option: ', b'1')
        io.sendlineafter(b'Enter your ciphertext in hex: ', ct_block.hex().encode())
        b = bytes([0] * 15 + [b_byte])

        io.sendlineafter(b'Enter the B used during encryption in hex: ', b.hex().encode())  

        if io.recvline() == b'Message successfully sent!\n':
            dec = [b_byte ^ fib[0]] + dec
            pt = bytes([dec[0] ^ flag_b[15]]) + pt
            break

    for b_byte in range(256):
        io.sendlineafter(b'Your option: ', b'1')
        io.sendlineafter(b'Enter your ciphertext in hex: ', ct_block.hex().encode())
        b = bytes([0] * 14 + [b_byte]) + xor(bytes(dec), bytes(fib[1: len(dec) + 1]))

        io.sendlineafter(b'Enter the B used during encryption in hex: ', b.hex().encode())

        if io.recvline() == b'Message successfully sent!\n':
            dec = [b_byte ^ fib[0]] + dec
            pt = bytes([dec[0] ^ flag_b[14]]) + pt
            break

    print(pt)

$ python3 solve.py 127.0.0.1:1337
[+] Opening connection to 127.0.0.1 on port 1337: Done
92fedbc7fb035693f5e8a9e5214f2829a645ce32cb462be33717082f961fa15d e1962d917c48723e6a3acc448bef370f 3ced7fab3844130b748f6445b4e6990b  
b'KL'
[*] Closed connection to 127.0.0.1 port 1337

Decryption

Now, let’s automate it to get all the 16 plaintext bytes for a block using a for loop:

def main():
    # ...

    ct_block = xor(encrypted_flag[:16], secret_a, flag_a)
    pt = b''
    dec = []

    for i in range(16):
        for b_byte in range(256):
            io.sendlineafter(b'Your option: ', b'1')
            io.sendlineafter(b'Enter your ciphertext in hex: ', ct_block.hex().encode())
            b = bytes([0] * (15 - i) + [b_byte]) + xor(bytes(dec), bytes(fib[1: len(dec) + 1]))  

            io.sendlineafter(b'Enter the B used during encryption in hex: ', b.hex().encode())

            if io.recvline() == b'Message successfully sent!\n':
                dec = [b_byte ^ fib[0]] + dec
                pt = bytes([dec[0] ^ flag_b[15 - i]]) + pt
                break

    print(pt)

$ python3 solve.py 127.0.0.1:1337
[+] Opening connection to 127.0.0.1 on port 1337: Done
31b0b9118dd27c5e97631bcf2fe708d270744b65306d721740e447fe9212278c cae439e59417b4c0576e5a45a2c3883a df41ffc451fd4b257f3615168ac540c3  
b'HTB{ABCDEFGHIJKL'
[*] Closed connection to 127.0.0.1 port 1337

Now, let’s wrap the above for loop into a function to dump all the blocks. For this, we must take into account that the corresponding values for a and b are the previous plaintext and ciphertext blocks, respectively (if needed, take a look at the scheme and isolate the middle blocks). I also tweaked the script a bit to show some information about the progress of the decryption process:

    flag_prog = log.progress('Flag')
    poa = log.progress('Bytes')

    def decrypt_block(ct_block):
        dec = []
        poa.status('0 / 16')

        for i in range(16):
            for b_byte in range(256):
                io.sendlineafter(b'Your option: ', b'1')
                io.sendlineafter(b'Enter your ciphertext in hex: ', ct_block.hex().encode())
                b = bytes([0] * (15 - i) + [b_byte]) + xor(bytes(dec), bytes(fib[1: len(dec) + 1]))  

                io.sendlineafter(b'Enter the B used during encryption in hex: ', b.hex().encode())

                if io.recvline() == b'Message successfully sent!\n':
                    poa.status(f'{i + 1} / 16')
                    dec = [b_byte ^ fib[0]] + dec
                    break

        return dec

    encrypted_flag_blocks = [encrypted_flag[i:i+16] for i in range(0, len(encrypted_flag), 16)]

    flag = b''
    a, b = flag_a, flag_b

    for block in encrypted_flag_blocks:
        ct_block = xor(block, secret_a, a)
        dec = decrypt_block(ct_block)
        flag += xor(dec, b)

        if b'\x01' not in flag:
            flag_prog.status(flag.decode())

        a, b = flag[-16:], block

    flag = flag[:flag.index(b'\x01')]
    flag_prog.success(flag.decode())
    poa.success()

$ python3 solve.py 127.0.0.1:1337
[+] Opening connection to 127.0.0.1 on port 1337: Done  
[+] Flag: HTB{ABCDEFGHIJKLM}
[+] Bytes: Done
[*] Closed connection to 127.0.0.1 port 1337

Flag

If we run it on the remote instance, we will find the flag after 15 minutes approximately:

$ python3 solve.py 167.71.137.186:32286
[+] Opening connection to 167.71.137.186 on port 32286: Done  
[+] Flag: HTB{cU5t0m_p4dd1Ng_w0nT_s4v3_y0u_tH1s_T1m3_:(!@}
[+] Bytes: Done
[*] Closed connection to 167.71.137.186 port 32286

The full script can be found in here: solve.py.