When programmers choose a cryptographic security level (e.g. an RSA modulus size, or a Diffie-Hellman group), I often see an line of reasoning like this:

The best attack on 768-bit RSA costs 1 million USD. Our data isn’t that valuable, so we’re safe using 768-bit RSA.

It’s reasonable to weigh the costs of added security against its benefits, but this particular logic is flawed and usually leads to the wrong conclusion. There’s a lot going on here, so let’s unpack it piece by piece:

Our data isn’t that valuable

First, it’s important to consider – is this actually true? “Value” is a difficult concept. Most importantly, it’s subjective; a company’s data might be quite valuable to one attacker, but not at all valuable to another.

To measure how valuable some asset might be to an attacker, you need to consider all of the possible uses any possible attacker might find for the information. That’s a lot to consider. Suppose a company stores the last four credit card number digits for each user. It’s tempting to assume that information has very little value to an attacker, but in actual fact, this information can be used to launch social engineering attacks to gain access to the user’s other accounts. It can be quite difficult to determine with any sort of accuracy how much a company’s data might be worth if compromised.

So far, we’ve only considered perfectly rational attackers. Real-world attackers operate on emotions and intuition, and might have motivations other than financial gain. They might also operate on false information. Suppose you store 10,000 full credit card numbers. What if an attacker thinks that you store a million? They might be willing to perform an attack that uses 100x more resources than what would be considered “rational”. When the attack succeeds, they’ll be unhappy with the small database they do find – but they’re still going to take advantage of those 10,000 CCs.

That said, let’s assume you’re able to produce a reasonably accurate estimate, and you even add 50% as a margin of safety. This brings us to the next (more interesting) problem:

The best attack on 768-bit RSA costs 1 million USD.

I’m unsure of the exact cost ($1M may be too high; see, e.g., this paper from 2010) – but let’s assume this estimate is accurate. So, for data worth much less than $1 million, 768-bit RSA is a good choice, right? Surprisingly, the answer is “no”.

1 million USD is an estimate of the cost to crack one RSA key in isolation. In the real world, however, there isn’t just one RSA key. A real attacker sees many RSA keys spread across many targets. There’s no guarantee that cracking two RSA keys is twice as expensive as cracking one, and in general, there’s no guarantee that cracking N RSA keys is anywhere near N times the cost of cracking one. But one thing is sure: cracking multiple RSA keys at a time likely costs much less per key than cracking them individually – and the per-key cost might be the number that the attacker cares about.

How much more efficient is it to crack a batch of RSA keys at once? We don’t really know: the problem of cracking RSA keys in batches has not had much study (publicly – I’m sure the NSA and GCHQ take exception here). But let’s look at some similar examples that have been studied.

Attacking multiple AES keys

AES is the world’s most popular block cipher. One of the basic security principles of a block cipher is that, if an attacker has access to both a plaintext block and the corresponding ciphertext block, they should not be able to figure out the key (since that would compromise all of the other blocks). Of course, every block cipher is vulnerable to a brute-force attack. In a brute-force attack, the attacker tries encrypting the plaintext block with every possible key until they find the one that produces the correct ciphertext block. With AES-128 (which has a 128-bit key), there are 2128 possible keys, so we would expect this attack to succeed after at most 2128 tries.

Now, what if we have eight targets? If we can convince them all to encrypt the same plaintext block, we can crack all eight keys in one go. We use the same brute force technique, trying each of the 2128 possible keys and comparing the resulting ciphertext block to the blocks that we have recorded, keeping track of which keys succeed. Once we’re done, we’ll have cracked all eight keys after at most 2128 tries.

Fortunately, 2128 is a really big number, and it’s currently impossible for the combined resources of the human race to pull off this attack against AES. But still, there’s something alarming here: the second scenario cost about the same as the first, meaning that the second scenario’s per-key cost is reduced by about a factor of 8. And yes, this attack can also be used against 1000 targets, 1,000,000 targets, or more, with a similar reduction in per-key cost. Against a weaker block cipher, this attack can be a much more serious threat.

