- 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

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!

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!

Let $m = m*1, m*2, \dots, \m_n$ after we divide it into $n$ equal sized chunks.

In ECB, $c = E(m) = E(m*1), E(m*2), \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?
- We always add the padding!

TODO: Look into padding oracle attacks!

- ECB reveals $m
*i = m*j$ because $c*i$ will equal $c*j$ - ECB doesn't hide the patterns across message blocks very well

- $m = m
*1, m*2, |m_2| \lt b$ - Encrypt the first block $c
*1 = E(m*1)$ and steal part of it $p$ and include it in $c_2$ - $c
*2 = E(m*2 | c_2)$ - Let $c
*1'$ be $c*1$ without $p$ You output $c*2 | c*1'$ (you switch them)

- Let $i$ be our counter
- $c
*i = E(i) \xor m*i$ - 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

To encrypt:

- pick a random IV $i$
- $c
*1 = E(m*1 \xor i)$ - $c
*2 = E(m*2 \xor c_1)$ - $c
*3 = E(m*3 \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

- Note: IV has to be set to zero!
- 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

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

- $c
*1 = m*1 \xor E(i)$ - $c
*2 = m*2 \xor E(c_2)$ - ...
- One advantage over CBC is that you don't need padding for CFB
- It uses XOR to compute the ciphertext

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

- define $E, D$ operations for encrypting and decrypting under $k$
**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 $m
*0$ and $m*1$ of the same length

**Phase II:**- Examiner picks $d \leftarrow {0,1}$ randomly
- examiner outputs $y = E(m
*d)$ 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 ($m
*0$ or $m*1$) 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 $m
*0$ and $m*1$ 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 $m
*0$ and $m*1$

- CBC mode is bad because can flip bits in $c
*1$ and encryptions of $c*2, 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

- Better be randomized

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}^b$

$c$ is CBC MAC'd under $k*2, k*3$ and result is XORed with $r$, obtaining $\sigma$

Ciphertext is $(c, \sigma)$

How does he decrypt?

See this paper for more details.