Overkill in cryptography

This morning, I did a training on Corporate Social Responsibility. One of the most important impacts on the environment of our company is energy use. And there are lots of ways to reduce energy use, some are quite simple and effective.

Watching the training I could not stop thinking of energy wasting practices in my area of expertise: cryptography. It it is not getting better; quite the contrary, in fact. Let me show a few ways in which cryptography is very wasteful, but before I do that, let’s help your intuition a bit.

Bits of security versus money and energy needed to brute force. For ECC and hash functions, double the first column

Arjen Lenstra was so friendly to convert several levels of security into energy use, which was an important source for this article. The $30 figure comes from crack.sh, which breaks DES for $30 per key. The money amounts of a million, billion and trillion are mine. Note that all these numbers are inaccurate; you use more that $30 of electricity per year, probably.

Things to note from this picture:

• Keys longer than 128 bits make no sense at all. Keys over 100 bits can be considered “unbreakable” against any attack, even state actors. If the NSA builds a Dyson sphere around the sun, you may want to use a few bits more.
• Not shown are hash functions and elliptic curve security strength. As a rule of thumb, you can double the “bits of security” for these. This means SHA256 is secure enough, as is Curve25519.
• Keys of 90 bits are enough for personal and small business applications, since it is just not worth breaking them.
• PIN security is much stronger than expected; this is because of additional security measures around PIN entry.
• The RSA numbers in this picture are probably too low. Otherwise the 862 bit RSA challenge would have been broken already by now.
• Moore’s law moves the “bits of security” points slowly down relative to the cost and energy numbers. This corresponds to about one bit every 1½ to 2 year.

How secure should my cryptosystem be?

If you are the user or designer of a cryptosystem, there are a few factors to take into account. Of the factors shown here, the first two argue to use less bits of security, while the last one argues to use more.

• Cost of implementing the system, which should be affordable.
• Environmental impact (energy use, pollution, etc.).
• Cost of attacking the system, which should be more than the expected “benefits” for the attacker.
• Compliancy with regulations.

I am talking about the entire cryptosystem, including the encryption method used inside this system. As I will show below, in most systems the encryption method is not the weak point.

Reasons for choosing longer keys

When studying cryptographic methods that are used in practice, I noticed a trend to use overly long keys. For example, nobody dares to use an RSA 1024 bit key for anything. Still, I would be happy to use RSA-1024 for protecting all my possessions, since I do not own anything that is worth so much that an attacker would be interested.

There are several reasons to choose a cryptographic method that is stronger than needed:

• For long term security, you have to take into account that systems with short keys will be broken. Since the GNFS factoring method was invented around 2000, many people were afraid this would happen to RSA. That’s why RSA is perceived to be weaker that it is in practice. But RSA-1024 still is not broken, even though GNFS has been improving steadily since then.
• Using a stronger encryption method is cheap. Using AES-256 is almost the same as using AES-128, except your key is 32 bytes instead of 16 bytes, and computation is 40% more work. But as you can see in the picture, you do not gain any extra security. By the way, using very long RSA keys is not that cheap; 3000 bits RSA is about 25 times as much work as 1000 bits.
• Compliancy rules force parties to choose encryption methods. For example, ETSI TS 119 312 and the SOG-IS Agreed Cryptographic Mechanisms specify that we must use at least 3000 bits RSA.
• Marketing. Every since DES was replaced by triple DES (with twice the key length) there is a feeling that key sizes need to be doubled for extra security.
• Related to that point: perceived security (because people don’t want to use a system they don’t trust).

Note that even though these are valid reasons for choosing a long key, there is no use to choose key lengths that fall of the scale of the picture. No attacker, whatever their capacity, is going to break 2048 bits RSA or AES-128; there aren’t enough resources on earth to do this.

But I heard that <some reference> is broken recently!

Yes, cryptosystems get broken. But believe me, this is not because the encryption system inside is broken. The only exceptions to this rule is if the encryption system is used in the wrong way. That’s why cryptography is so hard.

If you really look into the details of an attacked system, you’ll find that the attack used well know weak points that are not cryptography:

• Human mistakes, where users of the system don’t understand the result of their actions
• Social engineering, where users of the system are manipulated by attackers
• Design flaws in the system
• Attacks on the operating system or software application

I don’t thinks references are needed here, there are plenty of examples of each of these.

Bad reasons for choosing long keys

The reasons for choosing longer keys that I listed above are not always good reasons, but there are also really bad reasons for choosing long keys. Here a few.

