Insomnihack Teaser 2016 – Bring the noise (Crypto) – Write-Up

Bring the noise : Quantum computers won’t help you

Category: Crypto Points: 200 Solves: 173

Dans ce challenge on nous fourni ce fichier python : server-bd6a6586808ab28325de37276aa99357.py

Tout d’abord, la première partie de ce chall « Bring the noise » :

POWLEN = 5

[...]

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

Nous devons soumettre une chaine de caractère dont les 5 premiers chars de son md5 correspondent à ceux fournis.
On peut résoudre cela avec un simple bruteforce :

POWLEN = 5
alpha = "abcdefghijklmnopqrstuvwxyz0123456789"
for a in alpha:
    for b in alpha:
        for c in alpha:
            for d in alpha:
                for e in alpha:
                    for f in alpha:
                        chaine = a+b+c+d+e+f
                        responsehash = hashlib.md5(chaine).hexdigest().strip()
                        if responsehash[:POWLEN] == "4807f":
                            print chaine

Puis vient la seconde partie du challenge :

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

[...]

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

[...]

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)

Ici la solution à soumettre est générée aléatoirement.
On nous fournit le résultat calculé à partir de la solution et les 6 coefs de 40 équations.
Avec la solution, une inconnu subsiste, la vibration aléatoire (-1, 0 ou 1) faisant partie de l’équation.

La solution a trouver est composée de 6 chiffre de 0 à 7 compris.
Donc 262144 solutions possible, ce qui est trouvable facilement par brute force.

lit = []
#chargement des résultats et des 6 coefs des 40 équations.
with open('list') as f:
    for line in f:
    	lit.append(line)

q, n, eqs = 8, 6, 40
equations = []

for a in range(8):
	for b in range(8):
		for c in range(8):
			for d in range(8):
				for e in range(8):
					for f in range(8):
						solution = [a, b, c, d, e, f]
						found = 1
						#test de tous les coefs pour cette solution tant qu'ils conviennent.
						for line in lit:
							if found == 1:
								coefs = line[:-1].split(', ')
								result = sum([solution[i]*int(coefs[i]) for i in range(n)]) % q
								#check du résultat dans les 3 cas de la vibration : -1, 0 ou 1.
								if ((result + q - 1) % q == int(coefs[6])) or ((result + q) % q == int(coefs[6])) or ((result + q + 1) % q == int(coefs[6])):
									found = 1
								else:
									found = 0
							else:
								break

						if found == 1:
							print str(solution)[1:-1]

Flag : INS{Errors0ccurMistakesAreMade}

Leopoldine.

Leave a Comment

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *