本 日 の 内 容 (1/2) 2012 年 度 CRYPTREC 技 術 報 告 書 ストリーム 暗 号 RC4の 安 全 性 評 価 -128 bit key RC4 (SSL3.0 /TLS 1.0 以 上 )の 安 全 性 評 価 代 表 : 五 十 部 孝 典 (ソニー 株 式 会 社 /

2014. 2.13 NICT 情 報 セキュリティ シンポジウム @ コクヨホール RC4の 脆 弱 性 とSSL/TLSへの 攻 撃 五 十 部 孝 典 ソニー 株 式 会 社

本 日 の 内 容 (1/2) 2012 年 度 CRYPTREC 技 術 報 告 書 ストリーム 暗 号 RC4の 安 全 性 評 価 -128 bit key RC4 (SSL3.0 /TLS 1.0 以 上 )の 安 全 性 評 価 代 表 : 五 十 部 孝 典 (ソニー 株 式 会 社 / 神 戸 大 学 ) 共 同 研 究 者 : 大 東 俊 博 ( 広 島 大 学 ), 森 井 昌 克 ( 神 戸 大 学 ) 神 戸 大 学 学 生 : 渡 辺 優 平, 長 尾 篤, 塚 畝 翼 http://www.cryptrec.go.jp/estimation/techrep_id2205.pdf RC4の 既 知 の 解 析 結 果 のサーベイ 新 しい 攻 撃 法 の 提 案 平 文 回 復 攻 撃 [FSE 2013] Broadcast setting Multi-session setting (SSL/TLS) 2013 年 RC4はCRYPTRECの 推 奨 暗 号 リストから 除 外 され, 運 用 監 視 リストへ

本 日 の 内 容 (2/2) その 後 の 研 究 動 向 SSL/TLSへの 平 文 回 復 攻 撃 の 改 良 現 実 的 な 平 文 パターンでの 評 価 [ICSS 2013] 比 較 的 安 全 な 実 装 方 法 (RC4-drop)への 拡 張 [SAC 2013] 成 功 確 率 の 向 上 [USENIX 2013] WPA-TKIPへの 攻 撃 の 拡 張 平 文 回 復 攻 撃 [FSE 2014]

発 表 の 流 れ 1. ストリーム 暗 号 RC4 2. RC4の 安 全 性 3. 新 しい 攻 撃 法 : 平 文 回 復 攻 撃 - Broadcast setting - Multiple session setting (SSL/TLS) CRYPTREC 技 術 報 告 書 に 記 載 されている 内 容 4. その 後 の 進 展

1. ストリーム 暗 号 RC4

ストリーム 暗 号 共 通 鍵 暗 号 のひとつ 秘 密 鍵 から 擬 似 乱 数 系 列 (キーストリーム)を 生 成 する 関 数 < 暗 号 化 > 秘 密 鍵 < 復 号 > 秘 密 鍵 ストリーム 暗 号 (RC4) ストリーム 暗 号 (RC4) 010100110101010110 010100110101010110 キーストリーム キーストリーム 平 文 暗 号 文 暗 号 文 平 文

RC4 1987 年 にRivestにより 開 発 されたストリーム 暗 号 最 も 広 く 使 われている 暗 号 の 一 つ WEP, WPA-TKIP, SSL/TLS, SSHなど RC4の 構 造 鍵 スケジューリング アルゴリズム(KSA) 擬 似 乱 数 生 成 アルゴリズム(PRGA) 鍵 K (1~256 byte) 初 期 化 0 1 2 255 内 部 状 態 S (256 byte) 生 成 1 byte 1 byte バイト 単 位 の 処 理 可 変 長 鍵 (1~256 byte) 推 奨 値 は16 byte(128 bit) 内 部 状 態 は256 byteの 配 列 S と 2つのindex i と j Z 1, Z 2, Z 3,, Z r 擬 似 乱 数 系 列 Z i (キーストリーム)

鍵 スケジューリングアルゴリズム(KSA) t = 1 i = 0 0 1 Time t S 0 0 1 255 j i J = 0 S 0 [x] = x loop j = j +S[ i ] + K[i] swap(s[ i ], S[ j ]) i = i + 1 end loop

鍵 スケジューリングアルゴリズム(KSA) t = 1 Time t 0 1 S 0 0 1 255 S 0 i j X i Y j 鍵 に 依 存 i = 0 J = 0 S 0 [x] = x loop j = j +S[ i ] + K[i] swap(s[ i ], S[ j ]) i = i + 1 end loop

鍵 スケジューリングアルゴリズム(KSA) t = 1 Time t 0 1 S 0 0 1 255 S 0 i j X i Y j S 1 Y X 鍵 に 依 存 i = 0 J = 0 S 0 [x] = x loop j = j +S[ i ] + K[i] swap(s[ i ], S[ j ]) i = i + 1 end loop

鍵 スケジューリングアルゴリズム(KSA) t = 1 Time t 0 1 S 0 0 1 255 S 0 i j X i Y j S 1 Y X 鍵 に 依 存 i = 0 J = 0 S 0 [x] = x loop j = j +S[ i ] + K[i] swap(s[ i ], S[ j ]) i = i + 1 end loop S 256 0 1

擬 似 乱 数 生 成 アルゴリズム (PRGA) t = 1 Time t 0 1 X X +Y S 0 X Y O i j i = 0 J = 0 Loop i = i + 1 j = j +S[ i ] swap(s[ i ], S[ j ]) Z = S[S[ i ]+S[ j ]] end loop

擬 似 乱 数 生 成 アルゴリズム (PRGA) t = 1 Time t 0 1 X X +Y S 0 X Y O j 1 S 0 i j X i Y O x i = 0 J = 0 Loop i = i + 1 j = j +S[ i ] swap(s[ i ], S[ j ]) Z = S[S[ i ]+S[ j ]] end loop

擬 似 乱 数 生 成 アルゴリズム (PRGA) t = 1 Time t 0 1 X X +Y S 0 X Y O j 1 S 0 S 0 i j X i X i Y x Y j O O i = 0 J = 0 Loop i = i + 1 j = j +S[ i ] swap(s[ i ], S[ j ]) Z = S[S[ i ]+S[ j ]] end loop S 1 Y i X j O

擬 似 乱 数 生 成 アルゴリズム (PRGA) t = 1 Time t 0 1 X X +Y S 0 X Y O j 1 S 0 S 0 i j X i X i Y x Y j O O i = 0 J = 0 Loop i = i + 1 j = j +S[ i ] swap(s[ i ], S[ j ]) Z = S[S[ i ]+S[ j ]] end loop S 1 Y i X j O Z = S [X+Y] =O

2. RC4の 安 全 性

ストリーム 暗 号 に 求 められる 代 表 的 な 安 全 性 出 力 系 列 の 乱 数 性 出 力 系 列 (キーストリーム)を 真 性 乱 数 と 識 別 することが 困 難 あるキーストリーム 系 列 の 集 合 から, 以 降 のキーストリームの 予 測 が 困 難 KSA RC4 PRNG 真 性 乱 数 識 別 攻 撃 Key 内 部 状 態 キーストリーム

ストリーム 暗 号 に 求 められる 代 表 的 な 安 全 性 出 力 系 列 の 乱 数 性 出 力 系 列 (キーストリーム)を 真 性 乱 数 と 識 別 することが 困 難 出 力 の 予 測 困 難 性 あるキーストリーム 系 列 の 集 合 から, 以 降 のキーストリームの 予 測 が 困 難 KSA RC4 PRNG 真 性 乱 数 識 別 攻 撃 Key 内 部 状 態 キーストリーム 予 測 攻 撃

ストリーム 暗 号 に 求 められる 代 表 的 な 安 全 性 出 力 系 列 の 乱 数 性 出 力 系 列 (キーストリーム)を 真 性 乱 数 と 識 別 することが 困 難 出 力 の 予 測 困 難 性 あるキーストリーム 系 列 の 集 合 から, 以 降 のキーストリームの 予 測 が 困 難 秘 密 鍵 回 復 困 難 性 キーストリームから 秘 密 鍵 を 求 めることが 困 難 KSA RC4 PRNG 真 性 乱 数 識 別 攻 撃 Key 内 部 状 態 キーストリーム 予 測 攻 撃 鍵 回 復 攻 撃

ストリーム 暗 号 に 求 められる 代 表 的 な 安 全 性 出 力 系 列 の 乱 数 性 出 力 系 列 (キーストリーム)を 真 性 乱 数 と 識 別 することが 困 難 出 力 の 予 測 困 難 性 あるキーストリーム 系 列 の 集 合 から, 以 降 のキーストリームの 予 測 が 困 難 秘 密 鍵 回 復 困 難 性 キーストリームから 秘 密 鍵 を 求 めることが 困 難 内 部 状 態 復 元 困 難 性 キーストリームから 内 部 状 態 を 復 元 することが 困 難 KSA RC4 PRNG 真 性 乱 数 識 別 攻 撃 Key 内 部 状 態 キーストリーム 内 部 状 態 復 元 攻 撃 予 測 攻 撃 鍵 回 復 攻 撃

RC4の 既 知 の 安 全 性 評 価 結 果 KSA RC4 PRNG 真 性 乱 数 識 別 攻 撃 Key 内 部 状 態 キーストリーム 内 部 状 態 復 元 攻 撃 予 測 攻 撃 鍵 回 復 攻 撃 予 測 攻 撃 Mantin [EUROCRYPT 2005] : 2 45 バイトのキーストリーム から85%の 確 率 で 1ビットの 予 測 が 可 能 識 別 攻 撃 Golic [EUROCRYPT 1997]: : 2 44.7 byteのキーストリームにより 識 別 可 能 Fluhrer et.al [FSE 2000] : 2 30.6 byteのキーストリームにより 識 別 可 能 Mantin [EUROCRYPT 2005] : 2 26.5 byteのキーストリームにより 識 別 可 能 (Multiple key) Mantin, Shamir [FSE 2001] : 2 8 byteのキーストリームにより 識 別 可 能

RC4の 既 知 の 安 全 性 評 価 結 果 KSA RC4 PRNG 真 性 乱 数 識 別 攻 撃 Key 内 部 状 態 キーストリーム 内 部 状 態 復 元 攻 撃 予 測 攻 撃 鍵 回 復 攻 撃 内 部 状 態 復 元 攻 撃 Knudsen et.al [ASIACRYPT 1998] : 計 算 量 2 779 白 石, 大 東, 森 井 [IEICE 2003] : 計 算 量 2 612 Miximov et.al [CRYPTO 2008] : 計 算 量 2 241 鍵 長 を241 bitより 長 くしても 安 全 性 は 向 上 しない 鍵 回 復 攻 撃 (weak key) Roos [R 1995] : 計 算 量 2 112, 確 率 2-10.9 Sepehrdad et al. [SAC 2010] : 計 算 量 2 38.09, 確 率 2-87.9 計 算 量 1, 確 率 2-122.06 Our [JIP 2014] : 計 算 量 2 96.36, 確 率 2-18.75

RC4の 既 知 の 安 全 性 評 価 まとめ 理 論 的 な 安 全 性 識 別 攻 撃 により, 擬 似 乱 数 との 識 別 が 容 易 全 数 探 索 より 効 率 的 に 鍵 の 探 索 ができるweak keyが 存 在 理 想 的 なストリーム 暗 号 としての 安 全 性 を 満 たしていない 実 際 的 な 安 全 性 現 実 的 に 脅 威 となるような 攻 撃 は 見 つかっていない 簡 単 に 識 別 できても, 鍵 回 復 等 の 攻 撃 ができるわけではない 鍵 回 復 攻 撃 や 内 部 状 態 推 定 攻 撃 の 計 算 量 は, 非 現 実 的

3. 新 しい 攻 撃 法 : 平 文 回 復 攻 撃

攻 撃 のポイント 現 実 的 なデータ 量 で 実 行 可 能 な 識 別 攻 撃 がベース KSA RC4 PRNG 真 性 乱 数 識 別 攻 撃 Key 内 部 状 態 キーストリーム 内 部 状 態 復 元 攻 撃 予 測 攻 撃 鍵 回 復 攻 撃 予 測 攻 撃 Mantin [EUROCRYPT 2005] : 2 45 byteのキーストリーム から85%の 確 率 で1ビットの 予 測 が 可 能 識 別 攻 撃 Golic [EUROCRYPT 1997]: : 2 44.7 byteのキーストリームから 識 別 Fluhrer et.al [FSE 2000] : 2 30.6 byte Mantin [EUROCRYPT 2005] : 2 26.5 byte (Multiple key) Mantin, Shamir [FSE 2001] : 2 8 byte 識 別 攻 撃 をさらに 改 良 新 たな 出 力 の 偏 りを 見 つけ, 理 論 的 にも 実 験 的 にも 証 明 効 果 的 な 攻 撃 モデルへの 適 用 Broadcast setting, multi session setting

Broadcast Setting 同 じ 平 文 P をユーザごとの 鍵 で 暗 号 化 して 送 信 するモデル 攻 撃 のゴール : 攻 撃 者 は 暗 号 文 から 平 文 Pを 求 める ユーザ 数 =X 平 文 P RC4 enc. 暗 号 文 C (1) C (2) ユーザ C (x) 鍵 はユーザ 毎 にランダムに 作 成 例 1. 複 数 のユーザが 同 じデータを 取 得 2 同 じデータを 何 度 も 取 得 => Multi session setting (SSL/TLS) 例 ) HTTPS + basic 認 証 - ネットワーク 利 用 者 認 証 - グループ 利 用 のWebページ OSイメージの 配 布 など

