This was a "relax" homework with an exception of problem 4 (iterative cryptosystems) and 5 (grandpre, hill climbing contest which nobody has solved so far). The average grade was 85. Below are several best solutions.  Again, some people submitted excellent works by e-mail or in hand writing, so they can't be shown here.

• Solution by Roman Dovgard (PS file) [1, 3, 4A, 4B,5B]
• Solution by  Paul Koning (text file)    [1, 2, 3, 4A, 5B]
• Solution by Omer Golz (in Hebrew)   [1, 3, 4A, 4B]
• Solution by Uri Barenholz (text file)   [4A,4B]
• Solution by Emmanuel Lanzmann     [1, 2, 4A,4B]
• Solution by Itsik Mantin (PS file)       [1, 4A,4B]

1. Cycle Detection
  A classical problem. Sometimes counters are not allowed (counter takes O(log n) bits). Even with this restriction it is possible to detect a cycle and find the cycle entry point.

2. Hellman's Tradeoff
a) Rho and cycle become about 10 times longer just by applying bithday paradox-like argument. Only 1/99 points of the orbit can be returned to (have 2 predecessors)
[1/99 and not 1/100, since leaves can not be met on our walk].

b) Consider a set |A| = mt of already covered points and a new row B with |B|=t points. For a normal random function the stopping condition (no collisions) is |A|*|B|= mt*t<N. In our case only 1/99 of points in A can be returned to, thus effectively A behaves as a set of size |A|/99 and thus new stopping condition is: |A|*|B|= mt*t<99N. That means that in this case coverage is better and thus we can use larger tables. The improvement however is only by a constant factor (even such degenerate function does not lead to perfect  "permutation-like" coverage).
 

3. Structure of DES
Obvious. Note that two outmost bits (a,b)  axxxxb are used to choose between rows of permutations. The intention was that in (b)  input to the F-function is:
1111 1111 1111 1111 1111 1111 1111 1110
and thus two S-boxes are affected after the expansion: S1 and S8.
Output of function F (after permutation) (IP was ignored):
a) 0011 1000 1101 1011 1111 1001 1100 1011
b) 0011 0000 1101 1011 0111 0001 1110 1001
Outputs differ in 5 bits.

From this excersise you have also learned about the ambiguity in numbering bits in DES: IBM and thus the standard number bits from 1 to N from the left to the right, the numbering of inputs/outputs of the S-boxes is MSB...LSB; while in modern computers the numbering is from 0 to N-1 and from the right to the left.
 

4.Fixed Points of the Weak Keys of DES
A naive approach would be to pick points at random and check each  of them for DES(x) = x. Since we know that there are 2^32 fixed points we would expect to perform about 2^32 trials before we reach one (and it would take about 5 times longer to find one with the required least significant digit). This would take many hours with optimised DES implementations.

However  Don Coppersmith shows a simple way to enumerate all the fixed points: A fixed point for a weak key can happen only if m8 = m9 (in Coppermith's notation), i.e after eight rounds the result look as (A,A) for arbitrary 32-bit value A. Due to similarity of encryption and decryption under weak keys, from this point the encryption process is reversed and thus ciphertext will be equal to the original palintext. This explains why there are exactly 2^32 fixed points and also provides a simple method to enumerate all of them.

• Pick an arbitrary value for A
• Encrypt (A,A) eight rounds under zero key
• Check if least significant digit is D, if not, then go to the first step.

5. Recover the S-boxes
This is a GOST like Feistel cipher (although some of you interpreted the description as a slightly different non-Feistel construction, it does not change the main results).
You were allowed to control part of the secret key (round subkeys) and the aim was to find the second part of the secret key (unknown S-boxes). This scenario is called a related key attack (see references below). In related key attacks the attacker is allowed to control part of the key or to know relations between keys.

Part I
Here it is possible to mount differential attack with appropriate choice of differences between keys.

Part II
Differential approach no longer works here due to the huge number of rounds.

Original attack by Olga Grinchtein, Serge Khristo

Denote round function by F.
Pick arbitrary X. Try to guess Y = F(X).
For each guess encrypt 64-bit plaintext (0,Y)
under subkeys:
X+Y, X+Y, X, X, X+Y, X+Y, X, X.
If Y = F(X) holds after 8 rounds we will receive (0,Y) with probability 1. And thus this will be the output after 8000 rounds. We need 16 equations Y = F(X) in order to recover all the S-boxes.  Complexity of this approach is about 2^{36}
chosen plaintext queries.

Slide attack was rediscovered by Kobi Kaminitz

Denote by B() 8000 rounds of the cipher with all subkeys equal to arbitrary value, and by R() single round of this cipher. Suppose that for some X we know  Y = R(X). Then R(B(X))=B(R(X)) can be tested. Instead of performing 2^{32} guesses for Y = R(X) one can use birthday paradox in a pool of only O(2^{16}) texts and in O(2^{16}) steps.

To be continued, under  construction

References
1. Eli Biham,
New Types of Cryptanalytic Attacks Using Related Keys (.ps), Proceedings of Eurocrypt'93, LNCS 765,
Journal of Cryptology, Vol. 7, No. 4, pp. 229-246, 1994.