Outline ======= - Review block cipher modes of operation; CBC-MAC, which is not always secure - Review definition of security; need to randomize; UFE - Finite fields, number theory - Information-theoretically secure MAC Block cipher modes of operation =============================== review from last time: ECB: c_i = E_k(m_i) CTR: c_i = m_i XOR E_k(IV + i) CBC: c_i = E_k(m_i XOR c_{i-1}), c_{-1} = IV another block cipher mode not mentioned last week: CBC-MAC construct a MAC out of a block cipher by running it in CBC mode w/ IV=0 use the last ciphertext block as MAC value in general, CBC-MAC is broken for variable-length messages even if IV is 0, adversary can change one plaintext block, splice msgs making CBC-MAC secure for var-length msgs: different key for last round! lots of alternative designs, problem set asks you to break one of them IND-CCA: adversary plays a game, guessing which of two plaintexts is encrypted observation: encryption must be randomized in order to be IND-CCA secure sketch of IND-CCA secure mode without ciphertext expansion (Desai's UFE): observation: must include random bits (IV) in ciphertext for decryption goal is to prevent meaningful decryption of tampered ciphertexts tangle the random bits with a MAC of the ciphertext e.g. XOR the IV and CBC-MAC of the ciphertext (under a different key) m random IV | | V +----------+ | (+)<-------| CTR (k1) | <--------+ | +----------+ | | | | +------------------+ V +---> | CBC-MAC (k2, k3) |---->(+) | +------------------+ | | | V V c0 c1 UFE: "unbalanced feistel encryption" be careful using CBC-MAC with variable-length messages! one solution is to use a different key (k3) for last round of CBC-MAC CTR itself is not IND-CCA secure, because IV randomness can be tampered with see Desai's paper for more details on why UFE construction is secure Finite fields, number theory review =================================== field: set S and two operations: + and * (addition and multiplication) S must contain two special elements 0 and 1 S under + is an abelian group with identity element 0 i.e., closed, associative [(a+b)+c=a+(b+c)], commutative [a+b=b+a], invertible [for all a, there exists b such that a+b=0], inverse intuitively called -a S^* (S except 0) under * is an abelian group with identity element 1 again, closed, associative, commutative, invertible inverse intuitively called a^{-1} the operations + and * are tied together with the distributive law: a*(b+c) = a*b + a*c as a corollary due to commutativity, (a+b)*c = a*c + b*c well-known fields: R (reals), C (complex), Q (rational) note: Z (integers) is not a field: not closed under multiplicative inverse cryptography usually works in a finite field common: Z_p (integers mod p) -- a field for any prime p most algorithms for integers work in finite fields, e.g. solve linear eqn: ax + b = 0 (mod p) x = a^{-1} * (-b) (mod p) 3x + 5 = 6 (mod 7) 3x = 1 (mod 7) x = 3^{-1} * 1 (mod 7) x = 5 (mod 7) finite field of q elements denoted by GF(q): galois field thm: if q=p^k, where p is prime and k>=1, then finite field GF(q) exists case: k=1, GF(p) is Z_p, integers mod p Z_p = { 0, 1, 2, ..., p-1 } Z_p^* = { 1, 2, .., p-1 } case: k>1, GF(p^k) elements can be thought of as polynomials of degree up to k-1 polynomial coefficients are from GF(p) multiplication happens modulo some fixed polynomial of degree k common: GF(2^k); e.g. AES performs many transformations in GF(2^8) will not spend as much time with these kinds of finite fields performing operations efficiently addition, multiplication: modular arithmetic subtraction: -a = p-a exponentiation (a^b): repeated squaring a in field b integer / 1, if b = 0 | a^b = { (a^{b/2})^2, if b is even | \ a * a^{b-1}, if b is odd instead of b multiplications, requires at most 2*log(b) multiplications fast in practice: ~millisecond to do 1024-bit modular exp on laptop O(k^3) time for k-bit inputs computing inverses / division: fermat's little theorem: a^p-a divisible by p in GF(p): a^p == a, or a^{p-1} == 1, or a^{p-2} == a^{-1} finding large (k-bit) primes: keep picking random numbers, test if they're prime, repeat if not primes are dense, so this works well prime number theorem, approximately: numbers around x are prime with prob. 1/ln(x) how to check for primality? converse of fermat's little theorem is "almost" true i.e. for candidate p, check for some x, if x^{p-1} == 1 (mod p) will be true if p is prime "likely" to be false if p is not prime (w.h.p. if p chosen randomly) usually test with x=2 there is a deterministic test due to Agrawal, Kayal, and Saxena (2002) in practice it's slower than the probabilistic testing if adversary doesn't choose prime, probabilistic testing suffices Info-theoretic secure MAC ========================= recall that we've seen cryptography under different assumptions encryption: stream and block ciphers are computationally secure one-time pad (OTP) is information-theoretic secure authentication: hash functions (and HMAC) are computationally secure is there an information-theoretic secure MAC? goal: want MAC_k(m) to say nothing about MAC_k(m') if m != m' regardless of adversary's computational power e.g. adversary is free to brute-force every possible key HMAC is not secure in an information-theoretic sense adversary can try every key, get a small number of possibilities maybe more than one because of hash collisions even so, still breaks MAC: adversary can compute MAC_k(m') with high prob. is it possible to construct a perfectly-secure MAC? secure but very expensive naive design choose random k_m for each message m ahead of time adversary has no idea what k_{m'} could be, given k_m observation: need key to be larger than MAC n-bit MAC value narrows down possible keys by 2^{-n} for unbounded adversary more efficient idea: think of a key as a linear function in Z_p (i.e., a*x+b) pick a large prime p (e.g. p = 2^{128} + 51) message must be a number mod p (so, 0 <= m < p) key is k = (a,b), where 0<=a