Multi Session Setting (SSL) 異 なるsessionにおいて, 同 じデータを 同 じpositionで 送 る 場 合 を 想 定 SSL/TLSでは 毎 session 異 なる 鍵 を 生 成 cookieやpasswordが 攻 撃 Target Session 1 Target P 1 RC4(k 1, P 1 ) C 1 = RC4(k 1, M) Session 2 Target P 2 RC4(k 2, P 2 ) C 2 Session X Target P X RC4(k x, P x ) C x

平 文 回 復 攻 撃 [FSE 2013] 攻 撃 1 : 平 文 の 初 期 byte 回 復 攻 撃 2 32 の 暗 号 文 から, 平 文 の 初 期 257 byteの 任 意 byte を 確 率 0.5 以 上 で 推 測 可 能 初 期 257 bytes の 任 意 byte 2 32 の 暗 号 文 Target 平 文 回 復 C (1) C (2) C (x) 攻 撃 2 : 逐 次 的 平 文 回 復 攻 撃 2 34 の 暗 号 文 から, 平 文 の 連 続 した 初 期 1000T byteをほぼ 確 率 1で 推 測 可 能 初 期 1000T bytes の 任 意 byte 2 34 の 暗 号 文 Target 平 文 回 復 C (1) C (2) C (x)

