Exchange AES Keys with RSA

Armed with their newer cryptography technologies, Alice and Bob have become more brazen in their covert operations. Alice has managed to infiltrate the Snow Den Records Center in West Antarctica and is attempting to steal a document related to genetic experiments to turn penguins completely white, thus creating a perfectly camouflaged Antarctic soldier. WA soldiers are quickly moving on her position, and she decides to risk transmitting the document over a short-wave radio to Bob who is monitoring from outside the building. Eve is certainly listening and Alice does not want her to know which document has been stolen.

The document is nearly ten megabytes. RSA encryption of the entire document will take forever. Fortunately, she and Bob agreed beforehand to use RSA encryption to send AES session keys and then transmit the document using AES-CTR with HMAC. Let’s create the code they will use to make this alphabet soup work.

Hopefully, all of the pieces here are familiar, and if you follow the code paths, it should also be pretty easy to see how things come together. Perhaps you’ve noticed that we are drawing on concepts from Chapter 3, Chapter 4, and Chapter 5! All of these pieces are coming together to shape a more advanced whole.

A few points are worth noting. First, we chose to use AES-CTR, so there is no need for padding. Earlier in the book, we used the term “nonce” to describe the initialization value to the algorithm, as this is what the cryptography library calls it. In other literature it is still called an IV, however, so we use that term here. Either way, the IV (or nonce) is the starting value for the counter.

Note that we are not using Sign-Then-Encrypt as we discussed in Chapter 5. As always, this is an example program not meant to be used for real security. You might want to review the issues we discussed in relation to Sign-Then-Encrypt to see how Eve could strip out the signature, change the keys, and re-sign.

Nevertheless, that’s not the major vulnerability we will discuss. After all, in our scenario, Bob is probably only going to accept data from Alice. The issues of swapping out a signature are more applicable when more than one signature can be accepted.

Like most of the APIs you’ve seen so far, we use update and finalize, but we added a new method called initialize . For transmission, Alice would call initialize first to get the signed and encrypted header with the session keys. Next, she would call update as many times as needed to feed the entire document through. When everything is finished, she would call finalize to get the HMAC trailer over all of the transmitted contents.

Asymmetric and Symmetric: Like Chocolate and Peanut Butter

Hopefully, Alice’s transmission to Bob in the exercise at the beginning of this chapter gave you a small taste for how asymmetric and symmetric cryptography work together. The protocol we outlined in code works, but lacks some important subtlety, as is often the case with our first attempts. As you might expect by now, the preceding code is not secure and we will demonstrate at least one problem with it shortly. It does illustrate the ideas behind putting the two systems together, though.

Let’s see what we can learn from what we have. We’ll start with session keys.

We first introduced the term session key in Chapter 4 but did not discuss it much. A session key is by nature a temporary thing; it is used for a single communication session and then discarded permanently, never to be reused. In the preceding code, notice that the AES and MAC keys are generated at the beginning of a session by the communications manager. Every time a new communications manager is created, a new set of keys is created. The keys are not stored or recorded anywhere. Once all the data is encrypted, they are thrown away.¹

On the receiving end, the session keys are decrypted using the recipient’s private key. Once these keys are decrypted, they are then used to decrypt the rest of the data and process the MAC. Again, after the transmitted data is processed, the keys can—and should—be destroyed.

Symmetric keys make good session keys for multiple reasons. First of all, symmetric keys are easy to create; in our example, we simply generated random bytes. We could also derive symmetric keys from a base secret by using key derivation functions. This is a common approach, and we will see later that you almost always need to derive multiple keys for typical secure communication. Regardless of how they are created, symmetric keys (and IVs) are plain old ordinary bytes, unlike most asymmetric keys that require some additional structure (e.g., public exponents, chosen elliptic curves, etc.).

Second, symmetric keys are good session keys because symmetric algorithms are fast. We have already mentioned this a time or two, but it is worth repeating. AES is typically on the order of hundreds of times faster than RSA, so the more data that can be encrypted by AES, the better. This is another reason that symmetric keys are sometimes called “bulk data transfer” keys.

