10
$\begingroup$

In traditional malware (especially ransomware) using RSA approach, the public key may be hard-coded in the malware binary and is used to encrypt a symmetric key generated on the system. The symmetric key itself is used to encrypt user files.

Some new variants of malware are using ECDH instead of RSA. How is ECDH used in this context securely when malware analysts can reverse engineer the malware binary to find the curve and the parameters?

I have done the following research on this issue:

So I understand the general concept of the logarithm problem where it is infeasible (computationally intensive) to find factors on the curve. But what I do not understand is this: if the curve and the pre-agreed parameters on the curve are hard-coded in the malware, can't malware analysts reverse engineer the malware binary to find the agreed upon curve and the parameters? Can this be then used to find the keys and beat the malware? If not, what is the "secret" that both malware developer and malware binary have access to (the two parties) but not the malware analyst who can reverse engineer the binary? For example, in the case of RSA, this secret is the private key which never leaves the attacker.

$\endgroup$
12
$\begingroup$

Quick summary. Ransomware works by a public-key key encapsulation mechanism: pick a secret key $h$ and an encapsulation $\sigma$ of it for the malware operator's public key, so that only the malware operator can recover $h$ from $\sigma$ using their private key; then encrypt all the files using a symmetric cipher under the key $h$, erase $h$, and pay the malware operator ransom to get $h$ back from $\sigma$.

It's easy to build a public-key key encapsulation mechanism out of a public-key key agreement scheme such as ECDH with a long-term public key for the recipient: Generate a single-use anonymous key pair for the sender, combine the sender's private key with the recipient's public key to derive $h$, erase the sender's private key, and transmit the sender's public key as the encapsulation of $h$. Using that as a subroutine, the malware then works just like it would with any public-key key encapsulation mechanism.

Details. First, for reference, here's a way malware on the host can use a public RSA modulus $n$, say between $2^{2047}$ and $2^{2048}$, with secret factorization $n = pq$ known only to the malware operator.

  1. Pick a nonnegative integer $x$ below $n$ uniformly at random using the host's random number generator, e.g. /dev/urandom on Unix or CryptGenRandom on Windows.
  2. Compute and store $y = x^3 \bmod n$.
  3. Compute $h = H(x)$, where $H\colon \mathbb Z/n\mathbb Z \to \{0,1\}^{256}$ is a random oracle. E.g., you might instantiate $H$ with SHA-256 on the little-endian $\lceil\log_{256} n\rceil$-byte encoding of the least nonnegative residue of $x$.
  4. Compute and store $c = \operatorname{AES-GCM}_h(\mathit{data})$, where $\mathit{data}$ is whatever important data are on the host's persistent storage that you're ransoming.
  5. Erase $x$, $h$, and $\mathit{data}$.
  6. When the hapless user pays the ransom, transmit $y$ and a proof of payment to the malware operator.

On receipt of $y$ and proof of payment, the malware operator can use secret knowledge of $p$ and $q$ to compute $x = y^d \bmod n$ where $d$ solves $3d \equiv 1 \pmod{\operatorname{lcm}(p - 1, q - 1)}$, and from there derive $h = H(x)$ for the luser to use to decrypt $c$ with AES-GCM.

The security of this scheme relies on the difficulty of computing cube roots of uniform random integers modulo $n$ without knowledge of the factorization of $n$. There are some integers whose cube roots modulo $n$ are very easy to compute: the ones that are perfect cubes as integers in the first place, so that ordinary real number cube root algorithms can compute them. But the vast majority of integers are not perfect cubes, so the probability that $y$ happens to be a perfect cube is negligible, and the cheapest algorithms we know to compute $x$ or $h$ given $y$ with nonnegligible probability work by factoring $n$, namely ECM and GNFS.

How does it work with ECDH? Fix a standard public field $k$, say $\operatorname{GF}(2^{255} - 19)$. Fix a standard public curve $E/k$, say $y^2 = x^3 + 486662 x^2 + x$. Fix a standard public $k$-rational point $G \in E(k)$ of large prime order, say $G = \pm x^{-1}(9)$. Fix a public $k$-rational point $P \in E(k)$ for which the malware operator knows a secret integer $s$ such that $$P = [s]G = \underbrace{G + G + \dots + G}_{\text{$s$ times}}.$$ Using these parameters, the malware on the host will:

  1. Pick a nonnegative integer $t$ between $2^{254}$ and $2^{255}$ that is a multiple of 8, uniformly at random using the host's random number generator, e.g. /dev/urandom on Unix or CryptGenRandom on Windows.
  2. Compute and store $Q = [t]G$.
  3. Compute $h = H([t]P)$.
  4. Compute and store $c = \operatorname{AES-GCM}_h(\mathit{data})$.
  5. Erase $t$, $h$, and $\mathit{data}$.
  6. When the hapless user pays the ransom, transmit $Q$ and a proof of payment to the malware operator.

