WEKO3
アイテム
改良Initial Structureを用いた中間一致攻撃
https://uec.repo.nii.ac.jp/records/2240
https://uec.repo.nii.ac.jp/records/22401baceb2b-b6af-421f-a02e-e7d4604ad405
名前 / ファイル | ライセンス | アクション |
---|---|---|
1130029.pdf (598.1 kB)
|
|
Item type | 学位論文 / Thesis or Dissertation(1) | |||||
---|---|---|---|---|---|---|
公開日 | 2013-03-25 | |||||
タイトル | ||||||
タイトル | 改良Initial Structureを用いた中間一致攻撃 | |||||
言語 | ja | |||||
言語 | ||||||
言語 | jpn | |||||
資源タイプ | ||||||
資源タイプ識別子 | http://purl.org/coar/resource_type/c_46ec | |||||
資源タイプ | thesis | |||||
著者 |
小松原, 航
× 小松原, 航 |
|||||
抄録 | ||||||
内容記述タイプ | Abstract | |||||
内容記述 | ハッシュ関数は任意長データに対して固定長データであるハッシュ値を出力する関数であり,認証や改竄防止などで使われる.ハッシュ関数の原像攻撃耐性とは関数Hについて出力hが与えられた際に,h=H(M)となるような入力M(原像)を求めるのが難しいという安全性である. 力づく攻撃で原像を求める場合,出力がnビットの関数の場合,Mを変えて2^n回関数を計算することで計算結果が与えられた出力と一致し,原像が求まる.これに対して中間一致攻撃とは関数を独立計算可能な2つの計算に分け,それぞれの計算を2^(n/2)回独立に行うことで,関数の中間で2^n回の一致を確かめ,原像を求める攻撃であり,力づく攻撃よりも少ない計算回数で原像を求められる.なお,一致を確かめるために独立計算を行う関数の一方の計算結果を2^(n/2)通りメモリに保存する.Initial Structure(IS)は,中間一致攻撃で独立計算可能なステップ数を増やす技術である.本研究ではISを2つの観点から改良し,以下の成果を得た. (成果1):Aokiらによる52ステップのSHA-0及び48ステップのSHA-1への中間一致攻撃では,ワード単位で解析されたISを用いていたため,少ないステップのISしか構築できなかった.本研究ではビット単位で解析し,多いステップのISを構築したことで,中間一致攻撃可能なステップ数を増やした結果,攻撃可能なステップ数を,SHA-0は52ステップから54ステップに,SHA-1は48ステップから54ステップに増やした. (成果2):SasakiらによるMD5と4-passHAVALの中間一致攻撃では,ISの一部の計算で独立計算ができなかった.そのためこの計算を行わず,計算結果を仮定して中間一致攻撃を行い,一致した後に仮定した計算結果が正しいかどうかのチェックを行う方法をとった.この方法ではチェックを行うために計算結果をメモリに保存する必要があり,その分メモリを多く使用することになり,結果的に膨大なメモリを必要とした.本研究ではISの計算の一部を,独立計算しやすい等価な計算に置き換えてCFを独立な2つの計算に分けることで,Sasakiらの攻撃のように余分なメモリを使用することなく攻撃可能とし,結果的に中間一致攻撃で必要なるメモリ量の劇的な削減に成功した.具体的には,MD5では2^45から2^13に,4passHAVALでは2^64から2^30に削減した. | |||||
学位授与機関 | ||||||
学位授与機関名 | 電気通信大学 | |||||
学位授与年度 | ||||||
内容記述タイプ | Other | |||||
内容記述 | 2012 | |||||
学位授与年月日 | ||||||
学位授与年月日 | 2013-03-25 | |||||
専攻 | ||||||
値 | 総合情報学専攻 |