Cryptography Reference
In-Depth Information
1
64
Pad
=
···
Length
1
0
0
Figure 3.3. Padding in the Merkle-Damgard scheme.
4. For i
=
1
,...,
n ,welet H i =
C ( H i 1 ,
B i ).
5. We define H n =
h ( M ).
We notice that this construction restricts to messages of size less than 2 64 bits. In
practice this is not a problem since this represents 2 097 152 Tera Bytes, which cannot
be managed with current technology.
Theorem 3.1 (Merkle-Damgard 1989 [56, 130]). With the above construction, if the
compression function C is collision-resistant, then the hash function h is collision-
resistant as well.
M
h ( M ), let
Proof. If we can construct a collision for the hash function h ( M )
=
=
M =
B 1 ,...,
B n . We also define H i and H j following the above
B 1 ,...,
B n and
B n ). Either this
is a collision on the compression function, or the inputs are equal. If this is the case, then
we have B n =
H n . Thus we have C ( H n 1 ,
C ( H n 1 ,
scheme. We have H n =
B n )
=
B n , but since the last block includes the length of the messages, M and M
have the same length, thus n
H n 1 , thus C ( H n 2 ,
=
n . We also have H n 1 =
B n 1 )
=
C ( H n 2 ,
B n 1 ). We continue the proof the same way. Since the messages are different,
we must have B i =
B i
at some point. Thus we must get a collision on the compression
function.
3.1.4 Example of MD5
MD5 is a famous cryptographic hash function example. It is widely used in Internet
applications. It was designed by Ronald Rivest at MIT in 1991 and published as the
RFC 1321 Internet standard in 1992 (Ref. [157]). It hashes arbitrary length bitstrings
onto 128 bits. MD5 stands for “Message Digest,” and is based on a previous algorithm,
MD4. It uses the Merkle-Damgard construction from a 128
×
512
128 compression
function. 1
The compression function is made from an “encryption function” by the Davies-
Meyer scheme: given an “encryption function” C 0 which maps a 128-bit value H
=
( A
,
B
,
C
,
D ) and a 512-bit key block B into a 128-bit value, we define
C ( H
,
B )
=
C 0 ( H
,
B )
+
( A
,
B
,
C
,
D )
where the addition here is the word-wise addition modulo 2 32 .
1
Note that some collisions on MD5 were exhibited at the CRYPTO'04 conference by Xiaoyun Wang and
Xuejia Lai. This means that MD5 should no longer be considered as a secure hash function and should be
replaced in most existing standards.
Search WWH ::




Custom Search