Computer Security: Art and Science

10.10 Exercises

1:
The problem of selecting a cryptographic key is equivalent to generating a random number from 0 to |K| � 1, inclusive. However, certain issues may complicate this process. This exercise asks you to examine them.

The DES has 16 keys with undesirable properties (the weak and semiweak keys). These keys cannot be used safely. Describe how to map the selection of a key for the DES into the problem of generating random numbers.
RSA requires that prime numbers be generated. The usual technique is to generate a large random number and test it for primality. Assuming that you have an algorithm P that tests for primality in a "reasonable" time,^[5] and assuming that you have a random number generator, how would you generate such a prime number efficiently?
^[5] In practice, P is tested for primality by applying a series of probabilistic tests on the chosen number until the probability of that number being composite is sufficiently low. See, for example, Rabin [825] and Adleman, Pomerance, and Rumley [10].
2:
Reconsider the case of Alice and her stockbroker, Bob. Suppose they decide not to use a session key. Instead, Alice pads the message (BUY or SELL) with random data. Explain under what conditions this approach would be effective. Discuss how the length of the block affects your answer.
3:
Modify Kohnfelder's scheme (see page 254) to allow a principal to issue its own certificate. Identify one or more problems other principals might have in relying on such a certificate. In particular, under what conditions would this solve the problem of an imposter spoofing the sender?
4:
Show that, under the Yaksha security scheme, Alice can obtain the session key by computing
5:
An X.509 certificate revocation list contains a field specifying when the next such list is expected to be issued. Why is that field present?
6:
Consider the following authentication protocol, which uses a classical cryptosystem. Alice generates a random message r, enciphers it with the key k she shares with Bob, and sends the enciphered message {r}k to Bob. Bob deciphers it, adds 1 to r, and sends {r + 1}k back to Alice. Alice deciphers the message and compares it with r. If the difference is 1, she knows that her correspondent shares the same key k and is therefore Bob. If not, she assumes that her correspondent does not share the key k and so is not Bob. Does this protocol authenticate Bob to Alice? Why or why not?
7:
Needham and Schroeder suggest the following variant of their protocol:

Alice Bob : Alice
Bob Alice : { Alice, rand₃ } k_Bob
Alice Cathy : { Alice, Bob, rand₁, { Alice, rand₃ } k_Bob }
Cathy Alice : { Alice, Bob, rand₁, k_session, {Alice, rand₃, k_session} k_Bob } k_Alice
Alice Bob : { Alice, rand₃, k_session } k_Bob
Bob Alice : { rand₂ } k_session
Alice Bob : { rand₂ � 1 }k_session

Show that this protocol solves the problem of replay as a result of stolen session keys.
8:
Consider an RSA digital signature scheme (see Section 10.6.2.1). Alice tricks Bob into signing messages m₁ and m₂ such that m = m₁m2 mod n_Bob. Prove that Alice can forge Bob's signature on m.
9:
Return to the example on page 269. Bob and Alice agree to sign the contract G (06). This time, Alice signs the message first and then enciphers the result. Show that the attack Bob used when Alice enciphered the message and then signed it will now fail.

Top

1:	The problem of selecting a cryptographic key is equivalent to generating a random number from 0 to \|K\| � 1, inclusive. However, certain issues may complicate this process. This exercise asks you to examine them. The DES has 16 keys with undesirable properties (the weak and semiweak keys). These keys cannot be used safely. Describe how to map the selection of a key for the DES into the problem of generating random numbers. RSA requires that prime numbers be generated. The usual technique is to generate a large random number and test it for primality. Assuming that you have an algorithm P that tests for primality in a "reasonable" time,^[5] and assuming that you have a random number generator, how would you generate such a prime number efficiently? ^[5] In practice, P is tested for primality by applying a series of probabilistic tests on the chosen number until the probability of that number being composite is sufficiently low. See, for example, Rabin [825] and Adleman, Pomerance, and Rumley [10].
2:	Reconsider the case of Alice and her stockbroker, Bob. Suppose they decide not to use a session key. Instead, Alice pads the message (BUY or SELL) with random data. Explain under what conditions this approach would be effective. Discuss how the length of the block affects your answer.
3:	Modify Kohnfelder's scheme (see page 254) to allow a principal to issue its own certificate. Identify one or more problems other principals might have in relying on such a certificate. In particular, under what conditions would this solve the problem of an imposter spoofing the sender?
4:	Show that, under the Yaksha security scheme, Alice can obtain the session key by computing
5:	An X.509 certificate revocation list contains a field specifying when the next such list is expected to be issued. Why is that field present?
6:	Consider the following authentication protocol, which uses a classical cryptosystem. Alice generates a random message r, enciphers it with the key k she shares with Bob, and sends the enciphered message {r}k to Bob. Bob deciphers it, adds 1 to r, and sends {r + 1}k back to Alice. Alice deciphers the message and compares it with r. If the difference is 1, she knows that her correspondent shares the same key k and is therefore Bob. If not, she assumes that her correspondent does not share the key k and so is not Bob. Does this protocol authenticate Bob to Alice? Why or why not?
7:	Needham and Schroeder suggest the following variant of their protocol: Alice Bob : Alice Bob Alice : { Alice, rand₃ } k_Bob Alice Cathy : { Alice, Bob, rand₁, { Alice, rand₃ } k_Bob } Cathy Alice : { Alice, Bob, rand₁, k_session, {Alice, rand₃, k_session} k_Bob } k_Alice Alice Bob : { Alice, rand₃, k_session } k_Bob Bob Alice : { rand₂ } k_session Alice Bob : { rand₂ � 1 }k_session Show that this protocol solves the problem of replay as a result of stolen session keys.
8:	Consider an RSA digital signature scheme (see Section 10.6.2.1). Alice tricks Bob into signing messages m₁ and m₂ such that m = m₁m2 mod n_Bob. Prove that Alice can forge Bob's signature on m.
9:	Return to the example on page 269. Bob and Alice agree to sign the contract G (06). This time, Alice signs the message first and then enciphers the result. Show that the attack Bob used when Alice enciphered the message and then signed it will now fail.