The challenge

This challenge basically consisted in recovering a flag that was encrypted using an algorithm based on random numbers generation from a seed, knowing only the first number generated and the encrypted text.

The algorithm

The algorithm used to encrypt the flag was as follows:

import random

def get_seed(l):
	seed = 0
	rand = random.getrandbits(l)
	raw = list()
	while rand > 0:
		rand = rand >> 1
		seed += rand
	if len(raw) == l:
		return raw, seed
		return get_seed(l)

def encrypt(m):
	l = len(m)

	raw, seed = get_seed(l)

	with open('encrypted.txt', 'w') as f:	
		for i in range(l):
			r = random.randint(1, 2**512)
			if i == 0:
				print("r0 =",r)
			encoded = hex(r ^ m[i] ^ raw[i])[2:]
			f.write(f"F{i}:  {encoded}\n")

First, the length l of the plain message m is calculated and used as input for the function getrandbits() from Python’s module random, obtaining a random number rand of l bits. Then, rand is bit-shifted to the right (which is equivalent to dividing by 2) until it reaches 0, and its value is added to seed and appended to the list raw at each iteration. At the end, raw would have a size of l and \(seed=\sum_{i=1}^l \frac{rand}{2^{i}}\) (the sum of all elements at raw). This seed is used in random.seed() to initialize Python’s PRNG (Pseudo Random Number Generator).

The encryption is then performed using a bitwise xor between each character of the text, an element from raw with the same index and a random number generated from the seed.

Tony Stark and James Rhodes

One of the files provided for this challenge was a PDF containing a transcription of the fictional conversation between Tony Stark (the player) and James Rhodes (the guy that encrypted the flag). At the end of this transcription, we have a big clue to solve this challenge, the first random number (r0) generated from the seed during the encryption.

r0 = 1251602129774106047963344349716052246200810608622833524786816688818258541877890956410282953590226589114551287285264273581561051261152783001366229253687592

Recovering the seed

Normaly, knowing only the first number from a random sequence would not help that much, but on this case, it is all that we need to recover the seed and with that the whole text.

Remember that for each character with index i, we do a xor with raw[i] and a new random number. What means that if we already know the first random number, and also the first characters of the flag (which has the format darkCON{.+}), we can find raw[0]. Because of how the list raw is filled, we have that raw[i+1] is equal to raw[i] / 2. And as seed is the sum of the elements on this list, it can be recovered as well.

Looking into the file encrypted.txt we have one line for each character of the flag, with the hex representation of the encrypted character. To recover the list raw, we can start with F0 (the first character) and after converting it to a base 10 number, perform an xor with r0 and the already known decrypted value of it ‘d’, obtaining raw[0]. After that, we can repeat the steps of the encryption algorithm to find the remaining values:

raw = [ F0 ^ r0 ^ ord('d')]
raw.extend([ raw[0] // 2 ** i for i in range(1, len(lines)) ])
seed = sum(raw)

Finally, we use the value of seed to seed the PRNG and repeat the same steps of the encryption routine to get the flag back.

Full decryption code

My final code was something like:

#!/usr/bin/env python3

import random

r0 = 1251602129774106047963344349716052246200810608622833524786816688818258541877890956410282953590226589114551287285264273581561051261152783001366229253687592
lines = [ int(l.rstrip().split(' ')[2], 16) for l in open("encrypted.txt", "r").readlines() ]
raw = [ lines[0] ^ r0 ^ ord('d')]
raw.extend([ raw[0] // 2 ** i for i in range(1, len(lines)) ])
seed = sum(raw)
print("".join( [ chr(lines[i] ^ raw[i] ^ random.randint(1, 2**512)) for i in range(len(lines)) ] ) )

And the flag was: darkCON{user_W4rm4ch1ne68_pass_W4RM4CH1N3R0X_t0ny_h4cked_4g41n!}

And that’s all, folks.