攻 撃 1: 平 文 の 初 期 byte 回 復 攻 撃 のアイデア 出 力 の 偏 りから 平 文 回 復 攻 撃 へ 変 換 可 能 [FSE 2001] キーストリームの2 byte 目 が0となる 確 率 が2/256 秘 密 鍵 RC4 Z 1, Z 2, Z 3, Z 4, 確 率 2/256 1/256 Z 2 の 値 0 キーストリームの 値 255

攻 撃 1: 平 文 の 初 期 byte 回 復 攻 撃 のアイデア 出 力 の 偏 りから 平 文 回 復 攻 撃 へ 変 換 可 能 [FSE 2001] キーストリームの2 byte 目 が0となる 確 率 が2/256 秘 密 鍵 RC4 Z 1, Z 2, Z 3, Z 4, P r : 平 文 の r byte 目 C r : 暗 号 文 の r byte 目 確 率 2/256 1/256 Z 2 の 値 0 キーストリームの 値 255 用 いる 関 係 式 : C 2 = P 2 XOR Z 2 C 2 =CON XOR Z 2 (Broadcast setting)

攻 撃 1: 平 文 の 初 期 byte 回 復 攻 撃 のアイデア 出 力 の 偏 りから 平 文 回 復 攻 撃 へ 変 換 可 能 [FSE 2001] キーストリームの2 byte 目 が0となる 確 率 が2/256 秘 密 鍵 RC4 Z 1, Z 2, Z 3, Z 4, P r : 平 文 の r byte 目 C r : 暗 号 文 の r byte 目 確 率 2/256 1/256 C 2 の 頻 度 表 Z 2 の 値 0 255 キーストリームの 値 用 いる 関 係 式 : C 2 = P 2 XOR Z 2 C 2 =CON XOR Z 2 (Broadcast setting) 確 率 0 キーストリームの 位 置 255 C 2 = P 2 XOR 0?

