狠狠撸

確率推論アルゴリズムに基づく
ストリーム暗号の鍵推定に関する一考察
飯窪祐二堀井俊佑松嶋敏泰
早稲田大学基幹理工学研究科数学応用数理専攻

1

１．研究背景
? 暗号公開鍵暗号
ブロック暗号
共通鍵暗号
ストリーム暗号
? ストリーム暗号
ビット毎に逐次的に暗号化を行う暗号．
鍵共通鍵
擬似乱数擬似乱数
生成器生成器
鍵系列鍵系列
平文 …010… 暗号文 …010… 平文
…110… …100… …110…

暗号化復号化

ストリーム暗号の安全性＝擬似乱数生成器の安全性
2

２．研究目的(1/2)
? 擬似乱数生成器の種類
? 非線形コンバイナ型 ? 非線形フィルター型
? E0（Bluetooth） ? A5/1，A5/2（携帯電話）
? RC4（Webブラウザ，無線LAN） etc…
? 従来研究
各擬似乱数生成器に対して，その構造に合わせた攻撃法．
例．非線形コンバイナ型乱数生成器に対して
?相関攻撃 [Siegenthaler ’85]
?高速相関攻撃 [Mihaljevic ’01]
etc…

攻撃攻撃攻撃

擬似乱数擬似乱数擬似乱数
生成器生成器生成器
3

２．研究目的(2/2)
? 本研究の目的
擬似乱数生成器を確率モデルとして捉えることで，統一的な
視点から様々な擬似乱数生成器に対する攻撃法を提案．

本研究の視点

擬似乱数擬似乱数擬似乱数
生成器生成器生成器

今回は例として，
非線形コンバイナ型乱数生成器とE0について攻撃を行った．
4

３．問題設定(1/2)
? 擬似乱数生成器の確率モデル
s ? {0,1}L ：鍵
z ? {0,1}N ：鍵系列
P ( z | s)
P (s) s 擬似乱数 z
生成器

ある確率分布に
従って発生 z は s から確定的
?0
P ( z | s) ? ?
? 既知平文攻撃 ?1
既知： z , P (s) , P (z | s)
未知： s
既知情報から未知 s を求める．
5

３．問題設定(2/2)
? 統計的決定理論に基づく最適な鍵推定 [Ety ’10]
s ? {0,1}L ：鍵の推定値
?
決定関数 s ? ? (z )
?

最適な決定関数 ? (z ) →平均誤り率最小
?

事後確率最大とする決定

? ? (z ) ? arg max P(s | z )
s
? arg max P (s, z ) （∵ベイズの定理）
s

擬似乱数生成器を同時確率関数で表現

鍵推定アルゴリズムの提案
6

４．拟似乱数生成器(1/4)
線形フィードバックシフトレジスタ(LFSR)を用いて構成されるものが多い．
? LFSR
xn ? {0,1}：LFSRの出力系列のnビット目
初期状態＝鍵擬似乱数系列を出力
（Nビット）
xL x2 x1
xL ?1

? ：１対１対応，出力から鍵を求めるのは容易
→ の代わりにの同時確率を考える．
? 出力系列の同時確率関数は，

nビット目の値は初期状態から
7 鍵＝一様と仮定確定的に決まる(= 0 or 1 )

