RC4, a stream cipher designed by Rivest for RSA Data Security Inc., has found several commercial applications, but little public analysis has been done to date. In this paper, alleged RC4 (hereafter called RC4) is described and existing analysis outlined. The properties of RC4, and in particular its cycle structure, are discussed. Several variants of a basic "tracking" attack are described, and we provide experimental results on their success for scaled-down versions of RC4. This analysis shows that, although the full-size RC4 remains secure against known attacks, keystreams are distinguishable from randomly generated bit streams, and the RC4 key can be recovered if a significant fraction of the full cycle of keystream bits is generated (while recognizing that for a full-size system, the cycle length is too large for this to be practical). The tracking attacks discussed provide a significant improvement over the exhaustive search of the full RC4 keyspace. For example, the state of a 5 bit RC4-like cipher can be obtained from a portion of the keystream using 2~(42) steps, while the nominal keyspace of the system is 2~(160). More work is necessary to improve these attacks in the case where a reduced keyspace is used.
展开▼
机译:RC4是由Rivest为RSA Data Security Inc.设计的一种流密码,已经发现了几种商业应用程序,但是迄今为止尚未进行任何公共分析。在本文中,描述了所谓的RC4(以下称为RC4)并概述了现有分析。讨论了RC4的特性,尤其是其循环结构。描述了基本“跟踪”攻击的几种变体,我们提供了针对缩小版RC4成功的实验结果。该分析表明,尽管完整大小的RC4仍然可以抵御已知的攻击,但密钥流与随机生成的比特流是有区别的,并且如果密钥流比特的整个周期的很大一部分都已生成,则可以恢复RC4密钥(同时认识到对于全尺寸系统,周期长度太大而无法实际操作)。讨论的跟踪攻击相对于完整RC4密钥空间的穷举搜索提供了重大改进。例如,可以使用2〜(42)个步骤从一部分密钥流中获得5位类似RC4的密码的状态,而系统的标称密钥空间为2〜(160)。在使用减少的键空间的情况下,需要做更多的工作来改善这些攻击。
展开▼