Trash Chain
Reverse engineering a hash function

Problem

It seems that my problems with hashing just keep multiplying...
nc umbccd.io 3100
Author: RJ

Solution

The challenge is as follows:
Welcome to TrashChain! In this challenge, you will enter two sequences of integers which are used to compute two hashes. If the two hashes match, you get the flag! Restrictions:
  • Integers must be greater than 1.
  • Chain 2 must be at least 3 integers longer than chain 1
  • All integers in chain 1 must be less than the smallest element in chain 2
    Type "done" when you are finished inputting numbers for each chain.
Hash function:
1
def H(val, prev_hash, hash_num):
2
return (prev_hash * pow(val + hash_num, B, A) % A)
Copied!
Computing hashes:
1
hashes = []
2
for chain_num in range(len(chains)):
3
cur_hash = 1
4
for i, val in enumerate(chains[chain_num]):
5
cur_hash = H(val, cur_hash, i+1)
6
hashes.append(cur_hash)
Copied!
Leverage the fact that
ABmod  A=0A^B\mod{A}=0
. If we simply pass in A as the input, the hash will be 0, and we can make the two hashes collide by forcing them both to be 0.
Since chain 2 must be 3 numbers longer than chain 1, we can simply use
AnBmod  A=0A^{nB}\mod{A}=0
, where n is any positive integer.
Testing our theory:
Of course, this works on the actual server as well.
Copy link