Cryptography Reference
In-Depth Information
H i = f ( H i− 1 ,x i )for i =1 ,...,n
h ( x )= g ( H n )
As mentioned earlier, the message to be hashed must be padded to a multiple
of b bits. One possibility is to pad x with zeros. Padding with zeros, however, may
also introduce ambiguity about x . For example, the message 101110 padded to 8 bits
would be 10111000 and it is then unclear how many trailing zeros were present in
the original message. Several methods are available to resolve this problem. Merkle
proposed to append the bit length of x at the end of x . To make the additional length
field easy to find, it is right-justified in the final block. Following this proposal, the
padding method of choice in currently deployed hash functions is to append a one,
a variable number of zeros, and the binary encoding of the length of the original
message to the end of the message.
Merkle and Damgard showed that in their construction, finding a collision for
h (i.e., finding two input words x and x with x
= x and h ( x )= h ( x )) is at least
as hard as finding a collision for the underlying compression function f .Thisalso
means that if f is a collision resistant compression function, and h is an iterated
hash function making use of f ,then h is a cryptographic hash function that is also
collision resistant. Put in other words, the iterated hash function inherits the collision
resistance property from the underlying compression function.
In the literature, there are many proposals for collision resistant compression
functions that can be turned into collision resistant cryptographic hash functions
according to the Merkle-Damgard construction. Some examples can, for example,
be found in [1, 2].
8.3
EXEMPLARY CRYPTOGRAPHIC HASH FUNCTIONS
The driving force for cryptographic hash functions was public key cryptography
in general, and digital signature systems in particular. Consequently, the company
RSA Security, Inc., played a crucial role in the development and deployment of
many practically relevant cryptographic hash functions. The first cryptographic
hash function developed by RSA Security, Inc., was acronymed MD (standing for
message digest ). It was proprietary and never published. MD2 specified in RFC 1319
[3] was the first published cryptographic hash function in widespread use (it was,
for example, used in the secure messaging products of RSA Security, Inc.). When
Merkle proposed a cryptographic hash function called SNEFRU that was several
Search WWH ::




Custom Search