Problem : Lem E. Tweakit is an aspiring embedded systems developer. Recall that RC4's internal state consists of an "S-Box" (S[]) and two pointers (i and j).
Lem, constrained by hardware, wants to implement the swap(S[i], S[j]) operation from RC4's Pseudo-Random Generation Algorithm (PRGA) without using a temporary variable. To perform the swap, Lem's PRGA uses the following algorithm:
Algorithm 1 LEM-SWAP(x, y)
1: x = x ? y
2: y = x ? y
3: y = x ? y
4: x = x ? y
Alyssa P. Hacker, who studied the RC4 stream cipher in CS4538, is concerned. In particular, Alyssa argues that his implementation exhibits a weakness that will compromise the privacy of data encrypted using his implementation of the RC4 PRGA.
(a) Alyssa is correct. Why? Explain your answer, providing a proof if necessary.
(b) Fix Lem's PRGA implementation by fixing LEM-SWAP(). Without using a temporary variable, provide the corrected LEM-SWAP() and show its correctness.
Having fixed LEM-SWAP(), Alyssa digs deeper into Lem's implementation. She notices another oddity: to save state space, his S-Box is an identity permutation of 128 elements (half the size of traditional RC4)! All KSA and PRGA operations are otherwise the same, but modulo 128.
(c) How will Lem's use of a 128 element S-Box affect the security of the resulting ciphertext? Explain your answer.