Finally, let’s also recognize that symmetric keys are good session keys because they are not always good long-term keys! Remember, symmetric keys cannot be private keys because they must always be shared between at least two parties. The longer a shared key is in use, the higher the risk that trust breaks down between the parties and the key should no longer be shared. In the case of Alice’s break-in to the Snow Den archive, she risks capture and the compromise of any keys she has with her. The loss of her asymmetric private key is serious, as we discussed when we talked about certificate revocation, but if Alice and Bob were using the same shared symmetric key for all of their communications, the loss of that key would be even worse as any intercepted communications between them that were encrypted using that key could now be decrypted.

On the other hand, asymmetric keys are very useful for long-term identification. Using certificates, asymmetric keys can establish a sort of proof of identity; once this is done, the shorter-term keys do the work of actually transmitting data between the authenticated parties. That said, sometimes ephemeral (quickly discarded) asymmetric keys are incredibly valuable. We will see this both with key exchanges that have the “forward secrecy” attribute and with how ransomware attackers lock up their victims’ files.

Measuring RSA’s Relative Performance

Even though we’ve hammered home just how much slower RSA is than AES, let’s have some fun and run a few experiments. We’re going to write a tester that will generate random test vectors for encryption and decryption. Then we can compare the performance of RSA and AES for ourselves.

Let’s start by creating some algorithms to test. We will define one class for each algorithm, and the instances of the class will build encryption and decryption objects. Builders will be self-contained, providing all keys and necessary configuration. Each will have a name attribute with a human-readable label and a get_cipher_pair() method to create a new encryptor and decryptor. This method must generate new encryption and decryption objects each time it is called.

The get_cipher_pair() operation creates new keys and nonces each time it is invoked. We could put this in the constructor because we don’t really care if we reuse keys for these speed tests, but the re-generation of a few bytes for a key and a nonce is probably not really a limiting factor for speed.

RSA encryption is a little more complicated. It really wasn’t meant to encrypt arbitrary amounts of data. Unlike AES, which has counter and CBC modes to tie blocks together, RSA must encrypt its data all at once, and the size of data it can manipulate is limited by various factors. An RSA key with a 2048-bit modulus cannot encrypt more than 256 bytes at a time. In fact, once you add in the OAEP (with SHA-256 hash) padding, it’s significantly less: only 190 bytes!²

If we were actually concerned about the security of the encryption, we could thus not use RSA for more than 190 bytes of data. However, what we are really testing here is a hypothetical RSA encryptor that does not exist in the real world. What we want to explore is this: if RSA could encrypt arbitrary amounts of data, how long would it take? For this test, we will encrypt each chunk of 190 bytes one at a time and concatenate the results together. Note that when we encrypt with the OAEP padding, the 190 bytes of plaintext becomes 256 bytes of ciphertext. When we are decrypting, we need to decrypt 256-byte chunks.

Although a truly secure RSA encryption algorithm would have to bind the bytes of the different individual encryption operations together, this version is the fastest it could ever be, so it gives us an upper bound on speed, making for an interesting comparison.

Note that we created our encryptor and decryptor to have the same API as the AES encryptor and decryptor. Namely, we provide update and finalize methods . The finalize methods don’t do anything as RSA encryption (with padding) processes each chunk exactly the same way. The chunk-by-chunk encryption takes each 190-byte piece of the input, encrypts it to the 256-byte ciphertext, and returns the concatenation of all of these pieces. The decryptor reverses the processes, taking each 256-byte chunk in for decryption. Our RSAAlgorithm class constructs the appropriate encryptor and decryptor using these classes.

Notice that a new random_data_generator contains timing and data specific to each individual test run. So a new object needs to be created for each test.

The stats dictionary is used for holding encryption and decryption times for the various algorithms in the various tests. These can be used to generate some fun graphs. For example, Figure 6-1 and Figure 6-2 are the encryption and decryption graphs for the tests we ran.

As you can see, RSA operations are so much slower, it’s not even really a comparison. By the way, if you run the tests we did, RSA encryption over 100 MiB can be slow (about 20 seconds on our computer), but decryption is so bad, it’s just off the charts (about 400 seconds for our tests!). RSA decryption is slower than RSA encryption, so this isn’t a surprise. When you have tests that run this long, make sure to save the statistics in raw, numerical format and then generate graphs from this data. That way you can regenerate graphs quickly and easily without running the entire test again.

