One-way compression function

Uses your system voice; voice and rate in settings.

Snapshot

≈ 10 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

In cryptography, a one-way compression function is a function that transforms two fixed-length inputs into a fixed-length output. The transformation is "one-way", meaning that it is difficult given a particular output to compute inputs which compress to that output. One-way compression functions are not related to conventional data compression algorithms, which instead can be inverted exactly (lossless compression) or approximately (lossy compression) to the original data. One-way compression functions are for instance used in the Merkle–Damgård construction inside cryptographic hash functions. One-way compression functions are often built from block ciphers. Some methods to turn any normal block cipher into a one-way compression function are Davies–Meyer, Matyas–Meyer–Oseas, Miyaguchi–Preneel (single-block-length compression functions) and MDC-2/Meyer–Schilling, MDC-4, Hirose (double-block-length compression functions). These methods are described in detail further down. (MDC-2 is also the name of a hash function patented by IBM.) Another method is 2BOW (or NBOW in general), which is a "high-rate multi-block-length hash function based on block ciphers" and typically achieves (asymptotic) rates between 1 and 2 independent of the hash size (only with small constant overhead). This method has not yet seen any serious security analysis, so should be handled with care.

In cryptography, a one-way compression function is a function that transforms two fixed-length inputs into a fixed-length output. The transformation is "one-way", meaning that it is difficult given a particular output to compute inputs which compress to that output. One-way compression functions are not related to conventional data compression algorithms, which instead can be inverted exactly (lossless compression) or approximately (lossy compression) to the original data. One-way compression functions are for instance used in the Merkle–Damgård construction inside cryptographic hash functions. One-way compression functions are often built from block ciphers. Some methods to turn any normal block cipher into a one-way compression function are Davies–Meyer, Matyas–Meyer–Oseas, Miyaguchi–Preneel (single-block-length compression functions) and MDC-2/Meyer–Schilling, MDC-4, Hirose (double-block-length compression functions). These methods are described in detail further down. (MDC-2 is also the name of a hash function patented by IBM.) Another method is 2BOW (or NBOW in general), which is a "high-rate multi-block-length hash function based on block ciphers" and typically achieves (asymptotic) rates between 1 and 2 independent of the hash size (only with small constant overhead). This method has not yet seen any serious security analysis, so should be handled with care. Preimage-resistance: If an attacker only knows the output it should be infeasible to calculate an input. In other words, given an output h , it should be unfeasible to calculate an input m such that \operatorname{hash}(m)=h . Second preimage-resistance: Given an input m_1 whose output is h , it should be infeasible to find another input m_2 that has the same output h , i.e. \operatorname{hash}(m_1) = \operatorname{hash}(m_2) . Collision-resistance: It should be hard to find any two different inputs that compress to the same output i.e. an attacker should not be able to find a pair of messages m_1 \ne m_2 such that \operatorname{hash}(m_1) = \operatorname{hash}(m_2) . Due to the birthday paradox (see also birthday attack) there is a 50% chance a collision can be found in time of about 2^{n/2} where n is the number of bits in the hash function's output. An attack on the hash function thus should not be able to find a collision with less than about 2^{n/2} work. Ideally one would like the "infeasibility" in preimage-resistance and second preimage-resistance to mean a work of about 2^n where n is the number of bits in the hash function's output. However, particularly for second preimage-resistance this is a difficult problem. A second preimage attack (given a message m_1 an attacker finds another message m_2 to satisfy \operatorname{hash}(m_1) = \operatorname{hash}(m_2) can be done according to Kelsey and Schneier for a 2^k -message-block message in time k \times 2^{n/2+1} + 2^{n-k+1} . The complexity of this attack reaches a minimum of 2^{3n/4+2} for long messages when k = 2^{n/4} and approaches 2^n when messages are short. R_h=\frac{\left|m_i\right|}{s\cdot n} The hash function can only be considered secure if at least the following conditions are met: The block cipher has no special properties that distinguish it from ideal ciphers, such as weak keys or keys that lead to identical or related encryptions (fixed points or key-collisions). The resulting hash size is big enough. According to the birthday attack a security level of 2 80 (generally assumed to be infeasible to compute today) is desirable thus the hash size should be at least 160 bits. The last block is properly length padded prior to the hashing. (See Merkle–Damgård construction.) Length padding is normally implemented and handled internally in specialised hash functions like SHA-1 etc. The constructions presented below: Davies–Meyer, Matyas–Meyer–Oseas, Miyaguchi–Preneel and Hirose have been shown to be secure under the black-box analysis. The goal is to show that any attack that can be found is at most as efficient as the birthday attack under certain assumptions. The black-box model assumes that a block cipher is used that is randomly chosen from a set containing all appropriate block ciphers. In this model an attacker may freely encrypt and decrypt any blocks, but does not have access to an implementation of the block cipher. The encryption and decryption function are represented by oracles that receive a pair of either a plaintext and a key or a ciphertext and a key. The oracles then respond with a randomly chosen plaintext or ciphertext, if the pair was asked for the first time. They both share a table for these triplets, a pair from the query and corresponding response, and return the record, if a query was received for the second time. For the proof there is a collision finding algorithm that makes randomly chosen queries to the oracles. The algorithm returns 1, if two responses result in a collision involving the hash function that is built from a compression function applying this block cipher (0 else). The probability that the algorithm returns 1 is dependent on the number of queries which determine the security level. H_i = E_{m_i}{(H_{i-1})} \oplus {H_{i-1}} The scheme has the rate (k is the keysize): R_{DM}=\frac{k}{1\cdot n} = \frac{k}{n} If the block cipher uses for instance 256-bit keys then each message block ( m_i ) is a 256-bit chunk of the message. If the same block cipher uses a block size of 128 bits then the input and output hash values in each round is 128 bits. Variations of this method replace XOR with any other group operation, such as addition on 32-bit unsigned integers. A notable property of the Davies–Meyer construction is that even if the underlying block cipher is totally secure, it is possible to compute fixed points for the construction: for any m , one can find a value of h such that E_m(h) \oplus h = h : one just has to set h = E_m^{-1}(0) . This is a property that random functions certainly do not have. So far, no practical attack has been based on this property, but one should be aware of this "feature". The fixed-points can be used in a second preimage attack (given a message m_1 , attacker finds another message m_2 to satisfy \operatorname{hash}(m_1) = \operatorname{hash}(m_2) ) of Kelsey and Schneier for a 2^k -message-block message in time 3 \times 2^{n/2+1} + 2^{n-k+1} . If the construction does not allow easy creation of fixed points (like Matyas–Meyer–Oseas or Miyaguchi–Preneel) then this attack can be done in k \times 2^{n/2+1} + 2^{n-k+1} time. In both cases the complexity is above 2^{n/2} but below 2^n when messages are long and that when messages get shorter the complexity of the attack approaches 2^n . The security of the Davies–Meyer construction in the Ideal Cipher Model was first proven by R. Winternitz. H_i = E_{g(H_{i-1})}(m_i)\oplus m_i The scheme has the rate: R_{MMO} = \frac{n}{1\cdot n} = 1 A second preimage attack (given a message m_1 an attacker finds another message m_2 to satisfy \operatorname{hash}(m_1) = \operatorname{hash}(m_2) ) can be done according to Kelsey and Schneier for a 2^k -message-block message in time k \times 2^{n/2+1} + 2^{n-k+1} . The complexity is above 2^{n/2} but below 2^n when messages are long, and that when messages get shorter the complexity of the attack approaches 2^n . H_i = E_{g(H_{i-1})}(m_i)\oplus H_{i-1}\oplus m_i The scheme has the rate: R_{MP}=\frac{n}{1\cdot n}=1 The roles of m_i and H_{i-1} may be switched, so that H_{i-1} is encrypted under the key m_i , thus making this method an extension of Davies–Meyer instead. A second preimage attack (given a message m_1 an attacker finds another message m_2 to satisfy \operatorname{hash}(m_1) = \operatorname{hash}(m_2) ) can be done according to Kelsey and Schneier for a 2^k -message-block message in time k \times 2^{n/2+1} + 2^{n-k+1} . The complexity is above 2^{n/2} but below 2^n when messages are long, and that when messages get shorter the complexity of the attack approaches 2^n . G_i = E_{K_i}(G_{i-1}) \oplus G_{i-1} H_i = E_{K_i}(p(G_{i-1})) \oplus p(G_{i-1}) p(G_{i-1}) is an arbitrary fixed-point-free permutation on an n -bit value, typically defined as p(x) = x \oplus c for an arbitrary non-zero constant c (all ones may be a convenient choice). Each encryption resembles the standard Davies–Meyer construction. The advantage of this scheme over other proposed double-block-length schemes is that both encryptions use the same key, and thus key scheduling effort may be shared. The final output is H_t || G_t . The scheme has the rate R_{Hirose} = \frac{k-n}{2n} relative to encrypting the message with the cipher. Hirose also provides a proof in the Ideal Cipher Model.

Sponge construction

The sponge construction can be used to build one-way compression functions.

Text derived from https://en.wikipedia.org/w/index.php?oldid=1327823459 under CC BY-SA 4.0; modifications have been made.

Sources cited in this revision

6 named source(s) extracted from the cited revision. A source with no author is shown by its publication; nothing is invented.