Crypto: Scrub Daddy

Challenge Description

We’ve intercepted a secret message encrypted using a custom stream cipher… but it doesn’t look very secure. Can you recover the original message?

Attachments

chal.py

SPONGE_STATE_SIZE = 48
SPONGE_RATE = 48
DELIMITER_A = 0xAD
DELIMITER_B = 0x77

def rotate(x, bits):
    ...

def permute_384(state8):
    ...

class Sponge:
    ...
    def read(self, num):
        return [self.state[i] for i in range(num)]

    def write(self, src, num):
        for i in range(num):
            self.state[i] ^= src[i]
    ...
    def permute(self):
        permute_384(self.state)
        
def encrypt_key(sponge, key):
    sponge.write(key, SPONGE_RATE)
    sponge.permute()
    
def encrypt(plaintext, key):
    sponge = Sponge()
    encrypt_key(sponge, key)
    
    currentBuffer = 0
    cipherText = []

    while (len(plaintext) - currentBuffer) >= SPONGE_RATE:
        sponge.write(plaintext[currentBuffer:], SPONGE_RATE)
        cipherText += sponge.read(SPONGE_RATE)
        sponge.permute()
        currentBuffer += SPONGE_RATE

    sponge.write(plaintext[currentBuffer:], len(plaintext) - currentBuffer)
    cipherText += sponge.read(len(plaintext) - currentBuffer)

    return cipherText

def toHexStr(arr):
    ...

if __name__ == "__main__":
    with open("message.txt", "r") as f:
        plaintext = [ord(c) for c in f.read()]
    with open("key.txt", "r") as f:
        key = [ord(c) for c in f.read().strip()]

    ciphertext = encrypt(plaintext, key)

    with open("output.txt", "w") as f:
        f.write(toHexStr(ciphertext))

output.txt

28299dd8354bbc7fcb005350f4f67c9329972bd7ada1477907f1432a5f6f2555913ec9a07d40727
344742279627157c05085a0117922b305da1508f654b7edc5e20504c0142c24088ed92bbaa6c46f
2319f67546d117b3de64089c5eb7b4a7fedad99483888165adf517bd6963ac9a6a7798bd300763b
3223d71ce07645dc631b20cfccc9acc49c47943aa327e3fd15fbb89cb1b09a10a31b1356543e722
043a8db3471b627989fb91f13c4a5a2c7a6f09e97eca29d2f47dfff6a3e35fd91071164810ade9a
0a7d26288b054ee183598415355f7c7ed35a3274b0455ca1c7781004b33ac2a641f3c5417f84703
1e70d6d53c7a1fd10c7a539af6f0f325cfcc430b3b76890026e0a77d9845f942bc6841548c30f70
cf921ba266fcb2bbf85e9ca394e068f8c3340869fafe8ff6995867f9fbe41223c6f516325f6c232
66f557be2eaded558885e61349465af1ba4365ef78a7108a70002677a23693a51d7f8a6c1b5e02a
4b0982afadb0ecd17bdfa3f5b772c5b02260f7859c4f3646f7846c97400e8d11eb7fe6cc9cb6187
5c8070c6b4b84ef173cc7ba5a9e174521c42831b613da8d791a9b3514dee2d561d90ae6dfdc8cef
19e85e3c3e4505049e23604218afbef88946bb845ff3ba1c8fb16e34e48972a11ef5bf8763c55a9
524da992e803ed3b0d50553046210ae78bffc82619323869b863c317a9e2d32d137379ae59ae1b5
e194e20f8e86d41bb524b11b9eea875a912496c61b1ba81aa3b94c4575125ef40699f200405c45d
57580d062359707bd1c586a062bae8af55e58ef2254b5fbed1a8389a40f566c59e1ae488d695092
9d2777e4c5c1bbce6dc6844d23a183a88bb7b57afeaeee10b4cc826c0f2914cb4b233154e097fd9
55ef7f8e2ca1b93be9256e

Approach

The basic part

