パリティ検査式を動的に構成する高速相関攻撃の解析

摘要

ストリーム暗号は，暗号化と復号に同じ秘密鍵を用いる対称鍵暗号の1つであり，秘密鍵および公開IVで決まるシードから擬似乱数系列を生成し，平文系列とシンボル毎の排他的論理和をとることで平文系列の情報を秘匿する．高速相関攻撃(FCA)は，擬似乱数生成器の構造を既知と仮定して，平文系列と暗号文系列の対から得られる擬似乱数系列から，擬似乱数生成器の内部状態を再構成するという既知平文攻撃である．FCAの議論では，一般に，攻撃対象として，非線形コンバイナ型乱数生成器(NCG)と呼ばれる複数の2元の線形フィードバックシフトレジスタ(LFSR)と非線形ブール関数から構成された擬似乱数生成器が想定されている．既に我々は，LFSRの出力系列を推定する際に，過去に推定したビットの情報を用いてパリティ検査式の集合を動的に構成し，それを用いてその他のビットを推定するという，新しいFCAの手法を提案している1．本稿では，我々の提案した手法に関して，攻撃の成功確率，攻撃に要する計算量，メモリサイズの理論式を導出し，既存手法2と比較することでその有効性を示す．