Overview

TeslaCrypt was a ransomware strain from 2015. It targeted home users and demanded a ransom of about $500. I looked at the second version of this ransomware, which had a vulnerability in the implementation of its cryptography.

The sample I looked at contained strings relating to the program DVD-Cloner, indicating that this malware spread by impersonating legitimate binaries.

We can also see that the program contains a section with very high entropy, indicating that the ransomware payload is encrypted. The easiest way to dump the decrypted program is to set a breakpoint at VirtualProtect and look at the address that is marked as executable.

The first time the program is run, it moves itself to %APPDATA% and saves itself under a random name. After this, the program exits, but it creates a new process with another copy of itself. Attaching the debugger to this process, we find that this copy of the ransomware is actually responsible for performing the encryption.

Once the files are encrypted, the extension .zzz is appended, and ransom notes called help_restore_files_[random extension].txt and help_restore_files_[random extension].html are dropped in each directory. The ransom note claims that it is CryptoWall 3.0 and that RSA-2048 was used in the encryption, none of which is true.

The Encryption Scheme

The program uses the open-source cryptography libraries from OpenSSL to perform the encryption. Specifically, it uses the bn library to handle arbitrarily large numbers and the ec library to perform encryption based on elliptic curves. In fact, the program contains strings that reveal many of the specific .c files that are in use, making it relatively straightforward to match functions in the decompiled code to functions in the OpenSSL libraries.

AES Encryption

TeslaCrypt uses 256-bit AES encryption in CBC mode. A random key is generated for each victim, and a random initialization vector is generated for each encrypted file. The initialization vector is saved to a header at the beginning of the encrypted file, and the AES key is encrypted using a scheme based on the Elliptic Curve Diffie-Hellman key exchange algorithm.

Elliptic Curve Diffie-Hellman

To encrypt the random AES key, the program uses a variation of the Elliptic Curve Diffie-Hellman algorithm. This was my first serious look at elliptic curve cryptography, so I’ve made a separate blog post with a brief overview of how ECDH works. If you’re unfamiliar with ECDH, you can find the writeup here.

The program randomly generates two public/private ECDH keypairs. The first of these keys is used as a master key that can be used to decrypt any file on the victim’s system; the second encrypts the AES key and might vary across different files. For the remainder of this writeup, I’ll be referring to these keys as the “Round 1 key” and the “Round 2 key.”

The program performs two ECDH key exchanges. The first key exchange uses a hard-coded public key and the Round 1 private key. The second key exchange uses the Round 1 public key and the Round 2 private key (which is also the AES key).

The hard-coded public key is the point

x = 0x8f28211163feb956ef1d50d9dc7917e3ae6dac2812cb534f7490a1bee72e0d21
y = 0xff10f31537a476feef8080cfb27a7ce5833b3b16765390a5e756f30b276f6c4a

The File Header

After the AES encryption, the program writes the following values to the file header:

  • The Round 1 public key.
  • The product of the x-coordinate of the first ECDH exchange and the Round 1 private key.
  • The Round 2 public key.
  • The product of the x-coordinate of the second ECDH exchange and the Round 2 private key.
  • The initialization vector used in the AES encryption.

The HTTP Request

The program sends out an AES-encrypted HTTP request to the C2 server containing the Round 1 private key. The hex string in this request is encrypted using the hard-coded key

C4 DC B2 0E 93 65 6A 2D 90 BF 85 1F DD B1 16 2B D4 F8 E9 F6 E7 F5 A8 2A 31 1D 40 68 92 6B D5 72

and initialization vector

DE AD BE EF 00 00 BE EF DE AD 00 00 BE EF DE AD

Once we decrypt the HTTP request, there are a few interesting fields. key is the private key, and addr is a Bitcoin wallet address. ip is the victim’s IP address retrieved from ipinfo.io, though it is malformed in the screenshot above because I did not recreate the ipinfo.io site on my simulated network. gate is always G1, and I’m unsure what it refers to. Finally, inst_id is the victim ID given in the ransom note.

If this request were to be intercepted, it would be possible to use the hard-coded AES key to decrypt the request and retrieve the key. However, TeslaCrypt’s primary targets were home users, who are unlikely to be logging any requests.

The Registry Key

