利用者:Roget/試訳/Merkle–Damgård構成

en:23:18, 6 September 2009

暗号学において, Merkle-Damgård構成またはMerkle-Damgårdハッシュ関数とは, 暗号論的ハッシュ関数の構成方法である. 現在広く用いられているハッシュ関数は, この一般的な構成に従うことが多い.

In cryptography, the Merkle-Damgård construction or Merkle-Damgård hash function is a method to build cryptographic hash functions. All popular hash functions follow this generic construction.

暗号論的ハッシュ関数は, 任意長のメッセージを固定長の出力に変換する. これは入力のメッセージを同じサイズのブロックに分け, 一方向圧縮関数 (固定長の入力をより短い出力に変換する) を用いて操作を行う. この圧縮関数として, ハッシュ用に設計された関数かブロック暗号が用いられる. SHA-1やSHA-0のように多くの場合では, 圧縮関数はハッシュ関数用に設計されたブロック暗号を用いる. Merkle-Damgård構成では, 入力をブロックに分け, 圧縮関数

各ラウンドで, 入力のブロックと前ラウンドの出力を結合して圧縮する.

A cryptographic hash function must be able to process an arbitrary-length message into a fixed-length output. This can be achieved by breaking the input up into a series of equal-sized blocks, and operating on them in sequence using a one-way compression function that processes a fixed-length input into a shorter, fixed-length output. The compression function can either be specially designed for hashing or be built from a block cipher. In many cases, including the SHA-1 and SHA-0 functions, the compression function is based on a block cipher that is specially designed for use in a hash function. The Merkle-Damgård hash function breaks the input into blocks, and processes them one at a time with the compression function, each time combining a block of the input with the output of the previous round.

Merkle-Damgård hash construction

Merkle-Damgård構成はRalph Merkleの博士論文に詳しい. MerkleとDamgårdが独立にこの構成が健全であることを示した. すなわち, 圧縮関数が衝突耐性を持つならば, 出来上がったハッシュ関数も衝突耐性を持つ. この構成が安全であることを証明するために, MerkleとDamgårdはメッセージ長を符号化してメッセージに加えるパディング関数を提案している. これを長さパディングまたはMerkle-Damgård強化法と呼ぶ (どうしよう?)

The Merkle-Damgård construction was described in Ralph Merkle's Ph.D. thesis. Ralph Merkle and Ivan Damgård independently proved that the structure is sound: if the compression function is collision-resistant, then the hash function will be also. In order to prove that the construction is secure, Merkle and Damgård proposed that messages be padded with a padding that encodes the length of the original message. This is called length padding or Merkle-Damgård strengthening.

図では,

In the diagram, the one-way compression function is denoted by f, and transforms two fixed length inputs to an output of the same size as one of the inputs. The algorithm starts with an initial value, the initialization vector (IV). The IV is a fixed value (algorithm or implementation specific). For each message block, the compression (or compacting) function f takes the result so far, combines it with the message block, and produces an intermediate result. The last block is padded with zeros as needed and bits representing the length of the entire message are appended. (See below for a detailed length padding example.)

To harden the hash further the last result is then sometimes fed through a finalisation function. The finalisation function can have several purposes such as compressing a bigger internal state (the last result) into a smaller output hash size or to guarantee a better mixing and avalanche effect on the bits in the hash sum. The finalisation function is often built by using the compression function. (Note that in some documents instead the act of length padding is called "finalisation".)

安全性の特徴

(Security characteristics)

この構成がよくつかわれるのは次の理由による. 圧縮関数fが衝突困難性を持つならば, この構成で得られたハッシュ関数も衝突困難性を持つ (MerkleとDamgårdによって示された). しかし, この構成ではあまり好ましくない以下の性質をもつ.

