TE: Insomni'hack 2016 Teaser - Bring the noise (Crypto 200pts)


In this challenge, we are given the following script running on port 1111 of bringthenoise.insomnihack.ch:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#!/usr/bin/env python

import SocketServer as ss
import struct
import os
from binascii import hexlify
import hashlib

FLAG = open('flag').read()
POWLEN = 5


def randint(bound):
    return struct.unpack('<L', os.urandom(4))[0] % bound


def 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
result = sum([solution[i]*coefs[i] for i in range(n)]) + (-1,0,1) % 8

class Handler(ss.StreamRequestHandler):

    def handle(self):
        put = self.wfile.write
        challenge = hexlify(os.urandom(1+POWLEN/2))[:POWLEN]
        put('Challenge = %s\n' % challenge)
        response = self.rfile.readline()[:-1]
        responsehash = hashlib.md5(response).hexdigest().strip()
        if responsehash[:POWLEN] != challenge:
            put('Wrong\n')
            return

        equations, solution = learn_with_vibrations()
        for equation in  equations:
            put(equation + '\n')

        put('Enter solution as "1, 2, 3, 4, 5, 6"\n')

        sol = self.rfile.readline().strip()
        if sol != str(solution)[1:-1]:
            put('Wrong\n')
            return
        put('%s\n' % FLAG)


class ReusableTCPServer(ss.ForkingMixIn, ss.TCPServer):
    allow_reuse_address = True


if __name__ == '__main__':
    HOST, PORT = ('0.0.0.0', 1111)
    ss.TCPServer.allow_reuse_address = True
    server = ReusableTCPServer((HOST, PORT), Handler)
    server.serve_forever()


Here's a breakdown of what the code does:

Part 1: The Challenge (i.e. a Proof of Work)

 
1
2
3
4
5
6
7
challenge = hexlify(os.urandom(1+POWLEN/2))[:POWLEN]
put('Challenge = %s\n' % challenge)
response = self.rfile.readline()[:-1]
responsehash = hashlib.md5(response).hexdigest().strip()
if responsehash[:POWLEN] != challenge:
    put('Wrong\n')
    return
  1. Get 3 random bytes from the OS and turn it into a hex string. The challenge string is formed by dropping off the last character from this hex string (e.g. from 3 random bytes 0x0A, 0x1B and 0x2C, we form a challenge string "0A1B2").
  2. Send this "challenge string" to the user and wait for a response from the user.
  3. Hash the user's response using MD5.
  4. If the hash prefix of the user's response matches that of the challenge string, the user gets to proceed.


 Part 2: Learning with Vibrations

 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
def 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
result = sum([solution[i]*coefs[i] for i in range(n)]) + (-1,0,1) % 8
  1. The script issues the user 40 equations and expects the user to guess the solution to the 40 equations.
  2. The solution is a list of 6 random integers where each integer is in the range of 0 to 7.
  3. Each equation is made up of 6 randomly generated coefficients (using the same method as the one used to generate the solution) appended with a "result"
  4. The integer "result" is initialized to the sum of the product of each digit in the solution with its corresponding coefficient in the same position, modulo 8.
  5. A "vibration", which is an integer in the range -1 to 1 is generated.
  6. The final "result" is obtained by adding 8 and the value of "vibration" to the intermediate value of "result", modulo 8.
  7. If the user is able to correctly guess the solution to these 40 equations, the user gets the flag.

Solving the Challenge:

Since a MD5 hash has 32 bytes, there are 16^32 distinct hashes. There are 16^27 MD5 hashes that are prefixed by the challenge string. Therefore, if we make more than 16^5 = 1048576 guesses, we are likely to encounter at least 1 guess which is prefixed by the challenge string. Here's how I chose to do it:


1
2
3
4
5
def solve_challenge(challenge):
    s = string.letters + string.digits
    for guess in imap(lambda p: "".join(p), product(s, repeat=4)):
        if hashlib.md5(guess).hexdigest().strip()[:5] == challenge:
            return guess

Basically, I bruteforced all possible strings of length 4 that are made up of characters from the list 's', where 's' is a 62-character long list of all ASCII letters and digits. Since each string is 4-characters long, and there are 62 distinct characters, we get a total of 62^4 = 14776336 unique strings. Since 14776336 >> 1048576, we are very likely to encounter a guess that would be prefixed by the challenge string. I've tested this a number of times and so far it has never failed to find a collision.


Solving the Equations:


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
def possible(soln, eqn):
    iv = sum([soln[i]*eqn[i] for i in range(6)])
    for vib in (-1,0,1):
        if eqn[-1] == (iv + vib) % 8:
            return True
    return False

def solve_eqns(eqns):
    for attempt in product(range(8), repeat=6):
        soln = True
        for eqn in eqns:
            if not possible(attempt, eqn):
                soln = False
                break
        if soln:
            return str(attempt)[1:-1]

