Expanding Weak-key Space of RC4 (Preprint)

スポンサーリンク

概要

• 論文の詳細を見る

• RC4 is a stream cipher designed by Rivest in 1987. It is the most famous stream cipher and widely used e.g., SSL/TLS, WEP and WPA. Although RC4 in particular implementations and settings such as the WEP implementation and the broadcast setting, was already broken, RC4 itself is not completely broken yet. In 2011, Teramura et al. generalized classes of weak keys of RC4 by using the predictive state, which are special classes of the internal state of RC4. The total number of Teramura et al.'s weak keys is approximately 2 117.29. Their weak-key attack can recover a 128-bit secret key with efficienc of 2 95.10, where efficiency is defined as time complexity per success probability of the attack. This attack works only if particular patterns of the keystream are observed. In this paper, we further expand weak-key space of RC4. By thoroughly analyzing the relation between the key and the initial state of the pseudo-random generation algorithm, we can find new classes of predictive state which are utilized for key recovery attacks. As a result, 2 118.58 keys can be defined as new weak keys, whose number is more than twice the number of Teramura et al.'s weak keys. Moreover, our attack is applicable to any keystream, while Teramura et al.'s attack is feasible only in particular patterns of the keystream. Given any keystream, our weak-key attack can recover a 128-bit secret key with efficiency of 2 115.11. Our attack is the best-known single-key key recovery attack on RC4 with respect to efficiency. In addition, if we focus on specific keystreams similar to Teramura et al.'s attack, the 128-bit secret key can be recovered with efficiency of 2 76.32, which is more efficient than Teramura et al.'s attack.------------------------------This is a preprint of an article intended for publication Journal ofInformation Processing(JIP). This preprint should not be cited. Thisarticle should be cited as: Journal of Information Processing Vol.22(2014) No.2 (online)------------------------------

• 2014-02-15

著者

• Takanori Isobe

  Kobe University

• Toshihiro Ohigashi

  Hiroshima University

• Masakatu Morii

  Graduate School of Engineering, Kobe University

• Atsushi Nagao

  Graduate School of Engineering, Kobe University

• Toshihiro Ohigashi

  Information Media Center, Hiroshima University

• Takanori Isobe

  Graduate School of Engineering, Kobe University

関連論文

• Slide Property of RAKAPOSHI and Its Application to Key Recovery Attack (Preprint)
• Expanding Weak-key Space of RC4 (Preprint)

スポンサーリンク