[Insane] ROT128

ROT128

9^th February 2024 / Document No. D24.102.33

Prepared By: aris

Challenge Author(s): aris

Difficulty: Insane

Classification: Official

Synopsis

• In this challenge, the task is to find collisions for a custom hash function. The resulting hash consists only of linear operations such as XOR and bitwise rotations. The player has to transform the problem into equations in the field $GF(2^{128})$, where XOR is equivalent to addition. Then they can automate the process to figure out $r_2, r_4, y$ and then $r_1, r_3, x$.

Description

• In the eerie stillness of the Bitting village, a dilapidated laboratory lies forgotten and forsaken, its ancient walls whispering secrets of unspeakable horrors. As you awaken within its confines, a shiver runs down your spine, the air thick with the weight of untold darkness. With no recollection of how you came to be here, you begin to explore the place. The dim glow of flickering lights casts long shadows across the worn floors, revealing rusted equipment and decaying machinery. The air is heavy with the scent of decay and abandonment, a tangible reminder of the atrocities that once transpired within these walls. Soon, you uncover the sinister truth lurking within the laboratory's forgotten depths. This place was a chamber of horrors, a breeding ground for abominable experiments in human cloning. The realization sends chills coursing through your veins, your mind reeling at the thought of the atrocities committed in the name of science. But there is no time to dwell on the horrors of the past, because a sinister countdown echoes through the laboratory, its ominous tones a harbinger of impending doom. Racing against the ticking clock, you discover the source of the impending catastrophe—a chemical reactor primed to unleash devastation upon the village. With the weight of the world upon your shoulders, you realize that you alone possess the knowledge to defuse the deadly device. As a chemist, you understand the delicate balance of chemical reactions, and you know that triggering a specific collision multiple times is the key to averting disaster. With steady hands and a racing heart, you get to work. As the seconds tick away, you feel the weight of the world bearing down upon you, but you refuse to falter.

Skills Required

• Sufficient experience in Python source code analysis.
• Basic research skills.
• Knowledge regarding extended Galois Fields $GF(2^n)$.

Skills Learned

• Become familiar with translating a problem from code to mathematical relations.
• Learn how to solve equations in $GF(2^n)$​ to find collisions for hash functions based on XOR and ROL operations.
• Learn how to convert XOR and other binary operations to polynomial representation.

Enumeration

In this challenge we are provided with a single file:

• server.py

This script contains the source code that runs when we connect to the remote instance.

Analyzing the source code

Let us first analyze the main flow of the server script.

ROUNDS = 3
N = 128

print('Can you test my hash function for second preimage resistance? You get to select the state and I get to choose the message ... Good luck!')

hashfunc = HashRoll()

for _ in range(ROUNDS):
    print(f'ROUND {_+1}/{ROUNDS}!')

    server_msg = os.urandom(32)
    hashfunc.reset_state()
    server_hash = hashfunc.digest(server_msg)
    print(f'You know H({server_msg.hex()}) = {server_hash.hex()}')

    signal.signal(signal.SIGALRM, handler)
    signal.alarm(2)

    user_state = input('Send your hash function state (format: a,b,c,d,e,f) :: ').split(',')

    try:
				user_state = list(map(int, user_state))
				
        if not validate_state(user_state):
            print("The state is not valid! Try again.")
            exit()

        hashfunc.update_state(user_state)

        if hashfunc.digest(server_msg) == server_hash:
            print(f'Moving on to the next round!')
            USED_STATES.append(sorted(user_state[:4]))
        else:
            print('Not today.')
            exit()
    except:
        print("The hash function's state must be all integers.")
        exit()
    finally:
       signal.alarm(0)

print(f'Uhm... how did you do that? I thought I had cryptanalyzed it enough ... {FLAG}')

First, an object of the custom hash function HashRoll is initialized that will be used through the rest of the challenge. It looks like that to get the flag, we have to complete a task 3 times in a row. The task is summarized as follows:

