3
CRYPTOGRAPHIC SECURITY

Cryptographic definitions of security are not the same as those that apply to general computer security. The main difference between software security and cryptographic security is that the latter can be quantified. Unlike in the software world, where applications are usually seen as either secure or insecure, in the cryptographic world it’s often possible to calculate the amount of effort required to break a cryptographic algorithm. Also, whereas software security focuses on preventing attackers from abusing a program’s code, the goal of cryptographic security is to make well-defined problems impossible to solve.

Cryptographic problems involve mathematical notions, but not complex math—or at least not in this book. This chapter walks you through some of these security notions and how they’re applied to solve real-world problems. In the following sections, I discuss how to quantify crypto security in ways that are both theoretically sound and practically relevant. I discuss the notions of informational versus computational security, bit security versus full attack cost, provable versus heuristic security, and symmetric versus asymmetric key generation. I conclude the chapter with actual examples of failures in seemingly strong cryptography.

Defining the Impossible

In Chapter 1, I described a cipher’s security relative to an attacker’s capabilities and goals, and deemed a cipher secure if it was impossible to reach these goals given an attacker’s known capabilities. But what does impossible mean in this context?

Two notions define the concept of impossible in cryptography: informational security and computational security. Roughly speaking, informational security is about theoretical impossibility whereas computational security is about practical impossibility. Informational security doesn’t quantify security because it views a cipher as either secure or insecure, with no middle ground; it’s therefore useless in practice, although it plays an important role in theoretical cryptography. Computational security is the more relevant and practical measure of the strength of a cipher.

Security in Theory: Informational Security

Informational security is based not on how hard it is to break a cipher, but whether it’s conceivable to break it at all. A cipher is informationally secure only if, even given unlimited computation time and memory, it cannot be broken. Even if a successful attack on a cipher would take trillions of years, such a cipher is informationally insecure.

For example, the one-time pad introduced in Chapter 1 is informationally secure. Recall that the one-time pad encrypts a plaintext, P, to a ciphertext, C = P ⊕ K, where K is a random bit string that is unique to each plaintext. The cipher is informationally secure because given a ciphertext and unlimited time to try all possible keys, K, and compute the corresponding plaintext, P, you would still be unable to identify the right K because there are as many possible Ps as there are Ks.

Security in Practice: Computational Security

Unlike informational security, computational security views a cipher as secure if it cannot be broken within a reasonable amount of time, and with reasonable resources such as memory, hardware, budget, energy, and so on. Computational security is a way to quantify the security of a cipher or any crypto algorithm.

For example, consider a cipher, E, for which you know a plaintext–ciphertext pair (P, C) but not the 128-bit key, K, that served to compute C = E(K, P). This cipher is not informationally secure because you could break it after trying the 2¹²⁸ possible 128-bit Ks until you find the one that satisfies E(K, P) = C. But in practice, even testing 100 billion keys per second, it would take more than 100,000,000,000,000,000,000 years. In other words, reasonably speaking, this cipher is computationally secure because it’s practically impossible to break.

Computational security is sometimes expressed in terms of two values:

• t, which is a limit on the number of operations that an attacker will carry out
• ε (called “epsilon”), which is a limit on the probability of success of an attack

We then say that a cryptographic scheme is (t, ε)-secure if an attacker performing at most t operations—whatever those operations are—has a probability of success that is no higher than ε, where ε is at least 0 and at most 1. Computational security gives a limit on how hard it is to break a cryptographic algorithm.

Here it’s important to know that t and ε are just limits: if a cipher is (t, ε)-secure, then no attacker performing fewer than t operations will succeed (with probability ε). But that doesn’t imply that an attacker doing exactly t operations will succeed, and it doesn’t tell you how many operations are needed, which may be much larger than t. We say that t is a lower bound on the computation effort needed, because you’d need at least t operations to compromise security.

We sometimes know precisely how much effort it takes to break a cipher; in such cases we say that a (t, ε)-security gives us a tight bound when an attack exists that breaks the cipher with probability ε and exactly t operations.

For example, consider a symmetric cipher with a 128-bit key. Ideally, this cipher should be (t, t/2¹²⁸)-secure for any value of t between 1 and 2¹²⁸. The best attack should be brute force (trying all keys until you find the correct one). Any better attack would have to exploit some imperfection in the cipher, so we strive to create ciphers where brute force is the best possible attack.

