Dancing Queen

Platform: CUSTOM | Category: Crypto | Type: Challenge | Difficulty: Medium | OS: N/A | **Author: XESXOR Techniques: inverse_quarter_round, key_recovery_from_keystream, known_plaintext_attack, permutation_inversion

Summary

Walkthrough of the CUSTOM Crypto Dancing Queen. Task: a custom ChaCha20 omits the final feed-forward addition (keystream = permute(initial_state) with no add-back), making the 20-round permutation fully invertible; a known plaintext and the flag ar

Description

A hand-rolled ChaCha20 implementation encrypts a known Lorem-ipsum message and the flag under the same key (different IVs). Given iv1, iv2, msg_enc, flag_enc, recover the flag.

English summary: We are given a self-contained ChaCha20 implementation (chacha20.py) and its output. A known plaintext and the flag are each encrypted with the same 256-bit key but different 96-bit IVs. The goal is to recover the flag. The implementation has a fatal bug that makes the keystream permutation invertible, leaking the key from a single known-plaintext block. ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

Analysis

ChaCha20 builds a 16-word (512-bit) state:

initial_state = [const(4) || key(8) || counter(1) || iv(3)]

In real ChaCha20, a keystream block is produced as:

working_state = initial_state
for 10 double-rounds: inner_block(working_state)   # the ARX permutation
keystream_block = working_state + initial_state    # <-- feed-forward add-back (mod 2^32, word-wise)

That final word-wise addition of the original initial_state is what makes the keystream one-way: even if you learn a keystream block, you cannot run the permutation backwards to recover the state, because you don't know working_state (only working_state + initial_state). ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

This challenge's encrypt() omits the add-back entirely:

 python read-only • copy allowed Copy
self._setup_state(key, iv)
for j in range(10):
    self._inner_block(self._state)
c += xor(m[i:i+64], words_to_bytes(self._state))   # keystream = permute(initial_state), NO add-back

So here keystream_block = permute(initial_state). The permutation is a composition of ARX (add-rotate-xor) quarter-rounds, every one of which is individually invertible. Therefore the whole block function is a bijection and we can run it backwards. ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

Counter detail: each block re-calls _setup_state, and _counter starts at 1 and is incremented after each block. Both messages fit in a single 64-byte block, so both use counter = 1.

Solution

1. Recover keystream block 0. Since c = m XOR keystream, and we know the first 64 bytes of msg: ks0 = msg_enc[:64] XOR msg[:64] — this equals permute(initial_state) for (key, iv1, counter=1).

2. Invert the permutation. Implement the inverse quarter-round by reversing the four ARX operations in reverse order, then reverse the eight quarter-round calls of the inner block, and apply the inverse inner block 10 times to ks0. The result is the original initial_state. ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

3. Extract the key. The recovered state's first four words equal the ChaCha constants 0x61707865, 0x3320646e, 0x79622d32, 0x6b206574 (sanity check), word 12 is the counter (= 1), words 13..15 equal iv1, and words 4..11 are the 256-bit key.

4. Decrypt the flag. Build [const || key || counter=1 || iv2], run the forward permutation, and XOR with flag_enc.

Inverse quarter-round (the core trick)

Each ARX step a += b; d ^= a; d <<<= k is reversed by d >>>= k; d ^= a; a -= b (mod 2^32), applied in reverse order: ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

 python read-only • copy allowed Copy
def inv_qr(x, a, b, c, d):
    x[b] = rotr(x[b], 7);  x[b] ^= x[c]; x[c] = word(x[c] - x[d])
    x[d] = rotr(x[d], 8);  x[d] ^= x[a]; x[a] = word(x[a] - x[b])
    x[b] = rotr(x[b], 12); x[b] ^= x[c]; x[c] = word(x[c] - x[d])
    x[d] = rotr(x[d], 16); x[d] ^= x[a]; x[a] = word(x[a] - x[b])

Full solve script

 python read-only • copy allowed Copy