Hopefully, these timed tests have helped to reinforce why, security reasons aside, symmetric ciphers are preferred over asymmetric ciphers for bulk data transfer.

Diffie-Hellman and Key Agreement

For the last couple of sections in this chapter, we will look at another type of asymmetric cryptography known as Diffie-Hellman (or DH) and a more recent variant called Elliptic-Curve Diffie-Hellman (or ECDH).

DH is a little different than RSA. Where RSA can be used to encrypt and decrypt messages, DH is only used for exchanging keys. In fact, it is technically called the Diffie-Hellman key exchange. As we have already explored in this chapter, outside of signatures, RSA encryption is largely used only for transmitting keys, also called “key transport.” This means that if Alice has Bob’s RSA public key, Alice can send Bob an encrypted key that only Bob can decrypt.

Figure 6-3 shows key transport in a TLS 1.2 handshake. We will discuss the TLS 1.2 handshake in more detail in Chapter 8, where this figure will also make an appearance. But notice that the client in this figure can generate a random session key, encrypt it under the server’s public key, and “transport” it back. This process also proves the server is in possession of the certificate because only the server could decrypt the session key and use it to communicate. No signatures are required for the server.³

On the other hand, DH and ECDH actually create a key seemingly out of thin air. No secrets are transmitted between the parties, encrypted or otherwise. Instead, they exchange public parameters that allow them to simultaneously compute the same key on both sides. This process is called key agreement .

To get started, Diffie-Hellman creates a pair of mathematical numbers, one private, one public, for each participant. The DH and ECDH key agreement protocol requires that both Alice and Bob have key pairs. In over-simplistic terms, Alice and Bob share their public keys with each other. The foreign public key and the local private key—when combined—create a shared secret on both sides.

A non-mathematical explanation in A. J. Han Vinck’s course “Introduction to Public Key Cryptography” [14] is depicted in Figure 6-4.

Please note that, unlike RSA, DH and ECDH do not allow for the transmission of arbitrary data. Alice can send Bob any message she chooses, encrypted under Bob’s RSA public key. Using DH or ECDH, however, all that the two can do is agree upon some random data; they don’t get to choose the message contents. The random data can be, and typically is, used as a symmetric key or for deriving symmetric keys.

In addition to not being able to exchange arbitrary contents, key exchange is also limited in that it requires bidirectional information exchange. In our scenario at the beginning of this chapter, Bob could not transmit for fear of discovery. Were that actually the case, DH and ECDH key exchanges would be impossible and RSA encryption would be the only option. This really isn’t an issue in almost all real-world scenarios. In real Internet applications, we typically assume that both sides are free to communicate with each other.

Unlike RSA there are a lot fewer pitfalls and gotchas.

There are only two parameters to the exchange: the generator and the key size. There are only two legal values for the generator, 2 and 5. Strangely enough, for a cryptographic protocol, the choice of generator doesn’t matter for security reasons but must be the same for both sides of the exchange.

The key size, however, is important and should be at least 2048 bits. Key lengths between 512 and 1024 bits are vulnerable to known attack methods.

The other recommended setting is to derive another key from the shared key rather than using the shared key directly. The key derivation function is similar to the ones we looked at in Chapter 3.

The TLS 1.2 handshake can either do the key transport using RSA encryption or key agreement using DH/ECDH. Again, this will be discussed in Chapter 8 in detail, but Figure 6-5 shows that both sides exchange the public data, derive a key, and can communicate using the agreed-upon keys. Unlike key transport, however, there is no authentication. Either or both sides will have to sign the public data to prove that possession of a public key.

In most circumstances, creating keys with DH or ECDH key agreement is preferred over RSA key exchange. There are a number of reasons but perhaps the biggest one is forward secrecy.

Diffie-Hellman and Forward Secrecy