Given the statement (t, t/2¹²⁸)-secure, let’s examine the probability of success of three possible attacks:

• In the first case, t = 1, an attacker tries one key and succeeds with a probability of ε = 1/2¹²⁸.
• In the second case, t = 2¹²⁸, an attacker tries all 2¹²⁸ keys and one succeeds. Thus, the probability ε = 1 (if the attacker tries all keys, obviously the right one must be one of them).
• In the third case, an attacker tries only t = 2⁶⁴ keys, and succeeds with a probability of ε = 2⁶⁴/2¹²⁸ = 2⁻⁶⁴. When an attacker only tries a fraction of all keys, the success probability is proportional to the number of keys tried.

We can conclude that a cipher with a key of n bits is at best (t, t/2ⁿ)-secure, for any t between 1 and 2ⁿ, because no matter how strong the cipher, a brute-force attack against it will always succeed. The key thus needs be long enough to blunt brute-force attacks in practice.

Quantifying Security

When an attack is found, the first thing you want to know is how efficient it is in theory, and how practical it is, if at all. Likewise, given a cipher that’s allegedly secure, you want to know what amount of work it can withstand. To address those questions, I’ll explain how cryptographic security can be measured in bits (the theoretical view) and what factors affect the actual cost of an attack.

Measuring Security in Bits

When speaking of computational security, we say that a cipher is t-secure when a successful attack needs at least t operations. We thus avoid the unintuitive (t, ε) notation by assuming a success probability of ε close to 1, or what we care about in practice. We then express security in bits, where “n-bit security” means that about 2_N operations are needed to compromise some particular security notion.

If you know approximately how many operations it takes to break a cipher, you can determine its security level in bits by taking the binary logarithm of the number of operations: if it takes 1000000 operations, the security level is log₂(1000000), or about 20 bits (that is, 1000000 is approximately equal to 2²⁰). Recall that an n-bit key will give at most n-bit security because a brute-force attack with all 2ⁿ possible keys will always succeed. But the key size doesn’t always match the security level—it just gives an upper bound, or the highest possible security level.

A security level may be smaller than the key size for one of two reasons:

• An attack broke the cipher in fewer operations than expected—for example, using a method that recovers the key by trying not all 2ⁿ keys, but only a subset of those.
• The cipher’s security level intentionally differs from its key size, as with most public key algorithms. For example, the RSA algorithm with a 2048-bit secret key provides less than 100-bit security.

Bit security proves useful when comparing ciphers’ security levels but doesn’t provide enough information on the actual cost of an attack. It is sometimes too simple an abstraction because it just assumes that an n-bit-secure cipher takes 2ⁿ operations to break, whatever these operations are. Two ciphers with the same bit security level can therefore have vastly different real-world security levels when you factor in the actual cost of an attack to a real attacker.

Say we have two ciphers, each with a 128-bit key and 128-bit security. Each must be evaluated 2¹²⁸ times in order to be broken, except that the second cipher is 100 times slower than the first. Evaluating the second cipher 2¹²⁸ times thus takes the same time as 100 × 2¹²⁸ ≈ 2^134.64 evaluations of the first. If we count in terms of the first, fast cipher, then breaking the slower one takes 2^134.64 operations. If we count in terms of the second, slow cipher, it only takes 2¹²⁸ operations. Should we then say that the second cipher is stronger than the first? In principle, yes, but we rarely see such a hundred-fold performance difference between commonly used ciphers.

The inconsistent definition of an operation raises more difficulties when comparing the efficiency of attacks. Some attacks claim to reduce a cipher’s security because they perform 2¹²⁰ evaluations of some operation rather than 2¹²⁸ evaluations of the cipher, but the speed of each type of attack is left out of the analysis. The 2¹²⁰-operation attack won’t always be faster than a 2¹²⁸ brute-force attack.

Nevertheless, bit security remains a useful notion as long as the operation is reasonably defined—meaning about as fast as an evaluation of the cipher. After all, in real life, all it takes to determine whether a security level is sufficient is an order of magnitude.

Full Attack Cost

Bit security expresses the cost of the fastest attack against a cipher by estimating the order of magnitude of the number of operations it needs to succeed. But other factors affect the cost of an attack, and these must be taken into account when estimating the actual security level. I’ll explain the four main ones: parallelism, memory, precomputation, and the number of targets.

Parallelism

The first factor to consider is computational parallelism. For example, consider two attacks of 2⁵⁶ operations each. The difference between the two is that the second attack can be parallelized but not the first: the first attack performs 2⁵⁶ sequentially dependent operations, such as x_{i + 1} = f_i(x_i) for some x₀ and some functions f_i (with i from 1 to 2⁵⁶), whereas the second performs 2⁵⁶ independent operations, such as x_i = f_i(x) for some x and i from 1 to 2⁵⁶, which can be executed in parallel. Parallel processing can be orders of magnitude faster than sequential processing. For example, if you had 2¹⁶ = 65536 processors available, you could divide the workload of the parallel attacks into 2¹⁶ independent tasks, each performing 2⁵⁶ / 2¹⁶ = 2⁴⁰ operations. The first attack, however, cannot benefit from having multiple cores available because each operation relies on the previous operation’s result. Therefore, the parallel attack will complete 65536 times faster than the sequential one, even though they perform the same number of operations.

Memory

The second factor when determining the cost of an attack is memory. Cryptanalytic attacks should be evaluated with respect to their use of time and space: how many operations do they perform over time, how much memory or space do they consume, how do they use the space they consume, and what’s the speed of the available memory? Unfortunately, bit security is concerned only with the time it takes to perform an attack.

Concerning the way space is used, it’s important to consider how many memory lookups are required as part of an attack, the speed of memory accesses (which may differ between reads and writes), the size of the data accessed, the access pattern (contiguous or random memory addresses), and how data is structured in memory. For example, on one of today’s general-purpose CPUs, reading from a register takes one cycle, whereas reading from the CPU’s cache memory takes around 20 cycles (for the L3 cache), and reading from DRAM usually takes at least 100 cycles. A factor of 100 can make the difference between one day and three months.

Precomputation

Precomputation operations are those that need to be performed only once and can be reused over subsequent executions of the attack. Precomputation is sometimes called the offline stage of an attack.

For example, consider the time-memory trade-off attack. When performing this kind of attack, the attacker performs one huge computation that produces large lookup tables that are then stored and reused to perform the actual attack. For example, one attack on 2G mobile encryption took two months to build two terabytes’ worth of tables, which were then used to break the encryption in 2G and recover a secret session key in only a few seconds.

Number of Targets

Finally, we come to the number of targets of the attack. The greater the number of targets, the greater the attack surface, and the more attackers can learn about the keys they’re after.

For example, consider a brute-force key search: if you target a single n-bit key, it will take 2ⁿ attempts to find the correct key with certainty. But if you target multiple n-bit keys—say, a number M—and if for a single P you have M distinct ciphertexts, where C = E(K, P) for each of the M keys (K) that you’re after, it will again take 2ⁿ attempts to find each key. But if you’re only interested in at least one of the M keys and not in every one, it would take on average 2ⁿ / M attempts to succeed. For example, to break one 128-bit key of 2¹⁶ = 65536 target keys, it will take on average 2^{128 − 16} = 2¹¹² evaluations of the cipher. That is, the cost (and speed) of the attack decreases as the number of targets increases.

Choosing and Evaluating Security Levels

Choosing a security level often involves selecting between 128-bit and 256-bit security because most standard crypto algorithms and implementations are available in one of these two security levels. Below 128 bits you’ll find schemes with 64- or 80-bit security, but these are generally not secure enough for real-world use.

At a high level, 128-bit security means that you’d need to carry out approximately 2¹²⁸ operations to break that crypto system. To give you a sense of what this number means, consider the fact that the universe is approximately 2⁸⁸ nanoseconds old (there’s a billion nanoseconds in a second). Since testing a key with today’s technology takes no less than a nanosecond, you’d need several times the age of the universe for an attack to succeed (2⁴⁰ times to be precise) if it takes exactly one nanosecond to test a key.

But can’t parallelism and multiple targets dramatically reduce the time it takes to complete a successful attack? Not exactly. Say you’re interested in breaking any of a million targets, and that you have a million parallel cores available. That brings the search time down from 2¹²⁸ to (2¹²⁸ / 2²⁰) / 2²⁰ = 2⁸⁸, which is equivalent to only one universe lifetime.

Another thing to consider when evaluating security levels is the evolution of technology. Moore’s law posits that computing efficiency doubles roughly every two years. We can think of this as a loss of one bit of security every two years: if today a $1000 budget allows you to break, say, a 40-bit key in one hour, then Moore’s law says that two years later, you could break a 41-bit key in one hour for the same $1000 budget (I’m simplifying). We can extrapolate from this to say that, according to Moore’s law, we’ll have 40 fewer bits of security in 80 years compared to today. In other words, in 80 years doing 2¹²⁸ operations may cost as much as doing 2⁸⁸ operations today. Accounting for parallelism and multiple targets, as discussed earlier, we’re down to 2⁴⁸ nanoseconds of computation, or about three days. But this extrapolation is highly inaccurate, because Moore’s law won’t and can’t scale that much. Still, you get the idea: what looks infeasible today may be realistic in a century.

There will be times when a security level lower than 128 bits is justified. For example, when you need security for only a short time period and when the costs of implementing a higher security level will negatively impact the cost or usability of a system. A real-world example is that of pay TV systems, wherein encryption keys are either 48 or 64 bits. This sounds ridiculously low, but that’s a sufficient security level because the key is refreshed every 5 or 10 seconds.

Nevertheless, to ensure long-term security, you should choose 256-bit security or a bit less. Even in a worst-case scenario—the existence of quantum computers, see Chapter 14—a 256-bit secure scheme is unlikely to be broken in the foreseeable future. More than 256 bits of security is practically unnecessary, except as a marketing device.

As NIST cryptographer John Kelsey once put it, “The difference between 80 bits and 128 bits of key search is like the difference between a mission to Mars and a mission to Alpha Centauri. As far as I can see, there is no meaningful difference between 192-bit and 256-bit keys in terms of practical brute-force attacks; impossible is impossible.”

Achieving Security

Once you’ve chosen a security level, it’s important to guarantee that your cryptographic schemes will stick to it. In other words, you want confidence, not just hope and uncertainty, that things will work as planned, all the time.

When building confidence in the security of a crypto algorithm, you can rely on mathematical proofs, an approach called provable security, or on evidence of failed attempts to break the algorithm, which I’ll call heuristic security (though it’s sometimes called probable security). These two approaches are complementary and neither is better than the other, as you’ll see.

Provable Security

Provable security is about proving that breaking your crypto scheme is at least as hard as solving another problem known to be hard. Such a security proof guarantees that the crypto remains safe as long as the hard problem remains hard. This type of proof is called a reduction, and it comes from the field of complexity theory. We say that breaking some cipher is reducible to problem X if any method to solve problem X also yields a method to break the cipher.

Security proofs come in two flavors, depending on the type of presumably hard problem used: proofs relative to a mathematical problem and proofs relative to a cryptographic problem.

Proofs Relative to a Mathematical Problem

Many security proofs (such as those for public-key crypto) show that breaking a crypto scheme is at least as hard as solving some hard mathematical problem. We’re talking of problems for which a solution is known to exist, and is easy to verify once it’s known, but is computationally hard to find.

For example, consider the challenge of solving the factoring problem, which is the best-known math problem in crypto: given a number that you know is the product of two prime numbers (n = pq), find the said primes. For example, if n = 15, the answer is 3 and 5. That’s easy for a small number, but it becomes exponentially harder as the size of the number grows. For example, if a number, n, is 3000 bits long (about 900 decimal digits) or more, factoring is believed to be practically infeasible.

RSA is the most famous crypto scheme to rely on the factoring problem: RSA encrypts a plaintext, P, seen as a large number, by computing C = P^e mod n, where the number e and n = pq are the public key. Decryption recovers a plaintext from a ciphertext by computing P = C^d mod n, where d is the private key associated to e and n. If we can factor n, then we can break RSA (by recovering the private key from the public key), and if we can obtain the private key, then we can factor n; in other words, recovering an RSA private key and factoring n are equivalently hard problems. That’s the kind of reduction we’re looking for in provable security. However, there is no guarantee that recovering an RSA plaintext is as hard as factoring n, since the knowledge of a plaintext doesn’t reveal the private key.

Proofs Relative to Another Crypto Problem

Instead of comparing a crypto scheme to a math problem, you can compare it to another crypto scheme and prove that you can only break the second if you can break the first. Security proofs for symmetric ciphers usually follow this approach.

For example, if all you have is a single permutation algorithm, then you can build symmetric ciphers, random bit generators, and other crypto objects such as hash functions by combining calls to the permutations with various types of inputs (as you’ll see in Chapter 6). Proofs then show that the newly created schemes are secure if the permutation is secure. In other words, we know for sure that the newly created algorithm is not weaker than the original one. Such proofs usually work by crafting an attack on the smaller component given an attack on the larger one—that is, by showing a reduction.

When you’re proving that a crypto algorithm is no weaker than another, the main benefit is that of a reduced attack surface: instead of analyzing both the core algorithm and the combination, you can simply look at the new cipher’s core algorithm. Specifically, if you write a cipher that uses a newly developed permutation and a new combination, you may prove that the combination doesn’t weaken security compared to the core algorithm. Therefore, to break the combination, you need to break the new permutation.

Caveats

Cryptography researchers rely heavily on security proofs, whether with respect to math problem schemes or to other crypto schemes. But the existence of a security proof does not guarantee that a cryptographic scheme is perfect, nor is it an excuse for neglecting the more practical aspects of implementation. After all, as cryptographer Lars Knudsen once said, “If it’s provably secure, it’s probably not,” meaning that a security proof shouldn’t be taken as an absolute guarantee of security. Worse, there are multiple reasons why a “provably secure” scheme may lead to a security failure.

One issue is with the phrase “proof of security” itself. In mathematics, a proof is the demonstration of an absolute truth, but in crypto, a proof is only the demonstration of a relative truth. For example, a proof that your cipher is as hard to break as it is to compute discrete logarithms—finding the number x given g and g^x mod n—guarantees that if your cipher fails, a whole lot of other ciphers will fail as well, and nobody will blame you if the worst happens.

Another caveat is that security proofs are usually proven with respect to a single notion of security. For example, you might prove that recovering the private key of a cipher is as hard as the factoring problem. But if you can recover plaintexts from ciphertext without the key, you’ll bypass the proof, and recovering the key hardly matters.

Then again, proofs are not always correct, and it may be easier to break an algorithm than originally thought.

Another important consideration is that hard math problems sometimes turn out to be easier to solve than expected. For example, certain weak parameters make breaking RSA easy. Or the math problem may be hard in certain cases, but not on average, as often happens when the reference problem is new and not well understood. That’s what happened when the 1978 knapsack encryption scheme by Merkle and Hellman was later totally broken using lattice reduction techniques.

Finally, although the proof of an algorithm’s security may be fine, the implementation of the algorithm can be weak. For example, attackers may exploit side-channel information such as power consumption or execution time to learn about an algorithm’s internal operations in order to break it, thus bypassing the proof. Or implementers may misuse the crypto scheme: if the algorithm is too complicated with too many knobs to configure, chances are higher that the user or developer will get a configuration wrong, which may render the algorithm completely insecure.

Heuristic Security

Provable security is a great tool to gain confidence in a crypto scheme, but it doesn’t apply to all kinds of algorithms. In fact, most symmetric ciphers don’t have a security proof. For example, every day we rely on the Advanced Encryption Standard (AES) to securely communicate using our mobile phones, laptops, and desktop computers, but AES is not provably secure; there’s no proof that it’s as hard to break as some well-known problem. AES can’t be related to a math problem or to another algorithm because it is the hard problem itself.

In cases where provable security doesn’t apply, the only reason to trust a cipher is because many skilled people tried to break it and failed. This is sometimes called heuristic security.

When can we be sure that a cipher is secure then? We can never be sure, but we can be pretty confident that an algorithm won’t be broken when hundreds of experienced cryptanalysts have each spent hundreds of hours trying to break it and published their findings—usually by attempting attacks on simplified versions of a cipher (often versions with fewer operations, or fewer rounds, which are short series of operations that ciphers iterate in order to mix bits together).

When analyzing a new cipher, cryptanalysts first try to break one round, then two, three, or as many as they can. The security margin is then the difference between the total number of rounds and the number of rounds that were successfully attacked. When after years of study a cipher’s security margin is still high, we become confident that it’s (probably) secure.

Generating Keys

