choreography Writeup

PlaidCTF 2022 - crypto 400 - 15 solves

Let's dance. nc choreography.chal.pwni.ng 1337

handout

Solved after the CTF was ended.

Analysis

We have block cipher: encrypt1 and encrypt2. key and block size is 4 bytes. Let key = [k0, k1, k2, k3]. We can perform chosen ciphertext attack with QUERIES = 500 queries for each encryption. Our goal is to recover the key.

The block cipher has the structure of generalized Feistel structure, with alternating key setting, having ROUNDS = 2 ** 22 + 2 performed per each encryption. So large round numbers. The only attack I knew to apply in this tremendously large round setting was Slide Attack. The complexity of slide attack is independent of the number of rounds, and it exploits the fact of weak key structures in iterated-round block ciphers.

Relation with encrypt1 and encrypt2

We can implement the decryption function decrypt1 of encrypt1 using encrypt2. So, we basically have a plaintext/ciphertext oracle with QUERIES = 500 queries. Proof:

def encrypt1(k, plaintext):
    a,b,c,d = plaintext
    for i in range(ROUNDS):
        a ^= sbox[b ^ k[(2*i)&3]]
        c ^= sbox[d ^ k[(2*i+1)&3]]
        a,b,c,d = b,c,d,a
    return bytes([a,b,c,d])
 
 
def decrypt1(k, ciphertext):
    c,d,a,b = ciphertext
    c,d,a,b = encrypt2(k, bytes([a,b,c,d]))
    return bytes([a,b,c,d])
 
def encrypt2(k, plaintext):
    a,b,c,d = plaintext
    for i in range(ROUNDS)[::-1]:
        b,c,d,a = a,b,c,d
        c ^= sbox[d ^ k[(2*i)&3]]
        a ^= sbox[b ^ k[(2*i+1)&3]]
    return bytes([a,b,c,d])
 
 
key = os.urandom(4)
 
m1 = os.urandom(4)
c1 = encrypt1(key, m1)
m1_ = decrypt1(key, c1)
 
assert m1 == m1_

Deep Dive into Slide Attack

Let me visualize each round of encrypt1. a, b, c and d correspond to each input byte.

Each round can be decomposed to two separate sub rounds r1 and r2, which have exactly the same structure but different keys. Also, we notice that for each sub round, half of the input is preserved(b and d does not change). For each sub round r1 and r2, we use different keys: (k0 and k1) or (k2 and k3). So overall structure is that, running 2 * ROUNDS sub rounds, with alternating key pairs.

We cannot directly apply vanilla slide attack in this setting and need something fancier.

We need to consider two properties:

1. Half of input data is preserved(b and d), having structure of generalized Feistel structure.
2. Each sub round is alternating, using two different key pairs.

Complementation Slide + Twisted Slide Attack to the Rescue

Advanced Slide Attack was suitable for the problem setting. We combine two attacks: Complementation Slide and Twisted Slide Attack. Section 3.3 Figure 4 describes the combination between two attacks.

To use the generalized Feistel structure, we first study how plain Feistel structure helps to reduce the attack complexity. See Section 3.2 fifth paragraph. The paragraph assumes that the setting is plain feistel structure with alternating key settings. Paragraph:

Moreover, there is a chosen-plaintext/ciphertext variant that allows us to reduce the number of texts down to 2 ** 17 with the use of structures. We generate a pool of 2 ** 16 plaintexts of the form (Li, R) and obtain their encryptions. Also, we build a pool of 2 ** 16 ciphertexts of the form (M0j, N0) and decrypt each of them, where the value N0 = R is fixed throughout the attack. This is expected to give one slid pair, and then the analysis proceeds as before.

We now extend the attack for generalized Feistel structures. We have chosen-plaintext/ciphertext variant that allows us to reduce the number of texts down to 2 ** 9 with the use of structure. Generate a pool of 2 ** 8 < 500 plaintext of the form (a', b, c', d) and obtain their encryptions, Also, we build a pool of 2 ** 8 < 500 ciphertexts of the form (a', b, c', d) and decrypt each of them. This is expected to give one slid pair. and by using up to 500 queries, it is likely to obtain several slid pairs.

Exploit Plan

1. Generate 2 * QUERIES = 1000 data of the form [a, b, c, d]. b and d will be constants, to use the fact that they are preserved after sub rounds. All data must be unique.
2. Send QUERIES = 500 plaintext obtained from 1, and get ciphertext using encryption oracle.
3. Send QUERIES = 500 ciphertext obtained from 1, and get plaintext using decryption oracle.
4. Find candidate slide pairs.
   • Let (A, B), (C, D) be two ciphertext/plaintext pairs. We can detect candidate slid pairs if A[1] == D[1], A[3] == D[3], B[1] == C[1], B[3] == C[3].
5. Find correct slide pairs by recovering k0, k1 using slid pair (A, D), (B, C). Let delta be the difference for Complementation Slide. delta is single byte so bruteforcable. Relations:
   • D[0] = sbox[k0 ^ A[1]] ^ A[0] ^ delta
   • D[2] = sbox[k1 ^ A[3]] ^ A[2] ^ delta
   • B[0] = sbox[k0 ^ C[1]] ^ C[0] ^ delta
   • B[2] = sbox[k1 ^ C[3]] ^ C[2] ^ delta
6. Recover k2 and k3 using delta. k2 ^ k3 == delta, so bruteforcable, having a search space of single byte.
   • k2 ^ k3 == delta because we first make an odd sub round r1 always line up. By this effect, the even sub round r2 have the constant difference delta to swap effect of k2 and k3.

Let n bits be block/key size. Time complexity: O(2 ** (n // 4)), Space complexity: O(2 ** (n // 4)). I get flag(after the CTF was ended :C)

PCTF{square_dancin'_the_night_away~}

Problem src: cipher.py, pow.py, run.sh

exploit driver code: solve.py