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:
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}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 :)).
Last updated