Challenge Description

Danish (original)

I en skjult dal i Asgård har jætterne udviklet en algoritme, som de hævder er uigennemtrængelig. Vi har fået adgang til nogle filer på tilforladelige måder. Herunder det output, der var på skærmen, da jætterne krypterede en vigtig besked.

Vi har desværre ikke nogen der er kyndige i jættekode. Måske du kan cracke deres kryptering?

English (from chatgpt)

In a hidden valley in Asgard, the giants have developed an algorithm that they claim is impenetrable. We have gained access to some files through reliable means. Below is the output that appeared on the screen when the giants encrypted an important message.

Unfortunately, we don’t have anyone skilled in giant code. Maybe you can crack their encryption?

File

We are also given the following file:

Solution

Unzipping the file we see that it contains two python scripts, two binary files and some output:

$ unzip filedump.zip
Archive:  filedump.zip
  inflating: cipher.bin
  inflating: encryption_output.txt
  inflating: encrypt.py
  inflating: iv.bin
  inflating: jaette_random_tools.py

$ cat encryption_output.txt
Secret jætte-key: 
De kommer aldrig igennem vores avancerede krypteringsalgoritme
HuihuheHiihaHeehheHiihaHaeHaaahaHiihaHohhaoHuooHyu
iv.bin not found, creating a default one

Encryption complete and written to 'cipher.bin'

Looking at encrypt.py we can see how the flag is encrypted:

from jaette_random_tools import ThorLCG, JaetteAES
import getpass
import hashlib


# Initialize the LCG with exposed parameters
a = 1664525
c = 1013904223
m = 2**32
password = getpass.getpass("Secret jætte-key: ")
seed = int(hashlib.sha256(password.encode()).hexdigest(), 16) % m
rng = ThorLCG(seed, a=a, c=c, m=m)

# Post signature jætte laugh, but make it random to make it more scary
laughparts = [
    "Haaaha",
    "Heehhe",
    "Hiiha",
    "Ha",
    "Huihuhe",
    "Hae",
    "Huoo",
    "Hohhao",
    "Hua",
    "Hyu",
]

print("De kommer aldrig igennem vores avancerede krypteringsalgoritme")

laugh_seed = rng.next()
print("".join([laughparts[int(l)] for l in str(laugh_seed)]))

# Generate a secret key
key = bytes([rng.get_random_byte() for _ in range(16)])  # 128-bit key

# Check that an iv.bin file is present, otherwise make one
try:
    with open("iv.bin", "rb") as iv_file:
        iv = iv_file.read()
except FileNotFoundError:
    print("iv.bin not found, creating a default one")
    # Create a default 
    iv = bytes(rng.get_random_byte() for _ in range(16))
    with open("iv.bin", "wb") as iv_file:
        iv_file.write(iv)

# Encrypt a super secret message using the secret key
with open("message.txt", "r") as message_input_file:
    payload = message_input_file.read()
cipher = JaetteAES(key)
ciphertext = cipher.encrypt(payload)

# Save the ciphertext to a file to be shared with jætte receivers
with open("cipher.bin", "wb") as cipher_file:
    cipher_file.write(ciphertext)

print("\nEncryption complete and written to 'cipher.bin'")

Since the key is generated by pulling values from the rng, breaking this randomness generator could let us generate the same key. We dont have the original seed because that is taken in by getpass.

But since the laugh from the output is also generated by a rng value we may be able to recover it and use it to recreate the values for the key.

From the name ThorLCG, we know that it is a Linear congruential generator and these are NOT cryptographically secure.

Looking at the implementation of ThorLCG from jaette_random_tools.py we can see that it is changing its state using a, c, and m that we know from encrypt.py and then returning the new state:

class ThorLCG:
    """
    Thor's Linear Congruent Generator for generating thunderous random numbers.
    Harness the power of Mjölnir.
    """
    def __init__(self, seed, a, c, m):
        self.state = seed
        self.a = a
        self.c = c
        self.m = m

    def next(self):
        self.state = (self.a * self.state + self.c) % self.m
        return self.state

    def get_random_byte(self):
        """Return a random byte (0-255)"""
        return self.next() % 256

So reversing the laugh will give us a state that we can then begin a new ThorLCG with as the initial state and the next values should then be the same as the ones used to generate the key, and then decrypt cipher.bin.

My solve script:

from jaette_random_tools import ThorLCG, JaetteAES
import re

a = 1664525
c = 1013904223
m = 2**32

laughs = re.split(
    '(H[^H]*)',
    "HuihuheHiihaHeehheHiihaHaeHaaahaHiihaHohhaoHuooHyu"
)[1::2]

laughparts = [
    "Haaaha",
    "Heehhe",
    "Hiiha",
    "Ha",
    "Huihuhe",
    "Hae",
    "Huoo",
    "Hohhao",
    "Hua",
    "Hyu",
]

laugh_seed = 0

for laugh in laughs:
    laugh_seed *= 10
    laugh_seed += laughparts.index(laugh)

rng = ThorLCG(laugh_seed, a=a, c=c, m=m)

key = bytes([rng.get_random_byte() for _ in range(16)])

with open('cipher.bin', 'rb') as cipher_file:
    ciphertext = cipher_file.read()

cipher = JaetteAES(key)
plaintext = cipher.decrypt(ciphertext)

print(plaintext)

And running my solve script we get the flag:

$ python solve.py
Alle Jættestyrker: Husk nu at bruge en god random number generator!
FDCA{YOU_BROKE_THE_RNG}