Cryptography is one of the most important safeguards applied over any data. To make data unreadable for unintended people is a really complex task, since if the encryption is not complex enough, it could easily be reverse engineered back to plaintext and thus our data becomes compromised.

In this blog we deal with Noncesense Encryption: a pun using Nonce(Number Used Only Once). It is a crypto-based lab on HackTheBox created by magicfrank00. If a Nonce is reused it leads to Nonsense. This lab deals with one of the two categories of Ciphers: Symmetric Ciphers; particularly Stream Ciphers and poses as an environment to show, how to crack Stream Ciphers.

What are stream ciphers?

A stream cipher is an encryption technique that works byte by byte to transform plain text into code that's unreadable to anyone without the proper key.

Stream ciphers are linear, so the same key both encrypts and decrypts messages. And while cracking them can be difficult, hackers have managed to do it. [No Encryption is 100% secure]

For that reason, experts feel stream ciphers aren't safe for widespread use. Even so, plenty of people still lean on the technology to pass information through the internet.

Workings of a stream cipher

Before getting into the lab it is very important to understand how exactly does a stream cipher function. Unlike block ciphers, stream ciphers intend to work on each bit of the data rather than dividing and encrypting them in blocks.

Stream Ciphers rely on:

• Plaintext. The message we want to encode

• Keystreams. A pseudorandom number generated using certain techniques which then replaces characters of the plaintext randomly. It could range anywhere from number, letters to even symbols

• Cipher Text. The final encrypted message created after performing all intended encryptions.

Generation of the key is a complicated process. Later we’ll look how our lab generates it’s key and see if we could exploit that to attain our flag.

Bits of plaintext enter the stream cipher, and the cipher manipulates each bit with the mathematical formula. The resulting text is completely scrambled, and the recipient can't read it without the proper key.
Spoiler: It’s really fun

Access to the lab

If you want to try your hand at the lab, you could click here

Upon running server.py we first assert that our FLAG has the format HTB{FLAG} and then run into the main() function. Here we create an instance of the class CustomEncryptionScheme() and enter an infinite loop awaiting user input. Whatever the user inputs is encrypted using the ces.encrypt(message).

encrypt(self, msg) —> __gen_key(self) —> __gen_base_key(self) —>__init__(self)

Into server.py:

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

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

def __init__(self):
        # __init__ initialises variables that used in the key generation
        self.generator = bytes_to_long(FLAG.encode()) #encoding our FLAG
        self.k = 0x13373 #static constant
        self.nonce = int(time()) #time at which the server starts
        self.counter = 0 #counter variable

__init__(self): Inside this function our FLAG is encoded into bytes and then turned to long. self.k is a static constant. self.nonce stores the time at which the server is started which will help us randomise and create more confusion. self.counter is another key element which causes more confusion in the encryption.

 def __gen_base_key(self):
        """
        __gen_base_key(self) is a function where a base is generated
        with the remainder when our FLAG is divided by some known constant, 
        i.e, (time + counter) * constant
        """ 
        key = self.generator % ((self.nonce + self.counter)*self.k)
        self.counter += 1
        return key

__gen_base_key(self): All of the data initialised in the previous function is then used by __gen_base_key(self) to generate our base key, which is just a remainder of our FLAG. self.counter is incremented everytime the function is invoked, leading to a different base key.

The formula simply translates to : key = FLAG % ((time + counter) * constant)

def __gen_key(self):
        key = self.__gen_base_key()
        kh = key >> 25 # shifts the base key and isolates high bits
        kl = key & 0x1ffffff # uses the AND operation to isolate low bits
        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

__gen_key(self): We perform a Pseudo-Random Number Generation (PRNG) algorithm. You can check this out PRNG .

Bit Slicing:

It slices the base key into two 25-bit halves.

• kh = key » 25 : This shifts the bits 25 places to the right, isolating the High 25 bits.

• kl = key & 0×1ffffff : This uses 0×1ffffff(binary for 25 1s) to isolate Low 25 bits.

Mixing:

• The new kl becomes the XOR of the old kh and kl.

• The new kh simply takes the value of the old kl.

Assembly:

Finally all of it is joined to form one huge integer

• new_key « 50 : This makes room for the next chunk by shifting the existing key 50 bits to the left.

• | tmp[i] : This uses a bitwise OR to drop the new 50-bit chunk into the empty space created.

This creates our 500-bit key (10 × 50 bits) and returns it to encrypt(self, msg)

def encrypt(self, msg) -> bytes:
        if type(msg) is str:
            msg = bytes_to_long(msg.encode()) #if msg is a string we turn it to bytes
        if type(msg) is bytes:
            msg = bytes_to_long(msg)

        key = self.__gen_key()
        return long_to_bytes(msg ^ key)

Inside the encrypt() method, upon checking if the msg is str or bytes we convert it to long type using the Crypto.Util.number long_to_bytes bytes_to_long. __gen_key() is used to generate our key

We use our newly generated key and XOR it with msg to create our encrypted message.

Finding the exploit:

Upon carefully observing the logic of server.py we find certain vulnerable parts

key = self.generator % ((self.nonce + self.counter)*self.k)

