Black Box

Aperi'CTF 2019 - Cryptography (175 pts).

Aperi’CTF 2019 - Black Box

Challenge details

Event Challenge Category Points Solves
Aperi’CTF 2019 Black Box Cryptography 175 2

La société ENO.corp organise un bug bounty pour mettre à l’épreuve la robustesse de leur tout nouveau HSM soi-disant ultra sécurisé. Vous n’avez pas accès physiquement au boitier, mais uniquement à un service de chiffrement.

nc black-box.aperictf.fr 9897

TL;DR

Black box cryptanalyse on a bit shuffling home crypto.

Methodology

We have access to an unknown encryption service. For each connection a new ciphertext is given. The plaintext must be given as an hexadecimal string.

Welcome to the bug bunty programm. A bounty will be awarded to those who can decrypt the following ciphertext :
2226ba225eb9cc826511b42e76ffb25c03d2778e62f48086504134ac801cabfe
Good luck !
Give me your plaintext:
00
Encrypted result:
00000000000000000000000000000000

As you can see, giving a null input produces a null output. Although we have given a single null byte as input, the resulting cipher is 16 bytes long. Let’s verify that.

Give me your plaintext:
0000
Encrypted result:
00000000000000000000000000000000
Give me your plaintext:
00000000000000000000000000000000
Encrypted result:
00000000000000000000000000000000
Give me your plaintext:
0000000000000000000000000000000000
Encrypted result:
0000000000000000000000000000000000000000000000000000000000000000

This is the behaviour of a block cipher. Our input is certainly padded to match the block length. We can assume it’s padded with null bytes because the result is the same as when we input a full block of null bytes.

Now it’s time to play with some inputs.

Give me your plaintext:
01
Encrypted result:
00000200000000000000000000000000
Give me your plaintext:
41
Encrypted result:
00000200000000800000000000000000
Give me your plaintext:
FF
Encrypted result:
00800300200400800008000000004000
Give me your plaintext:
FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
Encrypted result:
ffffffffffffffffffffffffffffffff
Give me your plaintext:
80
Encrypted result:
00000000000000000000000000004000

The results are very interesting. Unlike a good encryption algorithm, the entropy of the resulting ciphertext is not maximal.

When 2 of our inputs have a bit in common, the ciphers also have a bit in common. You can see that with the first 2 that where tried :

  • 01 -> 00000200000000000000000000000000

  • 41 -> 00000200000000800000000000000000

When a null input is given, a null output is produced. When all the input bits are set, all the output bits are set. This looks more like the bits are shuffled rather then encrypted. This can be better seen when looking at their binary representation.

>>> tobin('01')
'00000001000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000'
>>> tobin('00000200000000000000000000000000')
'00000000000000000000001000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000'
>>> tobin('41')
'01000001000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000'
>>> tobin('00000200000000800000000000000000')
'00000000000000000000001000000000000000000000000000000000100000000000000000000000000000000000000000000000000000000000000000000000'

Now that we suppose the bits are shuffled, we can build a table to keep track of where each bit is moved. To do that we will send a plaintext containing only 0 bits except one and see at which position in the ciphertext the single high bit is located. We will do that for each 128 bits of a block. This is perfect because it turns out we only have 128 encryption available before the program exists.

def getSwap(i):
    m = '0'*i+'1'
    m = m.ljust(16*8, "0")
    r = stob(send(btos(m).rjust(16*8, '\x00'))).zfill(16*8)
    return r.find("1")

swap = []

for i in range(16*8):
    swap.append(getSwap(i))

result = ''
for b in get_blocks(cipher):
    bi = stob(b).zfill(16*8)
    decrypted = [0]*(16*8)
    for i in range(16*8):
        decrypted[i] = bi[swap[i]]
    result += ''.join(decrypted)

Once we know where every bit is moved, we can easily revert the process for each block of the flag.

The complete script is available in solve.py

python solve.py
[+] Opening connection to black-box.aperictf.fr on port 9897: Done
[*] c6c2d366667b59dfd169c362349780217602e2c28d5ec2dfc882484411de00fa
[+] APRK{Ev3ry_D4y_1_m_Shuffl1n}\x00\x00\x00\x00
[*] Closed connection to black-box.aperictf.fr port 9897

Flag

APRK{Ev3ry_D4y_1_m_Shuffl1n}

ENOENT