攻 撃 1: 平 文 の 初 期 byte 回 復 攻 撃 のアイデア 出 力 の 偏 りから 平 文 回 復 攻 撃 へ 変 換 可 能 [FSE 2001] キーストリームの2 byte 目 が0となる 確 率 が2/256 秘 密 鍵 RC4 Z 1, Z 2, Z 3, Z 4, P r : 平 文 の r byte 目 C r : 暗 号 文 の r byte 目 確 率 2/256 1/256 C 2 の 頻 度 表 Z 2 の 値 0 255 キーストリームの 値 用 いる 関 係 式 : C 2 = P 2 XOR Z 2 C 2 =CON XOR Z 2 (Broadcast setting) 確 率 最 も 多 く 出 現 するC 2 がP 2 の 値 と 推 測 される 2 8 通 り 以 上 の 暗 号 文 があれば 十 分 高 い 確 率 で, 暗 号 文 から 平 文 の2 byte 目 を 特 定 可 能 0 キーストリームの 位 置 255 C 2 = P 2 XOR 0?

キーストリームの 偏 り 既 知 のキーストリームの 偏 り[FSE 01, FSE 11] Z r = 0 bias [FSE 11] Z 2 = 0 bias [FSE 01] This figure is created by Jiageng Chen

キーストリームの 偏 り 4 種 類 の 新 しい 偏 りを 発 見 し, 理 論 的 にも 証 明 Extended key length dependent bias [Our] Z 3 = 131 bias [Our] Z r = r bias [Our] Z r = 0 bias [FSE 11] Z 2 = 0 bias [FSE 01] Conditional bias [Our] This figure is created by Jiageng Chen

