**Tags:** crypto

Rating:

# A primed hash candidate

## Statement

>After the rather embarrassing first attempt at securing our login, our student intern has drastically improved our security by adding more parameters. Good luck getting in now!

We are then given access to a remote server running the following python code :

```python

ERROR = "Wrong password with hash "

SUCCESS = "Login successful!\nFlag: REDACTED\n"

PASSWD = 91918419847262345220747548257014204909656105967816548490107654667943676632784144361466466654437911844

secret1 = "REDACTED"

secret2 = "REDACTED"

secret3 = int("xxx")

def hash(data):

out = 0

data = [ord(x) ^ ord(y) for x,y in zip(data,secret1*len(data))]

data.extend([ord(c) for c in secret2])

for c in data:

out *= secret3

out += c

return out

data = input("Please enter password below\n")

try:

while True:

if hash(data) == PASSWD:

print(SUCCESS)

break

else:

print(ERROR + str(hash(data)))

data = input("Please enter password below\n")

except EOFError:

pass

```

## Analysis

We see that the server asks us for a password. It then hashes it using a custom function and compares it to the `PASSWD` value. We then need to find an input producing the given hash. As the server is kind enough to give us the hash of inputs we feed him, this will be useful for our attack.

The hashing function works in three steps:

1. Our input is xored with the word `secret1`.

2. `secret2` is appended to the previous xored string.

3. The final string is then mapped to an integer using a pseudo base-conversion.

### Finding secret3

The first thing to remark is that an null string is a valid input:

```

Please enter password below

Wrong password with hash 102600138716356059007219996705144046117627968461

```

The given hash is then `f(secret2)` where `f` is the pseudo-conversion function.

For any given input `m` its hash is then `hash(m) = f(m xor secret1) * secret3^len(secret2) + f(secret2)`. We then know that `secret3` divides `gcd(hash(1)-f(secret2), hash(0)-f(secret2))`. We compute the gcd using sage for example :

```python

sage: hash0 = 19005887928914280732260134378748151614599045204546

sage: hash1 = 18783496307853128677280688327194704466734557942945

sage: fsecret2 = 102600138716356059007219996705144046117627968461

sage: gcd01 = gcd(hash0-fsecret2, hash1-fsecret2)

sage: factor(gcd01)

233^20

```

We then deduce that `secret3 = 233`.

### Finding secret2

This step is actually not necessary since we already know `fsecret2`, but we can stll invert the base-conversion function that encrypted `secret2` by converting the integer in base 10 to an integer base 233, and displaying each 'digit' as an ascii character.

```python

chars = []

fsecret2 = 102600138716356059007219996705144046117627968461

while fsecret2 > 0:

modulo = fsecret2%233

chars.append(chr(modulo))

fsecret2 = fsecret2//233

print(b"".join(chars[::-1]))

```

Running the code gives us `secret2 = 'ks(3n*cl3p%3925(*4*2'`

### Finding secret1

To find `secret1`, we can process similarly as we did in the last step. First, we need to hash a very long input, to make sure that all characters of `secret1` are indeed xored at one point.

We can then take the hash of `20*'0' = '00000000000000000000'`, which should be long enough. We find that

`hash(20*'0') = 18126456734850052517766482160657835416461226894114798664396414018388402487161697110017734000706`

Then, we can substract the known part from `secret2` and `secret3` to stay with the interesting stuff.

We end with the following code :

```python

chars = []

bighash = 18126456734850052517766482160657835416461226894114798664396414018388402487161697110017734000706

interestingpart = (bighash - fsecret2) // (233**20)

while interestingpart > 0:

modulo = interestingpart%233

chars.append(chr(modulo ^ ord('0')))

interestingpart = interestingpart//233

print("".join(chars[::-1]))

```

Running the code gives us `el3PH4nT$el3PH4nT$el`, we then deduce that `secret1 = 'el3PH4nT$'`

### Decoding the password

Now that we know all the secrets, we are able to compute back the password from the hash `PASSWD`. The only difficulty is that we don't know the length of the original password, and so we can't use the same trick as before without modifying it, as we don't know which character of `secret1` to xor from.

Nevertheless, we are only interested in the length of the password modulus the length of `secret1`, so we can bruteforce this part.

```python

for l in range(len(secret1)):

interestingpart = (PASSWD-fsecret2)//233**20

index = l

chars = []

while interestingpart>0:

modulo = interestingpart%233

chars.append(chr(modulo ^ ord(secret1[index%9])))

index=(index+8)%9

interestingpart = interestingpart//233

if(hash("".join(chars[::-1])) == PASSWD):

print("".join(chars[::-1]))

```

This gives us a collision for the given hash: `GZZ9t3W3Ar34un44m8PLXX6`.

We can get the flag now:

```console

Please enter password below

GZZ9t3W3Ar34un44m8PLXX6

Login successful!

Flag: sdctf{W0W_s3cur1ty_d1d_dRaStIcAlLy_1mpr0v3}

```

Original writeup (https://github.com/MockingHawk/ctf-write-ups/blob/main/sdctf-2021/a-primed-hash-candidate.md).