Thirty-two review questions and eighteen problems — and two of them are more interesting than the rest, because one of the book’s own questions cannot be answered as printed.
How to use this page
-
Review questions R1–R32 — grouped as the book groups them, from the four properties through to intrusion detection.
-
Problems P1–P18 — the classical ciphers, RSA (Rivest–Shamir–Adleman) Rivest–Shamir–Adleman The public key algorithm that became almost synonymous with public key cryptography. introduced in ch. 8 by hand, Diffie-Hellman, a key distribution centre, and two protocol attacks worth doing slowly.
-
Two widgets from the chapter, configured to check P6, P7 and P8 directly.
-
The Wireshark and IPsec (IP Security) IP Security The network-layer security suite, most often used in tunnel mode to build VPNs. introduced in ch. 8 labs — what they contain, and which of them this site can ship.
-
An interview with Steven M. Bellovin — the book’s closing card, and the last page of the book.
Why this matters
Three problems here are worth more than the rest together, because each one breaks something that looked finished.
P15 takes ap4.0 — the protocol section 8.4 certified as working — and defeats it by running two copies at once. P16 does the same to the public key version, and lands exactly on the pizza prank. P9(d) shows Diffie-Hellman, which removes the need for a shared secret, giving up authentication in exchange.
All three failures are the same failure: a protocol can be correct in isolation and wrong in context.
Review questions
Review questions R1–R32
Grouped as the book groups them. Answer before revealing.
R1Confidentiality against integrity
What is the difference between message confidentiality and message integrity? Can you have one without the other?
Hint: Ask what each property would still guarantee if the other were removed.
R2Three pairs of Internet entities needing secure communication
Give three specific example pairs of Internet entities that may want secure communication.
R3Symmetric against public key, from a service perspective
What is the important service-level difference?
R4What attack does an intruder holding a matched pair have?
An intruder has an encrypted message and its decrypted version. Which attack can she mount?
R5Counting blocks, mappings and keys
Consider an 8-bit block cipher.
a.How many possible input blocks does it have?
b.How many possible mappings are there, and how many possible keys?
R6How many keys does the system need?
N people each want to communicate with the other N − 1, with no other member of the group able to decode their exchange.
How many keys are required with symmetric key encryption? And with public key encryption?
Hint: For the first, count pairs. For the second, count people.
R7Modular arithmetic in your head
With n = 10,000, a = 10,023 and b = 10,004, compute (a × b) mod n.
R8A bit pattern as a number
What decimal number corresponds to the message 10101111?
R9Why a hash beats a checksum
In what way does a hash provide a better integrity check than an Internet checksum?
R10Can a hash be reversed?
Can you "decrypt" a hash of a message to obtain the original message?
R11A flawed variation of the message authentication code
Suppose the sender sends (m, H(m) + s), the concatenation of H(m) with the secret s. Is this flawed?
Hint: Ask what Trudy can read off the wire, and what she could then build.
R12Verifiable and nonforgeable
What does it mean for a signed document to be verifiable and nonforgeable?
R13Signing the hash rather than the message
In what way is a public-key-encrypted message hash a better signature than a public-key-encrypted message?
R14True or false: a certificate is encrypted with the issuer's public key
Typically the entire certificate would be encrypted with certifier.com's public key. True or false?
R15MAC or digital signature?
Alice has one message she will send to anyone who asks. Thousands of people want it, and each wants to be sure of its integrity.
Which integrity scheme suits this situation?
R16The purpose of a nonce
What is the purpose of a nonce in an end-point authentication protocol?
R17Once in whose lifetime?
What does it mean to say a nonce is a once-in-a-lifetime value? In whose lifetime?
R18Is an HMAC scheme replay-proof?
Is the integrity scheme based on HMAC susceptible to playback attacks? If so, how can a nonce fix it?
Hint: Nothing in H(m + s) refers to when it was computed.
R19PGP: how does Bob know Alice wrote it?
How does Bob know for sure that Alice created the message? Does PGP use a message authentication code for integrity?
R20True or false: the TLS record has a sequence-number field
In the TLS record, there is a field for TLS sequence numbers. True or false?
R21The purpose of the TLS handshake nonces
What is the purpose of the random nonces in the TLS handshake?
R22True or false: the server sends the IV in the clear
A TLS session uses a block cipher with CBC. The server sends the client the initialization vector in the clear. True or false?
R23Where does the deception fail?
Bob opens a TCP connection to Trudy, who is pretending to be Alice. During the handshake Trudy sends Bob Alice's certificate.
At what step of the TLS handshake does Bob discover he is not talking to Alice?
Hint: Trudy can send Alice's certificate, because it is public. What she cannot do is act on it.
R24True or false: a new security association per packet
Typically a new SA is established for each packet sent in a stream. True or false?
R25A TCP retransmission over IPsec
TCP runs over IPsec between headquarters and the branch office. If TCP retransmits the same packet, will the two datagrams R1 sends have the same sequence number?
R26True or false: an IKE SA and an IPsec SA are the same
An IKE SA and an IPsec SA are the same thing. True or false?
R27WEP encryption (the question with two problems)
This question cannot be answered as printed — see the note below it.
The book asks: data 10101100, keystream 1111000 — what is the ciphertext? What is wrong with the question, and what is the answer once it is repaired?
Hint: Count the bits on each side.
R28The two data structures of a stateful filter
Name them and describe what each does.
R29True or false: a stateless filter can use TCP flag bits
A traditional stateless packet filter may filter on TCP flag bits as well as other header fields. True or false?
R30True or false: per-interface access control lists
In a traditional packet filter, each interface can have its own access control list. True or false?
R31Why an application gateway needs a filter beside it
Why must an application gateway work together with a router filter to be effective?
Hint: What stops a user simply going around the gateway?
R32True or false: signature-based systems inspect payloads
Signature-based intrusion detection and prevention systems inspect the payloads of TCP and UDP segments. True or false?
R27 is broken twice over
The question gives data 10101100 — 8 bits — and a keystream 1111000 —
7 bits. An exclusive-or needs operands of equal length, so the question as
printed has no answer. With the keystream repaired to 11110000, the
ciphertext is 01011100.
And the deeper problem: R27 asks about WEP (Wired Equivalent Privacy) Wired Equivalent Privacy The original 802.11 security specification, whose flaws left users no safer than with no security at all. introduced in ch. 8 , which this edition removed from section 8.8 entirely, telling readers to consult the references or earlier editions. The review question tests material the chapter no longer contains.
Verified against the page image. This is the sixth slip found in chapter 8.
Problems
Problems P1–P18
Numeric answers are checked with a 1 per cent tolerance. Two of the chapter's widgets appear below, set up to check specific problems.
P1The monoalphabetic cipher, both ways
a.Using Figure 8.3, encode "This is an easy problem."
b.Decode "rmij'u uamu xyj."
P2How much a known-plaintext attack saves
Show that knowing seven (ciphertext, plaintext) pairs reduces the substitutions to check by about 10⁹.
P3Does one chosen plaintext break the polyalphabetic cipher?
Will a chosen-plaintext attack using "The quick brown fox jumps over the lazy dog." decode all messages?
Hint: That sentence contains every letter — but how many times, and in which positions?
P4Rounds that undo themselves
In Figure 8.5, each table Tᵢ reverses the order of its eight input bits, and the 64-bit scrambler changes nothing. The input is 10100000 repeated eight times.
a.With n = 3, what is the output?
Hint: Reversal is its own inverse. What does applying it three times do?
b.Now change the last bit of the input from 0 to 1. How does the output change?
c.Repeat both parts with a scrambler that inverses the order of the 64 bits.
P5Storing the tables
a.How many bits of storage do the eight 8-bit-by-8-bit tables need in total?
b.How does that compare with a full-table 64-bit block cipher?
P6Block cipher, with and without chaining
Use Table 8.1 with plaintext 100100100.
a.Without CBC, what is the ciphertext?
b.Trudy sniffs it, knowing a 3-bit block cipher without CBC is used but not which one. What can she surmise?
c.Now with CBC and IV = 111, what is the ciphertext?
P7Encrypting "dog"
RSA with p = 3 and q = 11.
a.Encode "dog" by encrypting each letter separately, then decrypt to recover it.
Hint: Compute n and z first, then pick a legal e.
b.Now encrypt "dog" as one message m rather than three.
P8Keys from a slightly larger pair of primes
RSA with p = 5 and q = 11.
a.What is n?
b.What is z?
P9Diffie-Hellman key exchange
Diffie-Hellman: p is prime, g < p, both public. Alice and Bob choose secrets S_A and S_B, compute public values T = g^S mod p, exchange them, and each raises the other's value to their own secret.
a.Prove that Alice and Bob obtain the same key.
b.With p = 11, g = 2, S_A = 5 and S_B = 12: what is Alice's public value T_A?
c.What is the shared key S?
d.Draw a timing diagram showing the man-in-the-middle attack, with lifelines for Alice, Trudy and Bob.
Hint: Trudy does not need to break the mathematics. She needs to run it twice.
P10Distributing a session key without public key cryptography
A key distribution centre shares a secret symmetric key with each registered user: K_A-KDC with Alice, K_B-KDC with Bob. The first message is K_A-KDC(A, B).
a.What is the second message, from the centre to Alice?
b.What is the third message, from Alice to Bob?
P11A third message with the same checksum
Compute a third message, different from Figure 8.8's two, with the same checksum.
Hint: Which two characters land in the same column of the 4-byte grid?
P12Integrity and confidentiality together
Alice and Bob share an authentication key S1 and an encryption key S2. Augment Figure 8.9 to provide both integrity and confidentiality.
P13Verifying BitTorrent blocks
A peer joins a torrent and obtains the .torrent file from a fully trusted source. Describe a simple scheme letting peers verify each block.
Hint: What can the trusted file carry that a malicious peer cannot forge?
P14Why OSPF uses a MAC rather than signatures
Why do you think a message authentication code was chosen over digital signatures?
P15Breaking ap4.0 by making it mutual
Both parties now authenticate each other using the same protocol. Show how Trudy, pretending to be Alice, can authenticate herself to Bob.
Hint: Two runs of the protocol can be interleaved, and both sides use nonces.
P16Authentication with public keys, and its gap
A public key version of ap4.0: Alice says who she is, Bob sends a nonce R, Alice returns K⁻_A(R), and Bob applies K⁺_A to recover R.
a.Diagram the protocol.
b.With no certificates in use, how can Trudy become a woman-in-the-middle?
P17Bob's side of Figure 8.21
Diagram the operations Bob performs on the package Alice sends.
P18What is possible with only one key pair
Bob has a key pair and Alice has his certificate. Alice has no key pair of her own. Everyone shares the same hash function H(·).
a.Can Bob verify that Alice created the message?
Hint: What would Alice have to possess for Bob to be sure it was her?
b.Can confidentiality be provided?
Check P6 here
| i | plaintext m(i) | into the cipher | ciphertext c(i) |
|---|---|---|---|
| 1 | 100 | 100 | 011 |
| 2 | 100 | 100 | 011 |
| 3 | 100 | 100 | 011 |
1 distinct plaintext block produced 1 distinct ciphertext block. The repeats are marked in red. Trudy cannot read them, but she can see that those blocks were the same — and that alone can be enough.
Set the plaintext to 100100100. The middle tab answers part (a); the third tab with IV 111 answers part (c).
Check P7 and P8 here
Bob generates his keys
- 2. n = pq
- 33
- z = (p−1)(q−1)
- 20
- 5. public key (n, e)
- (33, 3)
- private key (n, d)
- (33, 7)
Step 4 found d = 7, because 3 × 7 − 1 = 20 divides exactly by z = 20.
| letter | m | me | c = me mod n | cd | cd mod n |
|---|---|---|---|---|---|
| d | 4 | 64 | 31 | 27512614111 | 4 ✓ |
| o | 15 | 3375 | 9 | 4782969 | 15 ✓ |
| g | 7 | 343 | 13 | 62748517 | 7 ✓ |
It opens on P7's keys: p = 3, q = 11, e = 3, encoding "dog". For P8, choose p = 5 and q = 11 and read n and z off the panel.
The two labs
The Wireshark lab captures the TLS (Transport Layer Security) Transport Layer Security Encryption, integrity and authentication added above TCP, in the application layer. introduced in ch. 2 records exchanged with an e-commerce server. It asks you to delineate and classify each one: which record types appear, and which fields each carries.
That one is reproducible here in spirit: the record structure is on section 8.6’s page as a clickable diagram, and the handshake as a two-scenario ladder. What a live capture adds is the mess of a real session, which is worth seeing.
Why the IPsec lab is not rebuilt here
The IPsec lab asks you to create security associations between Linux machines — first by hand, then by letting IKE (Internet Key Exchange) Internet Key Exchange The IPsec protocol that establishes security associations automatically. introduced in ch. 8 create them. The second half needs four Linux machines, two with two Ethernet adapters each.
Nothing about that is simulable in a browser, and pretending otherwise would teach the wrong thing. The lab’s whole value is that the associations are real. You configure state on two kernels, then watch datagrams that a packet sniffer shows as protocol 50, with the original addresses invisible inside.
If you have the machines, do it. If you do not, section 8.7’s datagram diagram is what the sniffer would have shown you.
An interview with Steven M. Bellovin
Voices from the field — Steven M. Bellovin
Steven Bellovin is at Columbia University, after many years at AT&T Labs Research. He describes his focus as “networks, security, and why the two are incompatible”. He was one of the creators of Usenet — the first newsgroup exchange network — and received the Usenix Lifetime Achievement Award for it in 1995.
On his own prediction. His original estimate for Usenet was one to two messages per day, from 50 to 100 sites at the most — ever. The growth turned out to be in people-related topics rather than the computer science he expected.
On what motivates the work. Two things: keeping computers useful, which means their function cannot be corrupted by attackers, and protecting privacy.
On what he learned from Fred Brooks. Outlook and trade-offs — “how to look at problems in the context of the real world, and how much messier the real world is than a theorist would like”. His summary is worth keeping: most computer work is engineering — the art of making the right trade-offs to satisfy many contradictory objectives.
On where security actually fails. This is the sharpest thing in the interview, and it points away from everything this chapter taught. “At least scientifically, we know how to do cryptography. That’s been a big help. But most security problems are due to buggy code, and that’s a much harder problem. In fact, it’s the oldest unsolved problem in computer science, and I think it will remain that way.”
On the challenge he names. Securing systems built out of insecure components. We can already do that for reliability in the face of hardware failures — can we do the same for security?
On advice. “Learning the mechanisms is the easy part. Learning how to think paranoid is harder. You have to remember that probability distributions don’t apply — the attackers can and will find improbable conditions. And the details matter, a lot.”
Worth noticing. He also observes that much of the security we have comes from isolation, since a firewall works by cutting off access. And we are in an era of increasing connectivity, where isolating things keeps getting harder. That is section 8.9’s mechanism and its expiry date, in one sentence.
What these problems are really testing
-
A protocol proved safe in isolation can fail when two runs interleave. P15 defeats ap4.0 by opening a second connection and using Bob as an oracle to answer his own challenge.
-
Diffie-Hellman removes the shared secret and gives up authentication. Trudy substitutes her own public value in both directions and holds two keys, one with each party — which is the pizza prank again, in a different costume.
-
The scaling argument for public key cryptography is separate from the key-agreement one. N people need N(N−1)/2 symmetric keys and only 2N with public keys — quadratic against linear, before anyone has said a word about how a secret would be agreed.