->*

Challenge 6 ("Chain of Demands")

Description

Congratulations, you are well past half finished with FLARE-On 12! its all downhill from here. Maybe you should just procrastinate and finish up these last couple of challenges on the last day.

This time, we are given an ELF executable named chat_client. I inspected it with IDA and noticed strings referencing Python and specifically PyInstaller, so I wasted no time and recovered the Python source code using pyinstxtractor and PyLingual.

The extracted files included the original source file, challenge_to_compile.py, a file named public.pem containing a PEM-encoded public key, and a JSON file chat_log.json tracking a history of messages exchanged in the chat. An excerpt is listed below for illustration:

[
  {
    "conversation_time": 24,
    "mode": "LCG-XOR",
    "plaintext": "Erm enable super safe mode",
    "ciphertext": "787cf6c0be39caa21b7908fcd1beca68031b7d11130005ba361c5d361b106b6d"
  },
  {
    "conversation_time": 30,
    "mode": "LCG-XOR",
    "plaintext": "Ok, activating now",
    "ciphertext": "632ab61849140655e0ee6f90ab00b879a3a3da241d4b50bab99f74f169d456db"
  },
  {
    "conversation_time": 242,
    "mode": "RSA",
    "plaintext": "[ENCRYPTED]",
    "ciphertext": "680a65364a498aa87cf17c934ab308b2aee0014aee5b0b7d289b5108677c7ad1eb3bcfbcad7582f87cb3f242391bea7e70e8c01f3ad53ac69488713daea76bb3a524bd2a4bbbc2cfb487477e9d91783f103bd6729b15a4ae99cb93f0db22a467ce12f8d56acaef5d1652c54f495db7bc88aa423bc1c2b60a6ecaede2f4273f6dce265f6c664ec583d7bd75d2fb849d77fa11d05de891b5a706eb103b7dbdb4e5a4a2e72445b61b83fd931cae34e5eaab931037db72ba14e41a70de94472e949ca3cf2135c2ccef0e9b6fa7dd3aaf29a946d165f6ca452466168c32c43c91f159928efb3624e56430b14a0728c52f2668ab26f837120d7af36baf48192ceb3002"
  }
]

The Python source defines several classes:

The SmartContracts class mediates deployment of contracts on the Ethereum blockchain (ugh!),
the LCGOracle and TripleXOROracle classes both contain bytecode of a specific contract and exposed a python interface to calling the respective contract functions,
ChatLogic defines, well... the chat logic, including encryption
and finally ChatApp creates a TkInter GUI.

The key component of the program logic lies in the ChatLogic.process_message method, which performs the actual encryption.

def process_message(self, plaintext):
    if self.conversation_start_time == 0:
        self.conversation_start_time = time.time()

    conversation_time = int(time.time() - self.conversation_start_time)

    if self.super_safe_mode and self.rsa_key:
        plaintext_bytes = plaintext.encode('utf-8')
        plaintext_enc = bytes_to_long(plaintext_bytes)
        _enc = pow(plaintext_enc, self.rsa_key.e, self.rsa_key.n)
        ciphertext = _enc.to_bytes(self.rsa_key.n.bit_length(), 'little').rstrip(b'\x00')
        encryption_mode = 'RSA'
        plaintext = '[ENCRYPTED]'
    else:
        prime_from_lcg = self.lcg_oracle.get_next(self.message_count)
        ciphertext = self.xor_oracle.encrypt(prime_from_lcg, conversation_time, plaintext)
        encryption_mode = 'LCG-XOR'

    log_entry = {'conversation_time': conversation_time, 'mode': encryption_mode, 'plaintext': plaintext, 'ciphertext': ciphertext.hex()}
    self.chat_history.append(log_entry)
    self.message_count += 1
    self.save_chat_log()
    return (f'[{conversation_time}s] {plaintext}', f'[{conversation_time}s] {ciphertext.hex()}')

Depending on whether "super safe mode" is used, either "LCG-XOR" or "RSA" encryption method is used. In the former case, the "LCG oracle" and "Triple XOR oracle" contracts are called to encrypt the plaintext. In the latter case, a naive RSA-like encryption (without any padding) is performed with some public key.

This leaves two paths open for investigation — we need to figure out what the contracts do and where the RSA key is from and if we can break the RSA encryption somehow.

Let's start with the contracts. The variable and function identifiers suggest that LCGOracle.get_next produces a pseudo-random number using a linear congruential generator (LCG), a famously insecure PRNG, and TripleXOROracle.encrypt encrypts the plaintext by "triple xoring" together it, the conversation timestamp, and the LCG output. (As we will see later, the LCG output may or may not be a prime, the identifier in that case is misleading.)

