Expanding Weak-key Space of RC4

• Item type: Journal(1)
• 公開日: 2014-02-15
• タイトル: Expanding Weak-key Space of RC4
• タイトル / 言語: en
• タイトル: Expanding Weak-key Space of RC4
• 言語: eng
• キーワード / 主題Scheme: Other
• キーワード / 主題: [一般論文(推薦論文)] cryptanalysis, stream cipher, RC4, weak key, predictive state, key recovery attack
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• 著者所属: Graduate School of Engineering, Kobe University
• 著者所属: Information Media Center, Hiroshima University
• 著者所属: Graduate School of Engineering, Kobe University
• 著者所属: Graduate School of Engineering, Kobe University
• 著者所属(英): en
• 著者所属(英): Graduate School of Engineering, Kobe University
• 著者所属(英): en
• 著者所属(英): Information Media Center, Hiroshima University
• 著者所属(英): en
• 著者所属(英): Graduate School of Engineering, Kobe University
• 著者所属(英): en
• 著者所属(英): Graduate School of Engineering, Kobe University
• 著者名: Atsushi, Nagao; Toshihiro, Ohigashi; Takanori, Isobe; Masakatu, Morii
• 著者名(英): Atsushi, Nagao; Toshihiro, Ohigashi; Takanori, Isobe; Masakatu, Morii
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 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 of; Information Processing(JIP). This preprint should not be cited. This; article should be cited as: Journal of Information Processing Vol.22(2014) No.2 (online); DOI http://dx.doi.org/10.2197/ipsjjip.22.357; ------------------------------
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: 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 of; Information Processing(JIP). This preprint should not be cited. This; article should be cited as: Journal of Information Processing Vol.22(2014) No.2 (online); DOI http://dx.doi.org/10.2197/ipsjjip.22.357; ------------------------------
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN00116647
• 書誌情報: 情報処理学会論文誌; 巻 55, 号 2, 発行日 2014-02-15
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7764