Title Near-colliding Keys in RC4
Search of key collisions in the RC4 stream cipher has been an active area.
We investigate near-colliding keys that lead to related states after key scheduling and related key stream bytes.
Our investigation reveals that near-colliding states do not necessarily lead to near-colliding key streams.
From this motivation, we present practical methods to find a related key pair with differences in two bytes,
that leads to a large number of matches in the initial key stream. In the process, we discover a class of related key
distinguishers for RC4. The best one of these shows that given a random key and a related one to that
(the last two bytes increased and decreased by 1 respectively), the first pair of bytes corresponding to the
related keys are the same with significant probability (e.g., approximately 0.011 for 16-byte keys to 0.044 for 30-byte keys).