• The server generates a random 32-byte message and computes the server hash with the HashRoll hash function. We will dive into it later.
• We are asked to provide our own internal state of the hash function but we have only two seconds to do so.
• Finally, the server message is rehashed but this time with our provided state and if the hash matches the server hash, we get the flag. In other words, the goal, for each round, is the following:

Find a state $S'$ such that: $$ H_{S'}(M) = H_S(M) $$ where $S$ the random state that was generated to compute the server hash and $M$​ the server message. For the sake of brevity, we denote the components of the state $S$ as $x, y, r_1, r_2, r_3, r_4$, where $x, y$ the $N$-bit numbers to be rotated and $r_1, r_2, r_3, r_4$ the rotation offsets.

However, the server does not accept any input. There are the following checks:

• The rotation offsets should be less than $N = 128$​.
• $x, y$ should be at least $1$ and at most $2^N - 2$.
• The rotation offsets quadruple cannot be submitted more than once, when sorted in ascending order.
• The sum of the four rotate offsets must be greater or equal to 2. With this check, we make sure that the player does not submit three or more zero rotate offsets as this could potentially result in unintended solutions to the problem.

These checks are performed by the function validate_state:

def validate_state(state):
    if not all(0 < s < 2**N-1 for s in user_state[-2:]) or not all(0 <= s < N for s in user_state[:4]):
        print('Please, make sure your input satisfies the upper and lower bounds.')
        return False
    
    if sorted(state[:4]) in USED_STATES:
        print('You cannot reuse the same state')
        return False
    
    if sum(user_state[:4]) < 2:
        print('We have to deal with some edge cases...')
        return False

    return True

Analyzing the custom hash function

Let us first inspect how the custom hash function looks like.

_ROL_ = lambda x, i : ((x << i) | (x >> (N-i))) & (2**N - 1)

class HashRoll:
    def __init__(self):
        self.reset_state()

    def hash_step(self, i):
        r1, r2 = self.state[2*i], self.state[2*i+1]
        return _ROL_(self.state[-2], r1) ^ _ROL_(self.state[-1], r2)

    def update_state(self, state=None):
        if not state:
            self.state = [0] * 6
            self.state[:4] = [random.randint(0, N) for _ in range(4)]
            self.state[-2:] = [random.randint(0, 2**N) for _ in range(2)]
        else:
            self.state = state
    
    def reset_state(self):
        self.update_state()

    def digest(self, buffer):
        buffer = int.from_bytes(buffer, byteorder='big')

        m1 = buffer >> N
        m2 = buffer & (2**N - 1)

        self.h = b''
        for i in range(2):
            self.h += int.to_bytes(self.hash_step(i) ^ (m1 if not i else m2), length=16, byteorder='big')

        return self.h

In summary, the digest $H = h_1 || h_2$ of the message $M = m_1 || m_2$ is produced as: $$ h_1 = R(x, r_1) \oplus R(y, r_2) \oplus m_1\ h_2 = R(x, r_3) \oplus R(y, r_4) \oplus m_2 $$ where $R$ is the rotate left function.

There is also the update_state function which receives an optional parameter called state. This function updates the internal state, either with random numbers or with the provided state, if there is any.

At first glance the problem to solve seems straight forward - all we have to do is, given only $h_1, h_2, m_1, m_2$, find the state that hashes to $h'_1 = h_1$ and $h'_2 = h_2$. The issue is that we have a very short amount of time to do so and tools that could automate this process such as z3 fail. As a consequence, the player should figure out how to craft such states manually using mathematics.

Solution

Finding the vulnerability

To begin with, this challenge was inspired by this post in which the OP basically asks for the same thing. In fact, the core idea of the intended solution is based on the accepted answer. The vulnerability of this hash function is that it is entirely linear. The state is connected to $h_1$ and $h_2$ linearly using the XOR operation. For now, we will not bother with the rotate function $R$ as we will dive into it later on.

Since XOR and rotates are not convenient to work with, let us see whether we can transform them to simpler mathematical operations. Before moving on, let us first establish some preliminaries.

Galois Fields (GF)

Galois Field (GF) is an alternative name for a finite field. In simple words, a finite field is a ring with a prime modulus $p$. Both finite fields and rings consist of two groups; the additive and the multiplicative group. The additive group is a group of which the group operation is addition and the multiplicative group is a group of which the group operation is multiplication. The difference between a ring and a finite field is that every element of a finite field is invertible in both the additive and the multiplicative groups. In order for an element to be invertible, it must be coprime with $p$ and since $p$ is prime, all integers less than $p$ are coprime with it. This is not true in the case of rings as the modulus is not prime. The additive inverse $x$ of $a$ in additive groups is defined as: $$ a + x \equiv 0 \pmod p $$ while in multiplicative groups is defined as: $$ ax \equiv 1 \pmod p $$ This is similar to how we define usual inverses over the integers.

We shall denote Galois Fields over some prime modulus $p$ as $GF(p)$. An example of a finite field is $GF(7)$ which consists of the following elements: $$ {0, 1, 2, 3, 4, 5, 6} $$ Its additive group contains exactly the same numbers as $GF(7)$ but the multiplicative group does not include $0$ as it is not invertible.

Now take $GF(2)$ which consists of ${0,1}$. The addition in this field is defined as: $$ 0 + 0 \equiv 0 \pmod 2\ 0 + 1 \equiv 1 \pmod 2\ 1 + 0 \equiv 1 \pmod 2\ 1 + 1 \equiv 0 \pmod 2 $$ Notice that this is identical to the truth table of XOR. It looks like working in $GF(2)$, we can replace the operation of XOR with addition. The issue is that in the challenge, there are not only $2$ elements, but $2^{128}$ (as $N = 128$). It turns out that we can extend the idea of $GF(p)$ to work for powers of $p$ as well, such as $GF(p^N)$. In our case, $p = 2$ and $N = 128$.

The elements of $GF(p^N)$ are conventionally represented as polynomials of degree at most $N$ with coefficients in $GF(p)$. One having studied how AES works internally, they will have already stumbled upon the polynomial representation of elements in $GF(2^{128})$. More precisely, the MixColumns step involves exactly addition and multiplication in this galois field.

Polynomial Representation in Galois Fields

Let us explain how polynomial representation works by setting $n = 3$; that is $GF(2^3)$. This field contains 8 elements; $1$ through $7$ (inclusive). We shall define the elements of this field using polynomials of degree $2$ and coefficients in $GF(2)$.

Notice that this is identical to representing the numbers in binary format, when there is a $1$-bit the corresponding power of two is included otherwise it is omitted. But since we work with polynomials, there will be powers of $x$ and not powers of $2$​. Therefore:

Integer	Binary Representation	Polynomial Representation
0	$000$	$0x^2 + 0x^1 + 0x^0 = 0$
1	$001$	$0x^2 + 0x^1 + 1x^0 = 1$
2	$010$	$0x^2 + 1x^1 + 0x^0 = x$
3	$011$	$0x^2 + 1x^1 + 1x^0 = x + 1$
4	$100$	$1x^2 + 0x^1 + 0x^0 = x^2$
5	$101$	$1x^2 + 0x^1 + 1x^0 = x^2 + 1$
6	$110$	$1x^2 + 1x^1 + 0x^0 = x^2 + x$
7	$111$	$1x^2 + 1x^1 + 1x^0 = x^2 + x + 1$

In other words, the elements of $GF(2^8)$ are represented as: ${0,\ 1,\ x,\ x + 1,\ x^2,\ x^2 + 1,\ x^2 + x,\ x^2 + x + 1}$. Adding any two elements of this set is equivalent to XORing them so for example: $$ 7 + 5 = (x^2 + x + 1) + (x^2 + 1) = 2x^2 + x + 2 = x \equiv 2 $$ Notice that $2x^2$ and $2$ cancel out since the coefficients of these polynomials are defined in $GF(2)$, so $2$ is equivalent to $0$​.

Transforming left rotate and XOR to Galois Fields operations