• 伸長可能性: 攻撃者が1つ衝突を発見した場合, 攻撃者は別の衝突を簡単に発見できる.
• 長いメッセージに対する第2原像攻撃は, しらみ潰しよりも効率よく計算できる.
• 多重衝突: 衝突を発見する計算量より少し多い計算量で多重衝突を発見できる.
• 牧畜攻撃?? (出力hをコミットした後, ハッシュ値がhになるような, 任意の文字列で始まるメッセージを構成する攻撃?)が, 衝突を発見する計算量よりは多いが, ランダムオラクルに対して行う場合の計算量よりも著しく少ない.
• 拡張攻撃??: 未知の入力Xのハッシュ値H(X)を与えられたとき, ハッシュ値H(pad(X) || Y)を計算するのは容易い (ここでpadはハッシュ関数の構成で使われるパディング関数である). すなわち, Xを知らなかったとしても, Xに関係する入力のハッシュ値を計算することが可能である .

ランダムオラクルはこの攻撃を許さない. またこの攻撃により, ランダムオラクルモデルで安全性が証明された自然な方式であっても単純な攻撃を受けることがある .

The popularity of this construction is due to the fact, proven by Merkle and Damgård, that if the one-way compression function f is collision resistant, then so is the hash function constructed using it. Unfortunately, this construction also has several undesirable properties:

• Length extension — once an attacker has one collision, he can find more very cheaply.
• Second preimage attacks against long messages are always much more efficient than brute force.
• Multicollisions (many messages with the same hash) can be found with only a little more work than collisions.
• "Herding attacks" (first committing to an output h, then mapping messages with arbitrary starting values to h) are possible for more work than finding a collision, but much less than would be expected to do this for a random oracle.
• "Extension attacks": Given the hash H(X) of an unknown input X, it is easy to find the value of H(pad(X) || Y), where pad is the padding function of the hash. That is, it is possible to find hashes of inputs related to X even though X remains unknown. A random oracle would not have this property, and this may lead to simple attacks even for natural schemes proven secure in the random oracle model.

Length padding example

To be able to feed the message to the compression function, the last block needs to be padded with constant data (generally with zeroes) to a full block.

For example, let's say the message to be hashed is "HashInput" and the block size of the compression function is 8 bytes (64 bits). (Note that as of 2008 a hash function needs to have at least 160 bits block size to be secure, but we use 64 bits in this example for simplicity.) So we get two blocks looking like this:

HashInpu t0000000

But this is not enough since it would mean that distinct messages starting by the same data and terminated by zero or more bytes from the padding constant data would get fed into the reduction function using exactly the same blocks, producing the same final hash sum.

In our example, for instance, the modified message "HashInput00" would generate the same blocks as the original message "HashInput".

To prevent this, the first bit of the padded constant data must be changed. As the constant padding is generally made of zeroes, the first padding bit will be mandatorily changed into "1".

In our example, we get something like this:

HashInpu t1000000

To harden the hash even further also, the length of the message can be added in an extra block.

So in our example, we would get three blocks like this:

HashInpu t1000000 00000009

To avoid ambiguity, the message length value must be itself resistant to length extensions. Most common implementations use a fixed bit-size (generally 64 or 128 bits in modern algorithms) and a fixed position at end of the last block for encoding the message length value.

Now that is a bit wasteful since it means hashing one full extra block for the length value. So there is a slight speed optimisation that most hash algorithms use. If there is space enough among the zeros padded to the last block the length value can instead be padded there.

Let's say here that, in our example the length value is encoded on 5 bytes (40 bits), thus it gets padded in the final block as "00009", not just "9" or with too many unnecessary zeroes. Like this:

HashInpu t1000009

See also

• Cryptographic hash function
• One-way compression function
• Ralph Merkle, Ivan Damgård, inventors of the Merkle-Damgård structure.

References

• Introduction to Modern Cryptography, by Jonathan Katz and Yehuda Lindell.

Chapman and Hall/CRC Press, August 2007, page 134 (construction 4.13).

• Handbook of Applied Cryptography by Menezes, van Oorschot and Vanstone (2001), chapter 9.