| 講演名 | 2009-03-09 パリティ検査式を動的に構成する高速相関攻撃の解析(情報通信基礎サブソサイエティ合同研究会) 福田 洋治, 白石 善明, 毛利 公美, 森井 昌克, |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | ストリーム暗号は,暗号化と復号に同じ秘密鍵を用いる対称鍵暗号の1つであり,秘密鍵および公開IVで決まるシードから擬似乱数系列を生成し,平文系列とシンボル毎の排他的論理和をとることで平文系列の情報を秘匿する.高速相関攻撃(FCA)は,擬似乱数生成器の構造を既知と仮定して,平文系列と暗号文系列の対から得られる擬似乱数系列から,擬似乱数生成器の内部状態を再構成するという既知平文攻撃である.FCAの議論では,一般に,攻撃対象として,非線形コンバイナ型乱数生成器(NCG)と呼ばれる複数の2元の線形フィードバックシフトレジスタ(LFSR)と非線形ブール関数から構成された擬似乱数生成器が想定されている.既に我々は,LFSRの出力系列を推定する際に,過去に推定したビットの情報を用いてパリティ検査式の集合を動的に構成し,それを用いてその他のビットを推定するという,新しいFCAの手法を提案している.本稿では,我々の提案した手法に関して,攻撃の成功確率,攻撃に要する計算量,メモリサイズの理論式を導出し,既存手法と比較することでその有効性を示す. |
| 抄録(英) | Stream cipher is one of primitive classes in symmetric key ciphers where plaintext symbols are combined with pseudo random symbols (key stream), by an exclusive-or operation. The random symbols are generated from random number generator which is initialized by using secret key and public IV. Fast correlation attack (FCA) is a known plaintext attack that assuming cryptanalyst knows structure of a target generator, he reconstructs internal state of the generator from the key stream. In FCA, a nonlinear combiner generator (NCG), which is composed of several linear feedback shift registers (LFSRs) and a nonlinear function, is generally considered as a target generator. We have already proposed an APP decoding based FCA that LFSR output bits are estimated by using some sets of parity checks, which is dynamically constructed by using previously estimated symbols. In this paper, we will evaluate the proposed FCA in terms of attack success probability and required time complexity, memory size, and show its effectiveness by comparing with the existing method. |
| キーワード(和) | ストリーム暗号 / 擬似乱数生成器 / 高速相関攻撃 / パリティ検査式 |
| キーワード(英) | stream cipher / pseudo random number generator / fast correlation attack / parity checks |
| 資料番号 | IT2008-53,ISEC2008-111,WBS2008-66 |
| 発行日 |
| 研究会情報 | |
| 研究会 | WBS |
|---|---|
| 開催期間 | 2009/3/2(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Wideband System(WBS) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | パリティ検査式を動的に構成する高速相関攻撃の解析(情報通信基礎サブソサイエティ合同研究会) |
| サブタイトル（和） | |
| タイトル（英） | Analysis of Fast Correlation Attack Using Dynamically Constructed Parity Checks |
| サブタイトル（和） | |
| キーワード(1)（和/英） | ストリーム暗号 / stream cipher |
| キーワード(2)（和/英） | 擬似乱数生成器 / pseudo random number generator |
| キーワード(3)（和/英） | 高速相関攻撃 / fast correlation attack |
| キーワード(4)（和/英） | パリティ検査式 / parity checks |
| 第 1 著者 氏名（和/英） | 福田 洋治 / Youji FUKUTA |
| 第 1 著者 所属（和/英） | 愛知教育大学 Aichi University of Education |
| 第 2 著者 氏名（和/英） | 白石 善明 / Yoshiaki SHIRAISHI |
| 第 2 著者 所属（和/英） | 名古屋工業大学 Nagoya Institute of Technology |
| 第 3 著者 氏名（和/英） | 毛利 公美 / Masami MOHRI |
| 第 3 著者 所属（和/英） | 岐阜大学 Gifu University |
| 第 4 著者 氏名（和/英） | 森井 昌克 / Masakatu MORII |
| 第 4 著者 所属（和/英） | 神戸大学 Kobe University |
| 発表年月日 | 2009-03-09 |
| 資料番号 | IT2008-53,ISEC2008-111,WBS2008-66 |
| 巻番号（vol） | vol.108 |
| 号番号（no） | 474 |
| ページ範囲 | pp.- |
| ページ数 | 8 |
| 発行日 | |