Using RSA encryption, we can generate a symmetric key, encrypt it under someone’s public key, and send it to them. This allows both parties to share a session key securely, provided that the exchange protocol follows certain rules. There are even ways to have both sides contribute to a key. Each party could send the other some random data, and the concatenation of both could be fed to a hash function to produce the session key.

Unfortunately, RSA key transport does not provide a really fantastic property called forward secrecy. Forward secrecy means that even if a key is eventually compromised, it does not reveal anything about previous communications.

Let’s go back to Alice, Bob, and Eve. Alice and Bob already assume that Eve is recording everything that is transmitted. That’s why they are encrypting the transmission in the first place. So, after the transmission is complete, Eve has a recording of the ciphertext that she cannot yet decrypt. But, rather than toss it aside, Eve files it away in storage.

But also recall that, in our scenario, Alice actually believed she was on the verge of being captured. If the guards capture her and her keys are compromised, what is lost? Fortunately, nothing. Remember that Alice encrypted the session keys under Bob’s public key. Capturing Alice won’t make it any easier to decrypt that data (do you see the advantage of this over shared keys?).

But suppose that Eve finds Bob, perhaps even a long time in the future. Even if it’s years later, if Eve manages to get Bob’s private key, she can go back to her recording of Alice’s previous transmission and decrypt it! Bob’s private key will still decrypt the session keys, and Eve will then be able to decrypt the entire transmission.

Forward secrecy is much stronger than this. If a protocol has forward secrecy, Eve can never recover data from a terminated session no matter what long-term keys she manages to obtain. Forward secrecy is not possible when session keys are sent directly via RSA encryption (in the way we’ve just described) because once the RSA private key is compromised, any recorded data from previous sessions is now vulnerable.

With Diffie-Hellman (DH) and Elliptic-Curve Diffie-Hellman (ECDH), forward secrecy is achieved by the use of ephemeral keys. RSA produces an ephemeral symmetric session key, but DH and ECDH actually produce ephemeral asymmetric keys as well! A new ephemeral key pair is (or should be!) generated with every single key agreement operation and then thrown away. The symmetric key is also ephemeral and thrown away after each session. Because DH and ECDH are typically used in this fashion, an “E” is often tacked onto the end of the acronym (DHE or ECDHE).⁴

Now that a new key pair is used for every exchange, compromising a single asymmetric key only reveals a single symmetric key and, accordingly, a single communications session. And when the ephemeral DH and ECDH private keys are properly disposed of, there is no key left for Eve to compromise and no way that she could ever decrypt these sessions. In some ways, it is akin to the old spy trope of swallowing the key so the spy’s nemesis can’t unlock the movie’s McGuffin.

Observe that, in theory, Alice and Bob could also do an ephemeral RSA key exchange. They could generate new RSA key pairs for every single key transport, sending each other their new public keys before transmitting the session key, then destroying the key pair after transmission.

The problem is that generating RSA keys is slow in computer terms. You might not have thought it took very long to generate your RSA keys for the examples in this book, but for computers involved in rapid communications (such as setting up a secure connection from your browser to a web site), RSA is mind-numbingly slow. DH and ECDH are much, much faster. Because of the key generation speed, DH and ECDH are the common choices for forward-secrecy-style communications.

This ephemeral mode of operation is the preferred mode for DH and ECDH under almost all circumstances, which is why DH and ECDH often mean DHE and ECDHE.

There’s only one other limitation to Diffie-Hellman methods: they have no authentication. Because the keys are completely ephemeral, there is no way to tie them to an identity; you don’t know with whom you are speaking. Remember that beyond communicating confidentially, we need to know with whom we’re communicating confidentially. By itself, DH and ECDH do not provide any such assurances.

For this reason, many DH and ECDH key exchanges also require a long-term public key, such as RSA or ECDSA, and that key is typically protected within a signed certificate. These long-term keys, however, are never used for encryption or key transport and are not used in the actual exchange of key data in any way. Their sole purpose is to establish the identity of the other party, usually by signing some of the ephemeral DH/ECDH data being exchanged, and to ensure freshness via some kind of challenge or nonce.