• Homebrew encryption. Some parties invent their own encryption system that uses very long keys. You can safely assume these are not secure, or at least not more secure than a well designed system with short keys.
• Misunderstanding systems. For example, HMAC is a “Message Authentication Code” that uses an underlying hash function. But that hash function is used in a way that does not depend on the so called “collision property” which means that you don’t need a full strength function like SHA-256. In fact, HMAC SHA-128 is perfectly secure, and even HMAC MD5 is unbreakable, even today, because it has a security level of 160 bits.
• Forgetting about context. For example, in the payment industry, payment transactions are valid for about a month; after that, there is no way to revert the payment. This means that almost all payments could be protected with a 3DES key, without any risk.
• Quantum computer scare. Publications have claimed that you would need to double the key length of your encryption to protect against quantum threats. This is almost certainly not true, as this ETSI report explains. Additionally, breaking RSA on a quantum computer is also still pretty far away, as EMV seems to agree, but that’s not the point of this article.

More wasteful cryptography

As if using long keys wasn’t bad enough, there are more ways in which cryptography is wasteful.

Key rotation is the requirement to change you keys regularly. The idea behind key rotation is that if someone somehow finds your key, they can only use it during the period you use the key. Historically, this made sense: if the Germans didn’t change their Enigma keys every day, the war would have been a lot shorter. Another related point is the laughable way in which passwords were protected (and sometimes still are). This allowed attackers to find many passwords in a matter of days. Forcing users to change their (long) passwords frequently doesn’t solve the problem; what you need is better password protection. If you don’t believe me, explain why your PIN is still secure, even though is it weaker than a weak password and rarely changes.

But today, every way in which you can find a key (by using side channel attacks, for example), finds the key in a few hours at most, often much faster than that. There is no amount of key rotation that is going to help against these attacks. In my career of about four decades in cryptography, I have not heard of a key that was compromised as a result of a cryptographic attack (not counting systematic attacks and errors, of course).

To be fair, there is a surprising reason to require key rotation: familiarity. As I said, key compromise is very unlikely, but possible. And if it happens, you need to be ready to change your keys immediately. So if you practice doing key changes regularly, this helps. Key rotation can play a role here.

Encryption uncompressed data is another way to waste resources. Encrypted data is completely random (by definition; if it isn’t, you are certainly using the wrong encryption). So if your data can be compressed, do it before you encrypt it, otherwise it is too late.

(Side note: the “compressible encryption” that Microsoft Outlook used until a few years ago for email storage was the laughing stock of cryptographers.)

HMAC key length

The strength of HMAC depends on the underlying hash function. In effect, HMAC is as secure as the full length of the hash function, not half of it as it is in the general case. The recommended length of HMAC keys is explained in a NIST document SP800–107r1. This document explains that SHA-1 is completely fine to use with HMAC. It also contains the phrase “In general, there is no benefit in generating K [key length] with more than 2C [twice the size of the hash] bits of security.”

Many, if not most application don’t dare to use SHA-1, because it is “broken”, so they use HMAC-SHA256. Furthermore, they conclude frrom the citation that the must choose the key length to be twice the hash size. The result is that many applications now use an HMAC with a 512 bits key “just to be safe”. Even if we could convert all of the matter in the universe to energy (with E=MC², remember?), you can just barely break HMAC with a key of 256 bits, so I think it is safe to call this “overkill”.

(If you have more examples, let me know; I may add them.)

Can this be fixed?

I would really like to contribute to reducing wasting of resources. Unfortunately, much of the damage has already been done:

• The Bitcoin network, which has an unbelievable energy use and managed to make a few people very rich at the cost of everyone else, cannot be stopped as long as there are people interested.
• News stories about “broken encryption” keep giving the wrong impression. For example the attack on the Thai smart cards in combination with the later attack on Latvia cards, both caused by bad prime random number generators, reduced trust in RSA because the news said that RSA keys were broken.
• Mark Stevens invented the concept of counter-cryptanalysis: this method allows to detect attempts to cause a collision of SHA-1 by just looking at one of the two messages in the collision. You can do this while calculating the hash value, effectively making SHA-1 secure again with a strength of 160 bits. Unfortunately, SHA-1 did not survive the scare caused by the false CA certificate attack of MD5 and the later SHA-1 collision. And, as Mark told me himself, almost everywhere where SHA1 is used today, counter-cryptanalysis is already implemented!
• Institutions are not likely to reduce their compliancy requirements, because they don’t want to lose their credibility.

So, alas, no happy ending. This article shows that people don’t make decisions based on security or efficiency, but on their “gut feeling” that is often based on lack of knowledge. We knew this already, of course.

If you want one advice out of all this: make sure you can change your cryptography by using “crypto agility” methods. This will protect you against future attacks by allowing you to switch on time. As a plus, this allows to prepare for the quantum computer.