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?
  • We always add the padding!

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}^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.