if __name__ == "__main__":
    with open("message.txt", "r") as f:             # [1]
        plaintext = [ord(c) for c in f.read()]
    with open("key.txt", "r") as f:                 # [2]
        key = [ord(c) for c in f.read().strip()]

    ciphertext = encrypt(plaintext, key)            # [3]

    with open("output.txt", "w") as f:              # [4]
        f.write(toHexStr(ciphertext))

1. Read the message
2. Read the key
3. Encrypt the message with the key
4. Write the ciphertext to the output file

We are interested in step 3, so let’s take a look at what encrypt is doing:

def encrypt(plaintext, key):
    sponge = Sponge() # [1]
    encrypt_key(sponge, key)
    
    currentBuffer = 0
    cipherText = []

    while (len(plaintext) - currentBuffer) >= SPONGE_RATE: # [2]
        sponge.write(plaintext[currentBuffer:], SPONGE_RATE) # [3]
        cipherText += sponge.read(SPONGE_RATE) # [4]
        sponge.permute() # [5]
        currentBuffer += SPONGE_RATE

    sponge.write(plaintext[currentBuffer:], len(plaintext) - currentBuffer)
    cipherText += sponge.read(len(plaintext) - currentBuffer)

    return cipherText

What is a sponge?

We see the phrase sponge a lot in this, so it’s probably worth starting there. A quick dive to Wikipedia tells us that:

a sponge function or sponge construction is any of a class of algorithms with finite internal state that take an input bit stream of any length and produce an output bit stream of any desired length

Scrolling down (I’ll leave reading the rest of it as an exercise to the reader), we get to a section about “Duplex Construction”:

It is also possible to absorb and squeeze in an alternating fashion.[1] This operation is called the duplex construction or duplexing. …

• The state S is initialized to zero
• for each r-bit block B of the input
  • R is XORed with B
  • S is replaced by f(S)
  • R is now an output block of size r bits.

Going back to our snippet above, this seems to look pretty similar to what’s happening in our challenge:

• At [1], we initialise the sponge state $S$ to 0
• At [2], we iterate over every $r$ bit block $B$ of the input
• At [3], we XOR $B$ into $S$
• At [4], we read $S$ into our ciphertext
• At [5], we permute $S$, s.t. $S$ is replaced by $f(S)$

This all looks well and good, except for one small problem - step 4 occurs before the sponge state is permuted. As a diagram:

If we follow this logic for a moment, we can start to draw a relationship between each cipher block:

The key observation to make here is that $C_i = S_i$ - in case it’s not already clear, let’s replace all $S_i$ with $C_i$ and see where it takes us:

The problem here is that the sponge plays no role in the security of this cipher anymore. Crucially:

every block of ciphertext is a function of the previous ciphertext block and the current plaintext block*

*besides the first ciphertext block

By XOR symmetry, this gives us a very neat equation to decipher all but the first block of ciphertext:

And we can whip up a python script to do exactly that:

from chal import permute_384, SPONGE_RATE

def decrypt(cipher_bytes):
    # Initialize state with first ciphertext block
    S = list(cipher_bytes[:SPONGE_RATE])
    plaintext = bytearray()

    # Decrypt each full chunk
    offset = SPONGE_RATE
    while offset + SPONGE_RATE <= len(cipher_bytes):
        chunk = cipher_bytes[offset:offset + SPONGE_RATE]
        permute_384(S)
        plaintext.extend([chunk[i] ^ S[i] for i in range(SPONGE_RATE)])
        S = list(chunk)
        offset += SPONGE_RATE

    # Decrypt remaining bytes
    rem = len(cipher_bytes) % SPONGE_RATE
    if rem:
        permute_384(S)
        last = cipher_bytes[-rem:]
        plaintext.extend([last[i] ^ S[i] for i in range(rem)])

    return bytes(plaintext)

if __name__ == "__main__":
    with open('output.txt', 'r') as f:
        ct = bytes.fromhex(f.read())

    decrypted = decrypt(ct)
    print(decrypted.decode('ascii'))

Output:

RISC{th1s_w4s_4_l1ttl3_b1t_tr1cky!}