Neo Diffie Hellman

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

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

here is the challenge code:

PYTHON

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

PYTHON

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

PYTHON

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.