Improved Collision Attacks on MD4 and MD5(Hash Functions,<Special Section>Cryptography and Information Security)

スポンサーリンク

概要

• 論文の詳細を見る

• At Eurocrypt'05, Wang et al. presented efficient collision attacks on MD5 and MD4 hash functions. They found a collision of MD5 with a complexity of less than 2^<37> MD5 hash operations, and a collision of MD4 with complexity less than 2^8 MD4 hash operations. In their attack, the procedure to generate a collision is divided into 4 steps. First, they determine the message differential and output differentials of chaining variables in each step, which generates a collision with small complexity. Second, they construct sufficient conditions that guarantee that the desired differential is always calculated. Third, they find a message modification that can satisfy the sufficient conditions with high probability. Finally, they search for a message that satisfies all sufficient conditions. In this paper, we focus on the message modification of MD5 and MD4, and propose a new message modification. Using our message modification, a collision of MD5 can be found with complexity less than 2^<29> MD5 hash operations, and a collision of MD4 can be found with complexity less than 3 MD4 hash operations. To improve the complexity from previous attacks, we mainly use two ideas. The first idea is to use message modification that can satisfy more sufficient conditions in the second round than in previous attacks. The second idea is to use message modification that can enable us to search for a collision starting from an intermediate step.

• 社団法人電子情報通信学会の論文
• 2007-01-01

著者

• OHTA Kazuo

  University of Electro-Communications

• SASAKI Yu

  University of Electro-Communications

• KUNIHIRO Noboru

  University of Electro-Communica-tions

• Naito Yusuke

  University Of Electro-communications

• Ohta Kazuo

  Department Of Informatics The University Of Electro-communications

• Kunihiro Noboru

  Univ. Tokyo Kashiwa‐shi Jpn

関連論文

• 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
• Extension of Secret Handshake Protocols with Multiple Groups in Monotone Condition
• 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 (特集:情報システムを支えるコンピュータセキュリティ技術の再考)
• Deterministic Polynomial Time Equivalence between Factoring and Key-Recovery Attack on Takagi's RSA
• 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)
• Small Secret CRT-Exponent Attacks on Takagi's RSA
• 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)
• Exact Analyses of Computational Time for Factoring in Quantum Computers(Public Key Cryptography)(Cryptography and Information Security)
• 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)
• Ring signatures: universally composable definitions and constructions (特集:情報システムを支えるコンピュータセキュリティ技術の再考)
• Differential-Linear Cryptanalysis of FEAL-8 (Special Section on Cryptography and Information Security)
• Leaky Random Oracle
• FOREWORD
• Solving Generalized Small Inverse Problems
• 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
• 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

もっと見る 閉じる

スポンサーリンク