"Maillon Faible" Write-up: DG'Hack 2022

This challenge was a nice teamwork moment at eShard. Here after our path to the Flag:

Challenge

https://www.dghack.fr/challenges/dghack/maillon-faible/

Vous avez à votre disposition tous les fichiers que nous utilisons pour sécuriser le code de tir nucléaire.
Merci d'effectuer toutes les vérifications nécessaires pour nous confirmer que ce code est bien en sécurité.

Here after you will find all files used to secure the nuclear code. Please make all necessary checks to confirm that this code is properly secured.

Four files are provided for this challenge:

• pki_extract.zip
• nuclear_launch_codes.zip
• encrypted_aes_key.bin
• nsa_communications.zip

Explore the files

After quick investigations on these files, we render with the following elements/

• pki_extract: is not a valid archive. But its content can be read as text.
• nuclear_launch_codes: seems to be a valid archive, but protected with a password.
• encrypted_aes_key: is most probably an encrypted AES key :-) .
• nsa_communications: is not a valid archive and its entropy suggest an encrypted file, we believe encrypted with the AES key...

Our starting point is clear: the only file that can be read in plain.

Play with public keys

from zipfile import ZipFile

zkeys = ZipFile('pki_extract.zip')
print(len(zkeys.filelist))
zkeys.infolist()[:5]

420





[<ZipInfo filename='./tmp/pubkey_1.pem' filemode='?rw-------' file_size=426>,
 <ZipInfo filename='./tmp/pubkey_2.pem' filemode='?rw-------' file_size=426>,
 <ZipInfo filename='./tmp/pubkey_3.pem' filemode='?rw-------' file_size=426>,
 <ZipInfo filename='./tmp/pubkey_4.pem' filemode='?rw-------' file_size=426>,
 <ZipInfo filename='./tmp/pubkey_5.pem' filemode='?rw-------' file_size=426>]

The pki_extract.zip file contains 420 public keys. First we can read and build the public keys:

from Crypto.PublicKey import RSA

pub_keys = [RSA.import_key(zkeys.read(key)) for key in zkeys.infolist()]
pub_keys[0]

RsaKey(n=23068829194480416163692165710239459815977973253263828630116450647425868586128627019467561273754574127288604984088074046342068153753692318330468046336394233318659196642579163323297343379074579673652811110844491088777882322384363042631547173239395214103388763977792987678401456578879975236363086518403796761923274329884377842884991411771759909806396090207985278011445566799893359150731321936203340451964440199258063475807006652611968380613075475509620533995261968388991966863689168272851103974732967985729557460560531198444356619368206467217976551554548138662397403729738719802303675870057358573878812052179701914497147, e=65537)

Lets see if at least two of them have a modulus with a common factor (use egcd package):

from egcd import egcd

for i in range(len(pub_keys)):
    for j in range(i + 1, len(pub_keys)):
        gcd = egcd(pub_keys[i].n, pub_keys[j].n)[0]
        if gcd != 1:
            print('Cool ! ', i, j)
            break
    if gcd != 1:
        break

Cool !  120 388

We are armed to recover the private keys... we started with the first one:

n = pub_keys[i].n
p = egcd(pub_keys[i].n, pub_keys[j].n)[0]
q = n // p

assert p * q == n

e = pub_keys[i].e
phi_n = (p - 1) * (q - 1)
d = pow(e, -1, phi_n)

assert e * d % phi_n == 1

rsa_key = RSA.construct((n, e, d, p, q))

assert rsa_key.has_private()

Decrypt the AES key

With this first RSA Private key we can now decrypt the binary file to recover the AES key:

with open('encrypted_aes_key.bin', 'rb') as fid:
    encrypted_aes_key = fid.read()

from Crypto.Cipher import PKCS1_OAEP

decryptor = PKCS1_OAEP.new(rsa_key)
aes_key = decryptor.decrypt(encrypted_aes_key)    

An AES key is pure random, there is no way the verify if the AES key is valid or not. We keep in mind that we have another RSA Private key to try, but let us continue with the nsa_communications.zip and test what is decrypted.

Decrypt the NSA archive

with open('nsa_communications.zip', 'rb') as fid:
    encrypted_nsa_data = fid.read()

from Crypto.Cipher import AES

nsa_data = AES.new(key=aes_key, mode=AES.MODE_CBC).decrypt(encrypted_nsa_data)

with open('decrypted_nsa.zip', 'wb') as fid:
    fid.write(nsa_data)

znsa = ZipFile('decrypted_nsa.zip')
print(len(znsa.filelist))
znsa.infolist()[:5]

270





[<ZipInfo filename='TEST_1.txt' filemode='?rw-------' file_size=854>,
 <ZipInfo filename='TEST_1.txt.sig' filemode='?rw-------' file_size=63>,
 <ZipInfo filename='AIPAC?_2.txt' filemode='?rw-------' file_size=499>,
 <ZipInfo filename='AIPAC?_2.txt.sig' filemode='?rw-------' file_size=64>,
 <ZipInfo filename='H:_MEMO_ON_URGENT_KYRGYZSTAN_CRISIS,_FIRST_HAND_REPORT_AND_RECOMMENDATIONS._SID_3.txt' filemode='?rw-------' file_size=18631>]

Nice, it seems that the nsa_communications.zip archive is well decrypted. The archive is corrupted, the first file cannot be extracted. We can fix that, but there is no interest for the rest of the challenge.

This archive contains 135 text files and the corresponding signatures. Searching the nuclear archive password in the archive was a waste of time, but we have signature material.

Let's have a look on the signatures:

files = [znsa.read(file) for file in znsa.filelist[2:] if 'sig' not in file.filename]
signatures = [znsa.read(file) for file in znsa.filelist[2:] if 'sig' in file.filename]

