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.