World Library  
Flag as Inappropriate
Email this Article

Preimage attack

Article Id: WHEBN0000969477
Reproduction Date:

Title: Preimage attack  
Author: World Heritage Encyclopedia
Language: English
Subject: Cryptographic hash function, MD2 (cryptography), SHA-1, Elliptic curve only hash, GOST (hash function)
Collection: Cryptographic Attacks
Publisher: World Heritage Encyclopedia

Preimage attack

In cryptography, a preimage attack on cryptographic hash functions tries to find a message that has a specific hash value. A cryptographic hash function should resist attacks on its preimage.

In the context of attack, there are two types of preimage resistance:

  • preimage resistance: for essentially all pre-specified outputs, it is computationally infeasible to find any input that hashes to that output, i.e., given y, it is difficult to find an x such that h(x) = y.[1]
  • second-preimage resistance: it is computationally infeasible to find any second input which has the same output as that of a specified input, i.e., given x, it is difficult to find a second preimage x′ ≠ x such that h(x) = h(x′).[1]

These can be compared with a collision resistance, in which it is computationally infeasible to find any two distinct inputs x, x′ that hash to the same output, i.e., such that h(x) = h(x′).[1]

Collision resistance implies second-preimage resistance,[1] but does not guarantee preimage resistance.[1]

Applied preimage attacks

By definition, an ideal hash function is such that the fastest way to compute a first or second preimage is through a brute force attack. For an n-bit hash, this attack has a time complexity 2n, which is considered too high for a typical output size of n = 128 bits. If such complexity is the best that can be achieved by an adversary, then the hash function is considered preimage-resistant.

Faster preimage attacks can be found by cryptanalysing certain hash functions, and are specific to that function. Some significant preimage attacks have already been discovered, but they are not yet practical. If a practical preimage attack is discovered, it would drastically affect many Internet protocols. In this case, "practical" means that it could be executed by an attacker with a reasonable amount of resources. For example, a preimaging attack that costs trillions of dollars and takes decades to preimage one desired hash value or one message is not practical; one that costs a few thousand dollars and takes a few weeks might be very practical.

All currently known practical or almost-practical attacks on MD5 and SHA-1 are collision attacks.[2][3] In general, a collision attack is easier to mount than a preimage attack, as it is not restricted by any set value (any two values can be used to collide). The time complexity of the collision attack, in contrast, is 2n/2.

See also


  • IETF RFC 4270: Attacks on Cryptographic Hashes in Internet Protocols
  1. ^ a b c d e Rogaway, P.; Shrimpton, T. "Cryptographic Hash-Function Basics: Definitions, Implications, and Separations for Preimage Resistance, Second-Preimage Resistance, and Collision Resistance" (PDF). Fast Software Encryption (2004) (Springer-Verlag). Retrieved 17 November 2012. 
  2. ^ Bruce Morton, Clayton Smith (30 January 2014). "Why We Need to Move to SHA-2". CA Security Council. 
  3. ^ "MD5 and Perspectives". 1 January 2009. 
This article was sourced from Creative Commons Attribution-ShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for and content contributors is made possible from the U.S. Congress, E-Government Act of 2002.
Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.
By using this site, you agree to the Terms of Use and Privacy Policy. World Heritage Encyclopedia™ is a registered trademark of the World Public Library Association, a non-profit organization.

Copyright © World Library Foundation. All rights reserved. eBooks from Project Gutenberg are sponsored by the World Library Foundation,
a 501c(4) Member's Support Non-Profit Organization, and is NOT affiliated with any governmental agency or department.