Date: 2009/1/9 (Fri) 15F30`17F00

      Place: Collaboration Room #7 (Information Science Building, 5th floor)

      Name: Mitsuru Matsui
          Mitsubishi Electric Corporation, Information Technology R&D Center, Information Security Department, Deputy Manager

      Title: Key Collisions of the RC4 Stream Cipher

      Abstract: 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}.