キーストリームの 偏 り 初 めの257 byteの 最 も 強 い 偏 り 値 の 実 験 値 と 理 論 値

攻 撃 1の 実 験 結 果 各 byteにおける 平 文 復 元 の 成 功 確 率 暗 号 文 数 : 2 24, 2 28, 2 32, 2 35 ランダムに 生 成 した256 通 りの 平 文 に 対 して 実 施

攻 撃 1の 実 験 結 果 各 byteにおける 平 文 復 元 の 成 功 確 率 暗 号 文 数 : 2 24, 2 28, 2 32, 2 35 ランダムに 生 成 した256 通 りの 平 文 に 対 して 実 施 暗 号 文 数 2 32 のとき, 先 頭 の257byteはそれぞれ 確 率 0.5 以 上 で 復 元 可 能

平 文 回 復 攻 撃 [FSE 2013] 攻 撃 1 : 平 文 の 初 期 byte 回 復 攻 撃 2 32 の 暗 号 文 から, 平 文 の 初 期 257 byteの 任 意 byte を 確 率 0.5 以 上 で 推 測 可 能 初 期 257 bytes の 任 意 byte 2 32 の 暗 号 文 Target 平 文 回 復 C (1) C (2) C (x) 攻 撃 2 : 逐 次 的 平 文 回 復 攻 撃 2 34 の 暗 号 文 から, 平 文 の 連 続 した 初 期 1000T byteをほぼ 確 率 1で 推 測 可 能 初 期 1000T bytes の 任 意 byte 2 34 の 暗 号 文 Target 平 文 回 復 C (1) C (2) C (x)

