Today: Ciphers II, Wed. March 4th, 2015

Today's project idea: "Program obfuscation"

Ideal block cipher

What should an ideal block cipher look like?

Remember an ideal hash function was the "random oracle."

$$ Enc(k, m): {0,1}^b \times {0,1}^b -> {0,1}^b $$

What we want: for each key $k$: $Enc(K, \cdot)$ is a random permutation of the message space ${0,1}^b$

Just like we assumed random oracles for hash functions, we also assume random block ciphers that are ideal!

Modes of operation

Better term would be domain extension.

What definition can we give for security of a mode of operation?

We'll see that all these modes are hopefully bad under current definition of security.

We assume a fixed input length block cipher that we want to transform into a variable input length encryption mode!

Electronic Code Book (ECB) mode

Let $m = m1, m2, \dots, \m_n$ after we divide it into $n$ equal sized chunks.

In ECB, $c = E(m) = E(m1), E(m2), \dots, E(m_n)$

If message length is not a multiple of cipher block size $b$ we can pad it out.

TODO: Look into padding oracle attacks!

Ciphertext stealing

Counter mode (CTR)

Cipher Block Chaining (CBC) mode

To encrypt:

Note: You need padding if your last block is $\lt b$, where $b$ is the cipher's block size.

To decrypt:


Cipher block chaining can be used for Message Authentication Codes (MACs).


                m, MAC(k, m)                    k
    Alice -----------------------------------> Bob 
                                Bob checks if MAC is correct for k and m

What can we use a MAC? We sort of need a complicated function of every block of the message and the key $k$

Authentication and confidentiality

What can you do to get both? Encrypt plaintext $p$ into $c$. Then compute MAC over $c$.

Cipher Feedback (CFB) mode

Are these modes any good?

Chosen ciphertext attack (IND-CCA)

IND-CCA2 game:

Note: The encryption scheme better be randomized or stateful if it's gonna satisfy this

LOL: We can do exams the same way: Have all students come up with a question and then let them take the exam. One student mentioned they can share questions and win the game. Ron said "yes, but you'd still have to solve them so I would win because you would learn the material"

Definition: Encryption scheme is IND-CCA secure if adversary wins with probability $1/2 + \epsilon$ where $\epsilon$ is negligible

Which modes satisfy IND-CCA2?

How do we fix these modes?

Unbalanced Feistel Encryption

We take an arbitrarily long message $m$ and we encrypt it by XORing it with a pad, that we obtain by running a block cipher in counter mode under some key $k_i$ and encrypting a random value $r$.

The problem with CTR mode was that the initial value for the counter was transmitted in the clear over the wire.

We take a random value $r$ in ${0,1}^b$

$c$ is CBC MAC'd under $k2, k3$ and result is XORed with $r$, obtaining $\sigma$

Ciphertext is $(c, \sigma)$

How does he decrypt?

See this paper for more details.