Chapter 7: Key Length

Download 458 b.
Hajmi458 b.

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

Do'stlaringiz bilan baham:

Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan © 2019
ma'muriyatiga murojaat qiling