Neo Diffie Hellman

June 25, 2025

السلام عليكم ورحمة الله وبركاته

Today challenge add a trick to Diffie-Hellman key exchange what happens if we use matrices ?

here is the challenge code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

from hashlib import sha256
from Crypto.Cipher import AES
from Crypto.Random import get_random_bytes, random
from Crypto.Util.Padding import pad


p = 1000117

Fq = GF(p)

G = matrix(Fq, [[8544, 7125, 942, 1054, 2338, 8223, 1149, 3981],
                [7803, 9243, 6830, 8788, 9576, 1916, 7762, 5861],
                [9026, 9381, 9235, 994, 6194, 508, 7351, 1406],
                [6410, 6445, 6086, 653, 1783, 4564, 8874, 4739],
                [2797, 8921, 113, 1078, 6810, 7392, 3659, 1316],
                [1688, 1010, 631, 6495, 7379, 5804, 7237, 527],
                [2211, 4452, 1519, 498, 9284, 3282, 9628, 4355],
                [1267, 9413, 3340, 2316, 8627, 1310, 4481, 4808]])

secret_a = random.randint(int(1000000), int(100000000))
secret_b = random.randint(int(1000000), int(100000000))

pub_a = G^secret_a
pub_b = G^secret_b

print("pubkey A:")
print(pub_a)
print("pubkey B:")
print(pub_b)

key_a = pub_b^secret_a
key_b = pub_a^secret_b

assert key_a == key_b

flattened = key_a.list()
matrix_bytes = ",".join(map(str, flattened)).encode('utf-8')

key = sha256(matrix_bytes).digest()

flag = open('flag', 'r').read().encode()

iv = get_random_bytes(16)
padded_plaintext = pad(flag, AES.block_size)

cipher = AES.new(key, AES.MODE_CBC, iv)
ciphertext = cipher.encrypt(padded_plaintext)

print(f"iv: {iv.hex()}")
print(f"flag: {ciphertext.hex()}")

The first thing I have noticed is that the range of exponents could be brute forced

1
2

secret_a = random.randint(int(1000000), int(100000000))
secret_b = random.randint(int(1000000), int(100000000))

so I have implemented a script to brute force the secret by guessing it here is the code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88

from hashlib import sha256
from Crypto.Cipher import AES
from Crypto.Util.Padding import unpad
from multiprocessing import Pool, cpu_count
import sys


p = 1000117
Fq = GF(p)

G = matrix(Fq, [[8544, 7125, 942, 1054, 2338, 8223, 1149, 3981],
                [7803, 9243, 6830, 8788, 9576, 1916, 7762, 5861],
                [9026, 9381, 9235, 994, 6194, 508, 7351, 1406],
                [6410, 6445, 6086, 653, 1783, 4564, 8874, 4739],
                [2797, 8921, 113, 1078, 6810, 7392, 3659, 1316],
                [1688, 1010, 631, 6495, 7379, 5804, 7237, 527],
                [2211, 4452, 1519, 498, 9284, 3282, 9628, 4355],
                [1267, 9413, 3340, 2316, 8627, 1310, 4481, 4808]])

pub_a = matrix(Fq, [[535437, 436702, 226549, 36181, 121389, 153630, 731259, 540567],
                   [907971, 938518, 894603, 755768, 216225, 593672, 741423, 23476],
                   [722305, 647423, 326338, 242088, 488457, 728979, 922735, 747889],
                   [297685, 306919, 290639, 27509, 2322, 325140, 477421, 280920],
                   [29774, 527786, 611495, 899899, 521717, 533020, 146923, 228648],
                   [220169, 473019, 557359, 889119, 915468, 309429, 426937, 289970],
                   [353297, 925012, 273876, 541080, 490035, 332930, 328121, 278415],
                   [486511, 551604, 110330, 675237, 32977, 360728, 468534, 470750]])

pub_b = matrix(Fq, [[278458, 53534, 847067, 639466, 299135, 226889, 76846, 630318],
                    [389389, 394186, 698985, 793202, 290495, 837646, 870685, 718848],
                    [758075, 979002, 904988, 856135, 697027, 565219, 562831, 586066],
                    [610508, 496282, 719959, 310184, 841117, 700200, 225924, 938975],
                    [553891, 268611, 42248, 348624, 769549, 609875, 442900, 984258],
                    [397633, 478352, 880372, 982228, 238901, 18500, 192661, 872537],
                    [927550, 649966, 414777, 456967, 907846, 112230, 445766, 510641],
                    [554075, 858774, 422448, 789101, 664939, 373076, 823091, 439356]])


iv = bytes.fromhex("dd389f38c4980b66ac5fd4c9cd5a7484")
ciphertext = bytes.fromhex("a514a4defc7a3c6a1024641231b6fb8b255f234ff6100aff911ff4b5b6a7990f5210c1768977d0dd900e323ab320ed67")


def check_secret(start_end):
    start, end = start_end
    for secret_guess in range(start, end + 1):
        if (G^secret_guess) == pub_a:
            return secret_guess
    return None

def brute_force_parallel():
    num_cores = cpu_count()
    print(f"Using {num_cores} CPU cores for parallel search")
    
    
    total_range = 100_000_000 - 1_000_000
    chunk_size = total_range // num_cores
    ranges = [(1_000_000 + i*chunk_size, 
              1_000_000 + (i+1)*chunk_size - 1) for i in range(num_cores)]
    
    
    ranges[-1] = (ranges[-1][0], 100_000_000)
    
    with Pool(num_cores) as pool:
        results = pool.imap_unordered(check_secret, ranges)
        for result in results:
            if result is not None:
                pool.terminate()  
                return result
    return None

if __name__ == '__main__':
    print("Starting parallel brute-force attack...")
    secret_a = brute_force_parallel()
    
    if secret_a:
        print(f"\nFound secret_a: {secret_a}")
        
        
        shared_key_matrix = pub_b^secret_a
        flattened = shared_key_matrix.list()
        key_bytes = ",".join(map(str, flattened)).encode()
        aes_key = sha256(key_bytes).digest()
        
        cipher = AES.new(aes_key, AES.MODE_CBC, iv)
        decrypted = unpad(cipher.decrypt(ciphertext), AES.block_size)
        print(f"\nDecrypted flag: {decrypted.decode()}")
    else:
        print("Failed to find secret_a")

Hope that this was useful thanks for reading.

Tags:

Categories: