词条 | 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:
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 {{nowrap|1=h(x) = h(x′)}}.[1] Collision resistance implies second-preimage resistance,[1] but does not guarantee preimage resistance.[1] Conversely, a second-preimage attack implies a collision attack (trivially, since, in addition to x′, x is already known right from the start). Applied preimage attacksBy 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. However, there is a general result that quantum computers perform a structured preimage attack in {{sqrt|2n}} = 2n/2, which also implies second preimage[2] and thus a collision attack. 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[3][4][5] on MD5 and SHA-1 are collision attacks{{Citation needed|date=March 2017}}. 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. Usual solutionsTo improve resistance to collision attacks, double hashing is a good solution {{Citation needed|reason=the pre-image resistance of any (iteratively applied) secure hash function should be 2^b tests of that (iteratively applied) hash function; double hashing only doubles the time required by the attack -- to actually slow things down, one should use a password hashing algorithm such as Lyra2|date=October 2018}} in case someone discovers a preimage attack on the first hash. The Bitcoin system uses double hashed SHA256[6] that was a common way to slow down hashing searches in the 2000s. See also
References
1. ^1 2 3 4 {{cite paper |last1= Rogaway |first1= P. |last2= Shrimpton |first2= T. |title= Cryptographic Hash-Function Basics: Definitions, Implications, and Separations for Preimage Resistance, Second-Preimage Resistance, and Collision Resistance|journal= Fast Software Encryption (2004) |publisher= Springer-Verlag|url= http://www.cs.ucdavis.edu/~rogaway/papers/relates.pdf|accessdate=17 November 2012}} {{cryptography navbox | hash}}{{DEFAULTSORT:Preimage Attack}}2. ^http://cr.yp.to/hash/quantumsha3-20101112.pdf 3. ^{{cite web |authors=Bruce Morton, Clayton Smith |date={{date|2014-01-30}} |title=Why We Need to Move to SHA-2 |publisher=CA Security Council |url=https://casecurity.org/2014/01/30/why-we-need-to-move-to-sha-2/}} 4. ^{{cite web |date={{date|2009-01-01}} |title=MD5 and Perspectives |url=https://www.cs.cmu.edu/~perspectives/md5.html }} 5. ^{{cite web | url=https://security.googleblog.com/2017/02/announcing-first-sha1-collision.html | title=Google Online Security Blog: Announcing the first SHA1 collision | publisher=Google | accessdate=2017-02-23}} 6. ^https://en.bitcoin.it/wiki/Block_hashing_algorithm 1 : Cryptographic attacks |
随便看 |
|
开放百科全书收录14589846条英语、德语、日语等多语种百科知识,基本涵盖了大多数领域的百科知识,是一部内容自由、开放的电子版国际百科全书。