４．擬似乱数生成器(2/4)
? 非線形コンバイナ型乱数生成器(NCG)
K個のLFSRと１個のK入力１出力非線形関数から構成される．
z n ? {0,1}：鍵系列のnビット目
xn1)
(
LFSR(１) zn
非線形
関数f
xn K )
(
LFSR(K)
f : {0,1}K ? {0,1}
? の同時確率関数

LFSR(k)の出力系列が偽
8 の同時確率が真

? E0
４個のLFSRと１個の有限状態機械(FSM)から構成される．
y n ：n時点のLFSRの出力の総和
? n ：n時点のFSMの状態

xn1)
(
LFSR(１) yn
( 4)
＋ FSM ? n ?1
x
?n
n
LFSR(４)
zn

FSMの状態遷移関数
9

? の同時確率関数
LFSR(k)の出力系列
の同時確率

10

５．確率推論アルゴリズムに基づく鍵推定(1/5)
z が与えられたもとで，同時確率を最大とするを求めたい．
（となる） →最適
→鍵の長さの指数オーダの計算量

近似手法として，本研究では．．．
sum-productアルゴリズムにより周辺確率を効率的に計算．
→ファクターグラフ上でメッセージ伝搬による計算
なぜなら．．．ストリーム暗号 [Mihaljevic ’01]
符号理論への攻撃 [Hosobuchi’06]
における復号
画像処理 etc…

→同時確率ではなく周辺確率を求めることが有効．
11

? ファクターグラフ
関数の因数分解の構造を表現したグラフ．

例 g ( x1 , x2 , x3 , x4 ) ? f A ( x1 , x2 , x3 ) f B ( x2 , x3 , x4 )

fA fB

○：変数ノード
■：因数ノード
x1 x2 x3 x4

12

? 擬似乱数生成器の同時確率関数のファクターグラフ
? LFSR部分 ? E0

xn2 )
(
xn3)
(

x (k )
x (k )
x (k ) xn1)
(
xn4 )
(
1 2 N

? NCGの非線形関数部分 yn
xn1)
(

?n ? n ?1
zn
xn K )
(
x ( 2)
n

13

? sum-productアルゴリズム(1/2)
ファクターグラフ上でメッセージと呼ばれる値を伝搬させること
で周辺確率を効率的に計算するアルゴリズム．
? x? f (x) ：xからfへのメッセージ
? f ? x (x) ：fからxへのメッセージ
→初期値を適当に仮定 ? x? f (x) f

? 変数ノード→因数ノードの更新 x
? f ? x (x)

n( x ) { f } n( f ) {x}
? 因数ノード→変数ノードの更新

14

? sum-productアルゴリズム(2/2)
? 周辺確率の計算
最大 I 回のメッセージ更新後，以下を計算．( I は予め設定)

x
なし???真の周辺確率
→ファクターグラフにループ
あり???近似周辺確率

の大きい方を鍵のビットとして推定
? 計算量
ファクターグラフに含まれる枝数の指数オーダ
→LFSR部分の枝数が非常に多い＝計算量：大
基本的に鍵の一部（Bビット）を全数探索
→前処理として[Mihaljevic ’01]の方法を用いることで枝数削減

15

６．シミュレーション(1/3)
? シミュレーション内容
? 同じLFSRの組を用いたNCGとE0について攻撃
K ?4

? パラメータ
L ：LFSRの長さの合計（鍵のビット数）固定
N ：観測された鍵系列長
B ：全数探索にあてるビット数変化

? それぞれ１０００回ずつ攻撃を行う．

16

? 実験１ L ? 64, N ? 60
1.E+00

攻 1.E-01
良
撃
1.E-02
成 NCG
功 1.E-03
確 E0
率 1.E-04 random
悪
1.E-05
残りのビットを
36 40 44 48 52 56 60
ランダムに選ぶ
B
計算量
小大
17

? 実験２ L ? 128, N ? 80
1.E+00

攻 1.E-01
良
撃
1.E-02
成 NCG
功 1.E-03
確 E0
率 1.E-04 random
悪
1.E-05
100 104 108 112 116 120 124
B
計算量
小大
18

７．考察
? 実験より
僅かではあるが，鍵の全数探索より少ない計算量で高い
攻撃成功確率となる．

? NCGについての従来法
? 高速相関攻撃[Mihaljevic ’01]
1つのLFSRに対する攻撃
→攻撃成功確率，計算量の比較が困難

課題
? E0についての従来法提案法との比較
? 条件付相関攻撃[Yi Lu ’05]
L=128に対して O (238 ) の計算量で高い攻撃成功確率．

19

８．まとめと今後の課題
? まとめ
? 擬似乱数生成器を確率モデルと見ることで，NCGとE0に対
する鍵推定アルゴリズムの提案を行った．
? 最適な鍵推定方法の近似手法として，sum-productアルゴリ
ズムを用いた．
? 提案した攻撃法について，シミュレーションによる評価を
行った．

? 今後の課題
? 提案法と従来法の比較．
? 他の擬似乱数生成器に対する鍵推定アルゴリズムの提案．
? 他の近似アルゴリズムによる計算手法の研究．

20

付録１．全数探索するビット

鍵
全数探索（合計Bビット）
B
→LFSR１つに対して，平均ビット
K

21

付録２．高速相関攻撃[Mihaljevic ’01]
? LFSRを“１つずつ”攻撃する

LFSR
非線形
関数f
LFSR

LFSR 通信路と近似

評価：１つのLFSRに対しての攻撃成功確率
→全てのLFSRに対しての攻撃成功確率は？
攻撃するLFSRの順番等も考慮すると難しい

22

付録３．[Mihaljevic ’01]の前処理
? パリティ検査行列
LFSRの出力ビット間の制約を表す．

?1011010 ? 行和計算１の数が少ない
?1101110 ? （GF(2)上）ものを探索

１の数が多い追加
＝枝数が多い

新たなパリティ検査行列

x1( k ) x2k )
(
xN )
(k

23

狠狠撸

ma99992011id508

Recommended

More Related Content

What's hot (14)

Viewers also liked (6)

More from matsushimalab (20)

ma99992011id508