Security of Cryptosystems Using Merkle-Damgard in the Random Oracle Model

スポンサーリンク

概要

• 論文の詳細を見る

• Since the Merkle-Damgård hash function (denoted by MDFH) that uses a fixed input length random oracle as a compression function is not indifferentiable from a random oracle (denoted by RO) due to the extension attack, there is no guarantee for the security of cryptosystems, which are secure in the RO model, when RO is instantiated with MDHF. This fact motivates us to establish a criteria methodology for confirming cryptosystems security when RO is instantiated with MDHF. In this paper, we confirm cryptosystems security by using the following approach: 1. Find a weakened random oracle (denoted by WRO) which leaks values needed to realize the extension attack. 2. Prove that MDHF is indifferentiable from WRO. 3. Prove cryptosystems security in the WRO model. The indifferentiability framework of Maurer, Renner and Holenstein guarantees that we can securely use the cryptosystem when WRO is instantiated with MDHF. Thus we concentrate on such finding WRO. We propose Traceable Random Oracle (denoted by TRO) which leaks values enough to permit the extension attack. By using TRO, we can easily confirm the security of OAEP encryption scheme and variants of OAEP encryption scheme. However, there are several practical cryptosystems whose security cannot be confirmed by TRO (e.g. RSA-KEM). This is because TRO leaks values that are irrelevant to the extension attack. Therefore, we propose another WRO, Extension Attack Simulatable Random Oracle (denoted by ERO), which leaks just the value needed for the extension attack. Fortunately, ERO is necessary and sufficient to confirm the security of cryptosystems under MDHF. This means that the security of any cryptosystem under MDHF is equivalent to that under the ERO model. We prove that RSA-KEM is secure in the ERO model.

• （社）電子情報通信学会の論文
• 2011-01-01

著者

• 米山 一樹

  電気通信大学情報通信工学専攻

• WANG Lei

  University of Electro-Communications

• OHTA Kazuo

  University of Electro-Communications

• NAITO Yusuke

  Mitsubishi Electric Corporation

• YONEYAMA Kazuki

  NTT Information Sharing Platform Laboratories, NTT Corporation

• Ohta Kazuo

  Department Of Informatics The University Of Electro-communications

• Yoneyama Kazuki

  Ntt Information Sharing Platform Laboratories Ntt Corporation

• Naito Yusuke

  Mitsubishi Electric Corp. Kamakura‐shi Jpn

• Yoneyama Kazuki

  NTT Information Sharing Platform Laboratories

関連論文

