In typical applications of cryptography, there usually are several distinct parties involved in a protocol. That might be part of the reason why cryptography has become so complicated. Even in simpler scenarios, where the sender and the recipient of a message are essentially the same person, there are applications for the arguably more advanced public-key primitives. There is also plenty of room for mistakes to be made.

Mallory has managed to install malware onto a machine she normally has no business of accessing. To carry out her evil plans, she has set up a way to control the victim machine remotely. She is able to send commands to and receive responses from the malware running there. This text is about the way Mallory applies cryptography to secure her messages.

Introducing Mallory

I have never been in touch with Mallory or anyone like her. She is simply a badly behaved person with a computer. She might be related to the attackers responsible for the espionage case at RUAG I wrote about earlier. For all we know, she uses a piece of malware almost identical to that found at RUAG. I would like to thank the Swiss GovCERT team for providing the motivation for this text and for helping me along the way.

How the messages are secured

Because of my lack of contact with Mallory, I can only guess what she wanted to achieve by her use of cryptography. Let us see what she ended up with.

All communication is encrypted by AES with a random 256-bit session key. The AES key itself is encrypted under a fixed ElGamal key modulo a 1024 prime and sent along with the AES ciphertext. Mallory uses two sets of ElGamal keys, one per direction of communication. She keeps one ElGamal private key to decrypt traffic from the victim and one ElGamal public key to encrypt commands. On the target machine, her Tavdig keeps a private key to decrypt the commands and a public key to encrypt answers.

One of the public keys is actually available to Mallory only. On the other hand, one private key is embedded in a piece of malware in the wild where people other than Mallory could possibly get a hold of it. There is a public key that is actually private and a private key that is somewhat public. For that reason, I shall use the terms encryption and decryption key instead of public and private.

Imagine we were aware of the setup and had a copy of the binary Mallory runs on the target system. Let us also imagine we could position ourselves somewhere between Mallory and her victim on the network. Because the command decryption key is in the binary, we could decrypt all commands the same way Tavdig does. We could not decrypt genuine replies from the malware, because the reply decryption key is held by Mallory only. We could however create arbitrary fake answers using the reply encryption key available in the binary .

Symmetry in asymmetric cryptography

By definition, the decryption key can decrypt and the encryption key can be used for encryption. It is a basic property of public-key encryption schemes, that the encryption key alone is of no use for decryption.

What about creating ciphertexts with the decryption key only? This might sound like a silly question. After all, the encryption key is usually public, anybody can use it to encrypt whatever they like. In our case however, Mallory keeps her encryption key secret. Nevertheless, it is still possible to generate an encryption of anything we like with the decryption key only. In consequence, given an appropriate position on the network, we can take over Mallory's bots.

The general case

Given an asymmetric encryption algorithm and a decryption key, one can always generate a random ciphertext \(C\) and then try to decrypt it. Repeat until the resulting random plaintext happens to be a reasonable message. If such reasonable messages only form a tiny fraction of all messages, this strategy is unlikely to work well.

When using hybrid encryption, as Mallory does, the plaintext of the asymmetric layer is the key for the symmetric layer. Any data is acceptable as a cryptographic key. Unless there is some special encoding in place, every random ciphertext will decrypt to a reasonable symmetric key for the inner layer.

In Mallory's work, there is no such encoding, any data is blindly interpreted as an AES key. The above strategy always works.

ElGamal encryption

Recall that ElGamal encryption is performed in a multiplicative group of integers modulo a prime \(p\) generated by \(g\). The decryption key is an exponent \(1<x<p-1\), the encryption key is the group element \(y=g^x\) modulo \(p\) along with \(g\). Both keys also contain the modulus \(p\).

To encrypt a message \(1\leq m<p\), pick a random \(k\), compute \(K=y^k\) and output the pair \(C=(g^k, Km)\), all modulo \(p\). To decrypt, compute \(K = (g^k)^x\mod p\) and then recover \(m\).

