Today I said a lot of things without writing them on the board (trying to
cover a lot of stuff in the 1:15 timeslot).

I'll try and re-state a few of the points I was trying to make in this
note in case you didn't get a chance to write them down during class.

The Sunday newspaper "cryptogram" asks you to perform a _ciphertext-only_
attack (you get no sample plaintext-ciphertext pairs).

When doing exhaustive key-search against DES given 20 (for example)
plaintext-ciphertext pairs, it takes 2^{55} expected key attempts
before finding the hidden key.  We do this by attacking the first key
pair P_1 and C_1.  Once we find a candidate key K that gives
C_1 == DES(K, P_1), we then test C_2 == DES(K, P_2) just to be sure.
There is a chance that the first test will succeed but this second one
will fail; if it fails we have to resume our key-search where we left off.
It's probably smart to try all 20 pairs when we think we've found the
key, just to be sure.  Remember, 20 is a small number next to 2^{55}.

The above assumes that the secret key was chosen randomly (as it usually is).
If we were worried that the secret key was chosen to foil our searching
attempt, we could generate the keys we are testing in _random_ order so
that it would not matter which key was chosen as the secret key... the
expected number of keys we'd have to try would be 2^{55}.

2DES ("double-DES"); no one uses it; insecure due to meet-in-the-middle.
Wiener-van Oorschot showed how to do meet-in-the-middle with less memory
(because 2^{63} bits is a LOT) at the cost of using a bit more CPU time.
(They use a few special data structures.)

3DES ("triple-DES") is still used and no good attacks are known against it.
RSA has a nice short discussion at
http://www.rsasecurity.com/rsalabs/faq/3-2-6.html

All of this is moot if AES (with its very large keys) is secure.
However recent work has shown how to view AES as an overdefined system of 
sparse multivariate
quadratic equations and there is fear afoot that this will lead to a 
practical attack on AES.
http://eprint.iacr.org/2002/044/

The number "16" for the rounds of DES was chosen for a variety of reasons:
it was a compromise between having enough security (more rounds gives
more security) and being fast enough (fewer rounds means a faster cipher).
It is believed that the security of properly-designed Feistel ciphers
increases exponentially in the number of rounds.  But remember: designing
block ciphers is a "mystical art" and the security of block ciphers cannot
be rigorous proven. Instead, designers try to build-in strength against all
known attack techniques.

Someone in class asked about related plaintexts under a fixed DES key.
Let's say we fix the DES key to be K, then encipher two different but
related plaintexts: 00000...0000 (64 zero bits), and 0000...0001 (63 zero
bits then a 1 bit).  The ciphertexts are DES(K, 00000...0000) and
DES(K, 0000...0001).  They should look NOTHING like each other!  In particular,
if there is a one bit difference between two plaintexts there should NOT
be a guaranteed one bit difference between their corresponding ciphertexts.
Remember: DES under a random key is trying to look like some random
permutation on 64-bit binary strings.  Therefore DES(K, 00000...0000) should
be some random 64-bit output and DES(K, 0000...0001) should be an
independent random 64-bit output with the only restriction being that it
can't be the same as DES(K, 00000...0000) because this would violate the
permutivity rule.

Hope this helps.  Send questions to me or Antonio.