This writeup uses a naive approach, see my writeup of involucrypt 2 for a better solution.

The challenge starts off with two files:

  • crypt.py
  • involucrypt1

The first one is a script that can encode a message, the second one contains crypted data.

Here is the (slightly redacted) script:

import itertools
import operator
import sys

BLOCK = 150

class mersenne_rng(object):
    ...

def keystream(seeds, length, base=None):
    key = base if base else []
    for seed in seeds:
        random = mersenne_rng(seed)

        for _ in range(BLOCK):
            if len(key) == length:
                break
            key.append(random.get_rand_int(0, 255))
            random.shuffle(key)
        if len(key) == length:
            break
    return key


def encrypt(string, key):
    key = keystream(map(ord, key), len(string))
    stream = itertools.starmap(operator.xor, zip(key, map(ord, string)))

    return bytearray(stream)


if __name__ == "__main__":
    if sys.version_info >= (3, 0):
        sys.stdout.buffer.write(encrypt(sys.stdin.read(), sys.argv[1]))
    else:
        sys.stdout.write(encrypt(sys.stdin.read(), sys.argv[1]))

I omitted the mersenne_rng class: you don’t need it to solve the challenge. It’s a particular type of RNG, the one used by python2. Since the script is cross-version, I think it’s just there to ensure coherent results.

The encryption consists in XORing the input data with an array of integers, which is generated by the keystream function. This stream is composed of different blocks of 150 integers. Each block corresponds to a letter of the key, whose ASCII code is used to seed the RNG that generates the block integers.

The tricky part is that after adding an integer to the stream (called key here), it is shuffled:

key.append(random.get_rand_int(0, 255))
random.shuffle(key)

This makes brute-forcing the blocks independently pretty hard. Fortunately, we don’t have to!

$ wc -c involucrypt1
370 involucrypt1

The file is 370 bytes long, so the key must be 3 chars long (370 divided by 150 is 2.47). This is really short, so let’s brute-force it!

import math
import string
import itertools

# Note: I renamed the script `crypt.py` to `ccrypt.py`, to avoid naming issues.
from ccrypt import keystream

ALPHA = string.ascii_lowercase

with open("involucrypt1", "rb") as f:
    data = f.read()

block_count = math.ceil(len(data) / 150)
iterations = len(ALPHA) ** block_count

for index, key in enumerate(itertools.product(ALPHA, repeat=block_count)):
    percent = index / iterations * 100
    print(
        f"{percent:.2f}% ({index} / {iterations}) : " + "".join(key),
        end="\r",
        flush=True,
    )

    key = keystream(map(ord, key), len(data))

    decoded = ""
    valid = True

    for char_key, char in zip(key, data):
        decoded_char = chr(char_key ^ char)

        if decoded_char not in string.printable:
            valid = False
            break

        decoded += decoded_char

    if valid:
        print("\n")
        print(decoded)
        break

After a second and a half (thanks to pypy3) short seconds, we see :

$ pypy3 brute_1.py involucrypt1
1.95% (342 / 17576) : ane

The flag is: TheKeyIsTooDamnWeak!

Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed do eiusmod tempor
incididunt ut labore et dolore magna aliqua. Ut enim ad minim veniam, quis nostrud
exercitation ullamco laboris nisi ut aliquip ex ea commodo consequat. Duis aute irure
dolor in reprehenderit in voluptate velit esse cillum dolore eu fugiat nulla pariatur.

I assumed the key was only made up of lowercase letters, but if the bruteforce didn’t work, I would have started it again with ALPHA = string.printable.

The key is ane, and the flag is TheKeyIsTooDamnWeak!. See my writeup of involucrypt 2 for a better solution.

View all of the DG’hAck articles.