Crypto 3

Block Ciphers
Much stronger than stream ciphers
Warning: Don't develop your own ciphers under any circumstance
Encrypts one message block at a time into a same size block as the original message block
Data Encryption Standard (DES) is popular with public sector and FIs
a bit of history...
1967 - Feistel developed Lucifer using a 128-bit key length
1972 - NBS issues RFP
IBM develops DES with a shorter 56-bit key and a 64-bit message block
1979 - DES phased out
2000 - NIST adopts AES
Idea behind DES is the Feistel network
Feistel network also influenced IDEA, RC5, Skipjack...
No swap on the last round
Each round only half of the previous round's plaintext gets encrypted
Write a recursive definition of a Feistel network
Prove that Feistel network is one-to-one, i.e. invertible
Proof: Construct the inverse
Take Fd and derive Ld-1. Rd is already equal to Rd-1
Feistel network inverts itself!!!
DES is a 16 round Feistel network using a 64-bit block so LHS na RHS are 32-bits each
DES was meant to be implemented in hardware, not in software
Most ATMs that FIs use are validate pins using DES
What do the S-boxes in DES signify?
Is there an S-box attack on DES?
What is the madness behind the choice of S-boxes' values?

Algortithm Performance (source Wei Dai)
Environment: Pentium 4, 2.1Ghz running Windows XP SP1
RC4 runs in about 113MB/second
SEAL runs in about 293MB/second
DES runs in about 21MB/second
3DES runs in about 61MB/second
IDEA runs in about 19MB/second
SHACAL-2 runs in about 20MB/second

Electronic Code Book (ECB) - break a message into blocks and encrypt each block separately
Ciphertext will be the same size as the plaintext
Deterministic constructions are problematic
i.e. send the same e-mail message twice and the attacker will see the same ciphertext twice which allows the attacker to learn info
ECB inherently leaks information
Recall Bart Preneel's photo example with a sillohuette revealed in the ciphertext
NEVER USE ECB to do encryption

Cipher Block Chaining (CBC)
CBC is a better method than ECB
DES uses CBC
XOR the Initial Value (IV) with the first block of plaintext
C1 is then XORd with P2...
Ciphertext will be a little longer than the plaintext
IV must be new and random for every message - non-deterministic
CBC encryption is inherently sequential which is problematic for high-end network device implementations i.e. harware VPNs
CBC provides no integrity for the ciphertext
With CBC, decryption is just as easy as encryption
Could use counter-mode to turn block cipher into a stream cipher to solve sequential encryption problem; counter-mode is making the encryption parallel
Still no ciphertext integrity guarantee

Output FeedBack mode (OFB)
Another mode of encryption; don't use it

Attacks on block ciphers
Exhaustive search - try every key
Recall RSA's DES Challenge
1997 Challenged solved in 3 months using distributed.net
1998 EFF paid Paul Kocher to develop DeepCrack. DES broken in 3 days
1999 Combined Search broke DES in 22 hours -- The death of DES
Never use a 56-bit cipher

3-DES uses 186-bit keys
AES uses 128, 143, 256-bit keys
128-bit key would be 2^72 harder to break than a 56-bit key and therefore not subject to exhaustive search attacks

What attacks would be better for 3-DES?
Why not use 2-DES?