If one were able to compute the decryption key \(x\) from the encryption key \(y=g^x\mod p\), they could also solve discrete logarithms in the group generated by \(g\). Let us hope that is unlikely. On the other hand, computing an encryption key from the decryption key is trivial. If \(g\) is available, compute the power \(y=g^x\mod p\). If the generator is unknown, simply select one at random. If you pick any \(1< g' < p-1\) and let \(y'=({g'})^x\), you will end up with an encryption key that works with the decryption key \(x\). It will probably be different from the "original" key \(y\), but just as good in creating ciphertexts.

For Mallory and her victim this means that anybody with access to the ElGamal decryption key within Tavdig can compute a corresponding encryption key and encrypt messages at will. Now we can even control the symmetric AES key, in contrast to the earlier general approach. There the key was essentially random, but equally useful.

For sending commands to the victim, the hybrid cipher used by Mallory is no better than a plain symmetric cipher would be. Note that in the case of symmetric keys, one can always trivially compute the encryption key from the decryption key (and vice versa).

ElGamal by Mallory

It turns out that Mallory's implementation in Tavdig allows the use of \(K = 1\). One can simply send the pair \((1,m)\) as an ElGamal ciphertext. Tavdig then decrypts it by raising the integer one to the power of \(x\) to recover \(m\) from \(m\). One can therefore use \(g=1, y=1\) as a universal ElGamal encryption key to control all the instances of Tavdig Mallory has ever deployed, independent of \(p\) or \(x\).

It turns that this particular use of a hybrid cipher to encrypt messages sent to the victim is even worse than the use of a simple symmetric scheme. Not even the decryption key is necessary to encrypt arbitrary commands.

(Textbook) RSA

Would the story be much different if Mallory used RSA in the asymmetric layer? It turns out that in contrast to ElGamal, it is generally not easy to compute RSA encryption keys from decryption keys alone. RSA is computed in the multiplicative group of integers modulo \(n=pq\) for prime \(p,q\). There is an integer encryption exponent \(e\) and a decryption exponent \(d = e^{-1}\mod(p-1)(q-1)\). To encrypt a message represented by an integer \(m\) modulo \(n\), raise it to the power of \(e\). Reverse the process by raising a ciphertext to the power of \(d\), all modulo \(n\).

The integer \(e\) along with the modulus \(n\) form the encryption key. The corresponding decryption key is represented by \(d\) and \(n\). Can one compute the encryption key from the decryption key?

In the real world, the task would be rather easy. For reasons of efficiency, the encryption exponent is often a small and simple number such as 65537 and therefore easy to guess. Also, the decryption key often includes the factors \(p\) and \(q\) to speed up computation. Given the factorization of \(n\), computing \(e\) from \(d\) (and vice versa) is trivial.

If, however, we are only given the modulus \(n\) and a randomly selected exponent \(d\), computing the corresponding encryption exponent \(e\) is hard. This follows from the symmetry between \(e\) and \(d\) within RSA. If it were easy to compute \(e\) from \(d\), it would also be easy to compute \(d\) from \(e\) and RSA as a cryptosystem would not exist.

When designing her hybrid system based on ElGamal encryption, Mallory did not pay attention to the special multiplicative properties of the number one. This allowed us to generate encryptions of arbitrary plaintexts even without the decryption key. In RSA, the integer one as a special case would also need some attention. Observe that RSA encryption and decryption leave the number one unchanged. If the integer one is sent as an RSA ciphertext, the corresponding plaintext is also one, independent of the actual key. In a hybrid scheme, the plaintext of the asymmetric layer is the key for the symmetric layer. Even if the symmetric key were fixed to equal one, we could still use it to encrypt arbitrary messages.

Somewhere, there is a cousin of Mallory, who chose RSA for their hybrid scheme and paid little attention to the special multiplicative properties of the number one.

Helping Mallory

Mallory apparently wants to send encrypted messages to the victim machines, her malware therefore has to include a decryption key. Knowledge of the key implies the ability to decrypt the commands. To prevent others in possession of the key(s) within the binary from creating valid messages, Mallory might consider the use of public-key digital signatures.

Her signing key would remain secret. The verification key is typically public, including it in the malware does not allow others to forge signatures. Public-key primitives such as ElGamal or RSA might be the right tools the job, when used properly. Mallory needs the primitives for signatures rather than for encryption.

The question, how her botnet can be made more sophisticated, shall remain open. The best course of action for Mallory is to stop writing malware and get a life instead.