Remember, to ensure forward secrecy, the Diffie-Hellman parameters must be regenerated for every key exchange. If you take a look through the cryptography library documentation, you’ll notice that they include sample code that, as written, does not provide forward secrecy. This code sample saves what should be a single-use key for later. Make sure that your keys are destroyed after use (never logged).

To use the ECDHExchange , both parties instantiate the class and call the get_public_bytes method to get the data that needs to be sent to the other party. When those bytes are received, they are passed to generate_session_key where they are de-serialized into a public key and used to create a shared key.

So, what’s with HKDF ? This is a key derivation function that is useful for real-time network communications, but should not be used for data storage. It takes the shared key as input and derives a key (or key material) from it. Notice that in our example, we derive both an encryption key and a MAC key. This is done by using HKDF to derive 64 bytes of key material and then splitting it into two 32-byte keys. In reality, we need to derive a lot more data, and we’ll discuss this in the next section. But for now, it demonstrates the basics of the ECDH exchange.

To repeat one last time, notice that ECDH is generating its private key on the fly. This key must be destroyed after every key exchange, along with any session keys created.

Our ECDH code so far just does the ECDH ephemeral key exchange. Both sides have a key, but since we aren’t yet doing any authentication, neither side can be certain about whom they’re talking to! Remember, the ephemeral nature of the ECDH keys means that they cannot be used to establish identity.

To remedy this, we are going to modify our ECDHExchange program to also be authenticated. In addition to an ephemeral asymmetric key, it will also use a long-term asymmetric key to sign the data.

Please note the difference between _private_key, which is generated and is ephemeral, and _auth_private_key. The latter is passed in as a parameter. This persistent key will be used to establish identity. We could use an RSA key here and it would work just fine, but in keeping with the elliptic-curve theme, we will assume this is an ECDSA key.

When the other side receives our data, they will need to unpack the first four bytes to get the length of the signature before they do anything else. The signature can be verified using the other party’s long-term public key (just like we did with RSA). If the signature works out, we have some confidence that the ECDH parameters we received came from the expected party.

The principles in this section are important. You might consider working through this section a couple of times until you are comfortable with both sending a key encrypted under RSA and generating an ephemeral key on the fly using DH or ECDH. Make sure you also understand why the DH/ECDH approach has forward secrecy and the RSA version does not.

Challenge-Response Protocols

We have briefly introduced challenge-response protocols in Chapter 5. In particular, Alice used challenge-response to validate that the man claiming to be Charlie was the owner of the certificate with the identity “charlie.” At its core, a challenge-response protocol is about one party proving to another that they currently control either a shared secret or a private key. Let’s look at both examples.

First, suppose that Alice and Bob share some key K_A,B. If Alice is communicating over a network with Bob, a simple authentication protocol is to send Bob a nonce N (potentially unencrypted) and ask him to encrypt it. For security reasons, it’s a good idea for the response to include the identity of the communicating parties. Accordingly, Bob should reply with {A, B, N}_KA,B. If only Alice and Bob share the key K_A,B, then only Bob could have responded to Alice’s challenge correctly. Even if Eve overhears the challenge and knows N, she should not be able to encrypt it without the key.

For the asymmetric example, it is more or less the same, but uses signatures generated by private keys. This time, Bob is communicating with Alice over the network and wishes to be sure that he is talking to the real Alice. So he sends a nonce N and asks her to sign it with her public key. As with Bob’s challenge, Alice should also send her name and Bob’s. Her transmission should therefore look like {H(B, A, N)}_K –1_A (for RSA signatures anyway). Bob verifies with the Alice’s public key that the signature is correct. Only the possessor of the private key could have signed that challenge.

Challenge-response algorithms are relatively simple, but they can go wrong in many ways. For one thing, the nonce must be sufficiently large and sufficiently random to be unguessable, even with knowledge of previous transmissions. In the early days of remote keys for cars, for example, the transmitter used a 16-bit nonce. Thieves only had to record a transmission once and then interrogate the system over and over until it cycled through all the possible nonces and returned to the one they recorded. At that point, they could replay the nonce and gain access to the car.