攻 撃 2 : 逐 次 的 平 文 回 復 攻 撃 258バイト 目 以 降 の 平 文 を 求 める 方 法 P 1 P 2 P 3 P 31 P 257 P 258, P 259, ここまでは 初 期 の 特 有 の 偏 りを 利 用 初 期 のような 強 い 偏 りが 存 在 しない 任 意 のbyteで 発 生 するlong term biasを 利 用 Digraph Repetition Bias (call ABSAB bias) [EUROCRYPT 2005] 既 知 の 最 も 強 力 なlong-term bias Gバイトのギャップの 後 に 同 じバターンが 生 じる (2バイト 単 位 ) キーストリーム.ABHLWECTSDGAB. gap G

攻 撃 2の 評 価 攻 撃 方 法 257 byteを 求 めたあと,ABSAB biasにより, 逐 次 的 に 求 めていく P 1 P 2 P 3 P 31 P 257 P 258, P 259, 2 32 の 暗 号 文 で 高 確 率 で 復 元 可 能 ( 攻 撃 1) ABSAB bias 計 算 機 実 験 4バイト(P 258,, P 261 )を 逐 次 的 に 復 元 したときの 成 功 確 率 理 論 値 暗 号 文 数 2 34 のとき 平 文 の 先 頭 2 50 1000 T bytesを 確 率 0.97 で 復 元 可 能 ( 識 別 攻 撃 Pr = 1 2-19, Xバイトの 復 元 の 成 功 確 率 (1 2-19 ) 255 X )

新 しい 攻 撃 法 ( 平 文 回 復 攻 撃 )まとめ 攻 撃 の 条 件 平 文 が 異 なる 鍵 で 暗 号 化 (Broadcast setting). SSL/TLSでは, 毎 session 同 じ 位 置 (multi session setting) 攻 撃 者 は 暗 号 文 を 集 めるのみ ( 暗 号 文 単 独 攻 撃 ) 攻 撃 能 力 2 24-2 35 の 暗 号 文 から, 平 文 を 高 確 率 で 求 めることができる. 実 際 の 影 響 2 24-2 32 の 暗 号 文 が 必 要 であるため, すぐさま 脅 威 になることはない. ほかの 脆 弱 性 と 組 み 合 わさってPracticalになる 可 能 性 あり. HTTPSリクエストを 大 量 にするJavascript 等 の 利 用

4. その 後 の 進 展

RC4の 攻 撃 の 進 展 FSE 2013での 発 表 以 降 さまざまな 攻 撃 の 改 良 が 行 われた SSL/TLSへの 平 文 回 復 攻 撃 の 改 良 現 実 的 な 平 文 パターンでの 評 価 [ICSS 2013] 比 較 的 安 全 な 実 装 方 法 (RC4-drop)への 拡 張 [SAC 2013] 攻 撃 の 確 率 向 上 [USENIX 2013] WPA-TKIPへの 攻 撃 の 拡 張 平 文 回 復 攻 撃 [FSE 2014]

平 文 空 間 を 制 限 した 場 合 における 平 文 回 復 攻 撃 [ICSS 2013] p a s s w o r d K 1 FSE 2013では 各 バイトにランダムな 値 (256 通 りの 値 )が が 代 入 されるとして 攻 撃 実 際 はある 特 定 の 平 文 空 間 で 使 用 (パスワード 等 ) 平 文 の 候 補 の 条 件 Case 1 : PIN code (0 9, 0x30 0x39, 10 種 類 ) Case 2 : ASCII code (except control code, 0x20 0x7e, 95 種 類 ) Case 3 : Randomly distributed (256 種 類 )

ASCII code Case 1 (PIN code) Case 2 (ASCII code except control code) ASCII 文 字 コード, available at : http://e-words.jp/p/r-ascii.html

