Section 13.5. Key Terms, Review Questions, and Problems


[Page 393 (continued)]

13.5. Key Terms, Review Questions, and Problems

Key Terms

arbiter

arbitrated digital signature

direct digital signature

digital signature

digital signature algorithm (DSA)

digital signature standard (DSS)

mutual authentication

nonce

one-way authentication

replay attack

suppress-replay attack

timestamp


[Page 394]

Review Questions

13.1

List two disputes that can arise in the context of message authentication.

13.2

What are the properties a digital signature should have?

13.3

What requirements should a digital signature scheme satisfy?

13.4

What is the difference between direct and arbitrated digital signature?

13.5

In what order should the signature function and the confidentiality function be applied to a message, and why?

13.6

What are some threats associated with a direct digital signature scheme?

13.7

Give examples of replay attacks.

13.8

List three general approaches to dealing with replay attacks.

13.9

What is a suppress-replay attack?

Problems

13.1

Modify the digital signature techniques of Table 13.1a and b to enable the receiver to verify the signature.

13.2

Modify the digital signature technique of Table 13.1c to avoid triple encryption of the entire message.

13.3

In discussing Table 13.1c, it was stated that alliances to defraud were impossible. In fact, there is one possibility. Describe it and explain why it would have so little credibility that we can safely ignore it.

13.4

In Section 13.2, we outlined the public-key scheme proposed in [WOO92a] for the distribution of secret keys. The revised version includes IDA in steps 5 and 6. What attack, specifically, is countered by this revision?

13.5

The protocol referred to in Problem 13.1 can be reduced from seven steps to five, having the following sequence:

(1)

A B:

(2)

B KDC:

(3)

KDC B:

(4)

B A:

(5)

A B:


Show the message transmitted at each step. Hint: The final message in this protocol is the same as the final message in the original protocol.

13.6

With reference to the suppress-replay attack described in Section 13.2:

  1. Give an example of an attack when a party's clock is ahead of that of the KDC.

  2. Give an example of an attack when a party's clock is ahead of that of another party.

13.7

There are three typical ways to use nonces as challenges. Suppose Na is a nonce generated by A, A and B share key K, and f() is a function such as increment. The three usages are

Usage 1

Usage 2

Usage 3

(1) A B:

(1) A B: E(

(1) A B: E(

(2) B A: E(

(2) B A:

(2) B A: E(Na))


Describe situations for which each usage is appropriate.

13.8

Dr. Watson patiently waited until Sherlock Holmes finished. "Some interesting problem to solve, Holmes?" he asked when Holmes finally logged out.

"Oh, not exactly. I merely checked my e-mail and then made a couple of network experiments instead of my usual chemical ones. I have only one client now and I have already solved his problem. If I remember correctly, you once mentioned cryptology among your other hobbies, so it may interest you."


[Page 395]

"Well, I am only an amateur cryptologist, Holmes. But of course I am interested in the problem. What is it about?"

"My client is Mr. Hosgrave, director of a small but progressive bank. The bank is fully computerized and of course uses network communications extensively. The bank already uses RSA to protect its data and to digitally sign documents that are communicated. Now the bank wants to introduce some changes in its procedures; in particular, it needs to digitally sign some documents by two signatories so that

  1. The first signatory prepares the document, forms its signature, and passes the document to the second signatory.

  2. The second signatory as a first step must verify that the document was really signed by the first signatory. She then incorporates her signature into the document's signature so that the recipient, as well as any member of the public, may verify that the document was indeed signed by both signatories. In addition only the second signatory has to be able to verify the document's signature after the step (1); that is the recipient (or any member of the public) should be able to verify only the complete document with signatures of both signatories, but not the document in its intermediate form where only one signatory has signed it. Moreover, the bank would like to make use of its existing modules that support RSA-style digital signatures."

"Hm, I understand how RSA can be used to digitally sign documents by one signatory, Holmes. I guess you have solved the problem of Mr. Hosgrave by appropriate generalization of RSA digital signatures."

"Exactly, Watson," nodded Sherlock Holmes. "Originally, the RSA digital signature was formed by encrypting the document by the signatory's private decryption key 'd', and the signature could be verified by anyone through its decryption using publicly known encryption key 'e'. One can verify that the signature S was formed by the person who knows d, which is supposed to be the only signatory. Now the problem of Mr. Hosgrave can be solved in the same way by slight generalization of the process, that is..."

Finish the explanation.

13.9

DSA specifies that if the signature generation process results in a value of s = 0, a new value of k should be generated and the signature should be recalculated. Why?

13.10

What happens if a k value used in creating a DSA signature is compromised?

13.11

The DSS document includes a recommended algorithm for testing a number for primality, as follows:

  1. [Choose w] Let w be a random odd integer. Then (w 1) is even and can be expressed in the form 2a m with m odd. That is, 2a is the largest power of 2 that divides (w 1).

  2. [Generate b] Let b be a random integer in the range 1 < b < w.

  3. [Exponentiate] Set j = 0 and z = bm mod w.

  4. [Done?] If j = 0 and z = 1, or if z = w 1, then w passes the test and may be prime; go to step 8.

  5. [Terminate?] If j > 0 and z = 1, then w is not prime; terminate algorithm for this w.

  6. [Increase j] Set j = j + 1. If j < a, set z = z2 mod w and go to step 4.

  7. [Terminate] w is not prime; terminate algorithm for this w.

  8. [Test again?] If enough random values of b have been tested, then accept w as prime and terminate algorithm; otherwise, go to step 2.

  1. Explain how the algorithm works.

  2. Show that it is equivalent to the Miller-Rabin test described in Chapter 8.

13.12

With DSS, because the value of k is generated for each signature, even if the same message is signed twice on different occasions, the signatures will differ. This is not true of RSA signatures. What is the practical implication of this difference?


[Page 396]
13.13

Consider the problem of creating domain parameters for DSA. Suppose we have already found primes p and q such that q|(p 1). Now we need to find g Zp with q mod p. Consider the following two algorithms:

Algorithm 1

Algorithm 2

repeat

repeat

select g Zp
gq mod

select h Zp
h(p 1)/p mod

until (h = 1 and g 1)

until (g 1)

return g

return g


  1. Prove that the value returned by Algorithm 1 has order q.

  2. Prove that the value returned by Algorithm 1 has order q.

  3. Suppose P = 40193 and q = 157. How many loop iterations do you expect Algorithm 1 to make before it finds a generator?

  4. If p is 1024 bits and q is 160 bits, would you recommend using Algorithm 1 to find g? Explain.

  5. Suppose P = 40193 and q = 157. What is the probability that Algorithm 2 computes a generator in its very first loop iteration? (if it is helpful, you may use the fact that when answering this question).

13.14

It is tempting to try to develop a variation on Diffie-Hellman that could be used as a digital signature. Here is one that is simpler than DSA and that does not require a secret random number in addition to the private key.

Public elements:

  
 

q

prime number

 

a

a < q and a is a primitive root of q

Private key:

  
 

X

X < q

Public key:

  
 

Y

= aX mod q


To sign a message M, compute h = H(M), the hash code of the message. We require that gcd(h, q 1) = 1. If not, append the hash to the message and calculate a new hash. Continue this process until a hash code is produced that is relatively prime to (q 1). Then calculate Z to satisfy Z x h X(mod aZ. To verify the signature, a user verifies that Y = (aZ)h = aX mod q.

  1. Show that this scheme works. That is, show that the verification process produces an equality if the signature is valid.

  2. Show that the scheme is unacceptable by describing a simple technique for forging a user's signature on an arbitrary message.

13.15

An early proposal for a digital signature scheme using symmetric encryption is based on the following: To sign an n-bit message, the sender randomly generates in advance 2n 56-bit cryptographic keys:

k1, K1, k2, K2,..., kn, Kn

which are kept secret. The sender prepares in advance two sets of corresponding nonsecret 64-bit validation parameters, which are made public:

u1, V1, u2, V2,..., un, Vn and v1, V1, v2, V2,..., vn, Vn


[Page 397]

where

vi = E(ki, ui), Vi = E(ki, Ui)

The message M is signed as follows. For the i th bit of the message, either ki or Ki is attached to the message, depending on whether the message bit is 0 or 1. For example, if the first three bits of the message are 011, then the first three keys of the signature are k1, K2, K3.

  1. How does the receiver validate the message?

  2. Is the technique secure?

  3. How many times can the same set of secret keys be safely used for different messages?

  4. What, if any, practical problems does this scheme present?




Cryptography and Network Security Principles and Practices
Cryptography and Network Security (4th Edition)
ISBN: 0131873164
EAN: 2147483647
Year: 2005
Pages: 209

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