On receipt of $Q$ and proof of payment, the malware operator can use secret knowledge of $s$ to compute $$[s]Q = [s\cdot t]G = [t\cdot s]G = [t]([s]G) = [t]P,$$ and from there derive $h = H([s]Q) = H([t]P)$ for the user to use to decrypt $c$ with AES-GCM.

This scheme is sometimes called ECIES. The pair $(s, P)$ serves as the recipient's long-term key pair, while the pair $(t, Q)$ serves as the sender's single-use key pair, for public-key key agreement with an elliptic-curve Diffie–Hellman function.* Choosing a single-use anonymous key pair like this turns a public-key key agreement scheme into a public-key key encapsulation mechanism.

The security of this scheme relies on the difficulty of computing discrete logarithms in the group $E(k)$. The parameters are all public; all that the adversary—in this case, the hapless user who has been afflicted by ransomware, or the IT specialists they hire to recover their data without just paying the ransom—doesn't know are the secret integers $s$ and $t$, the AES-GCM key $h$, and the poor user’s data.


* The curve chosen, Curve25519, admits a fast algorithm to compute $x([s]G)$ given only $s$ and $x(G)$, which is why the Diffie–Hellman function is called X25519; we actually don't ever compute the $y$ coordinates or full points, just the $x$ coordinates above, but the notation got cumbersome when everything was written as $x(Q)$, $H(x([t]P))$, etc.

$\endgroup$
  • $\begingroup$ Thank you for the details. One question: do I understand correct that here 'H' is a hash function and 'h' is the symmetric key deployed in data encryption? $\endgroup$ – learnerX May 7 '18 at 4:00
  • 1
    $\begingroup$ @learnerX Correct: $H$ is a hash function—specifically, a random oracle, which you might instantiate by a key derivation function such as HKDF-SHA256—and $h$ is its output, a key used for symmetric-key authenticated encryption with associated data. $\endgroup$ – Squeamish Ossifrage May 7 '18 at 4:14
  • $\begingroup$ Shouldn't (Q,c,t) be transmitted to operator and not just (Q,c) in step 6. I mean 't' was generated randomly on host and is required by operator to derive 'h'? $\endgroup$ – learnerX May 7 '18 at 4:26
  • 1
    $\begingroup$ @learnerX The magic is the equation $[t]P = [t\cdot s]G = [s\cdot t]G = [s]Q$. The malware operator knows $s$ and $Q$, so they can compute $[s]Q$ and get the same point as $[t]P$ which was computed on the host with knowledge of $t$ but not $s$. $\endgroup$ – Squeamish Ossifrage May 7 '18 at 4:31
  • 1
    $\begingroup$ @learnerX Yes, knowledge of $t$ or $s$ would suffice to decrypt the data: $G$, $P$, and $Q$ are public; the secret is $[t\cdot s]G = [t]P = [s]Q$. But after the deed is done, nobody knows $t$ unless (a) the victim's random number generator is completely broken, or (b) the malware failed to erase its copy of $t$. $\endgroup$ – Squeamish Ossifrage Jun 6 '18 at 18:53
6
$\begingroup$

ECDH can be used for public key encryption just like RSA can be used for public key encryption. However, the EC problem cannot be used directly to encrypt data like the RSA algorithm can be used.

Instead Diffie-Hellman is with a static key pair (similar to RSA) and an ephemeral key pair. The public key of the receiver can be used with the temporary private key to derive a symmetric key such as an AES key. This key can be used to encrypt the data. Then the data is send together with the temporary public key. Then this key can be used with the static private key to derive the same AES key, which finally can be used to decrypt the data. This way of using Diffie-Hellman key agreement to keep data confidential is called IES or ECIES when it is used with Elliptic Curve Cryptography.


So except for the method on how the symmetric key is established, the scheme is very similar to RSA encryption. And in both cases the security relies on a private key of a static key pair. Cracking either ECIES or RSA is considered very hard if the scheme is implemented correctly. Only a fully fledged quantum computer may break RSA or ECIES directly as neither scheme is secure against quantum analysis.


The parameters of the curve are always public. Leaking them does not let an adversary be able to calculate the private key nor the secret key calculated using the ephemeral key pair.


Note that there are some other models that use the hardness of the ECC problem to encrypt messages. But in general they similarly rely on a static key pair for the security of the scheme. ECIES is the most likely scheme to be used though.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.