• A-7-29 パスワードベース認証付き鍵交換の安全性における(不)可能性(A-7. 情報セキュリティ,一般セッション)
• ハッシュリストの閲覧可能なランダムオラクルモデル(情報通信基礎サブソサイエティ合同研究会)
• 受信者の条件を秘匿したAttribute-Based Encryption
• Task-Structured PIOAフレームワークを用いた適応的攻撃者に対するDiffie-Hellman鍵交換の安全性解析(セキュリティ,フォーマルアプローチ論文)
• Secret Handshakeの安全性について(情報通信基礎サブソサイエティ合同研究会)
• Cryptanalysis of Two MD5-Based Authentication Protocols: APOP and NMAC
• Extended Password Recovery Attacks against APOP, SIP, and Digest Authentication
• ハッシュリストの閲覧可能なランダムオラクルモデル(情報通信基礎サブソサイエティ合同研究会)
• ハッシュリストの閲覧可能なランダムオラクルモデル(情報通信基礎サブソサイエティ合同研究会)
• Toward the Fair Anonymous Signatures : Deniable Ring Signatures(Signatures,Cryptography and Information Security)
• Security of Cryptosystems Using Merkle-Damgård in the Random Oracle Model
• Preimage Attack on 23-Step Tiger
• Secret Handshakeの安全性について(情報通信基礎サブソサイエティ合同研究会)
• Secret Handshakeの安全性について(情報通信基礎サブソサイエティ合同研究会)
• AS-3-3 非線形ランプ型秘密分散(招待講演,AS-3.情報ハイディングの理論と技術,シンポジウム)
• 分散画像の回転を許す一般アクセス構造に対して複数の画像を隠す視覚復号型秘密分散法
• 確率的メータリング法(ブロードバンドモバイル時代における基礎技術)(情報通信サブソサイエティ合同研究会)
• 確率的メータリング法(ブロードバンドモバイル時代における基礎技術)(情報通信サブソサイエティ合同研究会)
• 確率的メータリング法(ブロードバンドモバイル時代における基礎技術)(情報通信サブソサイエティ合同研究会)
• Extension of Secret Handshake Protocols with Multiple Groups in Monotone Condition
• Standard Deviation and Intra Prediction Mode Based Adaptive Spatial Error Concealment (SEC) in H.264/AVC
• Variable Block Size Motion Vector Retrieval Schemes for H.264 Inter Frame Error Concealment
• Cryptanalysis of Two MD5-Based Authentication Protocols : APOP and NMAC
• Practical Password Recovery Attacks on MD4 Based Prefix and Hybrid Authentication Protocols
• Extended Password Recovery Attacks against APOP, SIP, and Digest Authentication
• A Strict Evaluation on the Number of Conditions for SHA-1 Collision Search
• New Message Differences for Collision Attacks on MD4 and MD5
• Improved Collision Attacks on MD4 and MD5(Hash Functions,Cryptography and Information Security)
• Universally composable client-to-client general authenticated key exchange (特集:情報システムを支えるコンピュータセキュリティ技術の再考)
• On Clock-Based Fault Analysis Attack for an AES Hardware Using RSL
• Universally Composable Hierarchical Hybrid Authenticated Key Exchange(Protocols,Cryptography and Information Security)
• Improved Collision Search for Hash Functions : New Advanced Message Modification
• Probabilistic Multi-Signature Schemes Using a One-Way Trapdoor Permutation(Discrete Mathematics and Its Applications)
• OAEP-ES : Methodology of Universal Padding Technique (Asymmetric Cipher) (Cryptography and Information Security)
• Solutions to Security Problems of Rivest and Shamir's Pay Word Scheme(Application)(Cryptography and Information Security)
• Provably Secure Multisignatures in Formal Security Model and Their Optimality
• Taxonomical Security Consideration of OAEP Variants(Discrete Mathematics and Its Applications)
• Proxiable Designated Verifier Signature
• Preimage Attack on 23-Step Tiger
• Power Analysis against a DPA-Resistant S-Box Implementation Based on the Fourier Transform
• Near-Collision Attacks on MD4 : Applied to MD4-Based Protocols
• Maurer-Yacobi ID-Based Key Distribution Revisited(Discrete Mathematics and Its Applications)
• Security of Cryptosystems Using Merkle-Damgard in the Random Oracle Model
• Visual Secret Sharing Schemes for Multiple Secret Images Allowing the Rotation of Shares(Discrete Mathematics and Its Applications)
• Efficient and Strongly Secure Password-based Server Aided Key Exchange
• Ring signatures: universally composable definitions and constructions (特集:情報システムを支えるコンピュータセキュリティ技術の再考)
• Differential-Linear Cryptanalysis of FEAL-8 (Special Section on Cryptography and Information Security)
• Leaky Random Oracle
• FOREWORD
• Universally Composable NBAC-Based Fair Voucher Exchange for Mobile Environments
• How to Shorten a Ciphertext of Reproducible Key Encapsulation Mechanisms in the Random Oracle Model
• Hierarchical ID-Based Authenticated Key Exchange Resilient to Ephemeral Key Leakage
• De-embedding of On-Chip Inductor at Millimeter-Wave Range
• Strongly Secure Predicate-Based Authenticated Key Exchange : Definition and Constructions
• Indifferentiable Security Reconsidered : Role of Scheduling
• Meet-in-the-Middle (Second) Preimage Attacks on Two Double-Branch Hash Functions RIPEMD and RIPEMD-128
• Toward Effective Countermeasures against an Improved Fault Sensitivity Analysis
• Proxiable Designated Verifier Signature
• A New Type of Fault-Based Attack: Fault Behavior Analysis

もっと見る 閉じる

スポンサーリンク