signatures[:4]

[b'0>\x02\x1d\x00\xfa\x0c\xb0\t\xd5\x0cx\xab\x02q\xca\xe4F\xd1\x08N\xf4\x87\xe56q=\xf2\xbcJ\x10\x11\xba\x02\x1d\x00\x80\x0e\x08h\r\xd1Ww\xf2\x9f\x97Bg\xd9\xa6\x91\xcd3\xd4\xb5\rE\xdfT\x81\xdc\x8a\x08',
 b'0=\x02\x1d\x00\xfa\x0c\xb0\t\xd5\x0cx\xab\x02q\xca\xe4F\xd1\x08N\xf4\x87\xe56q=\xf2\xbcJ\x10\x11\xba\x02\x1c\x13\xf5\n\xab\xe3v\xd3\x01A\xf6\xaa]\xa4c\xa1S\xfa\xea \xac\xd9`\x97$\x03\\>\xf6',
 b'0=\x02\x1d\x00\xfa\x0c\xb0\t\xd5\x0cx\xab\x02q\xca\xe4F\xd1\x08N\xf4\x87\xe56q=\xf2\xbcJ\x10\x11\xba\x02\x1c\x16\x85K\x9d\xad\x1b\t-\xbc\x83x\xb8a\xcb\xd2QL\x1d((\x1e\x04\x15\x0f\xae\xa6\r\xcb',
 b'0=\x02\x1d\x00\xfa\x0c\xb0\t\xd5\x0cx\xab\x02q\xca\xe4F\xd1\x08N\xf4\x87\xe56q=\xf2\xbcJ\x10\x11\xba\x02\x1cL\xbe\xbd\x87!\r\xf9\xd8ENl\x03o4>\xf9UW\xc0\xa6=,~\xb1B\xb7\xfc!']

We can see that the signatures:

• are about 512-bit long,
• have all quite the same first half.

The varying bytes of the first half are bytes 1 and 34. And we can see that these bytes correspond to:

• the length of the whole signature,
• the length of the second half.

The signature size, and the fact that the first part is very similar was a good indication that we are in presence of EC-DSA signatures with extra stuff (we realized afterwards that it was DER encoded EC-DSA signatures).

A quick look at the lengths of identified parts:

for sig in signatures[:6]:
    print(len(sig) - 2, sig[1], len(sig) - 35, sig[34])

62 62 29 29
61 61 28 28
61 61 28 28
61 61 28 28
61 61 28 28
62 62 29 29

We are almost sure that we have ecdsa signatures, so couples (r, s). But, a key observation is the common first part, which indicates that each signature was generated with the same nonce. A very well none weakness of EC-DSA!

To perform the so called nonce reuse attack, we need the common r value, two signatures with the same nonce and the two corresponding plaintexts. The following code is an extract from this repo.

from ecdsa import SigningKey, VerifyingKey, der

def rs_from_der(der_encoded_signature):
    rs, _ = der.remove_sequence((der_encoded_signature))
    r, tail = der.remove_integer(rs)
    s, _ = der.remove_integer(tail)

    return r, s

r1, s1 = rs_from_der(signatures[0])
r2, s2 = rs_from_der(signatures[42])

plain1, plain2 = files[0], files[42]

assert r1 == r2

We can now try to recover the private key used for the ECDSA signature, with the following script. Again, the code is copied from this repo.

def recover_from_hash(curve, r, s1, h1, s2, h2, hashfunc):
    order = curve.order

    r_inv = inverse_mod(r, order)
    h = (h1 - h2) % order

    for k_try in (s1 - s2,
                  s1 + s2,
                  -s1 - s2,
                  -s1 + s2):

        k = (h * inverse_mod(k_try, order)) % order
        secexp = (((((s1 * k) % order) - h1) % order) * r_inv) % order
        signing_key = SigningKey.from_secret_exponent(secexp, curve=curve, hashfunc=hashfunc)
        if signing_key.get_verifying_key().pubkey.verifies(h1, Signature(r, s1)):
            return signing_key

    return None

But we are missing two important elements:

• the curve used for the signature
• the hash function.

We can brute-force these two parameters. From the lengths analysis we guessed that the signatures are couple of 224-bit values, we can suppose that the curve is either NIST224p or BRAINPOOLP224r1. And for the hash function, we can test all the hashlib available function !

from ecdsa import NIST224p, BRAINPOOLP224r1
from ecdsa.numbertheory import inverse_mod
from ecdsa.ecdsa import Signature
import hashlib

for hashname in hashlib.algorithms_guaranteed:
    if 'shake' in hashname:
        continue
    hashfunc = getattr(hashlib, hashname)
    for curve in [NIST224p, BRAINPOOLP224r1]:
        h1 = int(hashfunc(plain1).hexdigest(), 16)
        h2 = int(hashfunc(plain2).hexdigest(), 16)
        
        res = recover_from_hash(curve, r1, s1, h1, s2, h2, hashfunc)
        if res is not None:
            print('!!!!!!!!!    Youpi    !!!!!!!!!')
            break
    if res is not None:
        break

!!!!!!!!!    Youpi    !!!!!!!!!

Unlock the Nuclear codes

We can try the recovered private key as password to unlock the nuclear_launch_codes.zip:

import gmpy2 as gp

password = str(res.privkey.secret_multiplier)

with ZipFile('nuclear_launch_codes.zip') as znuclear:
    flag = znuclear.read('nuclear_launch_codes.txt', pwd=password.encode())
    
flag

b'DGHACK{I7_700K_4_WH1L3_8U7_Y0U_N0W_H4V3_7H3_FL4G}'

Well done !!

Thank's

Many thanks to the DGA team for this nice CTF. Looking forward for the one next year!