$($Android Keystore Attack$)$

Let E : $\{0,1\}$k $\backslash$times $\{0,1\}$n $->\{0,1\}$n be a good blockcipher. Let CBC$[$E$].$Enc$($K$,$M$)$ denote the encryption of a message M under the CBC mode of blockcipher E under key K$,$ and define CBC$[$E$].$Dec$($K$,$C$)$ for decryption similarly. For simplicity, assume that here we only deal with full$-$block messages. Let H : $\{0,1\}->\{0,1\}$n be a hash function.

A recent implementation in Android Keystore uses the following authenticated encryption scheme: to encrypt a message M under the key K$,$ we output CBC$[$E$].$Enc$($K$,$H$($M$)\backslash |$ M$).$ For decryption, given the key K and ciphertext C$,$ we first run CBC$[$E$].$Dec$($K$,$C$)$ and parse the result as T$\backslash |$ M$,$ where $|$T$|=$ n$.$ We then output M if T $=$ H$($M$),$ and output $$ otherwise. In some sense, it$$s similar to the Encrypt$-$with$-$Redundancy paradigm that we studied and broke in class. However, the main difference here is that the redundancy H$($M$)$ is put at the beginning of the message, instead of at the end.

Show that the Android encryption scheme is insecure by giving an authenticity attack.