Unbreakable

This is a writeup for Unbreakable, a challenge that was part of ASCWG 2025

Before we start, this challenge was one of the first attempts at creating a more 'realistic' cryptography challenge, which I respect, I will provide my feedback later.

Handouts

We're given a .pcap file containing a tls key exchange, and a params.txt containing DH parameters

-----BEGIN DH PARAMETERS-----
MIGHAoGBAQxn6qbQaxmBfw2xnnZangJ79Exx1gozR1dRf2NMytxLwq1+Qonj0E/D
wtyKvZubz5w7gVIjvvFc/fUEsr5wvGE/GYFVlhk1w3uoDDhQHdoWGRSKNgxMW/UZ
Yi0fIA5Lxf3jpYKqItSIJyYdaMtTimY5NF7mD7sav+GEAtqOoE8DAgEC
-----END DH PARAMETERS-----

Analysis & Solver

So, inspecting the packets in the pcap file we can extract the public diffie hellman parameters used in the key exchange, A, B, p, g, and the client random and server random, and lastly, the cipher suite used in encryption.

So the cipher suite is TLS_DHE_RSA_WITH_AES_128_CBC_SHA256 .

Okay so we can just copy value for all these parameters, I noticed the p in the .pcap is not equal to the p in the params.txt. And I also noticed that p in the pcap is composite, so out of curiosity I did tried to gcd between them and I found that:

$GCD(p_{pcap},p_{params.txt}) = p_{params.txt}$

And that q = p_pcap // p_params is also a large prime, so from now on I'll rename p_pcap to N for context.

Now, we try factorizing p-1 (the order of p) and we find that its a bunch of 45 bit primes, very smooth lol.

So I decide to do pohlig-hellman to retrieve alpha.

from sage.all import *
# from pcap  
n = 0x026da5e48506222782ad4f571311db0dc3ddd606ad525dfdf6ecad87ab54e01e8bd7e7729654db92e7de6ee642ed7857eb01b5c5cae303c42db95f9e5be0f08fd18a603c899f07081cad66ac0c2498d0ae66aa64b4998c821139b9fa57c5b479134aff75865e878ee0c184bd3d39f3d173131a605464b8805c32763228fdc265e61a45cb12b91ddeb5579e02ee14bc56928152f47509bec85ea007bf791894915b0567201921e4b48b9276ad644a675ce78882132c5939dad91f4fac65718ff13640f78f8ce660a9e858150eac23b0a0bf62fb15ae70b469f6bba0439ec901188f51a99bb4eade7608cfdca7acf8123cb52c442ecc46941cfcec97550ebdecbc31
A = 0x0e9e94f03d6dd901e44b4c04ce876e202a8d43373c7ffee374b6d833d806c03764919f2b1615b4f664cf2d6e70e0a4af23bd7c8088d3139b529a3919639a736478d71b91063143ce332fbbdba841b16e5bbe1c8300e953c0914e262b29f69d1d04462809605e8ad3f359dca22e0c7b7a73139e649af721ec2ae4ce76a0bef245dce9248435592faba79793eb439a6e2a0798c5ed7dea2945f3adeadcf9e980fc8a4597f35305d9d7328752dd94691d8289828af000884f6308385cd7b6b643e58b34268e2e4ac151feefed048c92f673dad5869cf26dc6ec1cfaa1949d3b8095962b4cfef71827249063f099acc8b2c43926af644f69663591619c4e31e519f9
B = 0x0221afb11938cb1fc0335894210daeacfd8ce929cff9a433b607a59c452bb2fff45c0a5ca857a42c6ad267e9e4d97200ef3ae61be453fe6e7761a6b93f41520f7b6566c731c1b661d07167990f431aeb0becc6dd7d7414ff8477c1d18f1c6b3c55faf6a20dc0976dc30b396d4499fdf27a2178c910a7f08452658c58689cbef548da5f12ed11474b5aa91ee033f6412ae424944afcfb0fb87f2727e8272da4ac5f8fbf30f9f3b7715d2877192133c4e342b55152d2da5ebbb99a3dad0f33a40f5f863c31772847d2a76e37a88a3096442e8fe6fed20e64cefe66cb23d2e28e22109bde899398a93ab4a7c1d33ee877084f96f8ce0b9b56eacee01e36915addd26a
# from params.txt
p = 188481049757722254887446294741765543978345244373357803285748557139380955689864149390822640119996411454499583101834756749814893915942331906825914752722686129146728313414926325181335481676891411570489611040565048816424707189697438089020659203823234671280879018477037306908989340237413694212744228716516386819843
g = 2

