D.2 Cryptographic hash functions

Hash functions were first introduced in connection with database management systems for easy searching of records in big tables. To achieve this goal, the information in a record is compressed to a quantity of fixed length, which is called a hash code, that serves as an identification label of a record. As will be outlined below, using hash functions for cryptographic purposes implies supplementary design requirements, which adds the attribute cryptographic to the term "hash function". Because only cryptographic hash functions are considered in this book, they will be simply referred to as hash functions .

A hash function maps an input of arbitrary length to a hash code of fixed length, n bits. Two categories of hash functions can be distinguished:

Unkeyed hash functions, which are generally referred to as message digest codes (MDC);
Keyed hash functions, which are generally referred to as MACs.

Hash functions are security mechanisms used for implementing the data authentication service (see Appendix C). The basic idea of using a hash function for implementing the data authentication service is to transfer the authenticity of an arbitrary long message to the authenticity of its hash code. The MDC is an essential security mechanism for implementing other security services (e.g., entity authentication and non- repudiation ). Thus, the MDC is a basic building block for an efficient implementation of digital signature schemes. A unified and comprehensive treatment of the analysis and design of cryptographic hash functions can be found in [1].

Even though an MDC is an unkeyed hash function, generally the payment system literature uses the term "hash function" to refer to an MDC. Even though we do not agree with this terminology abuse, we conform to it so as not to confuse the reader. Therefore, in the remainder of this appendix the term "hash function" is used to designate only an MDC. Note that rigorously speaking the MAC is also a hash function, which is parameterized by a secret key, but for the goals of this book the terms "hash function" and "MAC" are disjunctively used.

D.2.1 Hash function

The following requirements are imposed on a hash function.

First, the hash function must be a one-way function, in the sense that given the input x is easy to compute H ( x ), while for all the images h in the range of H it is computationally unfeasible to derive an input x such that h = H ( x ), a feature that is sometimes called first preimage resistance . The description of H is publicly known.
Second, even though there are arguments x ‰ x ² for which H ( x ) = H ( x ² ), giving a pair ( x , H ( x )), it is computationally unfeasible to find x ² such that H ( x ) = H ( x ² ), a feature that is called second pre-image resistance . This feature is enough for providing an adequate level of security against external attackers , which can only observe the pairs ( x , H ( x )) but have no way to influence the choice of x . However, in order to provide protection against inside attackers, consisting of one of the communicating parties, a supplementary condition must be fulfilled. It must be computationally unfeasible to find any arguments x ‰ x ² for which H ( x ) = H ( x ² ), a case for which the hash function is said to be collision resistant.

Over the years many hash function candidates were proposed.

In the first generation of hash functions, the fixed bit-length of the hash code was 128 bits. Among the most popular cryptographic primitives used as hash functions in this category are the algorithms MD4 [4] and MD5 [5], which were proposed by the RSA Laboratories, and the RIPEMD algorithm, proposed by the research project RACE-R1040 financed by the European Commission [6]. Some successful attacks, however, have revealed that these cryptographic primitives were not collision resistant. These attacks showed that providing the collision resistance feature for a hash function required that the length of the hash code be at least 160 bits.
A second generation of hash functions, with the length of the hash code of 160 bits, contains the SHA-1 algorithm, the Secure Hash Algorithm that is proposed by the National Institute of Standards and Technologies (NIST) in the United States [7]. The European equivalent is the RIPREMD-160 [8], proposed by Dobbertin, Bosselaers, and Preneel as a collision-resistant hash function improving on the original RIPEMD proposal.

Since no secret key is involved in the computation of a hash function, there is no overhead involved by the key management. In this case, however, a supplementary authentication channel is needed for every hash code. To better understand this, assume that a hash code is intended to protect the authenticity of a public encryption key used by a bank to receive encrypted messages from clients . To this end, the bank sends its client a letter containing a tamper evident part, which, when it is opened, reveals the verification hash code of the public encryption key. The public encryption key itself is sent in clear over the Internet, with no protection. After receiving it, the customer applies the indicated hash function to the message consisting of this key, and if it matches the verification hash code received by mail, the public encryption key sent over the Internet can be accepted as authentic . In this case the classic mail service provides the authentication channel for protecting the authenticity of the verification hash code.

D.2.2 MAC

The MAC is a suitable mechanism implementing secure messaging for integrity and authentication on the communication channel established between the sender and the receiver. In the case of a MAC, the authenticity of data relies on the secrecy and authenticity of a secret key K , which guarantees the origin of data. Assume that the sender and receiver have exchanged the secret key K in the framework of a key management scheme. Then, in order to provide the data authentication service for a message M , the sender has to compute the MAC value on M using the secret key K . The sender transmits both the message M and the MAC value to the receiver. After receiving the message M , the receiver computes using the same secret key K the MAC verification value on M and compares it with the received MAC value. If the computed MAC and the received MAC are equal, the receiver has the confirmation that the origin of data is that claimed, and that data was not modified during its transmission. If a unique time-variant sequence is included in the message M , the replay threat can also be countered, as explained in Section D.7. The secure messaging for integrity and authentication implemented with a MAC is schematized in Figure D.3.

Figure D.3: Data authentication using a MAC.

Technically, a MAC is a hash function H that is parameterized by the secret key K . Given an input x of arbitrary length and the secret key K , the MAC value of the input x is computed as MACvalue = H ( x, K ). The length of the MAC value is fixed, n bits, with n ‰ 32 64. The description of H is publicly known. Given the value of the input x and of the secret key K , the computation of H ( x , K ) must be easy. However, giving only x it is computationally unfeasible for an attacker that does not know K to determine H ( x , K ) with a better probability than 1/2 ⁿ , which is, in fact, the probability of guessing the MAC value. Moreover, the history of sequences { x _i , H ( x _i , K )} obtained from previous computations of the MAC on input values x _i that can be chosen by the attacker does not help to determine the key K nor the image H ( x ² , K ) for any new input value x ² .

One category of MAC primitives is that derived from the corresponding MDC primitives, appending the secret key K to the data to be authenticated. They are referred to as keyed MAC. The secret key K can be appended in front of the data to be authenticated as a prefix [i.e., MAC ( K )[ x ] = MDC ( K x )]. The secret key can be also appended at the end of the data to be authenticated as a suffix [i.e., MAC ( K )[ x ] = MDC ( x K )]. There is also the possibility that the secret key envelopes the data to be authenticated, being appended both in front and at the end of the data to be authenticated [i.e., MAC ( K )[ x ] = MDC ( K x K )]. Even though a MAC constructed from an MDC offers a high throughput, there is the suspicion of a certification weakness concerning this type of construction [9]. A second category of MAC primitives is based on block ciphers, and their construction will be discussed in Appendix E, Section E.4.