Fun Times with Encryption
Time for a throwback! This year, I posted my new article "The Art of the Compensating Control" over a three week period back in April. A reader recently contacted me about a claim I make in Part 4 of the posting. He says:
In your April 2009 blog The Art of the Compensating Control (Part 4) Tax day special, you stated that using the random function in COBOL to generate your key was in a sense, "a really bad idea". I have no knowledge of encryption so I don't see the fault with the process. How would this be equivalent to only 53 bits of encryption?
Excellent question! The basis of this post relies on a tool by Mandylion Labs called the Brute Force Calculator.
True 128-bit encryption means that the key is 128 "bits" of data long. A bit of data can either be a 1 or a 0. 8 bits make a byte, 1024 bytes make a kilobyte, and so on. An example 128-bit key might look like...
0010100010101011001010001010101100101000101010110010
1111101010110010100010101011001010001010101100101000
101010110010100010101011
Theoretically, this would be truly random, and you can use the entire "key space" offered by the key size and the algorithm you wish to use because you are placing a 1 or a 0 in each of the 128 bits.
Now let's look at how ASCII-based numbers (or if you like, EBCDIC) are represented in binary. Each ASCII character (or number in our case) is equivalent to 8 bits of data, or 1 byte of data (yes, technically 7 with 1 bit of parity). For example, the binary value for the ASCII character '1' is '00110001'. So now, 16 digits (128-bits / 8 bits [because each number takes 8 bits to be represented in binary] = 16 positions), or characters, would be all you can use to make up your key. If you know that your key is based on binary representation of ASCII numerical values, then you effectively know that each 8 bits of data can only be one of the following values:
- 0: 00110000
- 1: 00110001
- 2: 00110010
- 3: 00110011
- 4: 00110100
- 5: 00110101
- 6: 00110110
- 7: 00110111
- 8: 00111000
- 9: 00111001
So based on this, you know that at least every 4 bits of data will ALWAYS be 0011, with no exception, because you based your binary key on the ASCII numerical values.
Using the calculator referenced above, you can calculate the "effective" key strength by understanding that 16 digits gets you a total of 10 quadrillion (10 with 15 zeros behind it) possible combinations. By taking that number and performing a logarithm using a base of 2 (because remember, binary numbers can be either 0 or 1, two different values) you find that 10 quadrillion effectively equals just over 2^53, or 53-bits of effective encryption. For comparison, if you are able to use the entire 128-bit key space, the total number of possible keys would be 340,282,366,920,938,000,000,000,000,000,000,000,000. That's a pretty big number!
So using the assumptions in the calculator (which may be outdated by way of computing power, especially in light of the recent improvements in GPU processing), 1,000 machines could crack it in less than 300 hours.
Granted that these examples are painting one particular picture. Yes you could get creative and just pull the last two digits of the binary values and use MORE digits, but isn't that the point? Create a better, more random key? If you are going down that road, why not just ask your user to type randomly on a keyboard while generating your key, then measure the time between keystrokes, combine it with the random number generator on your machine, and get about the closest you will get to true randomness with 128 0 or 1 rounded values?
Give the calculator a try! There are some other great things you can do with this sheet like calculating how effective your enterprise password scheme would be against a (non-rainbow table based) brute force attack.
Comments
A lot of numbers for my little brain to process, but it is very well explained. Thanks!
Posted by: Clay Keller | July 28, 2009 8:15 AM
Mmmm, brute force is tasty. 1000 zombies running Nvidia CUDA would probably take an average of 2 hours to crack keys. More info than anyone probably cares to read is below.
Generating all the possible keys is computationally cheap compared to actually testing the keys one at a time against a ciphertext to see if the key fits. When running each key through the algorithm, the computational power required for each key will vary based upon algorithm complexity and key length. For example, AES is faster than TDES, with the gap in performance depending upon the implementations. However, AES-128 has a higher key space than TDES's 112-bits of comparable symmetric strength. Also, it makes a difference if you have a known plaintext vs ciphertext only. Known plaintext can compare results quickly whereas ciphertext only has to look for data patterns that don't appear to be gibberish.
If you're trying to brute force passwords against a known hash, it gets even more fun. MD5 hashes can be computed about 3 times faster than SHA1 hashes. Multiple iterations can be used to slow down the brute force process. The PBKDF2 recommended minimum is 1000 iterations.
In context with this article and the use of 16 pseudorandom integers to create a 128-bit key: Let's assume it's to be used for encryption of data with an AES-128 key: Take into account that the average time to find a key would be at 50% of the key space. The ECRYPT Yearly Report on Algorithms and Key Sizes 2008 provides some interesting numbers on cracking speed. After doing some math with the numbers in that report, it would appear that using a PC connected to $1,000 of modern FPGA hardware (75 Xilinx Spartan-3 FPGAs) enables one to test a little more than 723,000,000 AES-128 keys per second against a known plaintext. It would take an average of 80 days for a single computer to crack the key discussed in the situation you're proposing. Take your army of zombies doing distributed computing running on CPU alone and we're talking 400 hours (17 days). If those 1000 zombies are running an Nvidia graphics card, the botmaster could throw in CUDA drivers in place of FPGA. Now we're talking 2 hours. Maybe a little more or less. Couldn't find exact numbers on CUDA and AES-128 key cracking.
Posted by: Lucas | July 28, 2009 2:34 PM
AWESOME analysis! Thanks Lucas!
Posted by: Branden Williams
|
July 29, 2009 4:51 AM