If you plan to encrypt something, you’ll have to generate keys, whether they are temporary “session keys” (like the ones generated when browsing an HTTPS site) or long-term public keys. Recall from Chapter 2 that secret keys are the crux of cryptographic security and should be randomly generated so that they are unpredictable and secret.

For example, when you browse an HTTPS website, your browser receives the site’s public key and uses it to establish a symmetric key that’s only valid for the current session, and that site’s public key and its associated private key may be valid for years. Therefore, it’d better be hard to find for an attacker. But generating a secret key isn’t always as simple as dumping enough pseudo­random bits. Cryptographic keys may be generated in one of three ways:

• Randomly, using a pseudorandom number generator (PRNG) and, when needed, a key-generation algorithm
• From a password, using a key derivation function (KDF), which transforms the user-supplied password into a key
• Through a key agreement protocol, which is a series of message exchanges between two or more parties that ends with the establishment of a shared key

For now, I’ll explain the simplest method: randomized generation.

Generating Symmetric Keys

Symmetric keys are secret keys shared by two parties, and they are the simplest to generate. They are usually the same length as the security level they provide: a 128-bit key provides 128-bit security, and any of the 2¹²⁸ possible keys is a valid one that can do the job as well as any other key.

To generate a symmetric key of n bits using a cryptographic PRNG, you simply ask it for n pseudorandom bits and use those bits as the key. That’s it. You can, for example, use the OpenSSL toolkit to generate a random symmetric key by dumping pseudorandom bytes, as in the following command (obviously, your result will differ from mine):

$ openssl rand 16 -hex
65a4400ea649d282b855bd2e246812c6

Generating Asymmetric Keys

Unlike symmetric keys, asymmetric keys are usually longer than the security level they provide. But that’s not the main problem. Asymmetric keys are trickier to generate than symmetric ones because you can’t just dump n bits from your PRNG and get away with the result. Asymmetric keys aren’t just raw bit sequences; instead, they represent a specific type of object, such as a large number with specific properties (in RSA, a product of two primes). A random bit string value (and thus a random number) is unlikely to have the specific properties needed, and therefore won’t be a valid key.

To generate an asymmetric key, you send pseudorandom bits as a seed to a key-generation algorithm. This key-generation algorithm takes as input a seed value that’s at least as long as the intended security level and then constructs from it a private key and its respective public key, ensuring that both satisfy all the necessary criteria. For example, a naive key-generation algorithm for RSA would generate a number, n = pq, by using an algorithm to generate two random primes of about the same length. That algorithm would pick random numbers until one happens to be prime—so you’d also need an algorithm to test whether a number is prime.

To save yourself the burden of manually implementing the key-generation algorithm, you can use OpenSSL to generate a 4096-bit RSA private key, like this:

$ openssl genrsa 4096
Generating RSA private key, 4096 bit long modulus
..............................................................................
...............................++
...............................................++
e is 65537 (0x10001)
-----BEGIN RSA PRIVATE KEY-----
MIIJKQIBAAKCAgEA3Qgm6OjMy61YVstaGawk22A9LyMXhiQUU4N8F5QZXEef2Pjq
vTtAIA1hzpK2AJsv16INpNkYcTjNmechAJ0xHraftO6cp2pZFP85dvknsMfUoe8u
btKXZiYvJwpS0fQQ4tzlDtH45Gj8sMHcwFxTO3HSIx0XV0owfJTLMzZbSE3TDlN+
JdW8d9Xd5UVB+o9gUCI8tSfnOjF2dHlLNiOhlfT4w0Rf+G35USIyUJZtOQ0Dh8M+
--snip--
zO/dbYtqRkMT8Ubb/0Q1IW0q8e0WnFetzkwPzAIjwZGXT0kWJu3RYj1OXbTYDr2c
xBRVC/ujoDL6O3NaqPxkWY5HJVmkyKIE5pC04RFNyaQ8+o4APyobabPMylQq5Vo5
N5L2c4mhy1/OH8fvKBRDuvCk2oZinjdoKUo8ZA5DOa4pdvIQfR+b4/4Jjsx4
-----END RSA PRIVATE KEY-----

Notice that the key comes in a specific format—namely, base64-encoded data between the BEGIN RSA PRIVATE KEY and END RSA PRIVATE KEY markers. That’s a standard encoding format supported by most systems, which then convert this representation to raw bytes of data. The dot sequences at the beginning are a kind of progress bar, and e is 65537 (0x10001) indicates the parameter to use when encrypting (remember that RSA encrypts by computing C = P^e mod n).

