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 1000

Flag 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<sup>ab</sup> mod q`

). The challenge asks us only to find little `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.