Chapter 7: Key Length

Chapter 7: Key Length

• Dulal C. Kar

Symmetric Key Length

• For a block cipher

• Cryptanalyst needs a small amount of ciphertext and the corresponding plaintext (known plaintext attack)
• Getting this plaintext and ciphertext is easy
• Just intercept standard header of an e-mail or a standard header of file formatted by a word processor

• Complexity

• For 64 bits, 264 keys possible
• Assuming a million keys a second, it will take 2285 years
• Algorithm must be secure so that there is no alternative to break any other way except using brute-force attack

Time and Cost Estimates for Brute-Force Attack

• Michael Wiener (1995)

• Designed 56-bit DES cracking, specialized parallel processing machine for $1 million, which can crack a key in 3.5 hours.
• Moore’s Law
• Computing power doubles approximately every 18 months, which means costs go down by a factor of 10 every 5 years
• $1 million of machine of 1995 will cost $10000 today
• Check table 7.1 for time estimates in 1995

Software Crackers

• Slower than hardware (1000 times slower)

• Distributed attack making use of idle time of microcomputers

• Easy to crack a 40-bit key

• Using 200 million giant Cray mainframe-like computers, each performing a million encryptions per second

• To recover a 128-bit key would take a million times the age of the universe

The Chinese Lottery

• Imagine, a brute-force, million-test-per second cracking chip was built into every radio and television sold in china

• See table 7.2 for results

Thermodynamic Limitations

• Second law of thermodynamics

• To record a single bit requires amount of energy no less than kT (k = 1.38*10-16 erg/deg-Kelvin and T = absolute temp)

• With T = 3.2 deg-Kelvin, to set/reset a bit, it would consume 4.4*10-16 ergs

• Annual output of our sun is about 1.21*1041 ergs

• enough to power 2.7*1056 single bit changes
• Enough to put a 187-bit counter through all its values
• Implies that 256-bit keys will be infeasible for cracking using brute-force attack

Public-Key Key Length

• Hard to factorize a product to obtain two large prime numbers

• Idea is used to make a trap-door one-way function

• Breaking public-key algorithms involve trying to factor the large number (or taking discrete logarithms in a very large finite field)

• Factoring large numbers is hard but getting easier faster than mathematicians expected

• If you want your keys to remain secure for 20 years, 1024 bits is likely too short

Recommended Public-Key Key Length

• Years 2005 -2010

• Individual: 1280 bits
• Corporation: 1536 bits
• Government: 2048 bits

• Year 2015

• Individual: 1536 bits
• Corporation: 2048 bits
• Government: 2048 bits

Comparing Symmetric and Public-Key Key Length

• A cryptosystem is likely to be attacked at its weakest point

• In a system that uses both symmetric and public-key cryptography, key lengths for each should be chosen to make both equally difficult to attack

• See table 7.9

• In general, choose a more secure public key length than your symmetric key length. Public keys stays longer

Birthday Attacks Against One-way Hash Functions

• Two brute-force attacks

• Given the hash of message, H(M), create another document M’ such that H(M) = H(M’)
• Find two random messages, M and M’ such that H(M) = H(M’)

• Second one is far easier attack

• Assume the hash function produces an m-bit output

• Finding a message that hashes to a given hash value would require hashing 2m random messages
• Finding two messages that hash to the same value would require 2m/2 random messages

• Example, if you want to drop the odds of someone breaking to less than 1 in 280, use a 160-bit one-way hash function