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 (`gab 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.