Cracking Keys with Current Intel CPUs -- written by Thomas Jerry Scott
Note: This document discusses time constraints in decrypting a message encrypted with a 64-bit key, a 74-bit key, ..., up to a 128-bit key using a brute force attack. All throughout this document, we will use terms such as "cracking a 64-bit key" or "to crack a 74-bit key," to mean is the longer and more technically precise terms "decrypting a message encrypted with a 64-bit key" or "decrypting a message encrypted with a 74-bit key."

Table of Contents for Cracking Keys Through Brute Force


  1. Some Definitions to be Used in this Article
  2. Brute Force Definitions
  3. Type of Computer Used in This Article

  4. Time Issues for Cracking
  5. Cracking a key in One Month
  6. Cracking a 128-bit Key by Brute Force

  7. Conclusions for our Current Pentiums
  8. How Fast is Intel Speeding Up Pentiums

  9. Return to the Main Menu
Return to the Beginning of This Document

Definitions Used in This Article


First some definitions are given, and then the times are generated. The document ends with conclusions on cracking messages encrypted with keys of differing lengths, as well as how the faster CPUs we will see in the future can possibly speed up the decryption process.

In this note, we are only only discussing cracking symmetric keys.

The following table shows symmetric key and asymmetric key lengths on the same line. The key lengths on each line present approximately the same algorithmic complexity.

From the table, you can see that the time to crack a message encrypted with a 56-bit symmetric key requires approximately the same time as cracking a 384-bit asymmetric key. This table is found in Bruce Schneier's Applied Cryptography as well as in a number of places on the Internet.

Table 1: Key Lengths for Symmetric and Asymmetric Keys
Symmetric Key Length Asymmetric Key Length
56 bits 384 bits
64 bits 512 bits
80 bits 768 bits
112 bits 1792 bits
128 bits 2304 bits


Return to the Beginning of This Document

What is a Brute Force Attack?


A brute force attack means that you will try ALL the POSSIBLE KEYS.

For a 64-bit key, there are 2^64 keys, and this number is approximately

1.85 * 10^19 or 18,500,000,000,000,000,000 keys
.

Can you name that number????

Currently reported hacks, such as the EFF DES hack and the Bovine DES hack, only had to look at 25% of the entire keyspace. So this would mean that in a normal "brute force effort" to crack a message encrypted with a 64-bit symmetric key, we would need to only look at (1.85*10^19)/4, or 4.625 * 10^18 or 4,625,000,000,000,000,000 keys.

Return to the Beginning to This Document

What Type Computer Are We Using in This Document?


In this document, we will assume that you have a dual Pentium 4D computer, with each processor running at 3.2 Ghz. Since not all algorithms have the same computational complexity, our fast 2-processor computer would be able to try between 1,000,000 and 4,000,000 keys per second, depending on the cryptographic algorithm being used.

Giving that multi-Pentium its best shot, we will assume that our fast computer will be able to test 4,000,000 keys per second. In scientific notation, this is represented as 2 * 10 ^ 6 keys per second.

Return to the Beginning to This Document

Time Issues: How Long Will It Take to Crack a 64-bit Key?


Our two processor Pentium 4D, 3.2 Ghz computer would take

4.625 *10^18 keys /(4 * 10 ^ 6 keys/second) = 1.6502 *10^12 seconds

to crack just one 64-bit encrypted message, or course, assuming that we only have to try 25% of the possibilities.

How long is 1.6502 * 10 ^12 seconds?

We know that 1 hour is 60*60 = 3,600 seconds.

Similarly, 1 day = 24 * 60 * 60 seconds and one year is 365 * 24 * 60 * 60 or 31,536,000 or 3.1536 * 10^7 seconds. Finally, one century is 100 * 31,536,000 or 3.1536*10^9 seconds.

Dividing the values, we get

(1.6502 * 10^12) total keys to check /(3.1536 * 10^9) centuries or the astonishing fact that our fast 4-processor pentium would take over 367 centuries just to crack one 64-bit key.

Now considering that it would take 367 centuries for our 2 processor 3.2 Ghz pentium computer to crack even a 64-bit key, a 64-bit key seems safe from a worst case brute force attack using currently available Intel Pentium technology.

To sum up, cracking one 64-bit encrypted message would take 367 centuries!!

Return to the Beginning to This Document

How Many Computers Needed to Crack a 64-bit Key in One Month?


Suppose you absolutely, positively have to crack one 64-bit crack in one month. This was what the US government needed to do in WW2. They solved this problem by taking over a German vessel each month and getting the keys to the German Enigma encryption machine.

Since our Pentium Two Processor 3.2 Ghz computer takes so long, we need to have lots and lots of these machines working in parallel.

If we had 1,000 of our machines, we could crack one message encrypted with a single 64-bit key in 367 Centuries/Machine /1000 machines = .367 of a Century, or 36.7 years, or 36.7 * 12 = 440 months.

With a million of these machines working in parallel, we would need 440 months /1000 = 0.44 of a month, or approximately 13 days.

So it would take a million of our 2 processor P4 3.2D Ghz Pentiums all working simultaneously for 13 days to crack one 64-bit key! Wow!

Remember, these one million computers are working on nothing else for this whole time, are battery backed up, and will not stop at all during this entire 13 day process!

Return to the Beginning to This Document

Going for the Gusto: Cracking a 128-bit Key


Next, we will consider a brute force crack of a 128-bit key. We will determine the number of Pentiums required as well as the time required by moving from key lengths of 64-bits to key lengths of 128-bits in increments of 10 bits. At each increment, we will increase either the time required or the number of Pentiums required.

We will use the numbers we have developed so far, i.e., we will use
the 1,000,000 Dual Processor 3.2 Ghz Pentium 4 computers and 13 days, which is about 0.43 of one month
to crack a 64-bit key as a basis.

How Long to Crack a 74-bit key?


Since 2^74 = 2^10 * 2^64, that would add 2^10 times more keys, or 1,024 more keys.

Thus to crack a 74-bit key in one month would take at least 1,000,000 * 1,000 = 10^9 or 430 million of our 2 Processor 3.2 Ghz Pentium 4 Systems.

How about an 84-bit key?


Next, using the same arguments, it would take 430 billion or 10^12 high-speed Pentiums at least one month to crack an 84-bit key.

Since there are about 6 billion people on the planet, this would mean that mean that we have 7 computers for every man, woman, and child on the planet. Of course, if we counted those who have passed, we would get a lot more computers, but those older ones (think Commodore 64, Apple 2, TRS-80, ...) would be much slower than the PentiumD 3.2 GHz we are using in this analysis.

At this point, we have to give up on a realistic crack of an 84-bit key in one month. Instead, we will move to more time!

How About a 94-bit Key?


Adding 10 more bits to the key, it would take

1 quadrillion or 10^15 high-speed pentium computers to crack a 94-bit key in at least one month.

Paraphrasing what these results tell us, this tells us that all the computers ever built, working on nothing but cracking this one 94-bit key, could maybe do the job in approximately one month.

This is a very generous assessment, but we are being generous in this discussion.

How About a 104-bit Key?



If we add 10 more bits to the key, ie, 104 bits, this means that

if all the computers ever built ran only this key cracking problem for approimately 90 years (90*12 = 1080, and ten more bits =1024) they could possibly crack the one 104-bit key.

How About a 114-bit Key?


Now, if we add 10 more bits to the key, we would now have a 114-bit key. Using the same time argument, we decide that it would take over

90,000 years for all the computers ever built to crack this one 114-bit key.

To sum up, it would takes all the computers ever built 90,000 years just to crack one 114-bit key!!!

How About a 124-bit Key?


Now, with a 124-bit key, it would take 90,000,000 years for all the computers ever built to crack the key by brute force! Wow! Is a 124-bit Key safe?

Of course, cracking a 128-bit key would be 16 times harder, so it would only take 1,440,000,000 years!!!

Return to the Beginning to This Document

Drawing Some Conclusions From These Discussions


  1. A 64-bit key is safe for information that is not being attacked by a governmental attack, provided it only needs to be secure for less than a year. Remember that a governmental attack is one some millions of dollars could be spent and a year or so of effort expended to solve the hacking problem. In this discussion, the hacking problem discussed is how to decrypt a message encrypted with a 64-bit symmetric key.

  2. A 128-bit key is computationally safe from all types of brute force attacks. As we just discovered it would take 1,440,000,000 0r 1.44 billion years to crack a crack a 128-bit key.

  3. As the recent DES hacks have shown, a 56-bit key is just not strong enough. 64-bit keys are much better, in fact, they are 256 times stronger!

  4. Because of their immunity to brute force attacks, cryptographers are clamoring for 128-bit key algorithms to be accepted.

  5. For these reasons, the US government finally liberalized encryption standards in 2000 and 2001 to allow 128-bit encrypted information to be legally exported.

    Hopefully, we have just demonstrated that the government in right in this case!


Return to the Beginning to This Document

How Fast is Intel Speeding up their Pentium Capability?


Intel is well known for being able to make faster CPU's in short times. We will assume that the Pentium design is scalable and Intel will double its CPU speed every two years. In addition, we will assume that modern operating systems will be able to handle much more massively parallel Intel Pentium designs. (These are very dubious assumptions, but we are being very generous to computer performance in this article!)

In other words, we will assume that the number of Intel CPUs that current motherboards and OS's will support will double as fast as Intel can double the CPU speed.

Finally, we will assume that performance in massively parallel designs is also completely linear. Completely linear means that an 8-processor box would perform twice as fast as a 4-processor box.

In the real world, linear performance is clearly not the case. Theoretical studies have shown that a goal of an 80% speed gain when you add a second processor is near optimum. But, as we said before in this discussion, we are giving everyone the benefit of the doubt!.

As examples of these types of scalability problems with current systems, consider recent history for the Windows NT and Solaris operating systems.

Microsoft NT 3.11 came out in 1993 with the possibility of 4 CPUs, and a theoretical limit of 32 CPUs. In 1999, we have a number of motherboard/NT combinations with 4 CPUs, and a few with 8 CPUs. The Windows 2000 versions support a Server with 2, 4, and 8 CPUs, and with OEM support, 16 and 32 CPUs.

In the Unix environment, Sun's Solaris operating system came out with 2 processors in the late 80's and early 90's. Some early Sparc/Solaris two processor designs actually ran some benchmarks slower than a single processor version with the same OS and CPU ran them. Now with version 8 of Solaris, Sun has 64 CPUs that can be supported!

Putting all this together, and despite what has just been noted, we are assuming that every two years produces both a 400% increase: twice as much CPU speed, and operating systems and motherboards that support double the number of CPU's with have totally linear performance. Putting all these factors together, this means that every two years, we have a four fold increase in performance.

Using this 4x speed gain every two years, we generate the following table, starting with our 2-processor, 3.2 Ghz Pentium 4D machine in the year 2006. This table shows the time it will take (in various units, as needed) to decrypt a message encrypted with a 64-bit key, considering that each two years brings a fourfold speed increase.

Table 2: Intel CPU Speed Increase
Year Time Time Unit Year Time Time Unit
2006 367 Centuries 2008 92 Centuries
2010 24 Centuries 2012 6 Centuries
2014 1.5 Centuries 2016 38 Years
2018 10 Years 2020 2.5 Years
2022 8 Months 2024 2 Months
2026 15 Days 2028 4 Days


Return to the Beginning to This Document