Date: 2009/1/9 (Fri) 15F30`17F00Place: Collaboration Room #7 (Information Science Building, 5th floor)
Name: Mitsuru MatsuiMitsubishi Electric Corporation, Information Technology R&D Center, Information Security Department, Deputy Manager
Title: Key Collisions of the RC4 Stream CipherAbstract: This talk explores ``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 keys.
We present a new state transition sequence of the key scheduling
algorithm for a related key pair of an arbitrary length that can lead
to key collisions and show as an example a 43-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 much shorter, say 20-30 bytes.
This result is remarkable in that the number of possible initial
states of RC4 reaches 256! = 2^{1684}.