As already discussed, the XOR operation can be expressed as addition in $GF(2)$ so all that is left is to figure out left rotate. According to the stackexchange post, we can represent left rotation as multiplication by powers of $2$. Rotation by $1$ bit is equivalent to multiplication by $2^1$, rotation by $2$ bits is equivalent to multiplication by $2^2$; in general, rotation by $k$ bits is equivalent to multiplication with $2^k$.

However, this is not entirely the case. Notice in the table above we introduced a variable $x$ to express the elements of $GF(2^3)$ as polynomials. It turns out that finite fields can define, what we call as polynomial rings. A polynomial ring in some variable $z$ over a finite field $\mathbb{F}_p$ is denoted as $\mathbb{F}_p[z]$ and it consists of polynomials of the form: $$ A = a_0 + a_1z + a_2z^2 + ... + a_nz^n $$ where the coefficients $a_i$​ are elements of $\mathbb{F}_p$​ and $z, z^2, ...$​ are symbols which are considered as powers of $z$​. In our challenge, the corresponding polynomial ring is $\mathbb{F}_2[z]$​.

Therefore, since the elements of polynomial rings are polynomials, we will represent left rotation by $k$ bits as multiplication by $z^k$ and not by $2^k$​.

Adjusting the solution to our challenge

The challenge task is to provide three distinct states to find collisions for three distinct messages. However the thread solution describes only one so we have to find two more and this is not something trivial to achieve.

Let us restate the problem that has to be solved. The sub-hashes are calculated as follows: $$ h_1 = R(x, r_1) \oplus R(y, r_2) \oplus m_1\ h_2 = R(x, r_3) \oplus R(y, r_4) \oplus m_2 $$ According to the thread solution, which does not include the extra XOR with $m_1$ and $m_2$, we know that the Hamming weights of both $h_1, h_2$ have the same parity; that is they are both odd or even. As a result, the Hamming Weight $h_1 \oplus h_2$ is always even. The hamming weight of a number $x$ is equal to the number of $1$-bits in its binary representation. Let us write a short script that checks this a few thousand times.

...
SNIPPED
...

def digest(self):
    self.h1 = self.hash_step(0)
    self.h2 = self.hash_step(1)
    return self.h1, self.h2

def hamming_weight(x):
    return bin(x).count('1')

hashroll = HashRoll()
for _ in range(10000):
    h1, h2 = hashroll.digest()
    # the parity of hamming_weight(h1) is the same as the parity of hamming_weight(h2)
    assert hamming_weight(h1) % 2 == hamming_weight(h2) % 2
    # hamming_weight(h1 XOR h2) is even
    assert hamming_weight(h1^^h2) % 2 == 0

This script completes successfully and no exception is raised which is a strong indication that the statement is true. By altering the digest method as follows:

def digest(self, buffer):
    buffer = int.from_bytes(buffer, byteorder='big')
    m1 = buffer >> N
    m2 = buffer & (2**N - 1)
    self.h1 = self.hash_step(0) ^^ m1
    self.h2 = self.hash_step(1) ^^ m2
    return self.h1, self.h2

the assertion check is not passed.

Nevertheless, let us proceed into figuring out a solution for $x, y, r_1, r_2, r_3, r_4$. Let us move $m_1, m_2$ into the other hand side and get: $$ h_1 \oplus m_1 = R(x, r_1) \oplus R(y, r_2) = H_1\ h_2 \oplus m_2 = R(x, r_3) \oplus R(y, r_4) = H_2 $$ At this point, following the solution in the thread post, we can set $r_1 = r_2 = r_3 = 0$ and $r_4 = 1$. Hence, $$ H_1 = x \oplus y\ H_2 = x \oplus zy $$ Then we can XOR the two hand-sides and get: $$ (z \oplus 1)y = H_1 \oplus H_2 $$ As $z \oplus 1$ is a factor of $H_1 \oplus H_2$, then the cofactor will be $y$. $$ y = \frac{H_1 \oplus H_2}{z \oplus 1} $$ Then we can solve for $x$ as: $$ x = H_1 \oplus y $$ However this worked because $H_1 \oplus H_2$ is divisible by $z \oplus 1$, but this is not always the case.

