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

• Ideal block cipher: what might this be?
• Modes of operation
• ECB, CTR, CBC (Cipher Block Chaining), CFB (Cipher Feedback Mode)
• Ideal (IND-CCA defn)
• Desai's "UFE" mode (Unbalanced Feistel Encryption)
• Project idea: "Program Obfuscation"

Today's project idea: "Program obfuscation"

• How do you take a program $P$ and give it to $A$ so that $A$ can execute it but not reverse engineer it

## 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.

• Add $1$ and as many zeros as needed to get to multiple of $b$ bits.
• What if message actually finishes like this?

TODO: Look into padding oracle attacks!

• ECB reveals $mi = mj$ because $ci$ will equal $cj$
• ECB doesn't hide the patterns across message blocks very well

#### Ciphertext stealing

• $m = m1, m2, |m_2| \lt b$
• Encrypt the first block $c1 = E(m1)$ and steal part of it $p$ and include it in $c_2$
• $c2 = E(m2 | c_2)$
• Let $c1'$ be $c1$ without $p$ You output $c2 | c1'$ (you switch them)

### Counter mode (CTR)

• Let $i$ be our counter
• $ci = E(i) \xor mi$
• No padding issues because we can just XOR as many bits as we have in the last block
• $i$ value can be sent in the clear to allow people who have the key to decrypt
• You shouldn't reuse the $E(i), E(i+1), ...$ pad (just like in OTR)
• This means use different $i$'s for different messages
• Important: If you encrypt $n$ blocks with IV $i$, then your next IV should be $\gt i + n$
• Note that since AES is a PRP, you will never see repetitions among the $E(i)$ pads
• If AES was a PRF, you would start seeing repeated $E(i)$'s after $\approx 2^64$ encryptions

### Cipher Block Chaining (CBC) mode

To encrypt:

• pick a random IV $i$
• $c1 = E(m1 \xor i)$
• $c2 = E(m2 \xor c_1)$
• $c3 = E(m3 \xor c_2)$
• ...

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

To decrypt:

• note that we can parallelize

IVs:

• $i = Enc(k, nonce)$
• TODO: not clear this is a good idea, look into requirements for CBC IVs

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

• integrity and authentication of message can be a goal sometimes
• we want Bob to only accept a message if it was sent by Alice

Example:

                m, MAC(k, m)                    k
Alice -----------------------------------> Bob
k
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$

• We can use the last block in CBC mode
• Note: IV has to be set to zero!
• TODO: lookup attack from SBU
• If you deal with variable length messages, you have to further tweak this by making the key for the last block different
• TODO: why? prevents a certain class of attacks

#### Authentication and confidentiality

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

• TODO: explain why MACing $p$ can be bad

### Cipher Feedback (CFB) mode

• $c1 = m1 \xor E(i)$
• $c2 = m2 \xor E(c_2)$
• ...
• One advantage over CBC is that you don't need padding for CFB
• It uses XOR to compute the ciphertext

## Are these modes any good?

### Chosen ciphertext attack (IND-CCA)

IND-CCA2 game:

• key $k$ picked at random (adversary does not see it0
• define $E, D$ operations for encrypting and decrypting under $k$
• variable input length encryption
• Phase I: Let the adversary play around w/ encryption, decryption boxes
• will decrypt or encrypt or both anything the adversary wants
• at the end, adversary output two message $m0$ and $m1$ of the same length
• Phase II:
• Examiner picks $d \leftarrow {0,1}$ randomly
• examiner outputs $y = E(md)$ as the _challenge ciphertext
• adversary is given $y$ and access to $E$ and $D$
• examiner will not let adversary decrypt $y$
• adversary should not be able to tell which message ($m0$ or $m1$) was encrypted
• adversary picks $d\hat when he's sure and outputs it • he wins if$d = d\hat$or loses otherwise Note: The encryption scheme better be randomized or stateful if it's gonna satisfy this • randomized encryption will not let adversary to just encrypt$m0$and$m1$and do a simple equality test on$y$• or it could be stateful and remember it encrypted$m$before and output a different ciphertext the 2nd time 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? • ECB mode is deterministic, so won't win • CTR mode is bad because in Phase II adversary can take$y$, flip a bit and ask the examiner to decrypt it • examiner will do it • adversary can see clearly whether result is$m0$and$m1$• CBC mode is bad because can flip bits in$c1$and encryptions of$c2, c_3, ...$will stay the same • Another attack is to take a prefix of the ciphertext and ask the decryption box to decrypt it • you can the tell between results • Bad property that these modes have w.r.t/ IND-CCA2: decrypt prefix of ciphertext$\Rightarrow$you get the prefix of message #### How do we fix these modes? • Better be randomized ## 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. • TODO: Problem as in overhead? We take a random value$r$in${0,1}^bc$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.