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 "
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

try:
while True:
if hash(data) == PASSWD:
print(SUCCESS)
break
else:
print(ERROR + str(hash(data)))
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:



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\$'

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