Cryptography: Theory and Practice:Hash Functions

cryptography: theory and practice 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.

1.  SHS is designed to run on a big-endian architecture, rather than a little-endian architecture.
2.  SHS produces a 5-register (160-bit) message digest.


Figure 7.9  Round 2 of MD4

3.  SHS processes the message 16 words at a time, as does MD4. However, the 16 words are first “expanded” into 80 words. Then a sequence of 80 operations is performed, one on each word.

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.

7.8 Timestamping

One difficulty with signature schemes is that a signing algorithm may be compromised. For example, suppose that Oscar is able to determine Bob’s secret exponent a in the DSS. Then, of course, Oscar can forge Bob’s 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 Bob’s 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 day’s newspaper proves that Bob did not compute y after the date in question. So Bob’s 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 Bob’s signature on z; and ID(Bob) is Bob’s 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



Cryptography. Theory and Practice
Modern Cryptography: Theory and Practice
ISBN: 0130669431
EAN: 2147483647
Year: 1995
Pages: 133
Authors: Wenbo Mao

flylib.com © 2008-2017.
If you may any questions please contact us: flylib@qtcs.net