Another way this can go wrong is via a “(hu)man-in-the-middle” (MITM) attack. Suppose that Eve wants to convince Alice that she is Bob. Eve waits until Bob wants to talk to Alice and then intercepts all of their communications. Then, she initiates communication with Alice pretending to be Bob. Alice responds with a challenge N to prove that the person she is talking to (Eve) is Bob. Eve immediately turns around and sends the challenge to Bob who, wanting to talk to Alice, was already expecting it. Bob happily signs the challenge and sends it back to Eve who forwards it directly on to Alice. (For a fascinating, but probably fictional example, Ross Anderson describes a “MIG-in-the-middle” scenario of this attack [1, Chap. 3].)

One way to defeat this MITM problem is to transmit information that only the true party can use. For example, even if Eve forwards along Bob’s response to the challenge it won’t help her if Alice’s response is to send Bob a session key encrypted under his public key. Eve won’t be able to decrypt it. If all subsequent communication takes place using that session key, Eve is still locked out. Alternatively, Alice and Bob could use ECDH plus signatures to generate a session key. Even if Eve can intercept every transmission between the two of them, Alice and Bob can create a session key that only they can use. The most Eve can do is block the communications.

The point here is to illustrate all the different kinds of considerations that need to go into authenticating the party you’re talking to.

Once the identity of a party has been established, all subsequent communications of the session must be tied to that authentication. For example, Alice and Bob might authenticate one another using challenge-response, but unless they establish a session MAC key and use it to digest all of their subsequent communications, they cannot be sure who is sending the message.

Sometimes, initialization data must be sent in the clear before encrypted communications can be established. All of this data must also be tied together at some point. After session keys have been established, one option is to send a hash of all the unauthenticated data sent so far using the newly established secure channel. If the hash doesn’t match what is expected, then the communicating parties can assume that an attacker, like Eve, has modified some of the initialization data.

In summary, when combining asymmetric and symmetric cryptography, don’t just think about the confidentiality part (encryption). Remember that knowing to whom you are speaking is just as important as, if not more important than, knowing that the communications between the two of you are unreadable to anyone else. You might not want the whole world to read your love poetry, but you definitely don’t want your amorous expressions to be received by the wrong person! Keep in mind that after establishing the other party’s identity, you must ensure that there is a chain of authenticity for all the remaining communications for the rest of the session. If the initial identity is proved with signatures and the remaining data is authenticated by MACs, ensure that there is no break in the chain as you switch from one to the other.

Common Problems

After seeing a bit about how asymmetric and symmetric keys work together, you might be tempted to create your own protocol. Definitely resist that urge. The goal of these exercises is to teach you the principles and to illuminate your understanding, but that alone is not sufficient to prepare you to develop cryptographic protocols. The history of cryptography is littered with protocols that were later found to be exploitable even though they were written by cryptographers with more experience than you or I have.

Let’s take the example we used with Alice sending the encrypted document to Bob. Did you notice that we broke one of our recommendations from previous chapters? Our data has no nonce! This means that Bob has no idea if the message from Alice is “fresh.” What if that data was recorded by Eve from a year ago and is just being replayed now?

Here’s another example. In our derivation of encryption keys, we only generated a single encryption key between both parties. This is only secure for one-way communication! If you want full-duplex communication (the ability to send data in both directions), you will need an encryption key for each direction!

But wait. Why can’t we use the same key to send data from Alice to Bob as we use to send data from Bob to Alice?

Do you remember what you learned about in Chapter 3? You do not reuse the same key and IV to encrypt two different messages! In full-duplex communication, that is exactly what you would be doing. Suppose that AEC-CTR mode is being used for the bulk data transport. If Alice uses a key to encrypt messages she sends to Bob, and Bob uses the same key to encrypt messages to Alice, both data streams could be XORed together to get the XOR of the plaintext messages! As we have seen, that is catastrophic. In fact, if Eve can trick Alice or Bob into encrypting data on her behalf (e.g., by planting “honeypot” data that will certainly be picked up and transmitted), she can XOR that data out leaving the other data as plaintext.

