Hash Breaker

23/03/2024

Tania , Mark 5

Challenge

Introduction

We are provided by the challenge 2 things:

a hash: “1a061d36422e5a08190009ddfd34d74d603f2f7c384a08b3521c08130d171dcf”,
and the function used to obtain it:

  
def ultrabrend(message):
    if len(message) < 29:
        message = ((message + " ") * 29)[:29]

    digest = [0]*32

    for i in range(len(message)):
        digest[i % 29] ^= ord(message[i])

    t = digest[0] * digest[28]

    for i in range(28):
        digest[i] = (digest[i] + digest[i+1]) % 256

    digest[28] = t // 256
    digest[29] = t % 256
    digest[30] = 0xff ^ len(message)
    digest = digest[16:] + digest[:16]

    for i in range(32):
        digest[i] ^= digest[(i+1) % 32] ^ i

    return "".join(["{:02x}".format(i) for i in digest])


string = input("Enter a message: ")
print("Hash:", ultrabrend(string))

Our goal is to obtain the initial message by reversing the hashing function.

First things first, the ending

This is the last operation made on digest[ ], the list returned as hex:

  
for i in range(32):
    digest[i] ^= digest[(i+1) % 32] ^ i

For the theoretical part, let $final[ ]$ be the list we’ve got, and $initial[ ]$ be the list before being processed by this step.

Now, to break it down:

$final[0] = initial[0] \oplus initial[1] \oplus 0,$
$final[1] = initial[1] \oplus initial[2] \oplus 1,$
$...$
$final[30] = initial[30] \oplus initial[31] \oplus 30$

and for 31, `(i+1) % 32` will take us back to index 0, which has been modified already:
$final[31] = initial[31] \oplus final[0] \oplus 31.$

From here, initial[31] becomes known,
$initial[31] = final[31] \oplus final[0] \oplus 31$

and can be used to find the entire initial list:
$initial[30] = initial[31] \oplus final[30] \oplus 30,$
$...$
$initial[0] = initial[1] \oplus final[0] \oplus 31.$

Now that we understand what it does, we can reverse it:

  
digest[31] = digest[31] ^ digest[0] ^ 31

for i in range(30, -1, -1):
    digest[i] = digest[i] ^ digest[i + 1] ^ i

Accessories

The next line (bottom-up) performs something like cutting the deck in cards and can easely be undone by repeating the process.

  
digest = digest[16:] + digest[:16]

The “accessories” we receive next are the length of the message and t (because $t = q \cdot 256 + r$, where q = t// 256 and r = t % 256).

digest[28] = t // 256
digest[29] = t % 256
digest[30] = 0xff ^ len(message)

To find the length, xor again: len = digest[30] ^ 255.

Our new knowns are $t$, $length$ and $final$ (the new final, the current one, before being processed at the step presented above). Remember length, it will come in handy later ;).

A little more math

for i in range(28):
    digest[i] = (digest[i] + digest[i+1]) % 256

This (+accessories) modifies the digest:

list	0	1	…	27	28	29	30	31
final	$x_0+x_1$	$x_1+x_2$		$x_{27}+x_{28}$	`t // 256`	`t % 256`	length	0
initial	$x_0$	$x_1$		$x_{27}$	$x_{28}$	0	0	0

Now we can reconstruct $t$ as final[28] * 256 + final[29]. This variable was initialized before this for, using the initial digest:

t = digest[0] * digest[28],

so we know that $t = x_0 \cdot x_{28}$.

To find a second equation using $x_0$ and $x_{28}$, we use final[ ]: $final[27] = x_{27} + x_{28}$ $final[26] = x_{26} + x_{27}$ $———-$ $subtraction$ $final[27] - final[26] = x_{28} - x_{26}$

$final[27] - final[26] = x_{28} - x_{26}$ $final[25] = x_{25} + x_{26}$ $———-$ $addition$ $final[27] - final[26] + final[25] = x_{28} + x_{25}$

$…$

By subtracting and adding repeatedly, we should obtain $x_{28} - x_0 = (result)$, therefore $x_{28}$ with regards to $x_0$: $x_{28} = (result) + x_0$, replace $x_{28}$ in our first equation, $t = x_0 \cdot ((result) + x_0)$ and obtain a quadratic equation: $x_0^2 + x_0(result) - t = 0$.

Here on out, the job is simple, as $x_0$ will probably take a positive value (take a peak above and notice it’s just xor’ed ASCII from the message). From $x_0$ and $final[0] = x_0 + x_1$ we find $x_1$ and repeat for all $x_i$.

Lastly, the beginning

For the last step, there is a message formatting:

if len(message) < 29:
    message = ((message + " ") * 29)[:29]

which transforms the message to be at least of length 29, and then the XOR overlay.

digest = [0]*32

for i in range(len(message)):
    digest[i % 29] ^= ord(message[i])

The digest (initialized with 0) gets xor’ed with the first 29 characters from the message. Since a ^ 0 = a, this is equivalent to initializing digest with message[ :29] in ASCII. Afterwards, the digest index moves back to 0 and it continues to xor it with the rest of the message.

digest	0	1	2	3	4	5	6	7	8	9	…	26	27	28
	m	e	s	s	a	g	e	_	m	e	…	e	s	s
	a	g	e

It would be impossible to deduce two random characters which xor’ed are equal to digest[i] and also make sense in the message. However, since the message should be the flag, we can safely presume it starts with “MetaCTF{”. And because a ^ b = c <=> a = c ^ b, we can check this presumption by xoring digest[ :8] with “MetaCTF{“.

The result was “ashabyss”, so totally not a coincidence :).

Remember length?

Length was smaller than $2 \cdot 29$, which means there are some letters at the end of digest which were not xored, and $len - 29$ tells us exactly where the raw piece starts.

Here we got “lags_deep_int0_the_h”, which matches “ashabyss” perfectly. As a cherry on top, “f” from “flags” and “}” xor’ed give digest[8], confirming the flag:

MetaCTF{flags_deep_int0_the_hashabyss}

Crypto