Advertisement
Published in:
2009 | OriginalPaper | Chapter
Key Collisions of the RC4 Stream Cipher
Author : Mitsuru Matsui
Published in: Fast Software Encryption
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
This paper studies “colliding keys” of RC4 that create the same initial state and hence generate the same pseudo-random byte stream. It is easy to see that RC4 has colliding keys when its key size is very large, but it was unknown whether such key collisions exist for shorter key sizes. We present a new state transition sequence of the key scheduling algorithm for a related key pair of an arbitrary fixed length that can lead to key collisions and show as an example a 24-byte colliding key pair. We also demonstrate that it is very likely that RC4 has a colliding key pair even if its key size is less than 20 bytes. This result is remarkable in that the number of possible initial states of RC4 reaches 256! ≈ 2
1684
. In addition we present a 20-byte near-colliding key pair whose 256-byte initial state arrays differ at only two byte positions.