Attacking TLS/SSL Diffie-Hellman handshakes

Some great research from May 2015 surveyed a variety of problems with how Diffie-Hellman was used on the web. Of particular interest, it detailed how a well-funded attacker (e.g. the NSA) could crack the encryption keys of a large portion of the TLS (a.k.a. “SSL”) connections on the web at a reasonable cost.

Diffie-Hellman is a way for two parties to agree on an encryption key across the internet without revealing the key to anyone eavesdropping on the connection. In order to use Diffie-Hellman, the two parties choose a mathematical group in which to do their calculations. A group consists of a very large prime number, and a small number like 2. Usually, servers are configured to use one of the official “standard” groups.

For a long time, cryptographers and security experts have known that 1024-bit groups are too weak to be used safely. However, the cost of breaking 1024-bit Diffie-Hellman was estimated at 100 million - 1 billion USD, so many still felt safe using 1024-bit groups for TLS.

With that in mind, here’s how the attack works:

Since a few common groups were shared across hundreds of thousands of websites, the attacker could pay a one-time fee to decrypt millions of TLS connections – a massive reduction in the cost per key.

A better metric: marginal cost

I’ve brought up the idea of “cost per target” (“per target” means per key, per ciphertext, or whatever is applicable). Interestingly, this is still not quite the right metric to measure attack cost. Suppose there are two targets, one with (digital) assets worth $10 million, and another with assets worth $100k. Suppose an attack on one of the targets would cost $1 million, while an attack on both targets would cost $1.01 million. Attacking the larger target by itself is clearly profitable ($10M - $1M = $9M profit). Attacking both targets is even more profitable ($10M + $100k - $1.01M = $9.09M profit). This is surprising though: even with a per-target cost of $505k, it’s still profitable to attack a target worth only $100k!

Cost per target is an interesting metric, but not actually the one we want. What we want is the marginal cost. The marginal cost asks the question “Suppose someone is performing an attack; how much extra would it cost to include us in the attack?” In the previous example, the marginal cost is $1.01M - $1M = $10k, a small amount compared to the value of the assets at stake ($100k).

A better approach

So what are these dollar numbers that we see quoted so often for RSA and other cryptosystems? They’re clearly not the marginal cost.

Cryptographers, for the most part, actually don’t study marginal cost. Instead, they evaluate the strength of a cryptosystem based on a different metric: minimum cost for first security failure. They measure the minimum resources needed before it is possible to produce any kind of break in a system’s security. With this metric, we get a very straightforward way of showing that something is secure: if producing any security failure at all requires more resources than are available to the entire human race, it’s safe to conclude that the cryptosystem is secure – against human attackers, anyway.

This is actually a much better approach to security:

When the paper about breaking 1024-bit Diffie-Hellman groups first came out, many came to the conclusion that standardized groups were a bad idea, and that individual websites should generate their own unique Diffie-Hellman group. I think this is misguided. Although this seems to raise the marginal cost, it doesn’t fix the fact that the minimum cost for first security failure for 1024-bit Diffie-Hellman is too low. A better solution is to upgrade to a 2048-bit Diffie-Hellman group, where the minimum cost for first security failure exceeds the capabilities of the human race. With 2048-bit DH (and above), the marginal cost becomes irrelevant, making it safe (and recommended) to use the standardized groups.

Takeaways

When deciding on a security level (key size or otherwise) for a cryptosystem, there are essentially two approaches. One is to set the security level so that the marginal cost of attack is always larger than the value an attacker could receive from the attack. The other is to set the security level so that attacks are impossible, given the limited resources of the human race.

I recommend using the second approach whenever possible, as it is more likely to result in a secure system. However, sometimes it may be necessary to use the marginal cost approach due to constraints (such as performance). In that case, be aware that: