Homework 3

1. Locate weak keys for RC4. Get RC4 code, compile and run it.

2. Write a program that identifies x-good keys, that is, keys which give x-resolved situations after x steps of KSA. and identifies x-weak keys, Verify that keys B+3:FF:N:k0:k1:k2:k3:k4: is (B+3)-weak, where N and ki are any byte values.

3. Improve your program to identify x-weak keys. These arre keys which are x-good and which after the KSA complete the situation is still x-resolved. By running random x-good keys, (first two bytes fixed) check whether it is true that 5% of them are x-weak.
   My program produced a list of weak keys.

4. Given an x-weak key, and the first output byte, calculate byte x of the key and verify it works. Try 3 x-weak keys found above.

5. In reality, ki is fixed, so our available pool of x-good keys of the recommended form has only 256 candidates, for n=0,...,255. Find a key k0,...,k4 which is not 3-weak, not 4-weak, neither 3- nor 4-weak, with the restricted class of x-good keys.

6. Estimate the percentage of keys k,k1,k2,k3,k4 that are are 3-weak by generating random keys and trying to find prefixes that give 3-weak keys. In this case, since we are a bit more theoretical and pessimistic, any prefix will do.