HackIM - Breaking Bad Key Exchange - Crypto Challenge

Reading time ~1 minute

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.

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:
    if g**x % q == 330:
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
    exp = i[0]*i[1]
    if g**exp % q == 399: 
        flg = "flag{"+str(i[0])+","+str(i[1])+"}"
        if flg not in p_flags:
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:

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.

niteCTF - CBC-Jail

A unique combination of Python jailbreak and crypto flaw that had me learning a lot about AES-CBC mode. Super fun for me to get this solu...… Continue reading

niteCTF - Rabin to the Rescue

Published on December 12, 2021

HTB CyberSanta 2021 - Crypto Writeups

Published on December 04, 2021