# Insomnihack 2016 : Crypto (200)
**Category:** crypto |**Points:** 200 |**Name:** Bring the noise |**Solves:** ? |**Description:**
> Quantum computers won't help you>> Source> Running on: bringthenoise.insomnihack.ch:1111
___
## Write-up
Our solution code can be found [here](https://github.com/nomoonx/insomnihack/blob/master/Bring%20the%20noise/crack.py).
After reading the [server code](https://github.com/nomoonx/insomnihack/blob/master/Bring%20the%20noise/server-bd6a6586808ab28325de37276aa99357.py), it's a python socket server. We can see at the end of the function Handler, there's one line output the FLAG.```pythonput('%s\n' % FLAG)```So, we need to beat the function Handler. We can seperate it into two parts.
### Part One```pythonchallenge = hexlify(os.urandom(1+POWLEN/2))[:POWLEN]put('Challenge = %s\n' % challenge)response = self.rfile.readline()[:-1]print response#I added for debuggingresponsehash = hashlib.md5(response).hexdigest().strip()if responsehash[:POWLEN] != challenge:    put('Wrong\n')    return```The variable POWLEN is 5 here.
It generated a random 5-characters string called challenge and will tell the client what challenge is. After get a response from client, compute the md5 of that response and compare the first 5 characters with challenge. So our problem became 'To generated a string whose md5 value has the same prefix as a given string'. Since md5 is a 32-digit hexadecimal number and the probabilities of each value is almost even, we can calculate the least time we need to try is 16^5=1048576 to get the same prefix value.So, we come up an idea is to check the md5 value of integer to see if it fits.```pythonfor i in range(1048976):    responsehash = hashlib.md5(str(i)).hexdigest().strip()    if responsehash[:5] == challenge:        request=i        break```After test, the hit rate is almost 1/3 which is acceptable. Of course, if we increase the range, the hit rate can be increased. But we need to balance the hit rate and the running time. So, it's good for now.
### Part Two```pythonequations, solution = learn_with_vibrations()for equation in equations:  put(equation + '\n')
print 'solution'print solution
put('Enter solution as "1, 2, 3, 4, 5, 6"\n')
print 'receving'sol = self.rfile.readline().strip()print solif sol != str(solution)[1:-1]:  put('Wrong\n')  return```All the print lines are added by us to do debugging.
So there's a function to generate equations and solution called `learn_with_vibrations`. The equations will be sent to client and the client should return a solution called sol here to be compared with that solution. Therefore, the problem became 'how to generate a solution from the equations'.
Let's see the `learn_with_vibrations` function.```pythondef learn_with_vibrations():    q, n, eqs = 8, 6, 40    solution = [randint(q) for i in range(n)]    equations = []    for i in range(eqs):        coefs = [randint(q) for i in range(n)]        result = sum([solution[i]*coefs[i] for i in range(n)]) % q        vibration = randint(3) - 1        result = (result + q + vibration) % q        equations.append('%s, %d' % (str(coefs)[1:-1], result))    return equations, solution```The solution is a randomly generated 6 digit array.Each row in equations is a randomly generated 6 digit array and a result calculated by itself and solution.Since we can know every equation, the only thing we need to do is brutal force all 6 digit array and use a reverse rule to check if that's the solution.```pythondef solve(equations):    q, n, eqs = 8, 6, 40    a=[1,2,3,4,5,6]    for a[0] in range(q):        for a[1] in range(q):            for a[2] in range(q):                for a[3] in range(q):                    for a[4] in range(q):                        for a[5] in range(q):                            flag=True                            for equation in equations:                                eq=equation.split(',')                                result = sum([a[i]*int(eq[i]) for i in range(n)]) % q                                tempFlag=False                                for i in range(3):                                    if(result+q+i-1)%q==int(eq[-1]):                                        tempFlag=True                                        break                                if not tempFlag:                                    flag=False                                    break                            if flag:                                return a```We should write it in a better way. But just 6 digit, so we used a brutal way to write it.