Outline
=======

 - Review from last time: encryption, randomness
 - Block ciphers
 - DES, AES
 - Modes of operation
 - Defining security

Administrivia:
    PS1 due Friday, PS2 will be out on Friday
    Victor's office hours today (Wednesday) 4-5pm; check course web site

Review
======

encryption: OTP, stream ciphers, generating random bits

Block ciphers
=============

different construction: encrypt a block of b bits at a time
    typically b = 64 or 128 bits
    pseudo-random permutation, modulated by key (DES: 56 bit, AES: 128/192/256)

		  p: plaintext
		  |
		  V
	      +-------+
    key k --> |  Enc  |
	      +-------+
		  |
		  V
		  c: ciphertext = E_k(p)

    ideal block cipher: a random permutation for each value of k

DES
===

outdated, but interesting to see what the structure looks like
common structure for designing a block cipher: feistel network

	L0	       R0	two halves of the plaintext
	|		|
	V     +---+	|
       (X)<---| f |<----+	each round's f takes k_i as input (not shown)
	|     +---+	|
	\-----\		|
	       \	|
	/------	\ ------/
	|	 \		N rounds of R_{i+1} = L_i XOR f(k_i, R_i)
	|	  \-----\		    L_{i+1} = R_i
	|		|
	V     +---+	|
       (X)<---| f |<----+
	|     +---+	|
       ...	       ...
	|		|
	V		V
	L		R	two halves of the ciphertext

k_i values derived from block cipher key k according to some key schedule
note: invertible by design, for any key schedule and function f

function f(32-bit input, 48-bit round key)
    32-bit input expanded to 48-bit input (half the bits duplicated)
    XOR round key and 48-bit input
    look up each of 8 6-bit groups in a 6-to-4bit table (substition box / Sbox)
	key property: non-linearity
    permute the resulting 32-bit value
	key property: diffusion
	bits from one s-box end up in different s-boxes next round

problems:
    key is too short (breakable in hours)
    differential attacks (Eli Biham and Adi Shamir, 2^47 chosen plaintexts)
	obtain encryptions of M and M XOR D, where D has a single bit set
    linear attacks (Matsui, 2^43 plaintext/ciphertext pairs)
	observe that a linear relation holds between some key bit & PT/CT bits
	with probability 1/2+epsilon.
	need 1/epsilon^2 samples to guess key bit.

AES
===

starting in 1997, NIST held a competition to choose a replacement for DES
winner was an algorithm called Rijndael (by Daemen and Rijmen)
parameters: 128-bit block size; 128-, 192- or 256-bit keys; 10, 12, or 14 rounds

represent the 128-bit data/state as an 4x4 array of bytes

    +-+-+-+-+
    |a|b|c|d|
    +-+-+-+-+
    |e|f|g|h|
    +-+-+-+-+
    |i|j|k|l|
    +-+-+-+-+
    |m|n|o|p|
    +-+-+-+-+

each round:

    1. AddRoundKey: XOR the round key (also 4x4 array) into the state
    2. SubBytes: look up each byte of array in a 256-entry S-box (permutation)
	S-box constructed as an inversion over GF(2^8) mod a fixed polynomial
	(good non-linearity, prevent linear/differential cryptanalysis) plus
	an affine transform (ax+b) on each byte (to avoid purely-algebraic
	relations that allow other cryptanalysis)
    3. ShiftRows: cyclically shift i'th row of state matrix by i:

	    abcd    abcd
	    efgh    fghe
	    ijkl -> klij
	    mnop    pmno

    4. MixColumns: transform each column [in last round, do AddRoundKey instead]
	(some invertible linear transformation)

to decrypt, run backwards: all steps are invertible
fast in software: 200MB/sec on my laptop
    can implement using just table lookups and XORs
    16 lookups in 4 256x32-bit tables (4KB ROM), 16 32-bit XORs per round

weaknesses:
    not enough rounds: 2^39 attack on 9-round variant of AES-256 (out of 14)
    weak key schedule for 256-bit variant (128-bit key schedule better)

Modes of operation
==================

