4.1 “We are under great pressure, Holmes.” Detective Lestrade looked nervous.“We have
learned that copies of sensitive government documents are stored in computers of one
foreign embassy here in London. Normally these documents exist in electronic form only
on a selected few government computers that satisfy the most stringent security requirements.
However, sometimes they must be sent through the network connecting all government
computers. But all messages in this network are encrypted using a top secret
encryption algorithm certified by our best crypto experts. Even the NSA and the KGB
are unable to break it.And now these documents have appeared in hands of diplomats of
a small, otherwise insignificant, country.And we have no idea how it could happen.”
“But you do have some suspicion who did it, do you?” asked Holmes.
“Yes, we did some routine investigation.There is a man who has legal access to
one of the government computers and has frequent contacts with diplomats from the
embassy. But the computer he has access to is not one of the trusted ones where these
documents are normally stored. He is the suspect, but we have no idea how he could
obtain copies of the documents. Even if he could obtain a copy of an encrypted document,
he couldn’t decrypt it.”
“Hmm, please describe the communication protocol used on the network.”
Holmes opened his eyes, thus proving that he had followed Lestrade’s talk with an
attention that contrasted with his sleepy look.
“Well, the protocol is as follows. Each node N of the network has been assigned
a unique secret key Kn. This key is used to secure communication between the node
and a trusted server.That is, all the keys are stored also on the server. User A, wishing
to send a secret message M to user B, initiates the following protocol:
1. A generates a random number R and sends to the server his name A, destination
B, and E(Ka, R). Get this solution
2. Server responds by sending E(Kb, R) to A.
3. A sends E(R,M) together with E(Kb, R) to B.
4. B knows Kb, thus decrypts E(Kb, R) to get R and will subsequently use R to
decrypt E(R,M) to get M.
You see that a random key is generated every time a message has to be sent. I admit
the man could intercept messages sent between the top secret trusted nodes, but I see
no way he could decrypt them.”
“Well, I think you have your man, Lestrade. The protocol isn’t secure because
the server doesn’t authenticate users who send him a request. Apparently designers
of the protocol have believed that sending E(Kx,R) implicitly authenticates user X as
the sender, as only X (and the server) knows Kx. But you know that E(Kx, R) can be
intercepted and later replayed. Once you understand where the hole is, you will
be able to obtain enough evidence by monitoring the man’s use of the computer he
has access to. Most likely he works as follows: After intercepting E(Ka, R) and
E(R,M) (see steps 1 and 3 of the protocol), the man, let’s denote him as Z, will continue
by pretending to be A and...
Finish the sentence for Holmes.
4.2 There are three typical ways to use nonces as challenges. Suppose Na is a nonce generated
by A,A
Describe situations for which each usage is appropriate. Get this solution
4.3 Show that a random error in one block of ciphertext is propagated to all subsequent
blocks of plaintext in PCBC mode (see Figure F.2 in Appendix F). Get this solution
4.4 Suppose that, in PCBC mode, blocks Ci and Ci 1 are interchanged during transmission.
Show that this affects only the decrypted blocks Pi and Pi 1 but not subsequent blocks. Get this solution
4.5 In addition to providing a standard for public-key certificate formats, X.509 specifies
an authentication protocol.The original version of X.509 contains a security flaw.The
essence of the protocol is
A B: A {tA, rA, IDB}
B A: B {tB, rB, IDA, rA}
A B: A {rB}
where tA and tB are timestamps, rA and rB are nonces, and the notation X {Y} indicates
that the message Y is transmitted, encrypted, and signed by X.
The text of X.509 states that checking timestamps tA and tB is optional for
three-way authentication. But consider the following example: Suppose A and B have
used the preceding protocol on some previous occasion, and that opponent C has
intercepted the preceding three messages. In addition, suppose that timestamps are
not used and are all set to 0. Finally, suppose C wishes to impersonate A to B. C
initially sends the first captured message to B:
C B: A {0, rA, IDB}
B responds, thinking it is talking to A but is actually talking to C:
B : C: B{0, roe B, IDA, rA}
C meanwhile causes A to initiate authentication with C by some means. As a result,A
sends C the following:
C responds to A using the same nonce provided to C by B.
A responds with
This is exactly what C needs to convince B that it is talking to A, so C now repeats the
incoming message back out to B.
So B will believe it is talking to A, whereas it is actually talking to C. Suggest a simple
solution to this problem that does not involve the use of timestamps. Get this solution
4.6 Consider a one-way authentication technique based on asymmetric encryption:
A B: IDA
B A: R1
A B: E(PRa, R1)
a. Explain the protocol.
b. What type of attack is this protocol susceptible to? Get this solution
4.7 Consider a one-way authentication technique based on asymmetric encryption:
A B: IDA
B A: E(PUa, R2)
A B: R2
a. Explain the protocol.
b. What type of attack is this protocol susceptible to? Get this solution
4.8 In Kerberos, when Bob receives a ticket from Alice, how does he know it is genuine? Get this solution
4.9 In Kerberos, when Bob receives a ticket from Alice, how does he know it came from
Alice? Get this solution
4.10 In Kerberos, Alice receives a reply, how does she know it came from Bob (that it’s not
a replay of an earlier message from Bob)? Get this solution
4.11 In Kerberos, what does the ticket contain that allows Alice and Bob to talk securely? Get this solution
4.12 The 1988 version of X.509 lists properties that RSA keys must satisfy to be secure,
given current knowledge about the difficulty of factoring large numbers. The discussion
concludes with a constraint on the public exponent and the modulus n:
It must be ensured that e log2(n) to prevent attack by taking the
eth root mod n to disclose the plaintext.
Although the constraint is correct, the reason given for requiring it is incorrect.What
is wrong with the reason given and what is the correct reason? Get this solution
4.13 Find at least one intermediate certification authority’s certificate and one trusted root
certification authority’s certificate on your computer (e.g. in the browser). Print
screenshots of both the general and details tab for each certificate. Get this solution
4.14 NIST defines the term cryptoperiod as the time span during which a specific key is
authorized for use or in which the keys for a given system or application may remain
in effect. One document on key management uses the following time diagram for a
shared secret key.
Explain the overlap by giving an example application in which the originator’s usage
period for the shared secret key begins before the recipient’s usage period and also
ends before the recipient’s usage period. Get this solution
4.15 Consider the following protocol, designed to let A and B decide on a fresh, shared
session key K'AB.We assume that they already share a long-term key KAB.
1. A B: A, NA
2. B A: E(KAB, [NA, K'AB])
3. A B: E(K'AB, NA)
a. We first try to understand the protocol designer’s reasoning:
• Why would A and B believe after the protocol ran that they share K'AB with
the other party?
• Why would they believe that this shared key is fresh?
In both cases, you should explain both the reasons of both A and B, so your answer
should complete the following sentences.
A believes that she shares K'AB with B since . . .
B believes that he shares K'AB with A since . . .
A believes that K'AB is fresh since . . .
B believes that K'AB is fresh since . . .
b. Assume now that A starts a run of this protocol with B. However, the connection
is intercepted by the adversary C. Show how C can start a new run of the protocol
using reflection, causing A to believe that she has agreed on a fresh key with B (in
spite of the fact that she has only been communicating with C).Thus, in particular,
the belief in (a) is false.
c. Propose a modification of the protocol that prevents this attack. Get this solution
4.16 What are the core components of a PKI? Briefly describe each component. Get this solution
4.17 Explain the problems with key management and how it affects symmetric cryptography. Get this solution
4.18 Consider the following protocol:
A KDC: IDA 7IDB 7N1
KDC A: E(Ka, [KS 7IDB 7N1 7E(Kb, [KS 7IDA]))
A B: E(Kb, [KS 7IDA])
B A: E(KS, N2)
A B: E(KS, f(N2))
a. Explain the protocol.
b. Can you think of a possible attack on this protocol? Explain how it can be done.
c. Mention a possible technique to get around the attack—not a detailed mechanism,
just the basics of the idea.
Note: The remaining problems deal with a cryptographic product developed by IBM,
which is briefly described in a document at this book’s Web site in IBMCrypto.pdf.
Try these problems after reviewing the document. Get this solution
4.19 What is the effect of adding the instruction EMKi?
EMKi: X E(KMHi, X) i 0, 1 Get this solution
4.20 Suppose N different systems use the IBM Cryptographic Subsystem with host master
keys KMH[i] (i 1, 2, . . . , N). Devise a method for communicating between systems
without requiring the system to either share a common host master key or to
divulge their individual host master keys. Hint: Each system needs three variants of its
host master key. Get this solution
4.21 The principal objective of the IBM Cryptographic Subsystem is to protect transmissions
between a terminal and the processing system. Devise a procedure, perhaps
adding instructions, which will allow the processor to generate a session key KS and
distribute it to Terminal i and Terminal j without having to store a key-equivalent
variable in the host. Get this solution