Before continuing with the technical stuff, let's quickly mention the naming choices. Both contracts have the word "oracle" in their names, which makes sense once you observe their definitions: In both cases, the ABI specifies the contract to be a pure function, meaning that it is a function in the mathematical sense; i.e. mapping inputs to outputs without producing side effects, mutating global state, etc. In other words, the function behaves deterministically with respect to its inputs, which is precisely the meaning of an oracle, at least in computer science.

class LCGOracle:
    def __init__(self, multiplier, increment, modulus, initial_seed):
        # ...
        self.contract_abi = [{
            'inputs': [
                {'internalType': 'uint256', 'name': 'LCG_MULTIPLIER', 'type': 'uint256'},
                {'internalType': 'uint256', 'name': 'LCG_INCREMENT', 'type': 'uint256'},
                {'internalType': 'uint256', 'name': 'LCG_MODULUS', 'type': 'uint256'},
                {'internalType': 'uint256', 'name': '_currentState', 'type': 'uint256'},
                {'internalType': 'uint256', 'name': '_counter', 'type': 'uint256'}
            ],
            'name': 'nextVal',
            'outputs': [{'internalType': 'uint256', 'name': '', 'type': 'uint256'}],
            'stateMutability': 'pure',
            'type': 'function'
        }]
# ...
class TripleXOROracle:
    def __init__(self):
        # ...
        self.contract_abi = [{
            'inputs': [
                {'internalType': 'uint256', 'name': '_primeFromLcg', 'type': 'uint256'},
                {'internalType': 'uint256', 'name': '_conversationTime', 'type': 'uint256'},
                {'internalType': 'string', 'name': '_plaintext', 'type': 'string'}
            ],
            'name': 'encrypt',
            'outputs': [
                {'internalType': 'bytes32', 'name': '', 'type': 'bytes32'}
            ],
            'stateMutability': 'pure',
            'type': 'function'
        }]

Conveniently, the ABI "metadata" contains argument names and types, hence we can write the function signatures (in a C-like syntax) as:

uint256_t nextVal(uint256_t LCG_MULTIPLIER, uint256_t LCG_INCREMENT, uint256_t LCG_MODULUS, uint256_t _currentState, uint256_t _counter);

byte32_t encrypt(uint256_t prime_from_lcg, uint256_t conversation_time, string_t _plaintext);

It may seem that the nextVal function has one more parameter than it ought to — remember that the LCG produces a value $x_n$ from $x_{n-1}$ using the following recurrence:

x_{n} = a \cdot x_{n-1} + c \bmod p

where $a$ is our LCG_MULTIPLIER, $c$ is the LCG_INCREMENT and $p$ the LCG_MODULUS. However, since we established that nextVal is a pure function, it cannot rely on any internal state to compute the result, and therefore, it always starts the computation with the seed (i.e. $x_0$ ) and iterates the generator _counter times to get the final value.

At this point, you could try to disassemble or decompile the Ethereum bytecode to verify these contracts do what their names claim, but it may be smarter to adhere to the YAGNI principle and explore the rest of the encryption logic first.

An obvious question to ask now is where the LCG parameters come from. The answer lies in ChatLogic._initialize_crypto_backend.

def _initialize_crypto_backend(self):
    self.seed_hash = self._get_system_artifact_hash()
    m, c, n = self._generate_primes_from_hash(self.seed_hash)
    self.lcg_oracle = LCGOracle(m, c, n, self.seed_hash)
    self.lcg_oracle.deploy_lcg_contract()
    print('[SETUP] LCG Oracle is on-chain...')
    self.xor_oracle = TripleXOROracle()
    self.xor_oracle.deploy_triple_xor_contract()
    print('[SETUP] Triple XOR Oracle is on-chain...')
    print('[SETUP] Crypto backend initialized...')

def _get_system_artifact_hash(self):
    artifact = platform.node().encode('utf-8')
    hash_val = hashlib.sha256(artifact).digest()
    seed_hash = int.from_bytes(hash_val, 'little')
    print(f'[SETUP]  - Generated Seed {seed_hash}...')
    return seed_hash

In human language, the parameters are chosen as primes derived from a SHA-256 hash of the machine's hostname (the _generate_primes_from_hash method simply iterates SHA-256 on the input to find primes). While this could in theory be brute-forced, intuition tells me that this challenge is about something more clever than that.

Indeed, looking at the chat logs, since we know 7 plaintext-timestamp-ciphertext triplets, we can reconstruct the first 7 outputs of the LCG by xoring each of the triplets together and then try to find the LCG modulus and other parameters.

Before doing that, let's check if the knowledge of the LCG parameters would help us decrypt the RSA messages. Let's see how the "super safe" RSA encryption is set up, starting in ChatApp.toggle_super_safe:

def toggle_super_safe(self):
    if self.super_safe_var.get():
        self.logic.super_safe_mode = True
        self.display_message_in_box('[SYSTEM] Super-Safe mode enabled. Generating RSA key...', 'system')
        Thread(target=self.generate_rsa_and_update_gui, daemon=True).start()
    else:
        self.logic.super_safe_mode = False
        self.display_message_in_box('[SYSTEM] Super-Safe mode disabled. Reverting to standard LCG-XOR.', 'system')

In turn, ChatApp.generate_rsa_and_update_gui calls ChatLogic.generate_rsa_key_from_lcg, listed below.

def generate_rsa_key_from_lcg(self):
    print('[RSA] Generating RSA key from on-chain LCG primes...')
    lcg_for_rsa = LCGOracle(self.lcg_oracle.multiplier, self.lcg_oracle.increment, self.lcg_oracle.modulus, self.seed_hash)
    lcg_for_rsa.deploy_lcg_contract()

    primes_arr = []
    rsa_msg_count = 0
    iteration_limit = 10000
    iterations = 0
    while len(primes_arr) < 8 and iterations < iteration_limit:
        candidate = lcg_for_rsa.get_next(rsa_msg_count)
        rsa_msg_count += 1
        iterations += 1
        if candidate.bit_length() == 256 and isPrime(candidate):
            primes_arr.append(candidate)
            print(f'[RSA]  - Found 256-bit prime #{len(primes_arr)}')

    print('Primes Array: ', primes_arr)
    if len(primes_arr) < 8:
        error_msg = '[RSA] Error: Could not find 8 primes within iteration limit.'
        print('Current Primes: ', primes_arr)
        print(error_msg)
        return error_msg
    else:
        n = 1
        for p_val in primes_arr:
            n *= p_val
        phi = 1
        for p_val in primes_arr:
            phi *= p_val - 1
        e = 65537

        if math.gcd(e, phi)!= 1:
            error_msg = '[RSA] Error: Public exponent e is not coprime with phi(n). Cannot generate key.'
            print(error_msg)
            return error_msg
        else:
            self.rsa_key = RSA.construct((n, e))
            # ...

The crucial observation here is that the LCG contract is redeployed with the exact same parameters as before and called with _counter equal to 0, 1, etc., the same way as before. The outputs are filtered for primes only and the first 8 are multiplied together to form the RSA modulus. If we could reproduce the LCG output sequence, we could clearly factor the modulus and decrypt the messages. This again strenghtens the hypothesis that the goal is to perform cryptanalysis on the LCG and reverse-engineer the parameters.

LCG Cryptanalysis

Given any three consecutive outputs of an LCG, it is trivial to find the multiplier and increment, provided we know the modulus and certain technical conditions between $a$ , $c$ and $p$ are met (but they usually are if the LCG is to be any good). Since

\begin{align*} x_1 &\equiv a \cdot x_0 + c \pmod p \\ \text{and } x_2 &\equiv a \cdot x_1 + c \pmod p, \end{align*}

we know that

x_1 - x_2 \equiv a (x_0 - x_1) \pmod p

and thus

a = (x_1 - x_2)(x_0 - x_1)^{-1} \bmod p.

Then, to find the increment $c$ , we can simply observe that

x_1 \equiv ax_0 + c \pmod p \iff c \equiv x_1 - ax_0 \pmod p.

In our situation, we don't have the modulus $p$ , which makes our life harder, but not impossible. As George Marsaglia noticed in 1968, sequences of consecutive LCG outputs form planes in 3D space, which gives rise to both algebraic and geometrical methods for recovering the modulus.

I implemented a method decribed by Moré which finds the LCG modulus as the greatest common divisor (GCD) of the determinants of all matrices containing two consecutive difference vectors. I am not going to go into a proof of why the method works, as I barely understand it myself, but know that the same method can be also (perhaps more intuitively) expressed in algebraic terms (though this one is more convenient to code).

import math

def lcg_find_params(sequence: list[int]) -> tuple[int, int, int, int]:
    def determinant(i, j, X):
        a1 = X[i] - X[0]
        b1 = X[i+1] - X[1]
        a2 = X[j] - X[0]
        b2 = X[j+1] - X[1]
        return abs(a1*b2 - a2*b1)

    lcg_mod = math.gcd(*(determinant(i, i + 1, sequence) for i in range(len(sequence) - 2)))

    differences = [sequence[i + 1] - sequence[i] for i in range(len(sequence) - 1)]
    lcg_mult = (differences[1] * pow(differences[0], -1, lcg_mod)) % lcg_mod
    lcg_incr = (sequence[1] - lcg_mult * sequence[0]) % lcg_mod
    lcg_seed = sequence[0] # We know this from context

    return lcg_seed, lcg_mult, lcg_incr, lcg_mod

Let's run this with the recovered outputs:

import json

def lcg_output_from_xor_pair(plaintext: str, ciphertext_hex: str, message_time: int) -> int:
    assert len(plaintext.encode()) <= 32

    pt = int.from_bytes(plaintext.encode() + (32 - len(plaintext.encode())) * b'\x00', "big")
    ct = int.from_bytes(bytes.fromhex(ciphertext_hex), "big")

    return (pt ^ ct ^ message_time)

with open("chat_log.json", "r") as f:
    chat = json.load(f)

lcg_outputs = []
for m in filter(lambda m: m["mode"] == "LCG-XOR", chat):
    lcg_outputs.append(lcg_output_from_xor_pair(m["plaintext"], m["ciphertext"], m["conversation_time"]))

lcg_seed, lcg_mult, lcg_incr, lcg_mod = lcg_find_params(lcg_outputs)

These were the intermediate results:

lcg_seed = 0xa151de1d76f12318fe16e8cd1c1678fd3b0a752eca163a7261a7e2510184bbe9
lcg_mult = 0x1919337810cc2fd68946430da81d00e60868547d33f321740f1b988b0db20c72
lcg_incr = 0x8708c5a5e5b369da11c7a68f0acac5211b040eb6b121bce5897496cf392b6c1b
lcg_mod  = 0xdab91d7e460d1c607dff2c152c9ca857ce2e317172850612dbb9fe38234aece1

RSA Factoring & Decryption

Now, having obtained the LCG parameters, we can reuse some of the code from the source to find the factors of the RSA modulus. One change that I made was that instead of checking if an output is a prime number (which is not difficult, but unnecessary here), I only check if it divides the RSA modulus.

# pip install cryptography
from cryptography.hazmat.primitives import serialization

def lcg_get_next(counter: int, lcg_seed: int, lcg_mult: int, lcg_incr: int, lcg_mod: int) -> int:
    x = lcg_seed
    for _ in range(counter):
        x = (lcg_mult * x + lcg_incr) % lcg_mod
    return x

with open("public.pem", "rb") as f:
    rsa_pubkey = serialization.load_pem_public_key(f.read()).public_numbers()
    rsa_modulus = rsa_pubkey.n
    rsa_pubexp = rsa_pubkey.e

primes_arr = []
iteration_limit = 100000
counter = 0
iterations = 0

while len(primes_arr) < 8 and iterations < iteration_limit:
    candidate = lcg_get_next(counter, lcg_seed, lcg_mult, lcg_incr, lcg_mod)
    counter += 1
    iterations += 1
    if candidate.bit_length() == 256 and rsa_modulus % candidate == 0:
        primes_arr.append(candidate)
        print(f'[RSA]  - Found 256-bit prime #{len(primes_arr)}')

After this, we have the following factors:

primes_arr = [
    0xa151de1d76f12318fe16e8cd1c1678fd3b0a752eca163a7261a7e2510184bbe9,
    0xb0028a8dd01b6d7e76ac89a11a8dd49e9c44ea08ed0f2b856982d37667d95fed,
    0xa6b0388650b40ddc160c59aadf60f7fa39dddff124ac4a2fd6d29d27ee3d17f1,
    0x8ae64b5e07a0990aafa7b36e4606d1277c403e89a7c00bf6c39ce18bc0023ed9,
    0x9a52f9a8d2276327a368c6df5360cdd43016537847ffad092cb9303eb00fb123,
    0x975366179f91f62c247d8ea1ebe3622810855f23f4a5a8163491cd3c05db7ac9,
    0xb723c8470645ac7f61f882c2306723a2001e0a48f04cf03904903d7585e0e70d,
    0xc44d8066725ff53c7fe28811d0b00e344c4351a86434cb781e97788a9ff8a07d,
]
assert math.prod(primes_arr) == rsa_modulus

Which allow us to find the private exponent (recall that $d = e^{-1} \bmod \varphi(n)$ ):

phi = math.prod(map(lambda x: x - 1, primes_arr))
rsa_privexp = pow(rsa_pubexp, -1, phi)

for m in filter(lambda m: m["mode"] == "RSA", chat):
    ct = int.from_bytes(bytes.fromhex(m["ciphertext"]), "little")
    pt = pow(ct, rsa_privexp, rsa_modulus).to_bytes(32, "big")
    try:
        print(pt.decode())
    except UnicodeDecodeError:
        print(pt)

Which prints the decrypted messages with the flag.

Actually what's your email?
It's W3b3_i5_Gr8@flare-on.com

While you may think that Web3 is great, and I will do my best not to judge you for it, it is obviously unwise to rely on just any bitcoin-style encryption to keep your private data safe. 😜 #DontRollYourOwnCrypto

Flag

W3b3_i5_Gr8@flare-on.com

Challenge 6 ("Chain of Demands")

Description

Writeup

LCG Cryptanalysis

RSA Factoring & Decryption

Flag