The Evil of Scale
16 November 2006

A recurring question about modern cryptography is how easy it is for sophisticated attackers to break it. A perennial question, people have been asking it more often since the U.S. domestic spying scandal broke early this year. Can a major government break a PGP message or something else equally as strong? If not now, when? After all, computers are getting faster all the time.

This is a difficult question to answer, and I’m going to go through it with math exposed, but we don’t have to use anything worse than some logarithms. I’m also going to make some assumptions that I think are reasonable:

• I will assume that this government can’t break the laws of physics as we understand them today. That means I’ll assume they can’t go faster than the speed of light, for example.
• I will assume that they don’t have alien technology or things that are hypothetical but completely unknown in the rest of the world. That means I’ll assume there are no quantum computers, DNA computers, and so on. I’m happy to let them be a few years ahead of us in semiconductor technology, but nothing outré.
• I will assume they do not have fundamental mathematical insights that we don’t have. For example, I’ll assume they can’t factor quickly.

These assumptions seem fair enough to me. We’re going to consider the problem of scale given the way the world looks in the early twenty-first century.

The brilliant comic strip artist, Bill Amend, touched on this problem a couple of weeks ago. You can find his strip here http://www.gocomics.com/foxtrot/2006/09/10/. In case that hyperlink goes dead, here’s the conversation:

Paige: “A math teacher offers to assign 1 second of homework the first week of school, 2 seconds the second week, 4 the third, and so on. If the amount of homework doubles every week, is this something you would agree to for the duration of the 36-week school year?”
Paige (looks to Peter): “I'm a little worried about answering this one wrong.”
Peter: “Is that Mr. Thompson? He’s evil.”

Mr. Thompson is indeed evil. People have a hard time understanding exponential growth. The answer to his question is the same as the answer to my first question. Here’s why:

In each week of the school year, a student who agrees to this arrangement will spend 2^week seconds doing homework. In the tenth week, the student will spend 2¹⁰ or 1,024 seconds doing homework. That’s a bit more than 17 minutes. Not bad. In the last week of the school year, however, the student will do 2³⁶ seconds of homework, and that’s a lot. 2³⁶ is more than 68 billion seconds. Or if you divide it out, it’s 2,179 years. That’s a lot of homework, especially the week after you did 1,089 years of homework.

Powers of two are nice to deal with because they’re the same thing as bits. 2³² is the number that overflows a 32-bit computer, just like a million is what overflows a six-digit odometer. If we talk about 128-bit keys, and we want to try every one of them, it will take 2¹²⁸ attempts.

2¹²⁸ is a very big number. Really big. Remember when we had 40-bit keys, and now we no longer use them? If you can fit a 40-bit key in a teaspoon, then a 56-bit key is a small swimming pool and an 80-bit key is a large swimming pool. A 112-bit key would cover the surface of the earth, and a 128-bit key is larger than the volume of the earth by quite a bit.

(Sidebar: Where do I get that answer? The mean radius of the earth is 6.37 million meters. The volume of a sphere is 4/3*pi*r^3. Therefore, the volume of the earth is 1082699464246399999995 cubic meters. There are a million milliliters in a cubic meter. There are also 5 milliliters in a teaspoon. So the number of teaspoons it takes to fill up the earth is (4/3) * 3.1416 * (6.37 * 10^6)^3 * 10000000 / 5. Lastly, if you want to convert something to a power of 2, you compute log(x)/log(2). That gives us 2^90.8 and the difference between a 40-bit key and a 128-bit key is 88 bits. So it’s actually a bit more than four earths.) <http://www.physlink.com/Education/AskExperts/ae419.cfm>

Okay, that’s mind-bending, but it doesn’t tell us anything about time. Key-cracking is all about time. So let’s suppose you get a lot of fast computers working on this problem: How long will it take them to try all the keys? Here’s an answer:Suppose you cover the surface of the earth with grass. Suppose that each of the blades of grass has a computer at its roots, and that little computer can do a billion key-checks per second. It will take this planet covered with computers more than a millennium to completely try a 128-bit key.

(Sidebar: Where do I get this number? The radius of the earth is, again, 6.37 million meters. The surface area of a sphere is 4 * pi * r^2. Let’s assume that a blade of grass takes up about 7mm of room. The number of seconds in a year is 86400 * 365.25. Of course, there are 1,000 years in a millennium, which gives us:
(6.37 * 10^6)^2 -- Square meters on the earth
* (1000/7)^2 -- 7mm per blade of grass
* 86400 * 365.25 * 1000 -- times the number of seconds in a millennium
* 1000 * 1000 * 1000 -- times 1 billion tries per second

This formula gives us 328228577913599999999967160730779744320, which is 2¹²⁷⁹, or just shy of 128 bits.)

We haven’t discussed how you’re going to power this covered planet (solar power, I presume) or cool it. I claim that it’s reasonable to assume no one has that sort of computing resources available to them.

But what about Moore’s Law, which isn’t really a law at all, but an observation? It is the observation that the number of transistors you can put on a chip doubles every 18 months. This observation implies that the cost of a computational task halves every 18 months. For our purposes, it also means that every 18 months, you lose a bit of security on a safe key. So after 15 years, that planet of computers could crack a key in a year, not a millennium.

However, there is a flip side to this situation as well. The problem with applying Moore’s Law to this sort of computation is that it can’t continue forever. Once transistors get to be the size of a single atom, it’s hard for them to get any smaller. Fifteen years after a transistor is the size of a single atom, it has to be one-thousandth the size of an atom. After 30 years, it’s one-millionth the size of an atom. To keep up with that sort of computing growth, we really do have to presume one of the outré technologies.

So let’s just ignore the difficulties for the time being. There is an excellent website at www.keylength.com that calculates a variety of cryptographic questions based on extending the growth of computing power. I went there, and using Arjen Lenstra’s model from 2004, assuming that DES with 56-bit keys became unsafe in 1982, a 128-bit key will be safe to use until the year 2090.

If that isn’t good enough—well, that’s why AES and other ciphers have 256-bit keys. PGP software will let you use 256-bit keys, too. (In fact, the newer PGP products work only with 256-bit keys.) According to Lenstra’s model, a 256-bit key will be good until the year 2282.

You shouldn’t be worrying about a basement in the NSA full of computers cracking the crypto on your email. What should you be worrying about? Well, evil math teachers is a good place to start, but in cryptography, that’s a question for another essay.