実 験 結 果 -Case 1 & Case 3 Case 1 : PIN code Case 3 : Randomly distributed Success Probability Success Probability Round number (r) Round number (r) 暗 号 文 数 2 23 2 25 2 28 2 32 Random 初 めの257 bytes 2 23 sessions ( 暗 号 文 ) Target 平 文 Random guessより 高 い 確 率

実 験 結 果 -Case 2 & Case 3 Case 2 : ASCII code Case 3 : Randomly distributed Success Probability Success Probability Round number (r) Round number (r) 暗 号 文 数 2 23 2 25 2 28 2 32 Random 初 めの257 bytes 2 25 sessions ( 暗 号 文 ) Target 平 文 Random guessより 高 い 確 率

比 較 的 安 全 な 実 装 方 法 (RC4-drop)への 拡 張 [SAC 2013] FSE 2013の 攻 撃 に 強 い 実 装 RC4-drop(n) への 攻 撃 RC4-drop(n): キーストリームの 先 頭 の n バイトを 捨 てる ( 推 奨 パラメータ n =768, 理 想 的 には n =3072 以 上 [CRYPTO 2002]) 初 期 のbiasは 排 除 される RC4 キーストリーム Z 1, Z 2, Z n, Z n+1, 暗 号 化 に 使 わず に 捨 てる 平 文 P 1, P 2, 暗 号 文 C 1, C 2, RC4のキーストリームの 初 期 のbiasが 取 り 除 かれる FSE2013の 攻 撃 を 含 む 従 来 の 攻 撃 が 無 効

比 較 的 安 全 な 実 装 方 法 (RC4-drop)への 拡 張 [SAC 2013] 任 意 のbyteに 存 在 する 複 数 のbiasを 組 み 合 わせて 利 用 Mantin s bias [EURO05] とFluhrer-McGrew bias [FSE00] Initial keystreamを 排 除 してもworkする 攻 撃 Any byte P Plaintext Recovery 2 35 ciphertexts C (1) C (2) C (x) Guess and determine technique Step 2: ABSAB biasで 推 測 P 286 P 298 P 299 P 300 Step 1: FM00 bias で 復 元 比 較 Step 1: P 300 をGuess 攻 撃 に 利 用 できる 暗 号 文 数 2 34 2 35 P 300 0.8867 1.0000

攻 撃 成 功 確 率 の 改 良 [USENIX 2013] 基 本 的 には,FSE 2013の 攻 撃 手 法 と 同 様 初 期 キーストリームの 偏 りから, 平 文 回 復 攻 撃 実 験 結 果 のみで, 偏 りの 理 論 的 考 察 はない 改 善 ポイント FSE 2013 : もっとも 強 い 偏 りの 値 を 推 測 に 利 用 USENIX 2013 : 各 byteの 偏 っている 分 布 すべてを 利 用 結 果 先 頭 256バイトの 平 文 を2 32 個 の 暗 号 文 から 確 率 0.96 以 上 で 回 復 できる(FSE 2013は0.5 以 上 ) 任 意 バイトを2 34 の 暗 号 文 から 確 率 0.99 程 度 で 回 復 できる(SAC 2013は0.89 程 度 )

WPA-TKIPへの 拡 張 [FSE 2014] WPA-TKIP 無 線 LANの 暗 号 化 方 式 でRC4を 利 用 WEP 鍵 更 新 方 法 を 変 更 : TKIP (Temporal Key Integrity Protocol) 新 しい 偏 りが 出 現 => 3 byteのivの 影 響 [eprint 2013] 攻 撃 初 めの256 byteは, SSL/TLSと 同 様 に2 30 程 度 で 回 復 可 能

