# HackIM – Breaking Bad Key Exchange – Crypto Challenge

HackIM time again. This year seemed slightly better organized than last year. Some nice challenges. I don’t think this challenge was worth 350 points but I’ll document my solution anyway in sort of a “what not to do” when making a crypto challenge. Here’s the clue including the image they gave as a description:

Breaking Bad Key Exchange

Hint 1 : in the range (1 to g*q), there are couple of pairs yielding common secrete as 399.

Hint 2 : ‘a’ and ‘b’ both are less than 1000Flag Format: flag{a,b}

Ok so we already know everything from the get go, we have the generator (`g`

) the modulus (`q`

) the results of the Diffie-Hellman-Merkle key exchange math for Alice and Bob (generally called `A`

and `B`

) and we even know the resulting secret number (`g`

). The challenge asks us only to find little ^{ab} mod q`a`

and little `b`

.

We’re given a set of constraints. Our search field is `g*q`

and our `a`

, `b`

are less than 1,000.

Why don’t they just tell us the answer?

A simple search finds the probably a,b pairs, we can do this very rapidly in Python. Coding in the constraints makes the operation very fast.

#!/usr/bin/python import itertools # generator and modulus from challenge g = 10 q = 541 a_s = [] b_s = [] for x in range(g*q): if g**x % q == 298: a_s.append(x) if g**x % q == 330: b_s.append(x) p_flags = [] # possible flags for i in itertools.product(a_s,b_s): if i[0] > 1000 or i[1] > 1000: # a and b cannot be over 1000 according to hint continue exp = i[0]*i[1] if g**exp % q == 399: flg = "flag{"+str(i[0])+","+str(i[1])+"}" if flg not in p_flags: p_flags.append(flg) print "[*] Possible flags:" print '\n'.join(p_flags)

When we run it we get a list of possible values for a, b in the flag format:

root@kali:~/hackim/crypto/dh# python bf.py [*] Possible flags: flag{170,268} flag{170,808} flag{710,268} flag{710,808}

The flag ends up being `flag{170,808}`

I think the challenge author here struggled because of the number of valid results which find `399`

as the mutually agreed secret key in this DH exchange. It felt like this challenge was forced in because a Diffie-Hellman challenge sounded like a neat idea. I think teaching DH in this way is ok but maybe for 50 points.