At this point we can make an assumption; $r_1$ and $r_3$ must be equal so that $x$ is eliminated when both hand-sides are XORed. However, in the challenge the sum $r_1 + r_2 + r_3 + r_4$ must be greater than 2. Therefore, setting $r_1 = r_2 = r_3 = 0$ and $r_4 = 1$ is out of question as the sum would be $1$​. These restrictions along with the 2-second timeout indicate that the solution needs to be automated.

First of all, let us write a function that connects to the challenge instance and receives the server message and its corresponding digest.

from Crypto.Util.number import isPrime, long_to_bytes as l2b

def get_server_message_and_hash(io):
		io.recvuntil(b'H(')
    server_msg = int(io.recv(64), 16)
    io.recvuntil(b' = ')
    server_hash = l2b(int(io.recvline().strip().decode(), 16))
    return server_msg, server_hash

Next, we need two Sage functions; one that extracts $m_1, m_2$ from the server message and another one that computes $H_1 = h_1 \oplus m_1, H_2 = h_2 \oplus m_2$​.

from Crypto.Util.number import bytes_to_long as b2l

N = 128

def extract_m1_m2(server_msg):
    m1 = server_msg >> N
    m2 = server_msg & (2**N - 1)
    return m1, m2

def compute_H1_H2(server_msg, server_hash):
		m1, m2 = extract_m1_m2(server_msg)
		H1 = b2l(server_hash[:16]) ^^ m1
    H2 = b2l(server_hash[16:]) ^^ m2
    return H1, H2

However, as aforementioned, all operations must be performed in the Polynomial Ring of $GF(2^{128})$ so we need two functions that converts an integer to an element of the polynomial ring and vice versa.

N = 128
F.<w> = GF(2^N)
PR.<z> = PolynomialRing(GF(2))

def int2pre(i):
    coeffs = list(map(int, bin(i)[2:].zfill(N)))[::-1]
    return PR(coeffs)

def pre2int(p):
    coeffs = p.coefficients(sparse=False)
    return sum(2**i * int(coeffs[i]) for i in range(len(coeffs)))

int2pre takes the binary representation of the integer, reverses it, and converts it to a polynomial. pre2int takes the coefficients of the polynomial and converts back to an integer.

Figuring out $r_2, r_4$

Now we need a way to ensure that we get a distinct valid factor of $B = H_1 \oplus H_2$ three times in a row. This requires us to factor the value of $B$, check its factors and find one that can be written in the form $2^{r_2} + 2^{r_4}$. In the case where $r_2 = 0, r_4 = 1$ this is equal to $2^0 + 2^1 = 3$. One can do a lot of testing to see that $3$ is almost always a factor of $B$. However, it would be convenient if we had a list of all the possible numbers that can be written in the form $2^{r_2} + 2^{r_4}$, so let us write a function to compute these numbers.

def get_all_possible_candidates():
    powers = '0123456789'
    cands = itertools.product(powers, repeat=2)
    d = {}
    for cand in set(cands):
        r2 = int(cand[0])
        r4 = int(cand[1])
        s = 2**r2+2**r4
        d[s] = sorted([r2, r4])
		return d

The format of each key-value pair is $(2^{r_2} + 2^{r_4} : [r_2, r_4])$.

{
	513: [0, 9],
	8: [2, 2],
	3: [0, 1],
	136: [3, 7],
	36: [2, 5],
	68: [2, 6],
	... SNIPPED ...
	66: [1, 6],
	544: [5, 9],
	128: [6, 6],
	1024: [9, 9]
}

Therefore each time, we can iterate through each candidate and check if it is a factor of $B$. If that's the case and the candidate is already used in previous states, keep the values of $r_2, r_4$.

Let us write a function that factors $B$ and extracts a candidate.

def extract_r2_r4_candidate(B, d, visited):
		factors = sorted([F(i^j).to_integer() for i,j in list(B.factor())])

    for fact in factors:
        if fact in visited:
            continue

        if fact in d:
            r2, r4 = d[fact]
            visited.append(fact)
            return (r2, r4)

