Hackerman Hash

You know when they say the preimages of a hashfunction should be hard to compute and than they choose some weak primitive recursive function. I present to you a revolutionary solution that builds upon (quite literally) one of the largest problems of computer science. Try bruteforcing this.

Category: Crypto

Solver: SchizophrenicFish2nds, Greenscreen23

Flag: GPNCTF{I_H0pe_y0u_d1d_N0T_BrUT3F0RC3_Th15?_D1d_Y0U!!_3s2l1j}

Writeup

Context

In this challenge, we are given the source code to generate “hashes” of the secret flag, and the outputs of several execution of this code. The flag is split into 4 byte chunks, then processed using the chain() and keyedAck() functions.

The output files contain the two pickled lists of salt values (input to keyedAck, along with the flag chunks) and ch values (outputs of keyedAck). Printing the huge results of the function as strings takes way too long, thus the outputs are in the binary pickle format.

Hash function

The more interesting function is keyedAck(), as it produces the ch output. If we can find the preimage, i.e. the flag input to the function from its successive outputs, we can reconstruct the flag.

def keyedAck(key):
    def ack(m,n):
        if m == 0:
            return n+key
        if n == 0:
            return ack(m-1,1)
        return ack(m-1,ack(m,n-1))
    return ack

Staring at this recursive construction leads to the following insights:

Analyzing the function, we can define the following closed formula:

$ ack(0, n) := n + key $

$ ack(1, n) := 1 + (n + 1) \cdot key $

$ ack(2, n) := 1 + \sum_{i = 1}^{n+1} 2 \cdot key^i $

The output ch can be thought of as a polynomial with key as the variable, i.e. $ f(key) $
The degree of the polynomial is $ deg(f) = salt + 1 $
We can think of the last monomial of the form $ key^{salt+1} $ as the dominating summand, since we are taking a fairly large base (32 bit integer) to a known power of about 150000 to 676901

We can now approximate the entire polynomial for a given salt with $f(key) \approx key^{salt+1}$. Thus, to get a key we take the salt+1-th root of ch, and then round the result to the nearest integer. This approach takes some minutes, but we get the exact values for the flag chunks as intermediate results. Now, we only need to interpret the results as bytes and concatenate them.

Mitigations

Hashes are defined as maps to a fixed set, so this definition does not hold here. We were able to extract the exact key used from the ever increasing ch outputs. Additionally, this scheme could have benefited from modular arithmetic to be considered a hash and also to make finding roots harder.

Other resources

Scripts

[1] Script for determining the respective key from a “ch” output and a salt

import sys, pickle

FILE = 'out0.txt'
data = pickle.loads(open(FILE, 'rb').read())

res = []
for i in range(len(data[0])):
    a = data[0][i]//2
    b = a^(1/(data[1][i]+1)) # (take the salt+1)-th root
    res.append(int(b.n(digits=100))) # round off values after the decimal point

for i in res:
    print(long_to_bytes(i).decode(), end="")
# GPNCTF{I_H0pe_y0u_d1d_N0T_BrUT3F0RC3_Th15?_D1d_Y0U!!_3s2l1j}

Writeup#

Context#

Hash function#

Mitigations#

Other resources#

Scripts#