Recall that AES uses a 128-bit key and encrypts 128-bit messages into
128-bit ciphertexts.  Suppose AES is secure, i.e. it is difficult
for an attacker to distinguish AES_k from a random function R.  Which
of the following ciphers are secure?

When you claim that E is secure, you do not need to justify your
answer.  When you claim that E is insecure, you should describe how
you would distinguish E from a random function efficiently.

Note: assume that all the sizes of objects below work out.  For
example, 11...1 in (2) must be a 128-bit vector of all 1s; In (6), k
and m must both be 256-bits; etc.

1. E(k,m) = k xor m
2. E(k,m) = AES(k,m) xor 11...1
3. E(k,m) = AES(00...0,m)
4. E(k,m) = AES(0...0,m xor k)
5. E(k,m) = AES(k1, AES(k0, m)), where k=(k0,k1), i.e. k is a 256-bit value.
6. E(k,m) = AES(k0, m0) | AES(k1, m1), where k=(k0,k1) and m=(m0,m1)
            and "|" is concatenation.
7. E(k,m) = AES^-1(k, AES(k,m) xor 11...1)



Discussion:

For E(k,x) = k xor x, the following distinguisher works:


          Given F, Let y1 = F(x1).
                       Let y2 = F(y1).
                       Then, F is E if y2 == y1, otherwise F is something


Here's another way of describing the problem:

I set up a server on the internet, and you can send a block of data, x,
to the server, and it will send you back a block of data y = F(x).  You
can send it as many blocks as you like.  Your goal as an attacker is to
figure out, "What is the function F implemented in the server?"

Now, you do know a little about the server's function, F.  When I set up
the server, I did one of two things: (1) I picked a key, k, and set F(x)
= E(k,x), or (2) I made a gigantic table:

x   | y
-------
0   | y0
1   | y1
2   | y2
etc.

There's an entry in the table for every possible value of x, and the y
values are completely random.  To compute F(x), the server just looks up
x in the table and returns the corresponding y value.


So let's see what happens when you pick a random x, obtain y1 = F(x)
from the server, and then ask the server for y2 = F(y1).  Suppose the
input and output to F is n-bits long.  There are two cases:

(1).  If F(x) = E(k,x) = k xor x, then y2 == F(F(x)) == x for all x.
(2).  If F is just a big random table, the F(F(x)) != x with extremely
high probability.  In fact, the probability that this happens is 1-2^-n.

So this gives you a way to figure out which way I set up the server.
Make the two queries above (i.e. y1=F(x) and y2=F(y1)).  If y2 == x, then
you know that the server is probably implementing E with some key k.
Otherwise, you know that the server is definitely implementing the
table.  The algorithm presented in class just puts this idea into code.

This attack is only possible because E(k,x) = k xor x is a very crummy
encryption algorithm.  If E(k,x) = AES(k, x), then it would be really
difficult to tell whether the server was implementing E or just some big
random table.  The homework asks you to consider several different
possible encryption schemes E.  Some of them are easy to distinguish
from a random table, some are not.


Note a few things about this attack: it only required 2 messages and
almost no computation (just the check x == y2).  It's very efficient.
In particular, it should take less than 2^n messages and less than 2^n
computation time.  Any attack you describe in the homework should also
be efficient.  Also, it doesn't work 100% of the time: If we're really
unlucky, the random table may happen to have F(F(x))==x for our randomly
chosen x.  That's ok.  As long as it works most of the time, that's good
enough.