A naive key exchange using RSA encryption could be exploited using this very same principle. Suppose that Alice sends Bob an initial secret K encrypted under Bob’s public key. Alice and Bob correctly derive session keys and IVs for full-duplex communication from K. As an example, Bob has a key K_B,A that he uses to send encrypted messages to Alice, and Alice has a key K_A,B that she uses to send encrypted messages to Bob. (Bob uses K_A,B to decrypt Alice’s messages and Alice uses K_B,A to encrypt Bob’s messages.)

But suppose that Eve records all of these transmissions. Then, at a much later date, she replays the initial transmission of K to Bob. Bob doesn’t know that it’s a replay and he uses K to derive K_B,A. Now he starts sending data to Eve encrypted under this key.

While it’s true that Eve does not have K_B,A and cannot decrypt Bob’s messages directly, she does have the messages Bob sent to Alice under the same key from the earlier transmissions. Again, assuming that Alice and Bob use AES-CTR, the two transmission streams can be XORed together to potentially extract sensitive information. There are ways to solve this (e.g., by reintroducing challenge-response) but there are many ways it can go wrong even still.

It is very difficult to get all the parts of a cryptographic protocol right, even for the experts. In general, do not design your own protocols. Use existing protocols as much as possible and existing implementations whenever feasible. Above all, we want to remind you one more time, YANAC (You Are Not A Cryptographer... yet!).

An Unfortunate Example of Asymmetric and Symmetric Harmony

Most of our examples of cryptography are beneficial in some way, or are at least not inherently evil. Unfortunately, bad guys can use cryptography just as well as the good guys. And given that they can make a lot of money from evil, they can be highly motivated to produce creative, efficient uses of the technology.

One area where bad guys are incredibly good at using cryptography is ransomware. If you’ve been living in a cave in West Antarctica for the past decade and haven’t heard about ransomware, it’s basically software that encrypts your files and refuses to unlock them until you pay the extortionists behind it.

The cryptography behind early ransomware was simplistic and naive. The ransomware encrypted every file with a different AES key, but all of the AES keys were stored on the system in a file. The ransomware’s decryptor could easily find the keys and decrypt the file, but so could security researchers. If you don’t want somebody to unlock a file, it’s bad idea to leave the keys just lying around (under the doormat, so to speak).

Ransomware authors logically turned to asymmetric encryption as a solution. The immediately obvious advantage of asymmetric cryptography is that a public key could be on the victim’s system and a private key could be somewhere else. For all of the reasons you’ve seen in this chapter, the files themselves cannot be encrypted with RSA directly. RSA doesn’t even have the capacity to encrypt data larger than between 190 and 256 bytes, and if it did, it would be too slow. The user might notice their system getting locked down long before the encryption was complete.

Instead, the ransomware could encrypt all of the AES keys individually. After all, an AES key is just 16 bytes for AES-128 and 32 bytes for AES-256. Each key can be easily RSA encrypted before being stored on the victim’s system. RSA encrypts with the public key, so as long as the private key isn’t available to the victim, they won’t be able to decrypt the AES keys.

There are two naive variants of this approach, both of which are problematic. The first approach is to generate the key pair ahead of time and hard-code the public key into the malware itself. After the malware encrypts all the AES keys with the public key, a victim has to pay the ransom to have the private key sent to them for decryption. The obvious flaw in this design is that the same private key would unlock all of the systems attacked by the ransomware, as each copy of the malicious attack file had the same public key baked into it.

The second approach is for the ransomware to generate the RSA key pair on the victim’s system and transmit the private key to the command and control server. Now there is a unique public key encrypting the AES keys, and when the attacker releases the private key for decryption, it only unlocks the specific victim’s files. The problem here is that the system has to be online to get rid of the private key, and many network monitoring systems will detect transmissions to risky IPs where command and control servers often operate. Transmitting the private key might give away the ransomware before it has even started encrypting files on the system. It is stealthier to do everything locally until the system is fully locked.

Modern ransomware solves all of these problems with a pretty clever approach. First, the attacker generates a long-term asymmetric key pair. For our purposes, let’s just assume it is an RSA key pair, and we will call these keys the “permanent” asymmetric keys.