A_p = []
Ms = []
for p_test in ecm.factor(p-1)[1:]: # removing the first entry (2) 
    try:
        F = GF(p)
        k = (p - 1) // p_test
        gp = pow(g, k, p)
        Ap = pow(A, k, p)
        Ap = F(Ap)
        log_A = Ap.log(gp)
        A_p.append(log_A)
        Ms.append(p_test)

        print(f"q: {p_test}, A_q: {log_A}")
    except Exception as e:
        print(f"Error with q={p_test}: {e}")  
# you dont have to do all factors, just enough to recover alpha which is like 5-6 factors       
alpha = crt(A_p, Ms)

assert pow(g, alpha, n) == A
s = pow(B, alpha, n)
print(f's = {s}') # s = 60688211686490993502225397016951709378899105728454300621619790878716459365293819429817061593788805624842645819708800542592578704113204283061530414854707762945163802740718097156641401944546594691622913268230011444106678784616711602156362897566986213535065055451307793398003279782892828100336922229947584416675331163165739089947208503530135765115141601317672241950654800909952170324515842678984776597868753762398260037024185244250838607852700041572953484387182066249251052243759375179760754772216756408532649414178383647906265224980773038167857850629631159784148136939564262138414791017733630907516898870886172325347692

This is stage 1, stage 2 of out attack is to build the client and server write keys + IVs using HMAC-SHA256 (inspired by the suite in the traffic)

import hashlib
import hmac
from Crypto.Cipher import AES

def prf_sha256(secret, label, seed, length):
    def p_hash(secret, seed, length):
        result = b''
        a = seed
        while len(result) < length:
            a = hmac.new(secret, a, hashlib.sha256).digest()
            result += hmac.new(secret, a + seed, hashlib.sha256).digest()
        return result[:length]
    
    return p_hash(secret, label + seed, length)

def derive_keys(master_secret, client_random, server_random):
    
    seed = server_random + client_random
    key_block = prf_sha256(master_secret, b"key expansion", seed, 128)
    
    keys = {}
    offset = 0
    
    keys['client_write_MAC_key'] = key_block[offset:offset+32]
    offset += 32
    keys['server_write_MAC_key'] = key_block[offset:offset+32]
    offset += 32
    keys['client_write_key'] = key_block[offset:offset+16]
    offset += 16
    keys['server_write_key'] = key_block[offset:offset+16]
    offset += 16
    keys['client_write_IV'] = key_block[offset:offset+16]
    offset += 16
    keys['server_write_IV'] = key_block[offset:offset+16]
    
    return keys

def decrypt_aes_cbc_with_mac(ciphertext, key, iv, mac_key):

    cipher = AES.new(key, AES.MODE_CBC, iv)
    decrypted = cipher.decrypt(ciphertext)
    
    padding_length = decrypted[-1]
    plaintext_with_mac = decrypted[:-padding_length]
    
    mac_length = 32
    plaintext = plaintext_with_mac[:-mac_length]
    received_mac = plaintext_with_mac[-mac_length:]
    
    return plaintext, received_mac

