Noncesense Encryption — HackTheBox

Description

The challenge presents a custom stream cipher implementation. The server encrypts user-provided messages using a custom key generation scheme where the FLAG itself is used as the "generator" (seed) for key derivation. The encryption is simple XOR: encrypt(msg) = msg ^ key, where the key is derived from the flag through a deterministic but obfuscated process involving a time-based nonce and an incrementing counter.

Source Code (server.py)

from time import time
from Crypto.Util.number import bytes_to_long, long_to_bytes

FLAG = open('flag.txt').read()

class CustomEncryptionScheme:
    def __init__(self):
        self.generator = bytes_to_long(FLAG.encode())
        self.k = 0x13373
        self.nonce = int(time())
        self.counter = 0

    def __gen_base_key(self):
        key = self.generator % ((self.nonce + self.counter)*self.k)
        self.counter += 1
        return key

    def __gen_key(self):
        key = self.__gen_base_key()
        kh = key >> 25
        kl = key & 0x1ffffff
        tmp = []
        for __ in range(10):
            for _ in range(25):
                kh, kl = kl, kh ^ kl
            tmp.append(kh << 25 | kl)
        new_key = 0
        for i in range(10):
            new_key = (new_key << 50) | tmp[i]
        return new_key

    def encrypt(self, msg) -> bytes:
        if type(msg) is str:
            msg = bytes_to_long(msg.encode())
        if type(msg) is bytes:
            msg = bytes_to_long(msg)
        key = self.__gen_key()
        return long_to_bytes(msg ^ key)

def main():
    ces = CustomEncryptionScheme()
    banner = """
--------------------------------
I feel like I'm a master of OTPs now
--------------------------------
This key generation scheme allows me to just use a single key to encrypt all my messages!
--------------------------------
Please go ahead and test it!"""
    print(banner)
    while True:
        message = input("Enter a message to encrypt (or type 'exit' to quit): ")
        if message.lower() == 'exit':
            break
        encrypted_message = ces.encrypt(message)
        print(f"Encrypted Message: {encrypted_message.hex()}")

if __name__ == '__main__':
    assert FLAG.startswith('HTB{') and FLAG.endswith('}')
    main()

Analysis

Three vulnerabilities are exploited sequentially:

Vulnerability 1: Known-Plaintext XOR Recovery

The encryption is simple XOR: encrypt(msg) = msg ^ key. By sending a known message (63 characters 'A' = 504 bits, covering the 500-bit key space), we recover the full XOR key:

key = bytes_to_long(known_msg) ^ bytes_to_long(ciphertext)

Vulnerability 2: Reversible Key Mixing (__gen_key)

The __gen_key function splits base_key into kh (upper 25 bits) and kl (lower 25 bits), then applies the recurrence relation kh, kl = kl, kh ^ kl 25 times.

Key observation: This is a linear transformation over GF(2), represented by the matrix:

M = [[0, 1],
     [1, 1]]

Critical fact: M^3 = I (identity matrix modulo 2). Therefore:

• M^25 = M^(25 mod 3) = M^1
• Inverse matrix: M^(-1) = M^2 = [[1,1],[1,0]]

This means:

orig_kh = kh_after ^ kl_after
orig_kl = kh_after

The 500-bit output key consists of 10 chunks of 50 bits each. We extract the first chunk (tmp[0]), apply the inverse transformation, and recover the original base_key.

Vulnerability 3: Flag Recovery via CRT

Each call gives us:

base_key_i = generator % ((nonce + i) * 0x13373)

where generator = bytes_to_long(FLAG).

This gives us the flag modulo different values for each counter value i. With ~20 samples and the generalized Chinese Remainder Theorem (for non-coprime moduli), we accumulate enough information to fully recover generator (the flag as an integer).

The nonce is int(time()) at connection time. We record the time window and brute-force a small range of possible nonce values.

Solution

#!/usr/bin/env python3
from pwn import *
from Crypto.Util.number import bytes_to_long, long_to_bytes
from math import gcd
from time import time
import sys

K_CONST = 0x13373

def reverse_gen_key(new_key):
    """Reverse __gen_key: extract first 50-bit chunk and invert the GF(2) mixing."""
    tmp0 = (new_key >> 450) & ((1 << 50) - 1)
    kh_after = (tmp0 >> 25) & 0x1FFFFFF
    kl_after = tmp0 & 0x1FFFFFF
    # M^(-1) = M^2 = [[1,1],[1,0]]: orig_kh = kh^kl, orig_kl = kh
    kh_orig = kh_after ^ kl_after
    kl_orig = kh_after
    base_key = (kh_orig << 25) | kl_orig
    return base_key

def gen_key_forward(base_key):
    """Forward __gen_key for verification."""
    kh = base_key >> 25
    kl = base_key & 0x1FFFFFF
    tmp = []
    for __ in range(10):
        for _ in range(25):
            kh, kl = kl, kh ^ kl
        tmp.append(kh << 25 | kl)
    new_key = 0
    for i in range(10):
        new_key = (new_key << 50) | tmp[i]
    return new_key

def extended_gcd(a, b):
    old_r, r = a, b
    old_s, s = 1, 0
    old_t, t = 0, 1
    while r != 0:
        quotient = old_r // r
        old_r, r = r, old_r - quotient * r
        old_s, s = s, old_s - quotient * s
        old_t, t = t, old_t - quotient * t
    return old_r, old_s, old_t

def general_crt(remainders, moduli):
    """Generalized CRT for non-coprime moduli."""
    r, m = remainders[0], moduli[0]
    for i in range(1, len(remainders)):
        r2, m2 = remainders[i], moduli[i]
        g = gcd(m, m2)
        if (r - r2) % g != 0:
            return None, None
        lcm_val = m * m2 // g
        _, x, _ = extended_gcd(m // g, m2 // g)
        x = x * ((r2 - r) // g) % (m2 // g)
        r = (r + m * x) % lcm_val
        m = lcm_val
    return r, m

def exploit():
    HOST = "TARGET_IP"
    PORT = 31804
    N_SAMPLES = 20
    known_msg = "A" * 63  # 504 bits > 500-bit key space
    known_msg_int = bytes_to_long(known_msg.encode())

    time_before = int(time())
    r = remote(HOST, PORT)
    time_after = int(time())

    r.recvuntil(b"quit): ")

    base_keys = []
    for i in range(N_SAMPLES):
        r.sendline(known_msg.encode())
        resp = r.recvline().decode().strip()
        r.recvuntil(b"quit): ")
        hex_str = resp.replace("Encrypted Message: ", "")
        enc_int = bytes_to_long(bytes.fromhex(hex_str))
        full_key = known_msg_int ^ enc_int
        base_key = reverse_gen_key(full_key)
        # Verify the reversal is correct
        if gen_key_forward(base_key) != full_key:
            continue
        base_keys.append(base_key)

    r.sendline(b"exit")
    r.close()

    # Brute-force nonce (small time window)
    for nonce in range(time_before - 10, time_after + 10):
        moduli = [(nonce + i) * K_CONST for i in range(len(base_keys))]
        # Verify base_key < modulus (required for modular reduction)
        if not all(bk < m for bk, m in zip(base_keys, moduli)):
            continue
        recovered, mod = general_crt(base_keys, moduli)
        if recovered is None:
            continue
        # Try multiples in case CRT modulus < flag value
        for k_mult in range(200):
            candidate = recovered + k_mult * mod
            try:
                flag = long_to_bytes(candidate).decode("ascii")
                if "HTB{" in flag and flag.endswith("}"):
                    print(f"FLAG: {flag}")
                    return flag
            except:
                pass
    return None

if __name__ == "__main__":
    exploit()

Mathematical Details

GF(2) Matrix Analysis

The recurrence (kh, kl) -> (kl, kh ^ kl) is multiplication by the Fibonacci matrix over GF(2):

M = [0 1]    M^2 = [1 1]    M^3 = [1 0] = I
    [1 1]          [1 0]          [0 1]

Period = 3, so M^25 = M^(25 mod 3) = M^1, and inversion is trivial: M^(-1) = M^2.

CRT Recovery

Having r_i = G mod m_i for m_i = (nonce + i) * K, the generalized CRT gives G mod lcm(m_0, m_1, ..., m_19). With enough samples, the LCM exceeds the flag value, and recovery is unique.