Count me out

I have developed a new, revolutionary cipher that is not constrained to one block cipher. It is safe and secure. If you are not convinced, I will provide a flag to anyone who manages to win the ‘In No Desirable Case Attacks Possible’ (IND-CPA) mode.

Category: Crypto

Solver: Greenscreen23, SchizophrenicFish2nds

Flag: GPNCTF{stop_breaking_it_It_is_even_called_safe}

Writeup

Context

We are presented with an IND-CPA game for an AES cipher with a custom block mode.

The game is as usual: We are able to encrypt an arbitrary amount of blocks, until we are ready to start the challenge. To start the challenge, we send two messages, one of which is encrypted and send back. We then have to decide which of two messages was chosen to solve the challenge. There are 1000 rounds of challenges we have to pass to get the flag.

The block cipher mode is as follows: An IV (a number of 16 bytes) is chosen at random. Each plaintext block is then first XORed with the IV and the IV is incremented by one. Afterwards, each block is encrypted using AES with a random key. The key and initial IV are chosen for each round, so subsequent messages use the same key and the incremented IV. Blocks are padded with 0-bytes to a multiple of 16 byte.

The randomness used comes from the python secrets module, and we therefore assume it to be secure.

Winning the game

We know that increasing an even number by one will only flip the last bit. But we don’t know whether we start with an even or an odd IV. To find out, we send two messages m1, m2, which are both exactly one block long and differ only in their last bit. If the IV was initially even, the two messages will be the same after the XOR and so the ciphertexts will be the same. Otherwise, the ciphertexts will differ.

If the ciphertexts were the same, then the IV will be even after the operation. Now we ask for an encryption e of the message m1. We know that the next encryption of the message m2, which differs only in the last bit compared to m1, will also yield e. So we start the challenge with the message m2 and a randomly chosen message. If we see the same ciphertext again, m2 was most likely encrypted. Otherwise, the random message must have been picked.

If the ciphertext differed, the solution is almost the same. We know that the IV was initially odd, so it must have been even when m2 was encrypted. So the next encryption of m1 must yield the same ciphertext e. We therefore start the challenge with m1 and a random message. If we receive e, then m1 was most likely encrypted. Otherwise, the random message must have been picked.

After all rounds are finished, we get the flag. This is implemented as a script [1], where BLOCK1 and BLOCK2 are m1 and m2. BLOCK_OTHER is the randomly chosen block that is used as the second message in all challenges.

Mitigations and further notes

Our described solution exploits the fact that their block cipher mode is deterministic and thus cannot be IND-CPA secure, by constructing chosen messages that map to the same input for the AES-ECB encryption function. For IND-CPA security, such “constructed” deterministic encryption needs to be avoided, as is the case with CTR and CBC. Here are more details about the game. Notice how we exploit the ECB determinism in our attack.

However, the SAFE challenge oracle itself is also flawed, by not checking whether the challenge messages allow for a trivial win by comparing ciphertext sizes. This flaw is unrelated to ECB and the custom SAFE mode of operation, as learning the maximum length of a message can never be avoided in symmetric cryptography.

Other resources

Scripts

[1] The script to solve the challenge

from pwn import *

BLOCK1 = b'\0' * 16
BLOCK2 = b'\0' * 15 + b'\x01'
BLOCK_OTHER = b'jemdogwgdwsdgpea'
chal = process('./cipher.py')

def enc(block):
    chal.recvuntil(b'oracle:')
    chal.sendline(block.hex().encode())
    return bytes.fromhex(chal.recvline().decode().strip())

def challenge(first, second):
    chal.recvuntil(b'oracle:')
    chal.sendline(b'challenge'.hex().encode())
    chal.recvuntil(b'first challenge plaintext:')
    chal.sendline(first.hex().encode())
    chal.recvuntil(b'second challenge plaintext:')
    chal.sendline(second.hex().encode())
    return bytes.fromhex(chal.recvline().decode().strip())

def ans(b):
    chal.recvuntil(b'b = ?:')
    chal.sendline(b)

for i in range(1000):
    print(i)
    enc_block_1 = enc(BLOCK1)
    enc_block_2 = enc(BLOCK2)

    if enc_block_1 == enc_block_2:
        enc_block_3 = enc(BLOCK1)
        test_block = challenge(BLOCK2, BLOCK_OTHER)
        ans(str(int(test_block != enc_block_3)).encode())
    else:
        test_block = challenge(BLOCK1, BLOCK_OTHER)
        ans(str(int(test_block != enc_block_2)).encode())

chal.interactive()