Cryptography: Theory and Practice by Douglas Stinson CRC Press, CRC Press LLC ISBN: 0849385210 Pub Date: 03/17/95 |
Previous | Table of Contents | Next |
The Secure Hash Standard is yet more complicated, and slower (about .2 Mbytes/sec on a SPARCstation). We will not give a complete description, but we will indicate a few of the modifications employed in the SHS.
Figure 7.9 Round 2 of MD4
The following expansion function is used. Given the 16 words X[0],..., X[15], we compute 64 more words by the recurrence relation
The result of Equation 7.1 is that each of the words X[16],..., X[79] is formed as the exclusive-or of a predetermined subset of the words X[0],...,X[15].
For example, we have
Figure 7.10 Round 3 of MD4
The proposed revision of the SHS concerns the expansion function. It is proposed that Equation 7.1 be replaced by the following:
As before, the operation means a circular left shift of one position.
One difficulty with signature schemes is that a signing algorithm may be compromised. For example, suppose that Oscar is able to determine Bobs secret exponent a in the DSS. Then, of course, Oscar can forge Bobs signature on any message he likes. But another (perhaps even more serious) problem is that the compromise of a signing algorithm calls in to question the authenticity of all messages signed by Bob, including those he signed before Oscar stole the signing algorithm.
Figure 7.11 Timestamping a signature on a message x
Here is yet another undesirable situation that could arise: Suppose Bob signs a message and later wishes to disavow it. Bob might publish his signing algorithm and then claim that his signature on the message in question is a forgery.
The reason these types of events can occur is that there is no way to determine when a message was signed. This suggests that we consider ways of timestamping a (signed) message. A timestamp should provide proof that a message was signed at a particular time. Then, if Bobs signing algorithm is compromised, it would not invalidate any signatures he made previously. This is similar conceptually to the way credit cards work: if someone loses a credit card and notifies the bank that isssued it, it becomes invalid. But purchases made prior to the loss of the card are not affected.
In this section, we will describe a few methods of timestamping. First, we observe that Bob can produce a convincing timestamp on his own. First, Bob obtains some current publicly available information which could not have been predicted before it happened. For example, such information might consist of all the major league baseball scores from the previous day, or the values of all the stocks listed on the New York Stock Exchange. Denote this information by pub.
Now, suppose Bob wants to timestamp his signature on a message x. We assume that h is a publicly known hash function. Bob will proceed according to the algorithm presented in Figure 7.11. Here is how the scheme works: The presence of the information pub means that Bob could not have produced y before the date in question. And the fact that y is published in the next days newspaper proves that Bob did not compute y after the date in question. So Bobs signature y is bounded within a period of one day. Also observe that Bob does not reveal the message x in this scheme since only z is published. If necessary, Bob can prove that x was the message he signed and timestamped simply by revealing it.
Figure 7.12 Timestamping (zn, yn, IDn)
It is also straightforward to produce timestamps if there is a trusted timestamping service available (i.e., an electronic notary public). Bob can compute z = h(x) and y = sigK(z) and then send (z, y) to the timestamping service, or TSS. The TSS will then append the date D and sign the triple (z, y, D). This works perfectly well provided that the signing algorithm of the TSS remains secure and provided that the TSS cannot be bribed to backdate timestamps. (Note also that this method establishes only that Bob signed a message before a certain time. If Bob also wanted to establish that he signed it after a certain date, he could incorporate some public information pub as in the previous method.)
If it is undesirable to trust the TSS unconditionally, the security can be increased by sequentially linking the messages that are timestamped. In such a scheme, Bob would send an ordered triple (z, y, ID(Bob)) to the TSS. Here z is the message digest of the message x; y is Bobs signature on z; and ID(Bob) is Bobs identifying information. The TSS will be timestamping a sequence of triples of this form. Denote by (zn, yn, IDn) the nth triple to be timestamped by the TSS, and let tn denote the time at which the nth request is made.
The TSS will timestamp the nth triple using the algorithm in Figure 7.12. The quantity Ln is linking information that ties the nth request to the previous one. (L0 will be taken to be some predetermined dummy information to get the process started.)
Now, if challenged, Bob can reveal his message xn, and then yn can be verified. Next, the signature sn of the TSS can be verified. If desired, then IDn-1 or IDn+1 can be requested to produce their timestamps, (Cn-1, sn-1, IDn) and (Cn+1, sn+1, IDn+2), respectively. The signatures of the TSS can be checked in these timestamps. Of course, this process can be continued as far as desired, backwards and/or forwards.
Previous | Table of Contents | Next |
Copyright © CRC Press LLC