Problem $4.$ Attacks on CBC$.$

a$.$ In class we discussed the ECBC $($encrypted CBC$)$ MAC for messages in $xL$ where $x=$

$\{0,1{\}}^n.$ Recall that RawCBC is the same as ECBC, but without the very last encryption

step. We showed that RawCBC is an insecure MAC for variable length messages. Here we

show a more devastating attack on RawCBC. Let $m_1$ and $m_2$ be two multi$-$block messages.

Show that by asking the signer for the MAC tag on $m_1$ and for the MAC tag on one additional

multi$-$block message $m_2^{\text{'}}$ of the same length as $m_2,$ the attacker can obtain the MAC tag on

$m=m_1||m_2,$ the concatenation of $m_1$ and $m_2.$

b$.$ Let's see a real$-$world attack on CBC encryption with a predictable IV$.$ Suppose Bob uses

AES$-$CBC encryption with key $k$ to encrypt blocks on disk, where each block is $4096$ bytes

long $(4$KB$),$ the default block size for Linux. Disk block number $i$ is CBC encrypted with

key $k$ and using an IV equal to the binary representation of $i.$ This ensures that if two blocks

on disk hold the same data, they result in different ciphertexts. Note that there is no need to

store the IV with the ciphertext because the IV is derived from the block number. Moreover,

if a single file spans multiple disk blocks, then each disk block is AES$-$CBC encrypted on its

own. All disk blocks are encrypted using the same secret key $k.$

Suppose an authoritarian regime publishes a subversive video $m$ and Bob stores $m$ encrypted

on his disk. Later, Bob's machine is seized and the authoritarian regime wants to test if Bob's

disk contains an encrypted copy of $m($if so$,$ Bob may have some explaining to do$).$ If this

were possible, it would be a serious violation of semantic security.

Show that the regime can create a multi$-$block video $m$ for which it is easy to test if the

encrypted $m$ is stored on Bob's disk. You do not know the block number where $m$ will be

stored on Bob's disk. However, you may assume that $m$ is block$-$aligned, that is$,$ the first byteof $m$ is stored as the first byte of some block on disk, byte number $4097$ of $m$ is the first byte

of the next consecutive block, etc. If $m$ is stored on Bob's disk then your test should always

say "yes". For simplicity, you may assume that all other content stored on Bob's encrypted

disk is random bytes.

Hint: Try to design a message $m$ that when encrypted as described above results in a sequence

of encrypted disk blocks, each $4096$ bytes long, where some two consecutive encrypted blocks

begin with the same sequence of $16$ bytes. It may help to first answer the question assuming

the first encrypted block of the message $m$ is stored in block number $i,$ where $i$ is an $($unknown$)$

even number. Then generalize your answer to an arbitrary $($unknown$)i.$

Note: in practice, disk encryption systems that use AES$-$CBC$,$ set the IV for block $i$ to be

AES$(k^{\text{'}},i),$ where $k^{\text{'}}$ is an independent secret key. This prevents your attack.