MD5に対するコリジョンアタックの改良
スポンサーリンク
概要
- 論文の詳細を見る
EUROCRYPT2005でWangらによりMD5への攻撃が提案された.この攻撃はコリジョンを作るための十分条件(sufficient condition)を求め, 確定的に条件を満たすようにメッセージを変更して攻撃の成功確率を上げている.この攻撃ではメッセージを変更しても満たせない条件が37個残る.よって攻撃の計算量は2^<37>である.その後KlimaはWangらの条件を33個に減らし, 攻撃の計算量を2^<33>に改良した.本稿では, より多くの条件を満たすことができるメッセージの変更法を提案し, 満たすことのできない条件の数を29個にする.この修正は確率的で, 修正が成功する確率は全体でおよそ1/2である.よって我々の提案する攻撃の計算量は2^<30>となる.さらにWangらのコリジョン探索アルゴリズムを改良し, 計算量を5/8程度に抑える方法を提案する.
- 社団法人電子情報通信学会の論文
- 2005-11-08
著者
-
太田 和夫
電気通信大学情報通信工学科
-
國廣 昇
東京大学大学院新領域創成科学研究科
-
國廣 昇
東京大学大学院新領域創成科学研究科複雑理工学専攻
-
佐々木 悠
Ntt情報流通プラットフォーム研究所:電気通信大学
-
國廣 昇
電気通信大学情報通信工学科
-
太田 和夫
電気通信大学
-
内藤 祐介
三菱電機株式会社
-
佐々木 悠
電気通信大学
-
内藤 祐介
電気通信大学
-
太田 和夫
電通大
関連論文
- 複数の計算量仮定を組み込んだメタ帰着技法による安全性解析 : ElGamal暗号の場合
- A-7-29 パスワードベース認証付き鍵交換の安全性における(不)可能性(A-7. 情報セキュリティ,一般セッション)
- 多重リング構造のk-out-of-n署名の修正提案(情報通信基礎サブソサイエティ合同研究会)
- ハッシュリストの閲覧可能なランダムオラクルモデル(情報通信基礎サブソサイエティ合同研究会)
- 受信者の条件を秘匿したAttribute-Based Encryption
- 1.証明可能安全性理論に向けて(暗号技術の証明可能安全性)
- 電子オークションプロトコルの技術動向:第一価格秘密入札プロトコルについて
- 研究グループが脆弱性を発見した場合にとるべき行動についての法的考察(プロジェクトマネジメント関係,一般)
- Task-Structured PIOAフレームワークを用いた適応的攻撃者に対するDiffie-Hellman鍵交換の安全性解析(セキュリティ,フォーマルアプローチ論文)
- Secret Handshakeの安全性について(情報通信基礎サブソサイエティ合同研究会)
- 画像の回転に対する新しい視覚復号型秘密分散法
- 暗号における理論と実装のギャップ : 置き換えアプローチの二面性(暗号理論入門(4))
- シミュレーションによるSubset-Cover Revocation法の性能比較
- APOPが破られた(オピニオン)
- Subset-Cover Revocation法の性能比較(モバイル環境におけるPerson to person高信頼性情報流通技術)(情報通信サブソサイエティ合同研究会)
- MicroMint方式におけるCollision生成法の解析
- ハッシュ連鎖つきコリジョンを用いた小額決済方式(モバイル環境におけるPerson to Person高信頼性情報流通技術)(情報通信サブソサイエティ合同研究会)
- ハッシュ連鎖つきコリジョンを用いた小額決済方式(モバイル環境におけるPerson to person高信頼性情報流通技術 : 情報通信サブソサイエティ合同研究会)
- ゼロ知識性の完全化による'On the Fly'認証方式の効率化(セキュリティ関係,一般)
- ゼロ知識性の完全化による'On the Fly'認証方式の効率化(セキュリティ関係,一般)
- ゼロ知識性の完全化による'On the Fly'認証方式の効率化(セキュリティ関係,一般)
- ゼロ知識性の完全化による'On the Fly'認証方式の効率化(セキュリティ関係,一般)
- ゼロ知識性の完全化による'On the Fly'認証方式の効率化(セキュリティ関係,一般)
- ゼロ知識性の完全化による'On the Fly'認証方式の効率化(セキュリティ関係,一般)
- ゼロ知識性の完全化による'On the Fly'認証方式の効率化(セキュリティ関係,一般)
- ゼロ知識性の完全化による'On the Fly'認証方式の効率化(セキュリティ関係,一般)
- ゼロ知識性の完全化による'On the Fly'認証方式の効率化(セキュリティ関係,一般)
- ゼロ知識性の完全化による'On the Fly'認証方式の効率化(セキュリティ関係,一般)
- ゼロ知識性の完全化による'On the Fly'認証方式の効率化(セキュリティ関係,一般)
- ゼロ知識性の完全化による'On the Fly'認証方式の効率化(セキュリティ関係,一般)
- ゼロ知識性の完全化による'On the Fly'認証方式の効率化(セキュリティ関係,一般)
- ゼロ知識性の完全化による'On the Fly'認証方式の効率化(セキュリティ関係,一般)
- ゼロ知識性の完全化による'On the Fly'認証方式の効率化(セキュリティ関係,一般)
- XOAEPX_ : OAEPの変形可能性について(モバイル環境におけるPerson to person高信頼性情報流通技術)(情報通信サブソサイエティ合同研究会)
- XOAEPX-** : OAEPの変形可能性について(モバイル環境におけるPerson to person高信頼性情報流通技術 : 情報通信サブソサイエティ合同研究会)
- XOAEPX-** : OAEPの変形可能性について(モバイル環境におけるPerson to person高信頼性情報流通技術)(情報通信サブソサイエティ合同研究会)
- 連鎖する複数業者との個人取引におけるプライバシー保護方法(その2)(ブロードバンドモバイル時代における基礎技術)(情報通信サブソサイエティ合同研究会)
- 連鎖する複数業者との個人取引におけるプライバシー保護方法(その2)(ブロードバンドモバイル時代における基礎技術)(情報通信サブソサイエティ合同研究会)
- 連鎖する複数業者との個人取引におけるプライバシー保護方法(その2)(ブロードバンドモバイル時代における基礎技術)(情報通信サブソサイエティ合同研究会)
- ハッシュ連鎖つきコリジョンを用いた小額決済方式(モバイル環境におけるPerson to person高信頼性情報流通技術)(情報通信サブソサイエティ合同研究会)
- ハッシュ連鎖つきコリジョンを用いた小額決済方式(モバイル環境におけるPerson to person高信頼性情報流通技術)(情報通信サブソサイエティ合同研究会)
- 解説 電子オークションプロトコルの技術動向--第一価格秘密入札プロトコルについて
- ランダムマップを使うハッシュ関数のコリジョンサーチ
- ハッシュリストの閲覧可能なランダムオラクルモデル(情報通信基礎サブソサイエティ合同研究会)
- ハッシュリストの閲覧可能なランダムオラクルモデル(情報通信基礎サブソサイエティ合同研究会)
- Bulk量子計算モデル上におけるGroverのアルゴリズムの繰返し回数について
- 物理的実現可能性に優れたNMR量子探索アルゴリズム(計算理論)
- A-7-11 MD4を用いたチャレンジ&レスポンス認証に対する現実的な攻撃(A-7.情報セキュリティ,一般セッション)
- 量子アルゴリズムに対する共通鍵暗号の安全性
- 公開鍵暗号系における双対性へのアプローチ
- Paillierの観点から見たディジタル署名の安全性の再考
- 否認機能を持つリング署名方式の再考(その2) : 署名者の匿名性を強化したグループ署名方式
- 双線形写像を用いた墨塗り署名方式の安全性について(セキュリティ基盤技術,ユビキタス社会を支えるコンピュータセキュリティ技術)
- Physically Unclonable Functionを用いたLuby-Rackoff型暗号の再考(セキュリティ関係,一般)
- Physically Unclonable Functionを用いたLuby-Rackoff型暗号の再考(セキュリティ関係,一般)
- Physically Unclonable Functionを用いたLuby-Rackoff型暗号の再考(セキュリティ関係,一般)
- MicroMint方式におけるCollision生成法の解析
- NMR量子計算機を用いた効率的探索アルゴリズムの設計について
- NMR量子コンピュータ上における効率的量子探索アルゴリズム
- A-7-1 PINを用いるアルゴリズム的耐タンパ認証装置の安全性について(A-7.情報セキュリティ,一般セッション)
- PINを用いるアルゴリズム的耐タンパ認証装置の再考(その2)
- A-7-4 マルチパーティモデルでの署名交換の公平性の再考(A-7.情報セキュリティ,一般講演)
- A-7-17 利用者のプライバシ保護を強化したブラインド署名方式(A-7. 情報セキュリティ, 基礎・境界)
- A-7-7 ES方式の通信効率に関する再考察(A-7. 情報セキュリティ)
- REACT-ES & OAEP++-ES : 更に有効な落し戸付き乗法的一方向性関数向け万能Padding方式(モバイル環境におけるPerson to person高信頼性情報流通技術)(情報通信サブソサイエティ合同研究会)
- REACT-ES & OAEP++-ES : 更に有効な落し戸付き乗法的一方向性関数向け万能Padding方式(モバイル環境におけるPerson to person高信頼性情報流通技術 : 情報通信サブソサイエティ合同研究会)
- REACT-ES & OAEP++-ES : 更に有効な落し戸付き乗法的一方向性関数向け万能Padding方式(モバイル環境におけるPerson to person高信頼性情報流通技術)(情報通信サブソサイエティ合同研究会)
- REACT-ES & OAEP++-ES : 更に有効な落し戸付き乗法的一方向性関数向け万能Padding方式(モバイル環境におけるPerson to person高信頼性情報流通技術)(情報通信サブソサイエティ合同研究会)
- 強識別不可能性理論とSHA-3プロジェクト : ハッシュ関数設計のための理論研究と実装研究の現状(一般:情報通信基礎サブソサイエティ合同研究会)
- 強識別不可能性理論とSHA-3プロジェクト : ハッシュ関数設計のための理論研究と実装研究の現状(一般:情報通信基礎サブソサイエティ合同研究会)
- 強識別不可能性理論とSHA-3プロジェクト : ハッシュ関数設計のための理論研究と実装研究の現状(一般:情報通信基礎サブソサイエティ合同研究会)
- Secret Handshakeの安全性について(情報通信基礎サブソサイエティ合同研究会)
- Secret Handshakeの安全性について(情報通信基礎サブソサイエティ合同研究会)
- AS-3-3 非線形ランプ型秘密分散(招待講演,AS-3.情報ハイディングの理論と技術,シンポジウム)
- 分散画像の回転を許す一般アクセス構造に対して複数の画像を隠す視覚復号型秘密分散法
- 確率的メータリング法(ブロードバンドモバイル時代における基礎技術)(情報通信サブソサイエティ合同研究会)
- 確率的メータリング法(ブロードバンドモバイル時代における基礎技術)(情報通信サブソサイエティ合同研究会)
- 確率的メータリング法(ブロードバンドモバイル時代における基礎技術)(情報通信サブソサイエティ合同研究会)
- 回転操作が可能な視覚復号型秘密分散法の一般的構成法
- 暗号プロトコルの安全性証明自動化技術 (特集 情報セキュリティ技術)
- Randomized Partial Checking Mix の一考察
- Randomized Partial Checking Mix の一考察
- Randomized Partial Checking Mix の一考察
- Randomized Partial Checking Mix の一考察
- Randomized Partial Checking Mix の一考察
- Randomized Partial Checking Mix の一考察
- 離散対数問題に基づいた多重署名を用いた追跡不可能な電子現金方式
- 4J-6 骨伝導技術を用いたカラオケシステムの提案(医療のインフォマティクス,一般セッション,コンピュータと人間社会,情報処理学会創立50周年記念)
- XOAEPX-** : OAEPの変形可能性について(モバイル環境におけるPerson to person高信頼性情報流通技術)(情報通信サブソサイエティ合同研究会)
- 安全性を証明可能なハッシュ関数の設計論
- RSA暗号に対する格子理論に基づく攻撃(その2)
- 暗号学における双対性 : ゴールとシナリオの間には(チュートリアル)
- RSA暗号に対する格子理論に基づく攻撃
- 墨塗り・削除署名の拡張
- 墨塗り・削除署名の拡張
- 使い捨てIDを用いた処理負荷の少ない相手認証方式の提案(情報通信基礎サブソサイエティ合同研究会)
- 多重リング構造のk-out-of-n署名の修正提案(情報通信基礎サブソサイエティ合同研究会)
- 多重リング構造のk-out-of-n署名の修正提案(情報通信基礎サブソサイエティ合同研究会)
- How to construct cryptosystems and hash functions in weakened random oracle models (情報セキュリティ)
- How to construct cryptosystems and hash functions in weakened random oracle models (情報通信システムセキュリティ)