Assignment 6

Due Wednesday, April 22, 2009 8:25 pm in recitation
(at the start of class)

Introduction

Please answer the questions precisely and concisely.

Reading

Crypto FAQ , RSA Labs
http://www.rsasecurity.com/rsalabs/faq/. Chapters 1-5.1.

Why Cryptography is Harder Than It Looks, Bruce Schneier
http://www.counterpane.com/whycrypto.html

Snake Oil Warning Signs: Encryption Software to Avoid
http://www.interhack.net/people/cmcurtin/snake-oil-faq.html

One-Time Pads, Crypto-Gram Newsletter: October 15, 2002.
http://www.counterpane.com/crypto-gram-0210.html#7

An Illustrated Guide to Crytpographic Hashes, Steve Friedl's Unixwiz.net Tech Tips. http://cyphunk.files.wordpress.com/2006/02/An%20Illustrated%20Guide%20to%20Cryptographic%20Hashes.pdf

Questions

For the first question, express your time in easy-to-grasp units. Use minutes if the answer is under an hour, hours if the answer is under a day, and years if the answer is over 365 days. For example, 172,800 seconds is harder to grasp than 2 days. Use 10x exponential notation if the answer is greater than 1,000,000 years. No more than three digits of precision are needed. Write 2.3*107 instead of 2.3129912*107.

  1. In 1998, The Electronic Frontier Foundation built a DES Cracker – a machine with thousands of custom gate arrays, each of which contains 24 search engines. Each search engine can examine 2.5 million keys per second. The machine was able to find a DES key for a document in under three days. In 1999, distributed.net was able to harness almost 100,000 PCs on the internet along with the DES Cracker and crack a key in 22 hours 15 minutes, testing about 245 billion keys per second.

    Suppose that you can, on average, crack a 56-bit key in half a day (12 hours) using a brute-force key search.

    1. How long will it take you to crack a 57-bit key?
    2. How long will it take you to crack a 128-bit key?
    3. Suppose that, in the future, you can crack a 56-bit key in just one second, how long will it take you to crack a 128-bit key?

    Please put your answers in the following format (specify your units: seconds, days, or years for the last column):

    part permutations time
    a    
    b    
    c    
  2. What size public key would you need to achieve comparable security to a 64-bit symmetric key? (See the Snake Oil article.)
  3. Why is a one-time pad an impractical cryptosystem even though it is the only one that is provably secure? (See the Crypto-Gram Newsletter and the Snake Oil article.)
  4. Explain the difference between public-key and symmetric cryptography. (See chapter 2.1 of the RSA Labs Crypto FAQ.)
  5. State three uses of hash functions (see the Illustrated Guide to Cryptographic Hashes).
  6. What is the difference between weakly collision-free and strongly collision-free hashes? (See chapter 2.1 of the RSA Labs Crypto FAQ.)
  7. What does it mean to add salt to a password? How does it make hashed passwords more secure?
    (see wikipedia and msdn)