notes

################################
Disclaimer: Notes taken for personal use; do not construe in the least bit
a guide or handout. Proceed to rely on these at your own risk!
###############################

1/3/2010
--------
Admin
Email ID: cs255ta@cs

SSL
PGP - privacy + dig signature
user auth - pwd management, smart cards, challenge-response
wireless - 802.11i, WEP, WPA2

Other
Elections
Auctions
Digital Cash
Copy Protection- DVD CSS, AACS
A5/1, A5/2 for GSM

History
Substitution cipher and breaking it
Vigenere's Cipher
Rotor Machines
DES
AES

Define block cipher
Vernam cipher, OTP

Shannon perfect secrecy definition - Pr over all keys for any 2 messages
and any ciphertext that E(k, m_i)=c is same.

1/5/2011
--------
Recap
Stream ciphers make OTP practical
  PRG, predictability and unpredictablity definitions
  weak PRG - linear congruential generator 
    broken
    glibc
    r[i]=r[i-3]+r[i-31] mod 2^32
  used in Kerberos v4

Attacks on OTP
  Two time pad - Project Venona and MPEE
  No integrity, i.e., malleability

  Hybrid encryption is better to use
  E(k, f) := AES(k, r) || f xor g(r)

RC4 discussion
  802.11b's RC4 implementation (WEP)

  m||crc(m) xor rc4(IV||k) = ciphertext
  publish (ciphertext, IV)

  Problem: IV is counter (sometimes), initializes to zero on reboot and
  frequently wraps around (2^24 IVs only)

  [FMShamir '01] first byte of RC4(0||k) ... RC4(10^6||k) => you can find k

Hardware stream ciphers
  LFSRs
  How they were badly used in DVD CSS, A5/1, Bluetooth E0

Good ciphers?
  ESTREAM project
  Trivium, well-designed for shift registers
  Different ciphers to be used on processors with word/double-word
  granularity
  For software implementation, Salsa20
  
1/10/2011
--------
Recap, OTP, Stream Cipher, Unpredictable, RC4, LFSR

Random bit generation
1. s/w generated: RFC 4086, NIST SP-800-90
entropy collector on a loop --> rng state (always xor new information so
that entropy can only increase)
- interrupt times
- scheduler

Linux /dev/random blocks, /dev/urandom never blocks 
OpenBSD had a bug

Windows has CNG (Crypto Next Generation) BCryptGenRandom (NIST SP-800)

2. h/w generated;
i810 chipset on Intel, unfortunately not used anymore
Thermal noise off of two transistors and then extractor applied

von Neumann extractor
01 sequence with bias p 
extractor (b1...b2n): for i=1 to 2n by 2, if bibi+1 = "01" output 1 else
output 0
rate was 75 kbps

glib() not cryptographically random
math.random() in js is not implemented correctly in (say) Safari

Block ciphers
DES - classic block cipher
History: LUCIFER cipher by IBM 1967 (128 bits key/block size)

Feistel Network
Design of the DES cipher
Talking about P-boxes and S-boxes

Abstraction of block cipher -- PRPs and PRFs. Formal syntactic and semantic
definitions

1/12/2011
---------
Pseudorandom Functions and Pseudorandom Permutations
F: K x X --> K

Security of PRFs -- indistinguishability of real world from ideal world

PRF switching lemma

Multi-message and single message definitions of security. CPA security.
Semantic security and the security of the OTP

Modes of operation, single message
1. ECB
2. Single-Key per use
3. Deterministic counter mode

Corresponding single message security definition

Modes of operation, multiple messages

Corresponding multiple messages definition

1. Nonce-based encryption
(k, n) pair is never ever reused
pick from sufficiently large space randomly, or use a counter
2. CBC with IV

1/19/2011
---------

Recap: PRP, PRF definitions
Semantic security of one-time key, i.e., single message
Modes of encryption: CTR, CBC. 

CPA security definition. Security of CBC - CPA analysis.
CBC with unique nonce

Randomized counter mode + CPA analysis
Nonce-counter mode 

Block cipher Attacks: DES requires 1 (PT, CT) pair to get unique key with
probability > 1-1/256. 2 (PT, CT) pairs => > 1-1/2^{72}. With 3 (PT, CT)
pairs, it is for all practical purposes 1. 

Proof: Consider \pi_1,...,\pi_2^{56} as 2^{56} permutations, one for each
key, from {0,1}^64 -> {0,1}^64. Idealized version. For every m, k 
Pr[\exists k_1 \neq k such that DES(k_1, m) = DES(k, m)] by union bound for
every possible key is 2^{56} x 2^{-64}. Therefore, we get 2^{-8} as
probability there is more than one key.

This generalizes to two, three, or multiple (PT, CT) pairs in a
straightforward manner.

Breaking DES.
1. DES challenge and some various benchmarks (distributed.net etc.) from
bruteforce

Strengthen it by using Triple-DES. E-D-E sometimes used to allow for
simultaneous implementation of single and triple DES. Sometimes E-D-E with
k3=k1 used. That is incorrect and there exist attacks.

Why not 2DES? Time-space tradeoff for MITM attack. Storage 2^56 =>
56.2^{56} attack exists, rather than 2^112.

2nd method to save DES: EX (k1, k2, k3, m) = k1 \xor E(k2, k3\xor m) If we
model black-box => best possible attack is 2^{|k1|+|k2|}
DESV and DESW are other possible fixes, but they're quite insecure.
Two-time pad for one of the keys either during encryption or decryption
unfortunately.

Side-channel attacks: Simple Power Analysis (SPA) Differential Power
Analysis (DPA)

1/24/2011
---------

Recap of various attacks on block ciphers. 

Linear and Differential Cryptanalysis overview. Differential cryptanalysis
requires more details. 

Linear cryptanalysis talks about biases in xors of specific bits. A small
bias of \eps will require about O(1/\eps^2) (PT, CT) pairs to get a good
confidence of those specific bits. 

DES: In the 5th S-Box there's a 2^-21 bias and that works out to getting 14
bits of information about the key with 2^42 (PT, CT) pairs. Therefore break
DES in 2^42 rather than 2^56. Over 1000 times faster than brute force
because of small linearity.

AES description and history behind the cipher. Rijndael.

Key -> Key expansion = Round keys -> Various rounds of encryption using a
PRF.

4-way independence conjecture. It states that irrespective of how the
function is implemented, following the general above scheme, if the number
of rounds can provably provide 4-way independence then the resulting cipher
is secure. 

Further detailed description of the AES encryption steps (4 steps) and the
roundkey expansion scheduling with 4x4 matrix notation.

Note, all but one step of AES is linear and even the SBox is implemented as
an inversion mod 256. This turns out to speed it up in hardware and
software.

Message Authentication Codes: Definitions, stress on requirement of a key
between parties -- malicious errors vs random errors.
WEP uses CRC, therefore guarantees no integrity.

Any secure PRF => secure MAC. sign(k,m)=F(k,m) if the output domain of the
PRF is large (otherwise simple guesses will lead to existential forgeries).

PRF=>MAC is inefficient. Use CBC-MAC and HMAC (in particular we'll discuss
NMAC). Small MAC => Big MAC is the problem. We can use small PRF => big PRF
constructions.

You can truncate a PRF and it is still secure. Same deal for MAC. Except
truncation will improve the adversaries advantage when guessing randomly. 

ANSI X9.19 standard.

1/26/2011
---------

Recap of message integrity. Raw CBC, Enc. CBC. Raw CBC secure only for
prefix-free messages.

CBC-MAC theorem: For every L > 0, F is a secure PRF over (K, X, X) => F_CBC
over (K^2, X^{\leq L}, X) defined as above satisfies:
PRFAdv [A, F_CBC] \leq PRFAdv[B, F] + (q^2 L^O(1))/|X|

Unfortunately it is sequential. Open problem for many years to make secure
parallel MAC. Answered in 2000.

PMAC construction. Let p(k, x) be a masking function.

Basically, you do m_i \xor p(k, i) and feed it to F(k_1, ) to get c_i. Output
F(k_2, \xor of all c_i) to be the MAC of the message blocks m1...mi...mL
Security term is 2L^2q^2/|X|

PMAC has advantages of being incremental. You can change one block of
message and not have to recompute the entire MAC.

Next construction is HMAC. We need to talk about collision resistant hash
functions. H: M -> T

Def of collision, and CRadv of adversaries -- some small discussion about
why it only makes sense if the adversary is uniform as opposed to
non-uniform. SHA-256, Whirpool and SHA-3 competition details.

Wang's attacks on MD5 and SHA-1, in 2005 and the need to design more secure
CRHFs.

Hash and MAC scheme. M^big -> M is a hash function. (K, M, T) is a MAC.
Then we can trivially construct BigMac for (K, M^big, T). Just hash it to M
and then use MAC. An existential forgery will break either the MAC or the
CHRF. 

Most general attack. Birthday attack. For outputs in |X| finding a
collision takes roughly \sqrt{|X|} time. 

Constructions: Iterated Merkle-Damgard construction. Message padding. Add
1000 || message length in 64-bits. Add dummy block if required. 

Lemma: If F is CRHF, then Merkle-Damgard construction is also collision
resistant. 

Proof. Basically iterate through the assumption of a collision through each
block starting backward. Either one of the intermediate steps there's a
collision and therefore we're done, or the two messages are the same and
there's a contradiction. Requires a little more argument to work out the
details, including padding block, different length messages etc.

Therefore beauty of this theorem -- suffices to construct a compressing
function that is CR for small domains. No need to worry about larger
constructions once we get this done. 

How to? Davies-Meyer construction. 

F(m, h) := E(m, h) \xor h

Here m acts as the key, and h acts as the message for the block cipher.
Difficult to prove security. Instead we assume ideal cipher model, which
states that E is basically as set of |K| random permutations which is
clearly not the case when you instantiate E with any succint program.

Thm: Suppose E_k(x) = E(k, x) is a collection of |K| random permutations
functions on X then finding a collision in Davies-Meyer will take at least
2^{n/2} evaluations of E where E(k,x) has outputs in {0,1}^n

1/31/2011
---------

R$ecap: Collision resistant hash functions. Compression function (say,
Daview-Meyer) + M-D paradigm.
Birthday attack.

Provable compression functions. F_{g, h, p} = g^a h^b mod p
Theorem (HW) Finding collision on F => d-log in group
Provable hash functions are really slow

Data integrity (MAC)
- Any PRF is a secure MAC (eg. AES) 
Problem: small PRF => big PRF

Suppose we have H: M -> T is a M-D hash function
MAC from H
Attempt 1: S(k, m) = H(k||m) vulnerable to extension attack trivially,
since the compression function is publicly known.
Attempt 2: HMAC
S(k, m) := H(k \xor opad || H(k \xor ipad || m)), where opad, ipad are
constants

Thm: If compression function f, is a PRF (with either of the two inputs to
be key) then HMAC is a secure PRF (and also secure MAC)

TLS: Must support HMAC-SHA1-96

Note, if H is CHRF, F is secure MAC => s(k, m) := F(k, H(m)) is a secure
MAC

Authenticated encryption: CPA security (semantic security multi-use key)
and CT integrity (dec rejects modified CT)
C.I. Game: Queries return E(k, m_i) and the adversary forges a ciphertext
that is not rejected, and not one of the outputs of previous challenges.

How does WEP do it?

m || CRC(m) 32 bits
\xor
RC4(IV||k)
-------------------
CT

CRC is inherently a linear function. \exists F such that CRC(m \xor b) =
CRC(m) \xor F(b)

Now, it is easy to see how you can find a forgery. Modify the corresponding
bits in the ciphertext and also modify CRC so that it will work even under
the encryption of RC4.

Constructions using MAC and Encryption black-boxes.
Say, MAC I=(S, V) that is EUF and cipher (E, D) that is CPA secure.

1. MAC-then-Encrypt (SSL/TLS)
t <- S(k-mac, m), c <- E(k-enc, m||t) output c

2. Encrypt-then-MAC (IPSec)
c <- E(k-enc, m) t <- S(k-mac, c) and output (c,t)

3. Encryt-and-MAC (SSH)
c <- E(k-enc, m), t <- S(k-mac, m) send across (c,t)

(3) is not generically secure, because MAC doesn't need to protect secrecy
of the message
(1) is also problematic. There are artificial MAC and Enc schemes such that
(1) fails.

(2) is the best way to do it. Because c hides all information about m, and
t makes sure there can be no modifications of c.

(1) and (3) are perfectly fine for (rand-CBC-enc and PRF-mac) but you can't
assume what MAC/Enc schemes are given.

Note: k-enc and k-mac are independent keys 
eg. k-enc <- prf(k, "enc") and k-mac <- prf(k, "mac")

Exception is CCM 802.11i standard -- the PRF is evaluated the message
spaces do not intersect.
- compute mac on [ctr || type || version || len || payload] ctr is not sent
in payload (because it runs on TCP and assumes it is synchronized).
- pad to 3DES block size (8 bytes)
- encrypt with (IV, k-enc)
- prepend header and transmit

First dec, then check pad, structures, and finally, check mac.

TLS 1.0 - if pad is invalid, send "dec failed" message
if mac is invalid, send "bad record mac" message
(was fixed in 1.1, always send dec failed)

** Don't reveal why it failed **

So far, we have authenticated encryption from CPA+MAC

Can we build authenticated enc from PRF directly?
Ans: OCB mode (very similar to PMAC)

2/02/2011
---------

Sharing keys between n players. O(n^2) keys required.
Better:- KDC. 

An example of a scheme requiring nonces etc. 
Some of the drawbacks, TTP required, and a single point of failure. The
advantage is it requires symmetric ciphers only. To get asymmetric ciphers,
you require lots more theory.

Public Key Crypto! 

Introduction to groups, modular arithmetic.

2/07/2011
---------

Recap of groups/modular arithmetic
Exponentiation
Public-key encryption
Diffie-Hellman
Discrete Log

2/09/2011
---------

Discussion of various groups. Elliptic curves

Pollard Rho and General Number Field Sieve time bounds
Diffie Hellman and ElGamal encryption

Hybrid encryption scheme -- ElGamal hybrid encryption
ElGamal CPA secure under random oracle and DDH.

Motivation and definition of CCA security -- makes sense for PKC

Thm: ElGamal system is CCA secure under random oracle, "interactive"-DH
assumption, and the symm cipher is EUF-CMA/CPA secure.

Trapdoor one-way function

A CCA secure scheme using TDFs. 

Number theoretic construction of TDFs -- RSA function and some background
about the Euler \varphi function.