#!/usr/bin/env python3
def b2w(b): return [int.from_bytes(b[i:i+4],'little') for i in range(0,len(b),4)]
def w2b(w): return b''.join(i.to_bytes(4,'little') for i in w)
def rotl(x,n): return ((x<<n)&0xffffffff)|((x>>(32-n))&0xffffffff)
def rotr(x,n): return rotl(x,32-n)
def word(x): return x % (2**32)
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

def qr(x,a,b,c,d):
    x[a]=word(x[a]+x[b]); x[d]^=x[a]; x[d]=rotl(x[d],16)
    x[c]=word(x[c]+x[d]); x[b]^=x[c]; x[b]=rotl(x[b],12)
    x[a]=word(x[a]+x[b]); x[d]^=x[a]; x[d]=rotl(x[d],8)
    x[c]=word(x[c]+x[d]); x[b]^=x[c]; x[b]=rotl(x[b],7)

def inv_qr(x,a,b,c,d):
    x[b]=rotr(x[b],7);  x[b]^=x[c]; x[c]=word(x[c]-x[d])
    x[d]=rotr(x[d],8);  x[d]^=x[a]; x[a]=word(x[a]-x[b])
    x[b]=rotr(x[b],12); x[b]^=x[c]; x[c]=word(x[c]-x[d])
    x[d]=rotr(x[d],16); x[d]^=x[a]; x[a]=word(x[a]-x[b])

def inner(s):
    qr(s,0,4,8,12); qr(s,1,5,9,13); qr(s,2,6,10,14); qr(s,3,7,11,15)
    qr(s,0,5,10,15); qr(s,1,6,11,12); qr(s,2,7,8,13); qr(s,3,4,9,14)
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

def inv_inner(s):  # reverse order of the 8 quarter-rounds
    inv_qr(s,3,4,9,14); inv_qr(s,2,7,8,13); inv_qr(s,1,6,11,12); inv_qr(s,0,5,10,15)
    inv_qr(s,3,7,11,15); inv_qr(s,2,6,10,14); inv_qr(s,1,5,9,13); inv_qr(s,0,4,8,12)

iv1=bytes.fromhex('e42758d6d218013ea63e3c49')
iv2=bytes.fromhex('a99f9a7d097daabd2aa2a235')
msg_enc=bytes.fromhex('f3afbada8237af6e94c7d2065ee0e221a1748b8c7b11105a8cc8a1c74253611c'
                      '94fe7ea6fa8a9133505772ef619f04b05d2e2b0732cc483df72ccebb09a92c21'
                      '1ef5a52628094f09a30fc692cb25647f')
flag_enc=bytes.fromhex('b6327e9a2253034096344ad5694a2040b114753e24ea9c1af17c10263281fb0fe622b32732')
msg=b'Lorem ipsum dolor sit amet, consectetuer adipiscing elit. Aenean commodo ligula.'
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

# 1) keystream block 0 from known plaintext (counter = 1)
ks0 = bytes(a^b for a,b in zip(msg_enc[:64], msg[:64]))

# 2) invert the permutation -> initial_state
state = b2w(ks0)
for _ in range(10): inv_inner(state)
assert state[:4] == [0x61707865,0x3320646e,0x79622d32,0x6b206574]  # constants check

# 3) extract the 256-bit key (words 4..11)
key = w2b(state[4:12])

# 4) decrypt the flag under iv2 (single block, counter = 1)
s = [0x61707865,0x3320646e,0x79622d32,0x6b206574] + b2w(key) + [1] + b2w(iv2)
for _ in range(10): inner(s)
flag = bytes(a^b for a,b in zip(flag_enc, w2b(s)))
print(flag.decode())

‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

Output: crypto{REDACTED} — "Mixing rounds are invertible!" The recovered key is 39fd1410fef6485bf3068ea0fb3a8ff6385b4483bc1f321cea4f15cc1c43496c. ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

Key Takeaways / Lessons

• Mastering inverse_quarter_round, key_recovery_from_keystream, known_plaintext_attack, permutation_inversion was key to this challenge.
• Always check for common misconfigurations and verify assumptions.

---

Crafted by XESXOR Research • 2026-06-22 • CUSTOM • Dancing Queen • Difficulty: Medium