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}
```