Cryptography: Theory and Practice:Hash Functions
 | Cryptography: Theory and Practice by Douglas Stinson CRC Press, CRC Press LLC ISBN: 0849385210 Pub Date: 03/17/95 |
| Previous | Table of Contents | Next |
Chapter 7
Hash Functions
7.1 Signatures and Hash Functions
The reader might have noticed that the signature schemes described in Chapter 6 allow only “small” messages to be signed. For example, when using the DSS, a 160-bit message is signed with a 320-bit signature. In general, we will want to sign much longer messages. A legal document, for example, might be many megabytes in size.
A naive attempt to solve this problem would be to break a long message into 160-bit chunks, and then to sign each chunk independently. This is analogous to encrypting a long string of plaintext by encrypting each plaintext character independently using the same key (e.g., ECB mode in the DES).
But there are several problems with this approach in creating digital signatures. First of all, for a long message, we will end up with an enormous signature (twice as long as the original message in the case of the DSS). Another disadvantage is that most “secure” signature schemes are slow since they typically use complicated arithmetic operations such as modular exponentiation. But an even more serious problem with this approach is that the various chunks of a signed message could be rearranged, or some of them removed, and the resulting message would still be verified. We need to protect the integrity of the entire message, and this cannot be accomplished by independently signing little pieces of it.
The solution to all of these problems is to use a very fast public cryptographic hash function, which will take a message of arbitrary length and produce a message digest of a specified size (160 bits if the DSS is to be used). The message digest will then be signed. For the DSS, the use of a hash function h is depicted diagramatically in Figure 7.1
When Bob wants to sign a message x, he first constructs the message digest z = h(x), and then computes the signature y = sigK(z). He transmits the ordered pair (x, y) over the channel. Now the verification can be performed (by anyone) by first reconstructing the message digest z = h(x) using the public hash function h, and then checking that verK(z, y) = true.
Figure 7.1 Signing a message digest
7.2 Collision-free Hash Functions
We have to be careful that the use of a hash function h does not weaken the security of the signature scheme, for it is the message digest that is signed, not the message. It will be necessary for h to satisfy certain properties in order to prevent various forgeries.
The most obvious type of attack is for an opponent, Oscar, to start with a valid signed message (x, y), where y = sigK(h(x)). (The pair (x, y) could be any message previously signed by Bob.) Then he computes z = h(x) and attempts to find x′ ≠ x such that h(x′) = h(x). If Oscar can do this, (x′, y) would be a valid signed message, i.e., a forgery. In order to prevent this type of attack, we require that h satisfy the following collision-free property:
DEFINITION 7.1 Let x be a message. A hash function h is weakly collision-free for x if it is computationally infeasible to find a message x′ ≠ x such that h(x′) = h(x).
Another possible attack is the following: Oscar first finds two messages x ≠ x′ such that h(x) = h(x′). Oscar then gives x to Bob and persuades him to sign the message digest h(x), obtaining y. Then (x′, y) is a valid forgery.
This motivates a different collision-free property:
DEFINITION 7.2 A hash function h is strongly collision-free if it is computationally infeasible to find messages x and x′ such that x′ ≠ x and h(x′) = h(x).
Observe that a hash function h is strongly collision-free if and only if it in computationally infeasible to find a message x such that h is not weakly collision-free for x.
Here is a third variety of attack. As we mentioned in Section 6.2, it is often possible with certain signature schemes to forge signatures on random message digests z. Suppose Oscar computes a signature on such a random z, and then he finds a message x such that z = h(x). If he can do this, then (x, y) is a valid forgery. To prevent this attack, we desire that h satisfy the same one-way property that was mentioned previously in the context of public-key cryptosystems and the Lamport Signature Scheme:
DEFINITION 7.3 A hash function h is one-way if, given a message digest z, it is computationally infeasible to find a message x such that h(x) = z.
We are now going to prove that the strongly collision-free property implies the one-way property. This is done by proving the contrapositive statement. More specifically, we will prove that an arbitrary inversion algorithm for a hash function can be used as an oracle in a Las Vegas probabilistic algorithm that finds collisions.
This reduction can be accomplished with a fairly weak assumption on the relative sizes of the domain and range of the hash function. We will assume for the time being that the hash function h : X → Z, where X and Z are finite sets and |X| ≥ 2|Z|. This is a reasonable assumption: If we think of an element of X as being encoded as a bitstring of length log2 |X| and an element of Z as being encoded as a bitstring of length log2 |Z|, then the message digest z = h(x) is at least one bit shorter than the message x. (Eventually, we will be interested in the situation where the message domain X is infinite, since we want to be able to deal with messages of arbitrary length. Our argument also applies in this situation.)
We are assuming that we have an inversion algorithm for h. That is, we have an algorithm A which accepts as input a message digest z ∈ Z, and finds an element A(z) ∈ X such that h(A(z)) = z.
We prove the following theorem.
| Previous | Table of Contents | Next |
Copyright © CRC Press LLC
EAN: 2147483647
Pages: 133