Cracking Encryption Algorithms

Need for secure encryption algorithms

Good cryptographic systems should always be designed so that they are as difficult to break as possible. Governments have always had concerns with strong encryption fearing that it could be used against their countries by criminals. Sophisticated technology is used by law enforcement agencies to decipher encrypted information that might contain incriminating evidence. In theory one can break any encryption algorithm by exhausting every key in a sequence. This brute force method requires vast amounts of computing power as length of the key increase. For example a 32-bit key takes 2^32 (4294967296) steps. A system with 40 bit keys (e.g. US-exportable version of RC4) takes 2^40 steps - this kind of computing power is available in most universities and even small companies.

Encryption key lengths & hacking feasibility

Type of Attacker	Budget	Tool	Time & Cost/Key 40 bit	Time & Cost/Key 56 bit
Regular User	Minimal $400	Scavenged computer time FPGA	1 week 5 hours ($.08)	Not feasible 38 years ($5,000)
Small Business	$10,000	FPGA 1	12 min.($.08)	556 days ($5,000)
Corporate Department	$300,000	FPGA ASIC 2	24 sec. ($.08) 0.18 sec. ($.001)	19 days ($5,000) 3 hours ($38)
Large Corporation	$10M	ASIC	0.005 sec.($0.001)	6 min. ($38)
Intelligence Agency	$300M	ASIC	0.0002 sec.($0.001)	12 sec. ($38)

As key lengths increase, the number of combinations that must be tried for a brute force attack increase exponentially. For example a 128-bit key would have 2^128 (3.402823669209e+38) total possible combinations. For example, to theoretically crack the 128-bit IDEA key using brute force one would have to:

• develop a CPU that can test 1 billion IDEA keys per second


• build a parallel machine that consists of one million of these processors


• mass produce them to an extent that everyone can own one hundred of these machines


• network them all together and start working through the 128 bit key space

Assuming ideal performance and no downtime, one should be able to exhaustively search the key-space in over 20,000 years. A common concern amongst many is deciding what key length is secure. There is a metronome for technological progress called Moore's Law which states that; "the number of components that can be packed on a computer chip doubles every 18 months while the price stays the same" . Essentially, this means that computing power per dollar doubles every eighteen months. Using a derivative of this above law one can also say that, if a key length of x is considered safe today, in 18 months the key length would have to be x+1 to keep up to par with the computing power. Recent studies performed by independent scientists have shown that key lengths should be no less than 90-bits long to ensure complete security for the next 20 years.

¹ FPGA (Field Programmable Gate Arrays) are programmable pieces of hardware specifically designed for encryption/decryption.

² ASIC (Application Specific Integrated Circuits) are also specialized hardware that can test 200 million keys per second.