Likewise, since there are only 8^6 = 262144 possible solutions, I used a bruteforce method in solving the equations. For each guess, I checked if it is possible to produce all 40 sets of equations. If it is impossible to produce any of the 40 equations, then the guess is definitely wrong. If there is a possibility that the guess produced the 40 equations, then it is likely that this guess is the correct solution!


Putting Everything Together:


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#!/usr/bin/env python

from binascii import hexlify
from itertools import *
import hashlib
import string
import socket
import time

def solve_challenge(challenge):
    s = string.letters + string.digits
    for guess in imap(lambda p: "".join(p), product(s, repeat=4)):
        if hashlib.md5(guess).hexdigest().strip()[:5] == challenge:
            return guess

def possible(soln, eqn):
    iv = sum([soln[i]*eqn[i] for i in range(6)])
    for vib in (-1,0,1):
        if eqn[-1] == (iv + vib) % 8:
            return True
    return False

def solve_eqns(eqns):
    for attempt in product(range(8), repeat=6):
        soln = True
        for eqn in eqns:
            if not possible(attempt, eqn):
                soln = False
                break
        if soln:
            return str(attempt)[1:-1]

address = ("bringthenoise.insomnihack.ch",1111)
print "Attempting connection to:", address
s = socket.create_connection(address)
challenge = s.recv(40).strip()[-5::]
print "Received challenge:", challenge
ans = solve_challenge(challenge)
print "Sending answer:", ans
s.send(ans + "\n")
time.sleep(1)
eqns = s.recv(2048)
eqns = eqns.split("\n")[:40]
eqns = list(map(lambda eqn: list(map(int, eqn.split(", "))), eqns))
print "Received the following equations:"
for eqn in eqns:
    print str(eqn)[1:-1]
soln = solve_eqns(eqns)
print "Sending solution:", soln
s.send(soln + "\n")
flag = s.recv(100)
print "Flag obtained:", flag

Executing my script, I get:


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
$ ./crypto.py
Attempting connection to: ('bringthenoise.insomnihack.ch', 1111)
Received challenge: 2146e
Sending answer: aoeJ
Received the following equations:
4, 6, 4, 2, 1, 5, 3
5, 6, 4, 3, 6, 0, 1
5, 1, 4, 5, 4, 0, 4
6, 5, 5, 4, 2, 2, 2
7, 5, 6, 6, 7, 7, 2
0, 2, 5, 1, 0, 4, 5
0, 1, 5, 1, 7, 3, 4
7, 1, 3, 0, 5, 5, 6
2, 7, 2, 6, 4, 1, 3
7, 7, 3, 2, 4, 5, 3
0, 4, 3, 1, 3, 3, 1
1, 2, 6, 4, 0, 7, 3
1, 0, 4, 5, 5, 0, 2
1, 3, 6, 0, 4, 2, 2
0, 0, 2, 3, 2, 1, 6
1, 4, 3, 4, 3, 4, 7
5, 4, 3, 4, 2, 5, 3
6, 7, 5, 0, 4, 3, 5
0, 7, 0, 5, 7, 1, 0
3, 7, 7, 3, 1, 4, 3
5, 0, 2, 6, 7, 7, 5
0, 1, 6, 7, 3, 2, 0
3, 6, 4, 2, 4, 4, 6
3, 5, 0, 5, 3, 7, 0
7, 2, 4, 5, 2, 7, 0
5, 3, 0, 0, 5, 2, 3
5, 1, 6, 1, 0, 0, 6
2, 0, 1, 3, 1, 0, 3
3, 3, 2, 3, 2, 0, 6
5, 5, 4, 4, 5, 4, 6
3, 5, 0, 6, 0, 1, 6
4, 5, 0, 2, 7, 1, 2
2, 7, 3, 7, 2, 3, 0
0, 7, 7, 5, 7, 1, 4
6, 1, 7, 0, 3, 5, 1
5, 3, 6, 0, 7, 5, 0
3, 0, 7, 6, 3, 2, 0
6, 4, 0, 5, 2, 1, 2
1, 4, 6, 1, 6, 5, 6
2, 2, 0, 0, 3, 6, 2
Sending solution: 0, 7, 2, 2, 3, 7
Flag obtained: INS{ErrorsOccurMistakesAreMade}

Hurray!


Moral of the Story:

Do NOT use MD5 hashing for any secure implementation. Collisions for MD5 hashes can be easily found using a reasonably efficient code on a modern computer (within seconds, according to this Wikipedia article - MD5).

Also, it might not always be ideal to reveal the source code of a "secure" system (i.e. security by obscurity - a potentially contentious point) because malicious users may easily find vulnerabilities in the system through reverse engineering.

Comments

Post a Comment