In order to ensure that the same Round 1 keypair is always used, the program creates a registry key under HKCU\Software\[victim ID number]. The key contains the value of the Round 1 public key, the first product, a Bitcoin wallet address, and the time of encryption. If this registry key is present, the program reads these values and reuses them rather than generate a new Round 1 keypair. However, even if the registry key is present, the program will still generate a new AES key if it is stopped and run again.

Replicating the Decryption Algorithm

Based on the HTTP request, we know that the creator of the ransomware has the Round 1 private key. They could then perform ECDH key exchange between the Round 1 private key and the Round 2 public key. Dividing the second product by the result of this key exchange, they can rederive the AES key and decrypt the files.

The following script reimplements this algorithm:

def retrieve_values(priv, pub1, pub2, prod1, prod2):
	hc_x = 0x8f28211163feb956ef1d50d9dc7917e3ae6dac2812cb534f7490a1bee72e0d21
	hc_y = 0xff10f31537a476feef8080cfb27a7ce5833b3b16765390a5e756f30b276f6c4a
	hc = Point(hc_x, hc_y)
	
	test_pub = secp256k1.double_and_add(secp256k1.G, priv)
	if(test_pub != pub1):
		print("failure on first public key:", test_pub)
		return
	
	ecdh1 = secp256k1.ecdh(hc, priv)
	print("ecdh 1 result:", hex(ecdh1))
	if(prod1 % ecdh1 == 0):
		next = prod1 // ecdh1
	else:
		print("failure on first ecdh:", hex(ecdh1))
		return
	
	ecdh2 = secp256k1.ecdh(pub2, priv)
	print("ecdh 2 result:", hex(ecdh2))
	if(prod2 % ecdh2 == 0):
		aes = prod2 // ecdh2
		print("successfully recovered aes key:", hex(aes))
		return
	else:
		print("failure on second ecdh:", hex(ecdh2))
		return

Writing a Decryptor

The flaw in the encryption comes from the product of the private key with the ECDH key exchange result. The product is a 512-bit number, and neither the private key nor the ECDH result will be prime most of the time. This means that it’s possible to factor it and retrieve the private key.

I initially dismissed this method, as I thought that most keys would end up having large factors that would be difficult to find in a reasonable amount of time. However, I later found out that this is exactly how TeslaCrypt was originally broken. Knowing this, I revisited the idea and was eventually able to use YAFU to factor a key.

For a test run, I factored the value

5AA8DFED3741DA01C0202D1359C3909BEE1570C5DA36505F1E76E362B2D65818CCD0E40E53FAF6F4FC1676B886E17759B454E0FA9D8EBD9EE8F8683DC0831DC7

which has a corresponding public key of

00 04 2F 9A 65 0A E2 F3 15 A4 40 45 59 19 48 70 F7 DC 9C AD AC 47 24 B0 2D B1 FD F5 F5 70 20 F5 74 11 20 E5 E9 88 F2 E8 67 A8 E3 00 78 4E E8 44 48 C4 2E E0 47 A3 48 B7 C2 BB 2E 90 59 2F D3 2C F9 3C

After a little over an hour, YAFU outputs the following factors:

***factors found***

P1 = 3
P1 = 3
P1 = 5
P1 = 7
P3 = 101
P3 = 773
P5 = 10837
P8 = 99807317
P25 = 1655126720228753303122051
P68 = 13781398374395757363311877843637355500151837520775480225177546547567
P43 = 7825723884698533506375783563522817813881993

ans = 1

From there, we need to figure out which of the divisors of this product is the correct private key. However, this is easy to do. The public key is given to us in the encrypted file header, so we can just generate the public key that goes with each private key candidate and see if it matches the given one:

def get_key_candidates(factors, pubkey):
	for i in range(len(factors)):
		for subset in combinations(factors, i):
			prod = 1
			for fac in subset: prod *= fac
			if(secp256k1.double_and_add(secp256k1.G, prod) == pubkey):
				print(prod)
				print(subset)

In this case, we recover the private key

86655516964165928432754623993726968327056923720817543761676186481982334307557 = 3 * 3 * 7 * 99807317 * 13781398374395757363311877843637355500151837520775480225177546547567

which we can then use to recover all encrypted AES keys and decrypt our files.