given a block cipher primitive, how to encrypt variable-len msgs?
    typically, break up message into b-bit blocks, encrypt a block at a time
    many ways to do this, called "modes of operation"; we will cover a few
    many modes require padding to an even block boundary
	(compare to stream ciphers, where it's easy to encrypt any # of bits)
    few possibilities: include length first, or DES-style padding (1 + N 0's)
	must be invertible, otherwise cannot reliably decode message
    denote m = m_0 || m_1 || m_2 || .. || m_n, where each m_i is b bits long

simplest: ECB (Electronic Code Book)

	m_0		m_1		m_2		m_n
	 |		 |		 |		 |
	 V		 V		 V		 V
	+-+		+-+		+-+		+-+
    k ->|E|	    k ->|E|	    k ->|E|	    k ->|E|
	+-+		+-+		+-+		+-+
	 |		 |		 |		 |
	 V		 V		 V		 V
	c_0		c_1		c_2		c_n

    decryption: reverse
    advantage: no synchronization required (other than block boundary)
	unlike stream ciphers, and later modes, can decrypt at any offset
    problem: if two plaintext blocks are the same, the ciphertexts will be equal
	bad if your data has patterns (many zeroes, repeated headers, etc)
	repeated unit can be very small (e.g. 64-bit for DES, 128-bit for AES)
	OK for encrypting random data, such as keys
    problem: malleable (tweaking one CT block only tweaks one PT block)
	no "diffusion" outside of each block
	not a problem if there's a MAC on the outside
	if a MAC is not an option, may need to rely on encryption's diffusion

CTR (Counter Mode)

	 i		i+1		i+2		i+n
	 |		 |		 |		 |
	 V		 V		 V		 V
	+-+		+-+		+-+		+-+
    k ->|E|	    k ->|E|	    k ->|E|	    k ->|E|
	+-+		+-+		+-+		+-+
	 |		 |		 |		 |
	 V		 V		 V		 V
  m_0 ->(+)	  m_1 ->(+)	  m_2 ->(+)	  m_n ->(+)
	 |		 |		 |		 |
	 V		 V		 V		 V
	c_0		c_1		c_2		c_n

    use a block cipher to generate a pseudo-random pad
	much like a stream cipher
    decryption: re-compute "pad" and XOR

    doesn't have the "determinism" problem of ECB
	same plaintext block can have different ciphertexts
    malleability: still no diffusion outside of each block
    requires synchronization on i (can send along with ciphertexts)
	usually called an "initialization vector" (IV)
	here, IV should not be reused (otherwise, OTP reuse!)

CBC (Cipher Block Chaining)

	m_0		m_1		m_2		m_n
	 |		 |		 |		 |
	 V		 V		 V		 V
  IV -->(+)	+------>(+)	+------>(+)	+------>(+)
	 |	|	 |	|	 |	|	 |
	 V	|	 V	|	 V	|	 V
	+-+	|	+-+	|	+-+	|	+-+
    k ->|E|	|   k ->|E|	|   k ->|E|	|   k ->|E|
	+-+	|	+-+	|	+-+	|	+-+
	 |	|	 |	|	 |	|	 |
	 +------+	 +------+	 +------+	 |
	 |		 |		 |		 |
	 V		 V		 V		 V
	c_0		c_1		c_2		c_n

    decryption:
	decrypt each block
	XOR decrypted block with previous ciphertext (or IV for block 0)
	highly-parallelizable (but not for encryption)
    less need for synchronization: can decrypt starting at any point
    IV should not be reused (otherwise can tell equality between first blocks)
    IV should not be predictable
	random IV works best
	if need to re-use IV (e.g. no place to store random IV), make it secret
    malleability: tweaking ciphertext changes two plaintext blocks

    can sometimes use CBC as a MAC, with a fixed IV ("CBC-MAC")
	treat last ciphertext as MAC
	bad idea to use same key for MAC and encrypt, esp. when using CBC-MAC!

CTS (Ciphertext Stealing)

    suppose the plaintext is not a multiple of b bits
    pad the plaintext with z zero bits to a multiple of b bits
    can recover last z bits of c_{n-1} from c_n
	decrypt c_n, last z bits of decrypted c_n are the z bits of z_{n-1}
	because the corresponding plaintext bits XOR'ed into it were zero
    thus, can omit z bits of c_{n-1} on transmission: no ciphertext expansion
    what happens if we encrypt just one block?
	the IV is the "previous" block's ciphertext
	if we are sending along the IV, can truncate IV to fewer bits
	if the IV is pre-computed by both sender and receiver, no luck

CFB (Cipher Feedback)

	 IV	+--------+	+--------+	+--------+
	 |	|	 |	|	 |	|	 |
	 V	|	 V	|	 V	|	 V
	+-+	|	+-+	|	+-+	|	+-+
    k ->|E|	|   k ->|E|	|   k ->|E|	|   k ->|E|
	+-+	|	+-+	|	+-+	|	+-+
	 |	|	 |	|	 |	|	 |
  m_0 ->(+)	| m_1 ->(+)	| m_2 ->(+)	| m_n ->(+)
	 |	|	 |	|	 |	|	 |
	 +------+	 +------+	 +------+	 |
	 |		 |		 |		 |
	 V		 V		 V		 V
	c_0		c_1		c_2		c_n

    similar to CBC
    decrypt: encrypt the previous ciphertext block (or IV), then XOR
    advantage: only run the block cipher forward (avoid CCA attacks on E)
    advantage: no need to pad last block to a multiple of b bits

Many other modes
    specifically, MAC + encrypt modes: CCM, EAX, OCB

Definition of security for encryption
=====================================

most block ciphers, stream ciphers aren't "provably" secure
    instead, cryptographers look for weaknesses and ways to avoid them
    e.g. diffusion, non-linearity properties mentioned in DES
    next week we'll start talking about number-theoretic cryptography..

suppose we assume the block cipher is "secure"; is some mode secure?

how to define security?  e.g. secure w.r.t. chosen-ciphertext attack (CCA)?
    one definition: IND-CCA (indistinguishable under chosen-ciphertext attack)
    definition is in terms of a game that adversary must win

    1. adversary chooses a pair of messages

	gets access to encryption and decryption oracles E_k and D_k (but not k)
	chooses two messages, m_0 and m_1, of equal length
	can remember some amount of state, as needed, for part 2

    2. examiner chooses one of two messages randomly

	b = random bit
	c = E_k(m_b)
	gives c to the adversary

    3. adversary tries to guess which message c corresponds to

	can continue to invoke E_k and D_k, except D_k(c)
	adversary outputs guess b'
	adversary wins if | P(b' == b) - 1/2 | is non-negligible

    a scheme is IND-CCA secure if there is no adversary that can win

is a block cipher IND-CCA secure?
    no, adversary can just encrypt m_0 and m_1
    must be randomized

are any of the modes IND-CCA secure?
    none of the above -- can decrypt first half of ciphertext and distinguish
    one alternative is to add a MAC on top of one of those modes to prevent CCA
    plus randomized mode (e.g. random IV)
    potentially wasteful: "ciphertext expansion" due to many invalid ciphertexts