Protecting Keys

Once you have a secret key, you need to keep it secret, yet available when you need it. There are three ways to address this problem.

Key wrapping (encrypting the key using a second key)
The problem with this approach is that the second key must be available when you need to decrypt the protected key. In practice, this second key is often generated from a password supplied by the user when he needs to use the protected key. That’s how private keys for the Secure Shell (SSH) protocol are usually protected.

On-the-fly generation from a password
Here, no encrypted file needs to be stored because the key comes straight out from the password. Modern systems like miniLock use this method. Although this method is more direct than key wrapping, it’s less widespread, in part because it’s more vulnerable to weak passwords. Say, for example, that an attacker captured some encrypted message: if key wrapping was used, the attacker first needs to get the protected key file, which is usually stored locally on the user’s file system and therefore not easy to access. But if on-the-fly generation was used, the attacker can directly search for the correct password by attempting to decrypt the encrypted message with candidate passwords. And if the password is weak, the key is compromised.

Storing the key on a hardware token (smart card or USB dongle)
In this approach, the key is stored in secure memory and remains safe even if the computer is compromised. This is the safest approach to key storage, but also the costliest and least convenient because it requires you to carry the hardware token with you and run the risk of losing it. Smart cards and USB dongles usually require you to enter a password to unlock the key from the secure memory.

To test key wrapping, run the OpenSSL command shown here with the argument -aes128 to tell OpenSSL to encrypt the key with the cipher AES-128 (AES with a 128-bit key):

$ openssl genrsa -aes128 4096
Generating RSA private key, 4096 bit long modulus
..........++
.............................................................................................................................++
e is 65537 (0x10001)
Enter pass phrase:

The passphrase requested will be used to encrypt the newly created key.

How Things Can Go Wrong

Cryptographic security can go wrong in many ways. The biggest risk is when we have a false sense of security thanks to security proofs or to well-studied protocols, as illustrated by the following two examples.

Incorrect Security Proof

Even proofs of security by renowned researchers may be wrong. One of the most striking examples of a proof gone terribly wrong is that of Optimal Asymmetric Encryption Padding (OAEP), a method of secure encryption that used RSA and was implemented in many applications. Yet, an incorrect proof of OAEP’s security against chosen-ciphertext attackers was accepted as valid for seven years, until a researcher found the flaw in 2001. Not only was the proof wrong, the result was wrong as well. A new proof later showed that OAEP is only almost secure against chosen-ciphertext attackers. We now have to trust the new proof and hope that it’s flawless. (For further details, see the 2001 paper “OAEP Reconsidered” by Victor Shoup.)

Short Keys for Legacy Support

In 2015, researchers found that some HTTPS sites and SSH servers supported public-key cryptography with shorter keys than expected: namely, 512 bits instead of at least 2048 bits. Remember, with public-key schemes, the security level isn’t equal to the key size, and in the case of HTTPS, keys of 512 bits offer a security level of approximately 60 bits. These keys could be broken after only about two weeks of computation using a cluster of 72 processors. Many websites were affected, including the FBI’s. Although the software was ultimately fixed (thanks to patches for OpenSSL and for other software), the problem was quite an unpleasant surprise.

Further Reading

To learn more about provable security for symmetric ciphers, read the sponge functions documentation (http://sponge.noekeon.org/). Sponge functions introduced the permutation-based approach in symmetric crypto, which describes how to construct a bunch of different cryptographic functions using only one permutation.

Some must-reads on the real cost of attacks include Bernstein’s 2005 paper “Understanding Brute Force” and Wiener’s 2004 paper “The Full Cost of Cryptanalytic Attacks,” both available online for free.

To determine the security level for a given key size, visit http://www.keylength.com/. This site also offers an explanation on how private keys are protected in common cryptographic utilities, such as SSH, OpenSSL, GnuPG, and so on.

Finally, as an exercise, pick an application (such as a secure messaging application) and identify its crypto schemes, key length, and respective security levels. You’ll often find surprising inconsistencies, such as a first scheme providing a 256-bit security level but a second scheme providing only 100-bit security. The security of the whole system is often only as strong as that of its weakest component.