Problem $3.$ Let $E$:$\{0,1{\}}^n\{0,1{\}}^n\{0,1{\}}^n$ be a function family. For each Kin$\{0,1{\}}^n,$ let

CBCMAC$[E_K]$:$(\{0,1{\}}^n{)}^{+}\{0,1{\}}^n$

be the standard CBC$-$MAC construction. Let $F$:$(\{0,1{\}}^n\{0,1{\}}^n)(\{0,1{\}}^n{)}^{+}\{0,1{\}}^n$ be

defined as follows: for all $K1,K2in\{0,1{\}}^n$ and Min$(\{0,1{\}}^n{)}^{+},$ let

$F_{K1,K2}(M)=F(K1,K2,M)=E_{K2}(CBCMAC[E_{K1}](M)).$

One can prove that if $E$ is a good PRF then $F$ is a good $($VIL$-)$PRF$.$

A widely used standard employs this construction as its PRF$.$ However, this standard also ex$-$

poses $V=MSB(s,E_{K1}(0^n))$ as an operational guarantee that the correct key $K1$ is begin used. ${?}^1$

This turns out to be a very bad choice.

Assume that $s=\frac{n}{2}.$ Given $V,$ give a PRF$-$attack that takes something like $2^{\frac{n}{1}}$ oracle queries to

distinguish $F$ from a random function. $($Hint: consider messages of the form $0^n||(x||R)$ for fixed

xin$\{0,1{\}}^s$ and random Rin$\{0,1{\}}^{n-s},$ and messages of the form $(xo+V)||R^{\text{'}}$ for random $R^{\text{'}}.)$

Notice that this is the square root of the number of queries one would hope it would take.

${?}^1$ The function $MSB(s,x)$ returns the most$-$significant $s$ bits of string $x.$