def main():
    # from previous script
    s = 60688211686490993502225397016951709378899105728454300621619790878716459365293819429817061593788805624842645819708800542592578704113204283061530414854707762945163802740718097156641401944546594691622913268230011444106678784616711602156362897566986213535065055451307793398003279782892828100336922229947584416675331163165739089947208503530135765115141601317672241950654800909952170324515842678984776597868753762398260037024185244250838607852700041572953484387182066249251052243759375179760754772216756408532649414178383647906265224980773038167857850629631159784148136939564262138414791017733630907516898870886172325347692

    # from .pcap    
    client_random = 0x19a4d59aa8039682faf6bb1ea9ec9542977e23941b1ea966e5d0cff8f2e389d8
    server_random = 0x8518043440128863a52c1ead2fae81916b62ef2bc99f188fdb699a177727fabf
    
    client_random_bytes = client_random.to_bytes(32, 'big')
    server_random_bytes = server_random.to_bytes(32, 'big')
    
    pre_master_secret = s.to_bytes((s.bit_length() + 7) // 8, 'big')
    
    seed = client_random_bytes + server_random_bytes
    master_secret = prf_sha256(pre_master_secret, b"master secret", seed, 48)
    
    print(f"Master secret: {master_secret.hex()}")
    
    keys = derive_keys(master_secret, client_random_bytes, server_random_bytes)
    
    print(f"Client write key: {keys['client_write_key']}")
    print(f"Server write key: {keys['server_write_key']}")
    print(f"Client write IV: {keys['client_write_IV']}")
    print(f"Server write IV: {keys['server_write_IV']}")

if __name__ == "__main__":
    main()

output is:

Master secret: 8524c5204e35e69ba92afd5ac57315f8a4065cf7b2e36ee8a0ea915dc5a3a17992e18e1db5412a3faa9fa40775e4675f
Client write key: b'\x0b4\xfa|T\xef\xcf\xceOV=^I#Fr'
Server write key: b'z9\xd8e\xf3\x11\xd4q\xdf\xb0\xbf&\x84C\xec\x16'
Client write IV: b'\xcb\xcdg\xb4\xff$;\xa7~\x86\xcb\xfa(\x8d-\xbf'
Server write IV: b'Z]\xc8\t\xb9\x95\xb7C\x19VySE\x96\xc77'

Finally we take the application ciphertexts we got from the pcap file and decrypt using the keys

from Crypto.Cipher import AES


Client_write_key = b'\x0b4\xfa|T\xef\xcf\xceOV=^I#Fr'
Server_write_key= b'z9\xd8e\xf3\x11\xd4q\xdf\xb0\xbf&\x84C\xec\x16'
Server_write_key =  b'\xeb\x07\xf5R\x06\xc5\xbc]\xe1\xe8\x11\xcb>\x14\xdbb'
Client_write_IV= b'\xcb\xcdg\xb4\xff$;\xa7~\x86\xcb\xfa(\x8d-\xbf'
Server_write_IV= b'Z]\xc8\t\xb9\x95\xb7C\x19VySE\x96\xc77'


def decrypt_aes_cbc(ciphertext, key, iv):
    cipher = AES.new(key, AES.MODE_CBC, iv)
    decrypted = cipher.decrypt(ciphertext)
    return decrypted



ct1 = 0x53f1d16dce50f0347820e66be29c50247cda52aba5224c65de0bdacc68fb8dc0be02cf1ddad15caa3a195da55f0e0cffc14eef56f550a4247f852b47e792916bce9ef32c9bb3dfc911a7191e3b1f27e717a4eff0c07a9db40d76c880b7461b968f502e58d2387e972663d36559864284a7df20d091da3fac0787462dff63af718b72c9cc2fea73235b4921de5fee7a00
ct2 = 0xa65e934f770b2129fc32fe0caeae8d5559e04b108da69e4b1b645681a9b41078c7cc863672d94f22429b6f37df06ddbe67fdf413ff78fd0cdbfe12a14d39c5d6f85f93d2e86ddfdcf79659ef3ccd2110


plaintext = decrypt_aes_cbc(
    ciphertext=ct1.to_bytes((ct1.bit_length() + 7) // 8, 'big'),
    key=Client_write_key,
    iv=Client_write_IV
)

plaintext2 = decrypt_aes_cbc(
    ciphertext=ct2.to_bytes((ct2.bit_length() + 7) // 8, 'big'),
    key=Server_write_key,
    iv=Server_write_IV
)

print("Decrypted plaintext:", plaintext.decode('utf-8', errors='ignore'))
print("Decrypted plaintext2:", plaintext2.decode('utf-8', errors='ignore'))

which gives us :

Decrypted plaintext: .M>ͤv*cϖHello, old friend!
I can see that, how cool it is.
ASCWG{S0m3_0ld_c00l_DH_b4ckd00rs}

I know to use the Client write key because the packet right before the packet containing the encrypted data had the ports 52249 -> 4455 which is the client port talking to the server port

And that's it

Feedback

The only not so nice part about the challenge is that dh params contained a different public modulus to the one in the communication which caused some confusion, I think it's a little guessy.

But overall, nice chall, except for this minor detail, excited to see more 'realistic' challenges, but let's try to maintain a level of fun-to-solve experience while doing it, kudos to the writer :)).