まとめ RC4の 安 全 性 ストリーム 暗 号 としての 安 全 性 は 満 たしていない Practicalな 識 別 攻 撃, weak keyの 存 在 SSL/TLS RC4 への 攻 撃 対 策 2 24-2 35 の 程 度 の 暗 号 文 から 平 文 は 特 定 可 能 平 文 空 間 を 限 定 するとさらに 効 率 化 可 能 攻 撃 者 は, 暗 号 文 を 集 めるのみでいいので, 基 本 的 にRC4を 使 わない 以 外 の 対 策 はない SSL/TLSでは,CBC modeもbeast, Lucky Thirteen, CRIME 等 の 脆 弱 性 が 報 告 されているため, => Authenticated Encryptionの 利 用

References [FSE 2013] T. Isobe, T. Ohigashi, Y. Watanabe and M. Morii, Full Plaintext Recovery Attack on Broadcast RC4 [ICSS 2013] Y. Watanabe, T. Isobe, T. Ohigashi, M. Morii, "Vulnerability of RC4 in SSL/TLS [SAC 2013] T. Ohigashi, T. Isobe, Y. Watanabe and M. Morii, How to Recover Any Byte of Plaintexton RC4 [USENIX 2013] N. J. AlFardan, D. J. Bernstein, K. G. Paterson, B. Poettering and J. C. N. Schuldt, On the Security of RC4 in TLS [SAC 2013] T. Ohigashi, T. Isobe, Y. Watanabe and M. Morii, How to Recover Any Byte of Plaintexton RC4 [FSE 2014] K. G. Paterson, J. C. N. Schuldt and B. Poettering, Plaintext Recovery Attacks Against WPA/TKIP [EUROCRYPT 2005] I. Mantin, "Predicting and Distinguishing Attacks on RC4 Keystream Generator" [EUROCRYPT 1997] J. D. Golic, Linear Statistical Weakness of Alleged RC4 Key-Stream Generator [FSE 2000] S. R. Fluhrer and D. A. McGrew, Statistical Analysis of the Alleged RC4 Keystream Generator [FSE 2001] I. Mantin and A. Shamir, A Practical Attack on Broadcast RC4 [ASIACRYPT 1998 ] L. R. Knudsen, W. Meier, B. Preneel, V. Rijmen, S. Verdoolaege, Analysis methods for (alleged) RC4 [IEICE 2003] Y. Shiraishi, T. Ohigashi, and M.Morii, "Internal-State Reconstruction of a Stream Cipher RC4 [CRYPTO 2008] A.Maximov and D. Khovratovich, "New State Recovery Attack on RC4" [R 1995] A. Roos, Class of weak keys in the RC4 stream cipher Two posts in sci.crypt, 1995 [SAC 2010] P.Sepehrdad, S. Vaudenay, and M. Vuagnoux, Discovery and Exploitation of New Biases in RC4 Discovery and Exploitation ofnew Biases in RC4 [JIP 2014] A. Nagao, T. Ohigashi, T. Isobe, and M. Morii, "Expanding Weak-Key Space of RC4," [FSE 2011] S. Maitra, G. Paul, and S. Sen Gupta, Attack on Broadcast RC4 revisit [CRYPTO 2002] I.Mironov, (Not so) Random Shuffles of RC4 [eprint 2013] S. Sen Gupta, S. Maitra, W. Meier, G.Paul and S. Sarkar Some results on RC4 in WPA

BEASTとの 比 較 仮 定 1 (HTTPリクエスト 大 量 に 生 成 可 能 ) RC4 : 最 悪 2 34 程 度 で 攻 撃 可 能 BEAST : 攻 撃 不 可 仮 定 2 (HTTPリクエスト 大 量 に 生 成 可 能 + リクエストPOSTの 長 さをコントロ ール 可 能 ) RC4 : 場 所 の 最 適 化 で2 34 以 下 の 攻 撃 は 可 能 BEAST : 攻 撃 不 可 仮 定 3 (HTTPリクエスト 大 量 に 生 成 可 能 + リクエストPOSTの 長 さをコントロ ール 可 能 + リクエストの 一 部 を 改 ざん 可 能 ) RC4 : 場 所 の 最 適 化 で2 34 以 下 の 攻 撃 は 可 能 BEAST : 最 悪 2 8 程 度 で 攻 撃 可 能 (byte 単 位 guess)