Figuring out the rest of the state

At this point we can solve for $y$ as:

y = B / int2pre(2^r2 + 2^r4)

Then, $x$ can be obtained as: $$ x = \frac{H_1 \oplus (y * 2^{r_2} )}{2^{r_1}} $$ Again, this requires $2^{r_1}$ to be a factor of the numerator. To ensure this is the case, we can follow similar procedure as we did to figure out $y$. The idea is to factor the numerator and iterate over the factors until $2^{r_1}$ is found. Then we select this specific value for $r_1$ (and $r_3$). Let us write a function that factors the numerator and extracts all the possible candidates for $r_1, r_3$.

def extract_r1_r3_candidates(numer):
    numer_factors = sorted([F(i^j).to_integer() for i,j in list(numer.factor())])
    cands = []
    for factor in numer_factors:
        r1 = int(math.log2(factor))
        if 2^r1 == factor:
            r3 = r1
            cands.append((r1, r3))
    return cands

Then for each candidate, it is tested whether $H_1, H_2$ are obtained using the state $r_1, r_2, r_3, r_4, x, y$. In that case, we send the state to the server and proceed to the next round.

Exploitation

Finally, let us write a function that submits the state.

def send_state(io, r1, r2, r3, r4, x, y):
		io.sendlineafter(b' :: ', f'{r1},{r2},{r3},{r4},{x},{y}'.encode())

To summarize, the skeleton of the solver is the following and is the part that runs until three collisions are found in the row.

def run_task(io, d, used_states, visited):
  	server_msg, server_hash = get_server_message_and_hash(io)

    if len(server_hash) < 32:
        return None

    H1, H2 = compute_H1_H2(server_msg, server_hash)

    B = int2pre(H1) + int2pre(H2)

    if not B:
    		return None
      
    r2_r4_cand = extract_r2_r4_candidate(B, d, visited)

    if not r2_r4_cand:
    		return None
      
    r2, r4 = r2_r4_cand

    assert B.mod(int2pre(2^r2 + 2^r4)) == 0

    y = B / int2pre(2^r2 + 2^r4)
    numer = int2pre(H1) - y * int2pre(2^r2)

    r1_r3_cands = extract_r1_r3_candidates(numer)

    if not r1_r3_cands:
    		return None
      
    for (r1, r3) in r1_r3_cands:
        x = numer / int2pre(2^r1)
        x = pre2int(PR(x))
        y = pre2int(PR(y))

        if sorted([r1, r2, r3, r4]) in used_states:
            continue

        if H1 == R(x, r1) ^^ R(y, r2) and H2 == R(x, r3) ^^ R(y, r4):
            state = r1, r2, r3, r4, x, y
            return state

Getting the flag

A final summary of all that was said above:

1. First, we noticed that to get the flag, we have to provide three distinct states to find a collision for three different messages.
2. The task is to solve a linear system of equations that consists of XOR and bitwise rotate operations.
3. We can represent this system as equations in $GF(2)$ because in this field, XOR is equivalent to addition.
4. We factored $H_1 + H_2$ and found a candidate for $r_2, r_4$. Then we solved for $y$.
5. Having obtained the above, we can apply the process similarly to find $r_1, r_3$ and $x$.

This recap can be represented by code with the pwn() function:

def pwn():
  	d = get_all_possible_candidates()
		while True:
        used_states = []
        visited = []
        done = 0
        io = remote('0.0.0.0', 1337)
        
        for _ in range(ROUNDS):
            state = run_task(io, used_states, visited)
            if state:
                r1, r2, r3, r4, x, y = state
                send_state(io, r1, r2, r3, r4, x, y)
                done += 1
                used_states.append(sorted([r1, r2, r3, r4]))
                print(f'round {done} done!')
                
                if done == ROUNDS:
                    io.recvline()
                    print(io.recvline().decode())
                    exit()
            else:
                print('fail!')
                io.close()
                break

if __name__ == '__main__':
		pwn()