- Some Definitions to be Used in this Article

- Brute Force Definitions

- Type of Computer Used in This Article

- Time Issues for Cracking

- Cracking a key in One Month

- Cracking a 128-bit Key by Brute Force

- Conclusions for our Current Pentiums

- How Fast is Intel Speeding Up Pentiums

- Return to the Main Menu

Return to the Beginning of This Document

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.

The following table shows symmetric key and asymmetric key lengths on the same line.

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

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

A

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

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,

Return to the Beginning to 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

Return to the Beginning to This Document

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.

Return to the Beginning to This Document

Suppose you

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.

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

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

to crack a 64-bit key as a basis.

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

Next, using the same arguments,

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!

Adding 10 more bits to the key, it would take

Paraphrasing what these results tell us, this tells us that

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

If we add 10 more bits to the key, ie,

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

To sum up,

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

- 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
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.*governmental attack*

- 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.
- 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!

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

- 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

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,

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

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.

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