Cryptography and Network Security (4th Edition)

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

What are the properties a digital signature should have?

What requirements should a digital signature scheme satisfy?

What is the difference between direct and arbitrated digital signature?

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

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

Give examples of replay attacks.

List three general approaches to dealing with replay attacks.

What is a suppress-replay attack?

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

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

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.

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

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

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.

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.

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

Describe situations for which each usage is appropriate.

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."

"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.

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?

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

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 2^a m with m odd. That is, 2^a 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 = b^m 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 = z² 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.

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?

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 Z_p with q mod p. Consider the following two algorithms:

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).

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.

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 a^Z. To verify the signature, a user verifies that Y = (a^Z)^h = a^X 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.

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

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?