Wednesday 4 November 2009

Cryptography vs Moores Law

All cryptographic algorithms are breakable (with the exception of a one-time pad that is longer than the data to be encrypted)

The type of algorithm, key length, and validity of the implementation are all important factors as to how easy a cryptosystem is to break.

A key component of the way cryptography keeps data secure, is the vast computational effort required to break the algorithm or brute force the keys.

This computational effort is measured in millions, billions, or trillions of years (etc) I often see literature quoting strength in "how many billions of years it would take to break". However, when calculating the effectiveness of algorithms and key lengths it is VERY important to consider other factors, such as Moore’s Law.


Moore’s Law
Moore’s law basically states that the number of transistors you can place on a substrate doubles every two years. This can result in a doubling of processing power approximately every 18 months.

This is an exponential, and exponentials have an extremely powerful effect over the short term.

Some basic calculations
So, if an algorithm will take a billion years to break, on a single computer with today’s technology, and you start today, but upgrade your technology every 18 months, how long will it take?

Only about 45 years

Let me say that again, the cryptographers say a billion years, I say 45; based on improvements in computer technology we will all seen in the home. It's a big difference, but I may not be around in 45 years, so what else can make a difference?

If you are running a botnet of 100,000 machines and your users are swapping out their own technology (which on average doubles the processing power every 18 months)? = About 20 years

And your botnet doubles in size every 1.5 years = About 11 years

And if in addition to the above, flaws discovered in algorithms and implementations on average half the processing requirement every 1.5 years = About 9 years

So much for a billion years! What are the solutions?

Increase key lengths regularly, fix implementation flaws, deploy new cryptographic algorithms as they become available - and kill the botnets.