__gen_base_key() uses the Flag and a known mod to derive the internal state. This sets up the classic CRT(Chinese Remainder Theorem) which can be used to solve for the FLAG

kh, kl = kl, kh ^ kl

The mixing logic in __gen_key() is not foolproof. It is bidirectional, i.e, it can easily be reversed by an attacker.

So we as attacker could reverse the mixing logic, obtain the remainders and divisors pairs, and after gaining lots of equations we could use CRT to get the FLAG.

Chinese Remainder Theorem

The following is a general construction to find a solution to a system of congruences using the Chinese remainder theorem:

• Compute

$$N = n_1 \times n_2 \times ... \times n_k.$$

• For each i = 1,2,…, compute

$$y_i = \frac N {n_i} = n_1n_2...n_{i-1}n_{i+1}...n_k.$$

• For each i = 1,2,…,k, compute

$$z_i \equiv {y{_i}}^-1 \mod n_i$$

using Euclid’s Extended algorithm

• The integer

$$x = \sum^k_{i=1} a_iy_iz_i$$

is a solution to the system of congruences, and x mod N is the unique solution modulo N.

Read more about CRT here.

Finding the Flag:

Vulnerable Code Logic:

Key ≡ FLAG (mod ( Time + Counter ) ×K )

Extracting the Keystream:

We send a known plaintext( preferably a tiny one) to the server. Since our key is 500 bits and our msg is tiny, the top bits of the generated ciphertext are the pure keystream.

for i in range(60):
    r.sendlineafter(b': ', b'a')

    # ... receive cipher_hex ...

    # The message 'a' only affects the bottom 8 bits.
    # The top bits are pure key leakage.
    top_50_bits = cipher_int >> 450

Reversing the Mixing:

server.py attempts to hide the modular remainder by mixing bits using XOR and SWAP operations, but they are easily reversible, and we can use this to recover the original remainder

def reverse_mixing(tmp_val):
    kh = tmp_val >> 25
    kl = tmp_val & 0x1ffffff

    # The server does this 25 times: kh, kl = kl, kh ^ kl
    # We reverse it 25 times:
    for _ in range(25):
        kh, kl = kl ^ kh, kh

    return (kh << 25) | kl

So far, it seems really simple. However I hit my first roadblock in the next part, where we implement CRT to solve these equations.

We need our divisors to be pairwise coprime, i.e, their GCD should be 1. Since our divisors include self.nonce which are timestamps, even timstampes start sharing the same common factor 2, which blocks us from executing the solver.

So in order fix this I had to manually filter these pairs, to make sure that the two numbers did not share a common factor.

Filtering out moduli:

# COPRIME FILTERING
for t_guess in range(current_time - 2000, current_time + 2000):
    clean_moduli = []
    clean_rems = []

    for r_val, idx in zip(remainders, indices):
        m_cand = t_guess + idx


        is_coprime = True
        for m_existing in clean_moduli:
            if gcd(m_cand, m_existing) != 1:
                is_coprime = False
                break

        if is_coprime:
            clean_moduli.append(m_cand)
            clean_rems.append(r_val % m_cand)

• Selection (m_cand): We pick a candidate integer from our generated list.

• Verification: We iterate through every modulus already saved in clean_moduli

• Test(gcd(m_cand, m_existing) ≠ 1):

  • If gcd > 1, then there is a common factor.

  • We discard m_cand as it is incompatible with our current set.

• Acceptance:

  • If gcd(m_cand, m_existing)==1 for all m_cand ∈ clean_moduli, then it is "safe" to add.

Now you might think about why do we need so many samples, in our case 60?

That is precisely because we are selectively choosing our data and discarding what we don’t need. If our total sample size is too low then we end up with very less number of usable samples, and CRT fails. Thus with a large size like 60 we ensure that even after discarding, we have decent number of usable samples.

Brute-Forcing:

Since we don’t exactly know when the server starts, we wrap our entire solver in a loop checking a particular window of time.

# Search window (+/- 2000 seconds) to handle timezone differences
for t_guess in range(current_time - 2000, current_time + 2000):

    # ... filtering logic happens here ...

    try:
        res = libnum.solve_crt(clean_rems, clean_moduli)
        flag_bytes = long_to_bytes(res)

        if b'HTB{' in flag_bytes:
            print(f"[+] FOUND FLAG: {flag_bytes.decode()}")
            break
    except Exception:
        pass

FINALLY, we end up with the FLAG: HTB{1ts_*******CRypt0} [Solve the lab and find it out]

Conclusion : What I Learned

This lab wasn’t just about scripting in python, but rather deep dived into discrete mathematics and how complex cryptography is.

Here’s what I learned from this challenge:

• The challenge shows that no matter how complex the key generation might look in code, if our mathematical seed is derived directly from the secret (Flag % Modulus) , the entire process is easily reversible by the attacker. Here also we didn’t break anything, we just reversed whatever was being generated.

• In my opinion the biggest roadblock I faced, was in the math. The strict requirements of Chinese Remainder Theorem requiring the divisors to be pairwise coprime.

• To bypass the timestamp issue, we can’t just try harder. The implementation of the Greedy GCD Filter to structure a clean set of data was important. This taught me that effective exploit development often requires filtering our dataset to fit the constraints of our solver.