Why?

What We're Going To Cover

• Hashes

• Ciphers

• Keys

• Protocols

Hashes

Checksums, Cyclic Redundancy Codes

sum, CRC-16, CRC-32, CRC-64

• Maps variously sized inputs into a known, finite output space.
• Primary use: Check integrity of a copy or transfer of data. Secondary use: Provide “fingerprints” or shorthands when referring to a collection of data.
• Output space range wildly in size, depending on algorithm. Anything from simple 1 and 2 byte checksums to 32 byte monsters.
  (10⁶⁷ > 2²⁵⁶ > 10⁷⁷)
• Problems with smaller/naïve algorithms:
  • Increased collisions
  • Decreased entropy
  • Predictable outputs

Hashes

Cryptographic Hashes

Snefru, MD5, SHA-1, RIPEMD, HAVAL

Avoids collisions

• Large output space
• More even distribution of outputs

Better entropy

• Single bit differences in input yield more changes in output
• Changes are more “scattered” through the output

Unpredictable output

• Prevents tailoring of data to a particular output
• Prevents guessing bits of input from the output

Hashes

Cryptographic Hashes

Snefru, MD5, SHA-1, RIPE-MD, HAVAL

Resulting in

• Strong certainty that a hash uniquely represents its input
• Work with a given input without actually revealing its contents.
• Detect unexpected or unauthorized tampering with data;
  or, detect changes to data or any size without storing copies for comparison
• Provide effective, verifiable, and nearly unique fingerprints for data

Ciphers

Plaintext

Data in its original form.

Cipher (aka Cypher, Encryption)

An algorithm for obfuscating data in a way that can be later undone, yielding the original data.

Ciphertext

Data in an obscured, or encrypted, form.

Key

Relatively small bit of data that drives a cipher's execution in a unique and unpredictable way.

Common Expressions

E_K( M ) = C
D_K( C ) = M
D_K( E_K( M )) = M

Ciphers

ROT

A Simple Substitution Cipher

• A rotation or “ROT” cipher
• Example to the right: ROT-2
• Earliest known use was the “Caesar” cipher, ROT-3
• ROT-13 still sees widespread use in Usenet and some mailing lists

Analysis

• This is a cipher, albiet a very weak one.
• The key, in this case, is a single number (the shift length).
• E₂( FOOBAR ) = HQQDCT
• Serious weakness: lack of entropy (feedback) in the ciphertext.

Ciphers

Symmetric and Asymmetric

Ciphers are generally categorized as:

Symmetric

• The same key that encrypts the data also drives the decryption process.
• ROT, DES, IDEA, RC5, Blowfish, Twofish, AES
• E_K( M ) = C      D_K( C ) = M

Asymmetric, or Public Key

• Uses different keys for encryption and decryption.
• RSA, El Gamal
• E_Kpri( M ) = C      D_Kpub( C ) = M     K_pub ≠ K_pri

Ciphers

Symmetric

DES, IDEA, RC5, Blowfish, Twofish, AES

