Brute Force Attack on AES
by C.B. Roellgen
A while aogo I was asked by a news editor about the quality of the Polymorphic Cipher. It was stunning to discover how easy it is to break ciphers like AES, Twofish or DES if users choose short passwords.
Here are some thoughts on this subject. Experts in cryptography will easily be able to follow this and will instantly agree to the conclusion:
Unfortunately is the length of the password and also the quality of the characters that are chosen by a user decisive. A password like "sgQWt12QWfgr9mkf" may have a high quality because it contains lower case- as well us upper case letters and numbers, but it is simply too short. Most users only use letters and numbers. There are 2x26 letters (lower- and upper case) + 10 numbers = 62 different characters. This alphabet consequently only uses 6 bit per character. 16 characters x 6 bit = 96 bit. Any cipher, be it AES Rijndael, Twofish or PMC can thus be attacked by somebody who has pretty good capabilities (please read below). The password is finally the last and only "line of defense".
Any cipher can be cracked with a kind of attack called "Brute Force Attack". Today, it works phantastically on DES because DES keys are limited to 56 bit. "Deep Crack" took advantage of the simple construction of DES: special chips with many DES function blocks that operate in parallel were manufactured and operated http://w2.eff.org/Privacy/Crypto/Crypto_misc/DESCracker/HTML/19980716_eff_descracker_pressrel.html ; this link unfortunately doesn't work any more (July 2008): http://www.eff.org/Privacy/Crypto/Crypto_misc/DESCracker/). Using thousands of normal personal computers in parallel also proved to be a good way to break DES keys.
AES is as well concieved in a way that eases manufacturing and operation on only very little chip area (that was one of the design goals for the AES contest!!!).
Axel Poschmann from the University of Bochum was able to implement AES with just 39567 transistors. Synopsys Design Vision V-2004.06-SP2 mapped his AES design to 0.151mm2 with 76% area utilizations for the cells (target: Artisan UMC 0.18µm L180 Process 1.8-Volt Sage-X Standard Cells). Taking into account that a modern 45nm CMOS process would shrink the design to a quarter of the size, AES can today be implemented on just 0.02869mm2 of silicon (cells only, no pads)! An 8'' wafer can thus carry with it's 32.000mm2 area approx. 1.1 million AES blocks.
Mr. Poschmann's implementation requires 2 clock cycles for key setup (encryption only) and 53 clock cycles to encrypt 128 bit.
Here's the paper:
56Mhz max. operating frequency will be beaten by a much higher performance of a 45nm process. Let's only assume 4 times higher speed. To test one key would then take approx. 250ns.
In order to take advantage of 1 million AES blocks, they will all be running in parallel. The AES blocks only need only to be connected to a serial bus that distributes key information and that transports commands and results. The wafer also needs a good power supply, cooling with fluorinert, a clock- and a data line. As a matter of consequence, the attack security of our password is reduced by 20 bit (2^20=1048576) due to the fact that an attacker who possesses such a wafer has copied the crypto core on a large scale (a million times = approx. 20 bit). From the original 96 bit only 76 bit remain, if just one special wafer is used to break a code instead of a Pentium IV running at several GHz. Each of the approx. 1 million AES function blocks can check roughly 4 million keys (22 bit) per second. One single Wafer can thus "eliminate" 42 bit. 1024 wafers (10 bit, all the hardware fits well in a broom closet) can even be afforded by comparably poor intelligence agencies in the world. This sums up to 52 bit per second, which is more than the length of the passwords that are chosen by most users.
AES is probably a phantastic algorithm. This method to break ciphers although applies to each and every cipher!
If an attacker who possesses those 1024 wafers wants to crack an especially important message that is encrypted with a known algorithm (the likelyhood for AES is pretty high), another 16 .. 17 bit melt away (one day on planet earth has 60x60x24 = 86400 seconds, which corresponds to 16 .. 17 bit). So an attacker can check 68 or 69 bit with 1024 wafers.
A medium-sized wafer fab produces more than 40.000 wafers per week. For sure a government agency like the Chinese secret service, the Russian FSB or the American NSA have the money to buy a one-week production of a wafer fab. Another 5 bit melt away. An attacker can thus check 73 to 74 bit with 40.000 wafers.
In just one day 73 ... 74 out of 96 bit have simply gone. ONLY 22 .. 23 bit security margin!
EACH AND EVERY CRYPTANALYST WILL BE ABLE TO CONFIRM THIS IMMEDIATELY.
According to Moore's Law, processing power doubles every 18 months. Each and every 18 months an attacker can book another bit on his side.
AES is only a 128 bit cipher and could prove to be unsuitable for eternity. Please keep in mind that the use of 256 bit keys that are finally crunched by a 128 bit block cipher are not strictly better than 128 bit keys. The cipher is consequently not better than any other good 128 bit cipher. AES is free of charge and it's the de facto standard. Thus, it is guaranteed that almost all security applications use AES. The investment for a code breaking machine will not be in danger.
Things are a little different if the cipher is different. PMC cannot be implemented on just 0.03mm2 chip space. The Polymorphic Cipher engine of TurboCrypt requires a complete microprocessor, a lot of memory and can thus be copied on a special 8" wafer on not more than 1024 function blocks (absolute maximum with a 45nm CMOS process). Only 10 bit are lost this way. PMC requires compiling of the actual encryption algorithm from the password. While AES only requires 2 clock cycles for key setup and 53 for the actual encryption, PMC has a 10.000 ... 100.000 times higher operating expense for key setup. PMC thus comes with an advantage of at least 1024 x 10.000 times (approx. 23 bit) compared with standard algorithms that have unfortunately been designed for use on ASICs, smart cards with tiny microprocessor cores and not really for large microprocessors.
Let's just talk about REAL security and what has to be observed when actually using encryption technology.
This here is only about the easiest approach to obtain plaintext from encrypted messages. Everybody who is really interested in reading encrypted messages has inevitably similar thoughts. There seems not to be the need to conceive complicated methods for shortcuts or things like that. DES has never been cracked by applying mathematics!!! Unfortunately DES can now be broken in seconds due to the fact that computers have become much faster and better than originally anticipated. What works with DES might also be a good approach to break other ciphers.
Is is fascinating to see that Deep Crack has just cost $250.000. As far as I know the project was financed by private persons. It is very likely that intelligence angencies have had such machines long before and they might also have invested a much higher amout of money (compared with Deep Crack).