Next the attacker creates some malware and hard-codes the permanent public key into the malware. When the malware activates on a victim’s machine, the first thing that it does is generate a new asymmetric key pair. Again, for simplicity, let’s assume that it is an RSA key pair. We will call it the “local” key pair. It immediately encrypts the newly generated local private key by the attacker’s permanent public key embedded in the malware. The unencrypted local private key is deleted.

Now the malware begins to encrypt the files on the disk using AES-CTR or AES-CBC. Each file is encrypted under a different key, and then each key is encrypted by the local public key. The unencrypted version of the key is destroyed as soon as the file is finished being encrypted.

When the whole process is done, the victim’s files are encrypted by AES keys that are themselves encrypted by the local RSA public key. These AES keys could be decrypted by the local RSA private key, but that key is encrypted under the attacker’s permanent public key, and the private key is not on the computer.

Now the attacker contacts the victim and demands the ransom. If the victim agrees and pays the ransom (usually by way of Bitcoin), the attacker provides some kind of authentication code to the malware. The malware transmits the encrypted local private key to the attacker. Using his or her permanent private key, he or she decrypts the local private key and sends it back to the victim. Now all of the AES keys can be decrypted and the files subsequently decrypted.

What’s clever about this algorithm is that the attacker does not disclose his or her permanent private key. It remains private. A secondary private key is decrypted by the attacker for the victim to use in unlocking the rest of the system.

While you are hopefully not a malware/ransomware author, this section should also be helpful to you in thinking about how to encrypt “data at rest.” Much of what we talk about in this book is to protect “data in motion,” which is data traveling across a network or in some other way between two parties. The ransomware example illustrates protecting data that stays largely in place, typically to be encrypted and decrypted by the same party.

Utilities that encrypt files on disk have to deal with the wretched key management problem just like they do with data in motion. In general, there will have to be one key per file just like there has to be one key per network communications session; this prevents key reuse. The keys (and IVs) must be stored, or it must be possible to regenerate them. If they are stored, they must be encrypted by some kind of master key and stored along with additional metadata about the algorithm used and so forth. This information can be prepended to the beginning of the encrypted file, or it can be stored somewhere in a manifest.

If the keys are regenerated later, this is typically done by deriving the keys from a password, as we have already discussed in Chapter 2. As there needs to be a different key for each file, a random per-file salt is used in the derivation process to ensure that key’s uniqueness. The salt must be stored with the file, and the loss of the salt would result in a lost file that could never be decrypted.

This is the basic cryptographic concept behind securing data at rest, but production systems are usually far more complicated. NIST, for example, requires that compliant systems have a defined cryptographic key life cycle. This includes a pre-operational, operational, post-operational, and deletion stages as well as an operational “crypto” period for each key. This period is further broken down into an “originator usage period” (OUP) for when sensitive data can be generated and encrypted and a “recipient usage period” (RUP) for when this data can be decrypted and read. Key management systems are expected to handle key rollover (migrating encrypted data from one key to another), key revocation, and many other such functions.

We won’t bother you with another reference to YANAC... but by this point in the book, we hope your own subconscious is starting to do it for us!

That’s a Wrap

The main thrust of this chapter is that you can wrap up a temporary symmetric communication session within an initial asymmetric session establishment protocol. A lot of the world’s asymmetric infrastructure is focused on long-term identification of parties and that infrastructure is useful for establishing identities in some way and based on some model of trust. But once that trust is established, it’s more secure and more efficient to create a temporary symmetric key (well, actually several of them) to handle encrypting and MACing the data going forward.

We reviewed, for example, that you can transport a key from one party to another using RSA encryption. This approach was the primary approach used for a long time. Although still present in many systems, it is being retired for many reasons. More favored these days is using an ephemeral key agreement protocol, such as DH and ECDH (actually, DHE and ECDHE to be precise) to create a session key with perfect forward secrecy.

Either way, whether by key transport or key agreement, the parties can then derive the suite of keys necessary for communications. Or, a single party can derive the keys necessary for encrypting data on a hard drive. In both cases, the asymmetric operations are primarily used to establish identity and get an initial key, while the symmetric operations are used for the actual encryption of data.

If you can understand these principles, you can be conversant about most cryptography systems you’ll find.