• Uses a single key for both encryption and decryption.
• Keys are usually treated as data for the engine.
• Encryption tries its best to scramble its data. Permutations and combinations of various bits in the data are thoroughly ripped apart and reassembled in a way that looks random (but isn't).
• Generally much faster than public key cryptography. In fact, most encrypted communications use a symmetric cipher algorithm.
• Requires that the key is managed in secret.

Ciphers

Symmetric

DES

The old Data Encryption Standard from 1976, based on IBM's Lucifer algorithm (1972). Uses a 56 bit key, and is no longer considered strong given modern computing power.

Triple DES

Three passes through DES with two different 56 bit keys, effecting a 112 bit key. Used when compatibility with older DES systems is required: set both keys equal.
C = E_K1( D_K2( E_K1( M )))
M = D_K1( E_K2( D_K1( C )))

AES

Advanced Encryption Standard, supports [128,256] bit keys. Chosen in 2001, made into a standard by NIST in 2002.

Ciphers

Symmetric

IDEA

International Data Encryption Algorithm, widely used in older PGP implementations. Patented, but freely available for non-commercial use. At one time, was considered one of the best alternatives to DES.

RC2, RC4, RC5

Rivest's Cipher (by Ron Rivest of RSA). RC5 was gaining popularity until NIST chose AES. Still see this family widely used in S/MIME and SSL.

Blowfish, Twofish

Bruce Schneier's algorithms. Twofish was a strong candidate for AES (along with RC5 and everyone else). Wide use in SSH. Very popular among crypto hackers.

Keys

Why does key length matter?

Time to perform a brute force search for comparable symmetric key algorithms...

Key Length (bits)	1995	2000	2005
40	68 seconds	8.6 seconds	1.1 seconds
56	7.4 weeks	6.5 days	19 hours
64	36.2 years	4.6 years	6.9 months
128	6.7 1020 years	8.4 1019 years	1.1 1019 years

Ciphers

Public Key

RSA, El Gamal

• Uses two different (but related!) keys for encryption and decryption.
  • One key only encrypts data.
  • The other key only decrypts data encrypted by the first key.
• Keys are related by mathematical properties.
• Encryption is typically a computation in finite space.
• Generally much slower than symmetric crypto.
• Permits insecure communication of public key.

Ciphers

Private Key Cipher: RSA

Public Key

N = product of two primes, P and Q
E = relatively prime to (P-1)(Q-1)

Private Key

D = E^-1 mod (P-1)(Q-1)

Encryption

C = M^E mod N

Decryption

M = C^D mod N

To Break

You have to factor the product of two prime numbers, each of which may be hundreds of digits in length.

Ciphers

Private Key Cipher: El Gamal

Public Key

P = prime
G < P
Y = G^X

Private Key

X < P

Encryption

K = relatively prime to P-1
A = G^K mod P
B = Y^KM mod P

Decryption

M = B / A^X mod P

To Break

You have to compute logarithms in a discrete (modulo) field.

Keys

Symmetric Cryptography

• Keys in a symmetric crypto system must be managed as secrets.
• But they must also be shared with everyone intending to decrypt the ciphertext.
• Keys must be changed from time to time; as the amount of ciphertext builds up over time, certain statistical attacks and other cryptanalysis becomes possible.
• These systems become especially vulnerable to eavesdropping and “man in the middle” attacks...

Keys

Man In The Middle Attack

• You send your key to the bank.
• But! The bank is really a crook pretending to be your bank.
• The crook now has your secret key.
• The crook generates his own secret key, and sends that to the bank, claiming to be you.
• When you send your transactions to the crook (posing as the bank), the crook can modify it any way he likes before sending it along to the bank.

This is also an example of a Protocol Attack. Note that the cipher algorithm itself is not under attack; instead, its useis being attacked.

Most failures in cryptography are not the fault of the algorithms; they are the result of bad protocols!

Keys

Public Key Cryptography

• Keys are generated in pairs, public and private.
  • The private key never needs to be sent or exchanged with anyone.
  • The public key can be freely shared with anyone.
• Because the public key can only decrypt data encrypted with the private key:
  • Authentication: We know only the holder of the private key can create a given ciphertext.
  • Non-repudiation: The author of a ciphertext cannot claim the message isn't hers.
• Keys are generally an order of magnitude larger than a symmetric cipher's key.
• Based on strong mathematical principles; much more resistant to statistical, differential, and linear cryptanalysis.
• Key pairs of reasonable length have effective lifetimes of years.

Protocols and Applications

We've got the basics down.

Combining these tools is where the real fun starts...

Probably a good time to take a break...

Protocols

Key Exchange

Problem

You want to communicate with someone at a distance using a fast symmetric cipher. How can you send them the key without eavesdroppers getting it, too?

Approach: Symmetric Key Exchange

In-room demonstration...

Protocols

Key Exchange

Problem

You want to send someone your public key. How do you know they get your key and not someone else?

Approach: Hash the Public Keys

1. Both sides of the conversation have private keys and exchange public keys.
2. Send each other a public key.
3. Generate a hash of your public key. Ask them to do the same.
4. Confirm (in person, over the phone) that the public keys match.

Alternatives: Publish your Public Keys

• Newspaper Classified Ads
• Public Key Servers

Protocols

Key Exchange

Problem

You want to communicate with someone at a distance using a fast symmetric cipher. How can you send them the key without eavesdroppers getting it, too?

Approach: Private Key Cryptography

1. Generate a new random symmetric key.
2. Encrypt it with your private key.
3. Encrypt that using their public key.
4. Send them the doubly-encrypted symmetric key.
5. First, they decrypt using their private key.
6. Next, they descrypt using your public key.
7. Result: they have the session key.

Protocols

Digital Signature

Problem

How to sign publicly available (unencrypted) data? More importantly, once signed, how do you prove the data hasn't changed later, in the future?

Approach: Public Key Encryption with a Secure Hash

You:

1. Generate a secure hash of the data. Throw in the current date and other info if you want.
2. Encrypt that hash with your private key.
3. Publish the encrypted document.

They:

1. Obtain the data to be verified, along with your encrypted data.
2. Generate a secure hash of the data.
3. Decrypt your encrypted data.
4. Compare the hashes to see if they match (along with whatever other data was encrypted).

Protocols

Digital Signature

The combination of secure hashes with private key encryption improves the latter:

• Authentication: We know only the holder of the private key can create a given ciphertext.
• Non-repudiation: The author of a ciphertext cannot claim the message isn't hers.
• Integrity: The data has not been modified in any way.
  Alternatively, you can match the signatures to a specific version of the document that was signed.

Oh, so that's why...