Security

Why Security, and Policy vs Mechanism

On one computer, the operating system can keep users apart: it owns the memory, the disk and the keyboard. A distributed system has no such single guardian. Its resources are scattered across many machines and its messages cross networks that the system does not control. This section sets out why that makes security hard, the model the textbook uses to describe the danger, and the first distinction every exam answer on security needs: policy versus mechanism.

Why a distributed system is hard to secure

The guide gives four related reasons. Each one follows from the very things that make a system distributed.

• Many entry points. The resources are spread over many computers, and every one of those computers is a door an attacker can try.
• Exposed channels. Messages travel over networks where attackers can read them, copy them or change them.
• Sharing. Many users share the resources, so the system has to decide who may do what. The textbook (CDK) puts it as: the need for security "arises from the desire to share resources".
• Propagation. Once one service is compromised, the damage can spread to the other parts of the system that trust it.

The security model: principals and the enemy

CDK's security model (first met in Part II) describes the setting in a few words. Processes encapsulate resources: a server process holds some data (files, bank accounts, grades) and lets other processes use it only through the operations in its interface. Each request is made on behalf of someone.

That is a very capable enemy, and it is deliberately so: if your design survives an enemy who can see and forge everything on the wire, it survives a weaker one too. Against such an enemy, protection needs three things, marked on the figure below: secure channels (so that copying and injecting achieve nothing), access control (so that even a genuine principal can do only what it is allowed to do), and endpoint security (so that the machines at each end are not themselves compromised).

Security policies vs mechanisms exam

When people say "this system is secure", they mean two different things at once: that it allows the right things, and that it actually stops the wrong ones. The course separates them.

The course example: the policy is "Only authorised teaching staff may change students' grades." Two mechanisms enforce it. First the system verifies the user's identity at sign-in (authentication), and then it checks that user's permissions, for example against an access control list (ACL, a list stored with a resource saying who may do what to it), before allowing the change.

The two are kept separate for two reasons. Without a policy you cannot judge whether a system is secure at all, because "secure" only means "enforces its policy". And the same mechanism can serve many different policies: one ACL mechanism can enforce a grades policy, a payroll policy and a file-sharing policy.

Check yourselfSelf-test Q1: distinguish a security policy from a security mechanism, with an example.

A policy states what is allowed (who may access which resources, and what protection is required), independent of technology. A mechanism is how the system enforces the policy. Example: the policy "only authorised staff may change grades" is enforced by the mechanisms of authentication at sign-in plus a permission check against an ACL.

Check yourselfWhich of these is a policy rather than a mechanism?

1. Every request carries a MAC computed with a session key.
2. Students may read, but not modify, their own enrolment records.
3. Passwords are hashed before they are stored.
4. The server checks the UNIX rwx bits before opening a file.

B. It says who may do what and names no technique. A, C and D are all techniques (a MAC, hashing, permission bits) that could enforce some policy, so they are mechanisms.

Threats and Attacks

Before you can defend a system you have to name what you are defending it against. This section gives the course's vocabulary for that: what a threat is, the three classes of threat, and the five methods of attack, each with a picture. These definitions are asked for almost word for word in exams.

Some threats are obvious. Anyone who can sniff (passively read the traffic on) a shared local network can collect the passwords that cross it. Others are subtle: if clients never check who the server is, an impostor can set itself up as the official file server and collect everything clients send it. Attacks can even target the security mechanisms themselves. A replay attack, which resends an old message, can defeat a naive authentication scheme that only checks that a message was encrypted with the right key.

Three classes of threat exam

Five methods of attack exam

Every method of attack needs a channel: either access to an existing channel, or a new channel that masquerades as an authorised one. The table gives the five methods with the guide's definitions; the pictures after it show each one happening. In all of them Alice is blue, Bob (or the server) is green, and the attacker is red.

Some attacks in more detail

Man-in-the-middle (MITM)

A man-in-the-middle attack is the most dangerous form of tampering. Mallory intercepts the first messages of a key exchange and substitutes his own keys. From then on he decrypts each message, reads or alters it, re-encrypts it with the correct key and forwards it, while both ends believe the channel is secure. Step through it below. (A public key is a key anyone may know that encrypts messages only the matching private key can decrypt; 10.4 explains these properly.)

Trust-on-first-use carries exactly this risk. SSH, for example, asks you to accept the server's key the first time you connect, and remembers it afterwards. No certification authority (CA, a trusted third party that vouches for keys) binds that key to the server's identity, so a man in the middle who is present at the very first connection is trusted from then on. This was a real exam question.

Past exam2016 Q7(a) · 2 marks Some systems, such as secure shell, require the user to explicitly trust a public key provided by the server when connecting for the first time. Name the security risk and explain why it is a risk.

• The risk is a man-in-the-middle attack, which is the weakness of trust-on-first-use.
• It is a risk because no certificate from a trusted CA binds the key to the server's identity, so the user cannot tell whether the key really belongs to the server.
• An attacker who intercepts the first connection can therefore present his own public key. The user accepts it, and from then on the attacker can decrypt, read or alter, re-encrypt and forward all traffic.
• After that, the wrong key is cached and trusted. The defence is to verify the key's fingerprint out of band, or to use CA-signed certificates.

Replay, and the idea of freshness

Replay works even against messages that are encrypted and authenticated, because the attacker never needs to read or forge anything: he copies bits and sends them again later. The receiver decrypts them perfectly. What is missing is freshness, some evidence that a message is new rather than a recording.

Denial of service (the lecturer's notes)

In a denial-of-service (DoS) attack, the attacker makes excessive, pointless invocations that overload the network bandwidth or the server's CPU. The lecturer's example: a building's electronic door locks can be disabled by flooding their controller with invalid requests, so that genuine card swipes are never processed. A firewall cannot stop such a flood, because the flood arrives through the very entrance legitimate traffic uses; the remedy has to be applied upstream, by quality-of-service (QoS) throttling.

Threats from mobile code

Mobile code is code downloaded from elsewhere and run locally, such as a Java applet. It runs inside the host process, so it can use anything the host can. That makes it a potential Trojan horse: code that claims an innocent purpose but uses resources that are available to the host and not to the code's author. The Java sandbox defends against this in four ways, numbered in the figure.

Information leakage and traffic analysis

Encrypting the contents of messages is not enough to stop leakage. Who talks to whom, when and how much still reveal information, and exploiting that is called traffic analysis. A sudden flood of messages to a stock dealer reveals heavy trading even if every message is encrypted; an anonymous user who always connects on Thursday afternoons can be identified by that habit. The countermeasure is to attach security levels to information and to channels, so that high-level information never flows into lower-level channels. This is the Bell–LaPadula model.

Check yourselfSelf-test Q2: distinguish a threat from an attack, and list and explain the three classes of threat.

A threat is a potential violation of policy; an attack is the actual execution of a threat. The three classes of threat are: (1) leakage, the unauthorised acquisition of information; (2) tampering, the unauthorised alteration of information; (3) vandalism, interfering with a system's operation without gain to the attacker.

Check yourselfSelf-test Q3: list and explain the methods of attack, and describe man-in-the-middle.

The five methods: eavesdropping (obtaining copies of messages without authority), masquerading (sending or receiving messages using another principal's identity without authority), message tampering (intercepting messages and altering them before passing them on), replaying (storing intercepted messages and sending them later; note that replay works even on encrypted messages) and denial of service (flooding a channel or resource to deny access to others).

In a man-in-the-middle attack, the attacker intercepts the first key exchange and substitutes his own keys, then decrypts, re-encrypts and forwards each message. It is defeated by certificate-authenticated keys.

Check yourselfAn attacker floods a building's door-lock controller with invalid requests. Which class of threat is this, which method of attack, and why won't the building's firewall help?

It is vandalism (interference without gain to the attacker) carried out by denial of service. A firewall forwards authorised-looking traffic through the normal entrance, and the flood arrives through that same entrance, so the firewall cannot separate it from genuine requests; the remedy is QoS throttling upstream.

Check yourselfTrue or false: if every message is encrypted with a strong key, an attacker learns nothing from the traffic.

False. Traffic analysis still reveals who talks to whom, when and how much (the stock-dealer and Thursday-afternoon examples). The countermeasure is information-flow control with security levels (Bell–LaPadula), not stronger encryption.

Secure Transactions and Secure Design

Knowing the attacks, we can ask two practical questions. What exactly must be protected when someone buys something online? And how do you go about designing a system so that it resists attacks you have not even thought of yet? The answers are a list of requirements and a list of worst-case assumptions, and both are favourite exam material.

Requirements for web purchases exam

Email, purchases, banking and micro-transactions all depend on security. For a purchase over the web, the guide lists four security requirements.

1. Authenticate the vendor to the buyer. The buyer must know they are dealing with the intended vendor's server, not an impostor.
2. Protect the buyer's payment details. They must be kept from third parties and delivered unaltered.
3. Protect the vendor's responses. Goods (for example, downloads) and confirmations must reach the buyer unaltered and undisclosed.
4. Support first-time buyers. No prior contact, shared secret or third party should be needed. The slide calls this a policy; CDK calls it a system requirement, imposed by the scale of the Internet.

Banking adds two more requirements: authentication of the account holder (the bank must know who is asking), and non-repudiation, which means the account holder cannot later deny having taken part in a transaction. TLS (10.11) meets requirements 1–4; non-repudiation needs digital signatures (10.8).

Designing secure systems

Complete security is hard to guarantee, much as bug-free software is. So the design method is not "make it perfect" but: list the threats, then show that each one is prevented by a mechanism, either by informal argument or by logical proof. The table in 10.12 is exactly such a list.

Auditing backs this up, because something will be missed. The system keeps a secure log of sensitive actions, such as failed sign-ins and permission changes, and the log is analysed for unusual trends. Each record holds four things:

Security also has to be weighed against other concerns. You balance cost against risk, considering the potential damage, the cost of protection and the effort an attacker would need. And you keep the system usable: security measures must not obstruct legitimate users, or they will be bypassed.

Worst-case assumptions and design guidelines exam

Secure design starts from worst-case assumptions about the environment. Each assumption leads directly to a guideline, and there are six.

Check yourselfSelf-test Q4: what are the worst-case assumptions and design guidelines for a secure system?

The six: interfaces are exposed (any message can reach any interface); networks are insecure (messages read, copied, falsified, sources faked); limit the lifetime and scope of each secret (use session keys and expiry); algorithms and code are available to attackers (publish algorithms, rely only on secret keys); attackers may have large resources (the biggest computers of the system's lifetime, plus a few orders of magnitude); minimise the trusted base (every trusted component is a potential weakness). Also say that you list the threats and show each is countered, keep audit logs, and balance cost against risk and usability.

Check yourselfWhich of these is not one of the course's secure-design guidelines?

1. Keep the trusted computing base small.
2. Keep the encryption algorithm secret so attackers cannot study it.
3. Use short-lived session keys.
4. Assume any message can be sent to any interface.

B. The guideline is the opposite: assume algorithms and code are available to attackers, publish the algorithm for scrutiny, and rely only on the secrecy of the keys. "Secret algorithms" is listed among the common pitfalls.

Check yourselfWhy is "support first-time buyers" the requirement that makes web commerce hard, and what does the guide note about its name?

Because the buyer and vendor share no secret and have no prior contact, so the shared-key techniques of 10.5 cannot be bootstrapped; something like public-key certificates is needed. The slide calls it a policy, while CDK calls it a system requirement, imposed by the scale of the Internet.

Cryptography Fundamentals

Almost every defence in this Part is built from cryptography: the science of transforming messages so that only the right people can read them, or so that changes to them can be detected. Before the protocols, you need the cast of characters, the notation the protocols are written in, and the two families of keys.

The cast and the notation

Security protocols are written as conversations between named people. The names are a convention from CDK (Fig 11.1), and they tell you each participant's role at a glance.

Encryption, decryption and keys exam

What each kind of key gives you

The slide sets out what each kind of key gives you, and this table of three cases is the foundation of everything that follows. Read each row as "who can undo this?".

In every case, secret keys and private keys must be stored securely. And there is a cost: public-key algorithms need 100–1000× the processing of secret-key ones.

Symmetric vs asymmetric cryptography exam

There are two families. In secret-key (symmetric) cryptography, one key both encrypts and decrypts, so the two parties must share it. In public-key (asymmetric) cryptography, each party has a pair of keys: what one key encrypts, only the other can decrypt. The lecturer's image for a key pair is a sheet of paper torn in half: the two halves match each other and nothing else.

The table compares the two families. Notice the tension between the speed row and the key-distribution row: each family is good at exactly what the other is bad at, which is why real protocols use both (10.7).

Confusion and diffusion exam

How does a cipher actually hide a message? Claude Shannon named two properties that concealment relies on, together with the secrecy of the keys (never of the algorithm).

• Confusion combines each block with the key by non-destructive operations, such as XOR and circular shift. This obscures the relationship between M and {M}K and defeats character-frequency analysis (counting which letters are common). Enigma used single-letter blocks, and it fell to exactly that kind of statistical analysis.
• Diffusion works by transposing parts of each block, to dissipate the patterns and redundancy in the plaintext. Cipher block chaining (CBC, 10.7) spreads the redundancy further, across blocks. Stream ciphers cannot diffuse, since they have no blocks.

Check yourselfAlice encrypts a message with her own private key K_Apriv and sends it. Who can read it, and what has she achieved?

Anyone holding K_Apub can decrypt it, and K_Apub is public, so there is no secrecy. What she has achieved is proof that the message came from her, because only she holds K_Apriv. This is the basis of digital signatures. To send Bob a secret she should encrypt with Bob's public key instead.

Check yourselfDES uses a 56-bit key. On average, how many keys must a brute-force attacker try, and what happens to that number if the key grows by one bit?

An N-bit key takes 2^N−1 tries on average, so 2⁵⁵ for DES. Each extra bit doubles the key space and therefore doubles the average work: cracking time is exponential in key length.

Check yourselfSelf-test Q5 (part): compare symmetric and asymmetric cryptography in three dimensions.

Speed: symmetric is fast; asymmetric is 100–1000× slower. Key distribution: symmetric needs a secure channel or trusted server per pair; asymmetric just publishes the public key (authenticated by a certificate). Signatures: symmetric gives only MACs, without non-repudiation; asymmetric gives true signatures with non-repudiation. (Also: symmetric is based on one-way functions, asymmetric on trap-door functions.) The "why hybrids" half of Q5 is in 10.7.

Check yourselfWhich property, confusion or diffusion, did Enigma lack enough of, and how was it broken?

Enigma encrypted single-letter blocks, so the relationship between plaintext and ciphertext letters kept the statistics of the language; it fell to statistical (character-frequency) analysis. Confusion with larger blocks obscures that relationship, and diffusion spreads patterns across a block.

The Four Basic Scenarios exam

Cryptography is a set of tools; this section shows them used. CDK gives four short scenarios, each a tiny protocol. Each one solves one problem and leaves another open, and the open problems are exactly what the big protocols later in this Part (Needham–Schroeder, Kerberos, TLS) were built to close. So read each scenario asking two questions: what does it achieve, and what can still go wrong?

First, the four uses of cryptography the scenarios demonstrate:

• Secrecy prevents eavesdropping.
• Integrity detects tampering, using redundancy such as a checksum placed inside the encryption, or a MAC (message authentication code, 10.8).
• Authentication works because successful decryption with a key known only to two parties proves that the sender knew that key.
• Digital signatures give authentication, integrity and non-repudiation together.

Scenario 1: secret communication with a shared key

The simplest case: Alice and Bob already share a secret key K_AB. Alice encrypts each message M_i with it, and Bob decrypts. If the decrypted result contains an agreed value, such as a checksum, Bob knows the message is from Alice (only she has the key) and has not been altered (any change would break the checksum). Step through it, including what Mallory can still do.

Scenario 2: an authentication server

To solve key distribution, bring in a trusted server, Sara. Sara knows a secret key for every principal: K_A, derived from Alice's password, and K_B, the key of Bob, who here is a file server. Sara never hands out these long-term keys; she hands out tickets. This is a simplified version of the Needham–Schroeder protocol of 10.9.

Challenge–response exam

Scenario 2 hides a clever idea in message 2: Alice proved she knows her password without ever sending it. That idea has a name, and it appeared on the 2016 exam.

The course gives four examples, and you will meet three of them again in this Part:

• Message 2 of Scenario 2. The reply is encrypted in Alice's password-derived key, so only the real Alice can use it. This was Needham–Schroeder's key insight: passwords need not be sent to be checked.
• Needham–Schroeder messages 4–5 (10.9): B sends {N_B}K_AB and A replies {N_B − 1}K_AB.
• Kerberos message 2 and its authenticators (10.10) work the same way.
• So does WEP when a device joins a wireless base station.

Past exam2016 Q7(b) · 3 marks Explain what is meant by challenge-response and give an example.

• Definition. Challenge–response is an authentication technique in which a party proves knowledge of a secret (a key or password) without transmitting the secret. The verifier sends a fresh challenge, either a nonce or data encrypted under the secret, and only someone who knows the secret can compute the correct response. Because the challenge is fresh, a recorded response cannot be replayed, and eavesdroppers never see the secret.
• Example (Needham–Schroeder). B sends {N_B}K_AB, and A proves it holds K_AB by returning {N_B − 1}K_AB.
• Example (Kerberos login). The AS replies with {K_CT, n}K_C, encrypted under the password-derived key K_C. Only the real user can decrypt it, and the password never crosses the network.

Scenario 3: public keys deliver a shared key (hybrid)

Scenario 2 needs a server that knows everyone's secret, which is impossible on the open Internet. Public keys avoid that: Bob can publish K_Bpub, and anyone can use it to send him a secret. But public-key operations are slow, so they are used only once, to deliver a fast symmetric session key. The tutors' Tutorial 10 version of this (T10-5) calls the third party a key distribution service.

Scenario 4: digital signature

The last scenario is about proof of origin rather than secrecy. Alice publishes a message M together with {Digest(M)}K_Apriv, and Bob verifies it with K_Apub. A digest (or secure hash) is a short, fixed-length fingerprint of a message; 10.8 covers digests and signatures in full.

Check yourselfIn Scenario 2, why can't Alice read or change the ticket, and why does that matter to Bob?

The ticket is encrypted with K_B, which only Bob and Sara know. Alice can forward it but cannot open it or forge a different one. That matters because Bob trusts the ticket's contents (the name "Alice" and K_AB) precisely because only Sara could have made it.

Check yourselfMatch each scenario to the problem it leaves open: Scenario 1, Scenario 2, Scenario 3.

Scenario 1 (shared key): key distribution and freshness (replay). Scenario 2 (authentication server): no replay protection, and the server must know everyone's key, so it does not scale to e-commerce. Scenario 3 (public key carries the session key): man-in-the-middle, unless the certificate is signed by a key obtained totally securely, which leads to certificate chains.

Check yourselfAn MCQ near-miss: in Scenario 3, Alice sends {K_AB}K_Bpub. Which is true?

1. Anyone with Bob's public key can recover K_AB.
2. Only Bob can recover K_AB, provided K_Bpub really is Bob's.
3. It proves to Bob that the message came from Alice.
4. It must be repeated for every message, because K_AB is slow.

B. Encryption with Bob's public key can be undone only with K_Bpriv. A is the mistake of confusing the two halves; C is false because anyone can encrypt with Bob's public key, so it says nothing about the sender; D has it backwards, since K_AB is the fast symmetric key and the public-key step happens once. The proviso in B is the MITM problem.

Certificates and Access Control

Scenario 3 ended with a question: how does Alice know that a public key really belongs to Bob? Certificates are the answer, and they are how the man-in-the-middle attack is defeated. The second half of this section turns to what happens after a principal has been identified: deciding what it may do (access control), what evidence it presents (credentials), and the coarse outer wall many organisations add (firewalls).

What a certificate is exam

CDK's example (Fig 11.3) is not about keys at all, which makes the idea clearer: Alice's bank issues a certificate saying that account 6262626 belongs to Alice, so that Alice can prove it to a vendor, Carol.

So Carol needs a public-key certificate for Bob's Bank, signed by an authority she trusts more, for example "Fred, the Bankers Federation". But then Carol must also know Fred's key authentically, so the trust problem is recursive. The recursion has to stop somewhere, and it stops by getting the top key out of band: handed over in person, or pre-installed with the software.

Certificate chains

That recursion, written down, is a certificate chain. At the top is the root: a self-signed certificate (one signed with its own private key) that is widely distributed, for example with the operating system or browser, and trusted by fiat. Its private key must be closely guarded. Below the root, each certificate is signed by the issuer above it. For example, Sara certifies Carol's key and Carol certifies Bob's. If Alice already trusts Carol, she can verify Bob's certificate directly; otherwise she first verifies Carol's using Sara's certificate.

Issues and requirements. Chains bring their own problems. You have to choose whom to trust as the root, and trust depends on purpose (a bank root for banking, say). Private keys can be compromised. And long chains are fragile, since each extra link is another place the chain can break. To make chains work there must be a standard format, and agreed rules for building chains, including what counts as a trusted authority.

Expiry and revocation. Certificates also need a way to stop being valid. Each one carries a validity period, and expired certificates are rejected. Revocation invalidates a certificate before it expires, for example after its private key is compromised. Revocation is cumbersome, because every holder of a copy must be told, through revocation lists or online checks. That is why expiry dates are the usual mechanism.

X.509

X.509 is the standard certificate format. It is part of the X.500 directory standard (Part IX) and is used in TLS. An X.509 certificate binds a public key to a subject by the issuer's signature, and certification authorities (CAs) such as Verisign issue them. Its fields fall into five groups:

To verify an X.509 certificate, you first obtain the CA's certificate from a reliable source, and then validate the signature with the CA's public key.

Access control

Authentication establishes who is asking; access control then decides what they may do. Requests take the form <op, principal, resource>, and the server first authenticates the principal, then checks its rights for that operation on that resource.

Rights are grouped by protection domain: an execution environment shared by processes, holding a set of <resource, rights> pairs. A domain is usually created per principal at login; in UNIX, a process's domain comes from its user and group IDs. A protection domain is an abstraction, and it is implemented in one of two ways:

• With capabilities, each process holds unforgeable tokens of the form <resource id, permitted operations, authentication code (signature)>, and requests take the form <op, userid, capability>.
• With access control lists (ACLs), each resource stores <domain, operations> entries. The UNIX rwx bits for owner, group and others are an example.

The table compares the two. Notice how they trade off: ACLs give immediate revocation, while capabilities are fast to check and easy to delegate, but hard to revoke and dangerous if stolen.

Credentials, delegation and firewalls

Credentials are the evidence a principal presents when requesting access, for example a certificate of identity that the server checks against an ACL. A credential "speaks for" its principal: a request signed with a user's private key is treated as coming from that user. Credentials can also be combined, which allows two-person rules (two signatures needed), role-based credentials (rights given to "lecturer" rather than to a named person), and so on.

Delegation is needed when a server must act for a user. For example, a print server needs to read the user's protected file in order to print it. The user gives it a signed delegation certificate (or a capability). The delegation is limited to a subset of the user's rights, and it is time-limited.

Firewalls intercept all external traffic and forward only authorised traffic. They have clear limits: they give no protection against insiders, they are coarse-grained, and they are ineffective against DoS floods.

Check yourselfSelf-test Q9: explain certificates and certificate chains.

A certificate is a statement signed by an authority, binding a key to a name. In a chain, each certificate is verified with its issuer's public key, all the way up to a pre-installed, self-signed root. The problems are choosing the root, key compromise, long chains and revocation.

Check yourselfSelf-test Q13: compare ACLs and capabilities.

An ACL is stored with the resource; the server authenticates the principal and searches the list; revocation is immediate (edit the list); a thief must steal an identity; delegation is awkward. A capability is held by the principal; checking is fast (validate the token, check the operation is in its set); revocation is hard (needs expiry or revocation lists); a stolen token works for the thief; delegation is easy (pass the token). In one line: ACLs give immediate revocation, capabilities give fast checks and easy delegation but are vulnerable to theft and hard to revoke.

Check yourselfWhy do most systems rely on expiry dates rather than revocation, and when is revocation still needed?

Revocation is cumbersome: every holder of a copy of the certificate must be told, through revocation lists or online checks. Expiry needs no communication at all; the certificate simply stops being accepted after its Not After date. Revocation is still needed when a certificate must die before it expires, typically because its private key has been compromised.

Check yourselfA company firewall blocks all inbound connections except to its web server. Name two threats it still does not address.

Any two of: insiders (they are already inside the wall); DoS floods against the web server (the flood arrives through the allowed entrance); anything finer-grained than the firewall's coarse rules, such as a legitimate-looking request from an outsider that abuses the web server itself.

Cryptographic Algorithms

So far, "encrypt with K" has been a black box. This section opens it a little: how a cipher handles a message longer than one block, which symmetric algorithms exist and which are broken, how RSA (the standard public-key algorithm) works with numbers small enough to do by hand, and why real protocols combine the two families. Remember the exam is closed book with no calculator, so the RSA example is worth practising on paper.

Block ciphers and cipher block chaining

A block cipher splits the message into fixed-size blocks (often 64 bits), pads the last block to full size, and encrypts each block. Encrypting the blocks independently has two drawbacks: it shows repeated patterns (identical plaintext blocks give identical ciphertext blocks), and it gives no integrity check (an attacker can delete, reorder or repeat whole blocks unnoticed).

Cipher block chaining (CBC) exam links the blocks together. Each plaintext block is XORed with the previous ciphertext block before it is encrypted:

C_i = E(K, P_i ⊕ C_i−1)    and to decrypt    P_i = D(K, C_i) ⊕ C_i−1

Decryption works because XOR is its own inverse: (X ⊕ C) ⊕ C = X. An initialisation vector (IV), for example a timestamp, is used as the "previous block" for the first block, so that identical messages encrypt differently. CDK points out one limitation: CBC needs a reliable channel, because losing a block breaks the decryption of the block after it.

Stream ciphers

Some data cannot wait for a full block: voice, for example. Stream ciphers are used for such real-time data. A keystream generator produces a stream of bits, for example a random-number sequence from an agreed seed, encrypted with the shared key. The ciphertext is plaintext ⊕ keystream, and the receiver, running the same generator, XORs the same keystream to decrypt. This is secure only if the keystream is never reused.

Symmetric algorithms

The table compares the symmetric algorithms by key and block size. The one to remember as a warning is DES, whose 56-bit key was brute-forced.

RSA exam

RSA is a public-key algorithm whose trap-door function is based on factoring large numbers: multiplying two big primes is easy, but recovering them from the product is infeasible. Key generation takes three steps:

1. Choose large primes P and Q, and compute N = PQ and Z = (P−1)(Q−1).
2. Choose d so that it has no common factor with Z.
3. Find e with e·d ≡ 1 (mod Z). In practice, take the first of Z+1, 2Z+1, 3Z+1, … that is divisible by d, and divide it by d.

The public key K_e = ⟨e, N⟩ is published, and the private key K_d = ⟨d, N⟩ is kept secret. To encrypt, compute c = M^e mod N; to decrypt, compute M = c^d mod N. ("x mod N" is the remainder after dividing x by N.) The message is split into blocks of k bits, which must satisfy 2^k < N so that each block is a number smaller than N.

RSA's security rests on the fact that finding d requires Z, and finding Z requires factoring N. That is infeasible for N > 10²⁰⁰, but 512-bit keys have fallen. CDK recommends keys of at least 768 bits, and 2048 is common.

Check yourselfSelf-test Q6: RSA with P = 5, Q = 11, d = 3. Find N, Z and e, and encrypt M = 2.

N = PQ = 55, and Z = (P−1)(Q−1) = 4·10 = 40. Next, e must satisfy 3e ≡ 1 (mod 40). Try Z+1 = 41 (not divisible by 3), then 2Z+1 = 81 = 3·27, so e = 27.

To encrypt, c = 2²⁷ mod 55. Since 2²⁰ ≡ 1 (mod 55), this reduces to c ≡ 2⁷ = 128 ≡ 18. As a check, decrypting gives 18³ = 5832 ≡ 2 (mod 55). ✓

Check yourselfIn RSA, which number must stay secret for the scheme to be safe, and why is publishing N not enough to give it away?

d (with N it forms the private key). Finding d requires Z = (P−1)(Q−1), and finding Z requires factoring N into P and Q, which is infeasible for large N (N > 10²⁰⁰). So publishing N and e reveals nothing usable, provided the key is long enough: 512-bit keys have fallen, CDK recommends at least 768 bits, and 2048 is common.

Hybrid protocols exam

Public-key cryptography makes key distribution easy, but it is too slow for bulk data. So hybrid protocols use public keys to authenticate the parties and exchange a secret session key, and then let symmetric encryption carry the data. TLS is one example; PGP is another (RSA, then IDEA or 3DES).

Check yourselfSelf-test Q5: compare symmetric and asymmetric cryptography, and explain why hybrids are used.

Symmetric cryptography is fast, but key distribution is hard and it gives no non-repudiation. Asymmetric cryptography is 100–1000× slower, but key distribution is easy (with certificates) and it supports real signatures. A hybrid combines the two: it uses public keys to authenticate and exchange a session key, then symmetric encryption for the data, as TLS does.

Cryptography pragmatics

A few practical figures explain the design choices above.

Check yourselfWrite the CBC encryption and decryption equations, and say why CBC needs an IV and a reliable channel.

C_i = E(K, P_i ⊕ C_i−1) and P_i = D(K, C_i) ⊕ C_i−1. The IV acts as C₀ so that identical messages encrypt differently. A reliable channel is needed because decrypting block i needs block i−1; if a block is lost, decryption breaks.

Check yourselfWhy is DES described as obsolete, and what replaced it?

Its 56-bit key is too short: it was brute-forced in 1997 (about 14,000 PCs over about 12 weeks), and the EFF did it in about 3 days in 1998. 3DES strengthened it (112 effective bits) but is slow; AES (Rijndael), the NIST winner in 2000, is the current standard.

Digital Signatures and MACs

A handwritten signature ties a person to a document. A digital document can be copied perfectly, so a digital signature has to be tied to the exact bits of the document, in a way nobody else can reproduce. This section covers what a signature must achieve, the hash functions that make signatures practical, the two ways to sign (with a private key, or with a shared key as a MAC) and when each is enough.

What a signature must be exam

Because digital documents are trivial to copy, the signer's secret must be bound to the whole bit sequence: change one bit and the signature must fail. Even so, signatures have limits. A signature does not prove when something was signed, and a signer who deliberately leaks the private key can later deny signing ("someone stole my key").

Secure digest (hash) functions exam

A secure digest function (or secure hash) H produces a short, fixed-length value h = H(M) from a message of any length. To be useful for signatures it must satisfy three properties:

1. It is easy to compute h from M.
2. It is hard to compute M from h, so the function is one-way.
3. It is hard to find M′ ≠ M with H(M′) = H(M). Otherwise a signature on M would also be valid for M′.

The reason to sign the digest rather than the message itself is cost: the digest is short and fixed-size, so the expensive public-key operation is done once on a few bytes, whatever the length of M.

The birthday attack

This attack targets property 3. Alice prepares a fair contract M and an unfair one M′, then makes many invisible variants of each (an extra space here, a different line break there) until one variant of each has the same hash. Bob signs the fair variant; Alice then swaps in the unfair one, and Bob's signature still verifies. Because collisions among many candidates are far likelier than hitting one particular hash (as with two people in a room sharing a birthday), a 64-bit hash needs only about 2³² variants. So hashes must be at least 128 bits.

Algorithms. The common hash algorithms are MD5 (128 bits, very fast), SHA-1 (160 bits) and SHA-2 (224–512 bits, the slide's example). CDK calls MD5 and SHA-1 adequate, but both now have practical collision attacks, so use SHA-2.

Signing with public keys exam

A public-key signature is made and checked in four steps:

1. A publishes K_pub, in a certificate.
2. A computes the digest h = H(M) and the signature S = {h}K_priv.
3. A sends M, S.
4. B decrypts S with K_pub to get h′, computes H(M) itself, and accepts if h = h′.

This works because only the holder of K_priv can make an S that decrypts correctly, and any change to M changes H(M). It therefore gives authentication, integrity and non-repudiation, provided the key stays private and the certificate is trusted. Notice the contrast with secrecy: for secrecy you encrypt with the recipient's public key, but for signing you encrypt with the signer's private key.

Signing with a shared key: MACs exam

A MAC (message authentication code) does a similar job with a shared secret key, in three steps:

1. A distributes a random key K to B over a secure channel.
2. A sends M, h, where h = H(M + K), the hash of M concatenated with K.
3. B computes H(M + K) itself and compares it with h.

Trade-offs. The advantage of a MAC is speed: there is no encryption, and hashing is 3–10× faster than symmetric ciphers. MACs are used in TLS. The drawback is that a MAC provides authentication and integrity but not non-repudiation, because both parties know K and either of them could have made h. In addition, only key holders can verify a MAC, and K must be distributed securely.

Check yourselfSelf-test Q7: explain how a public-key digital signature is made and verified.

The signer sends M, {H(M)}K_priv. The verifier decrypts the signature with K_pub, recomputes H(M) and compares the two. This gives authenticity, integrity and non-repudiation. For it to be secure, the hash must be one-way, collision-resistant and at least 128 bits long (because of the birthday attack), for example SHA-2.

Check yourselfSelf-test Q8: MAC vs signature.

A MAC is h = H(M + K), made with a shared key. It is cheap, but it gives no non-repudiation, because either party could have made it, and only key holders can verify it. A signature uses a private key, so anyone can verify it and it gives non-repudiation, but it costs more.

Check yourselfA bank needs records that a customer cannot later deny having authorised. Is a MAC enough?

1. Yes, because the MAC proves integrity.
2. Yes, if the MAC key is at least 128 bits.
3. No: the bank also knows the MAC key, so it could have made the MAC itself.
4. No, because MACs cannot be verified at all.

C. Non-repudiation needs something only the customer could have produced: a signature with the customer's private key. A true-but-irrelevant point (integrity, key length) does not fix that, and D is false, since key holders can verify a MAC.

Check yourselfWhy must a hash used for signatures be at least 128 bits, when nobody is trying to invert it?

Because of the birthday attack on collision resistance: the attacker only needs some pair of fair and unfair variants with the same hash, and for an n-bit hash that takes about 2^n/2 variants. A 64-bit hash falls to about 2³², which is feasible.

Needham–Schroeder exam

Scenario 2 had no replay protection. The Needham–Schroeder secret-key protocol is the full form of that authentication-server idea, with nonces added so that each party can tell a fresh message from a recording. It is the ancestor of Kerberos, and it is examined message by message, so learn the five messages exactly as written here.

The authentication server S holds a ⟨name, secret key⟩ pair for every principal; for a user, the key is derived from the password. A nonce is a value used only once (typically a random number), included in a message to prove that the message is fresh: a reply that contains the nonce you just chose cannot be a recording of an older reply.

The five messages

Why N_B − 1 and not N_B?

Message 4 is {N_B}K_AB. If A simply sent it back unchanged, the reply could equally have come from an attacker who merely reflects message 4 back to B, without knowing K_AB at all. Returning a transformed value, which needs decrypting, changing and re-encrypting, proves that A can actually use K_AB.

The weakness, and the fix exam

The protocol's weakness is that B cannot tell whether message 3 is fresh: B's own nonce only appears from message 4 onwards, and the ticket contains nothing B can check for age. So an intruder who obtains an old K_AB (keys break given time) and the ticket that went with it can replay message 3, answer the challenge in messages 4–5, and so impersonate A.

Fix. Put a timestamp in the ticket, making it {K_AB, A, t}K_B, so that B can check that t is recent. Kerberos uses exactly this fix. (CDK misprints the key here as K_Bpub; it is B's secret key K_B.)

The public-key variant (brief)

There is also a public-key version, which needs no server holding everyone's secrets. Instead the two parties exchange nonces under each other's public keys:

Check yourselfSelf-test Q10: describe the Needham–Schroeder protocol, its weakness and the fix.

The five messages: (1) A → S: A, B, N_A; (2) S → A: {N_A, B, K_AB, {K_AB, A}K_B}K_A; (3) A → B: {K_AB, A}K_B; (4) B → A: {N_B}K_AB; (5) A → B: {N_B − 1}K_AB. N_A proves that message 2 is fresh, and N_B − 1 proves that A holds K_AB. The weakness is that message 3 can be replayed by someone holding an old K_AB. The fix is to add a timestamp, {K_AB, A, t}K_B, as Kerberos does.

Check yourselfIn message 2, what does each part prove or deliver to A?

Encryption under K_A proves it came from S (only S and A know K_A). N_A proves it is fresh, a reply to this request. B confirms which principal the key is for. K_AB is the new session key. {K_AB, A}K_B is the ticket for A to forward to B.

Check yourselfWhy does B send {N_B}K_AB and expect {N_B − 1}K_AB back, rather than {N_B}K_AB?

An attacker who knows nothing could simply reflect {N_B}K_AB back to B. Returning a transformed value requires decrypting N_B, changing it and re-encrypting, which only a holder of K_AB can do.

Kerberos exam

Kerberos is Needham–Schroeder made practical for a real organisation. It provides authentication and key distribution for an intranet (a single management domain), following Needham–Schroeder but using timestamps as nonces, which closes the message-3 hole. It came from MIT's Project Athena, is specified as RFC 4120, and is the default in Windows. The basic arrangement: passwords are known only to the user and Kerberos, and each server's key is known only to that server and Kerberos.

Architecture: a KDC with two services

At the centre is a Key Distribution Centre (KDC), which contains an Authentication Service (AS) and a Ticket-Granting Service (TGS) that share a database of keys. Splitting the KDC in two means the user's password is used only once per login: after that, the client talks to the TGS using a session key instead. A client goes through three steps, each at a different frequency.

• Step A, once per login session: the AS issues a TGS ticket.
• Step B, once per server session: the TGS issues a server ticket.
• Step C, once per transaction: the client makes a request to the server.

Security objects: ticket, authenticator, session key

Kerberos uses three kinds of security object. Getting the difference between the first two right is a classic exam point.

• A ticket, {C, S, t1, t2, K_CS}K_S, is issued for a particular server and shows that the client was recently authenticated by Kerberos. It holds a validity period (t1 to t2) and a session key, and the client name inside it stops an impostor from using a stolen ticket. A ticket is reusable until it expires.
• An authenticator, {C, t}K_CS, is built by the client to prove its identity and its freshness. It is used only once.
• A session key is a random key for each client–server pair. It encrypts authenticators, and data where required.

In the protocol, ticket(C, S) stands for the ticket's contents and {ticket(C, S)}K_S for the sealed ticket; likewise auth(C) is the authenticator's contents and {auth(C)}K_CS the sealed authenticator. The TGS is itself treated as a server called T, so ticket(C, T) holds the session key K_CT between the client and the TGS.

The protocol, message by message

The table traces the full protocol: steps A to C are the three above, and the optional step D adds mutual authentication. In it, n is a nonce.

Why timestamps, and how a user logs in

The timestamps do two jobs. They block replay of old messages, or of tickets left in memory; and they give tickets a lifetime, which is what lets rights be revoked: once a ticket expires, the user has to ask the KDC again, and can be refused.

Logging in is step A seen from the user's side:

1. The login program sends the user's name to the AS.
2. It decrypts the AS's reply with the typed password, and checks the nonce.
3. It keeps the session key and the TGS ticket, and erases the password, which never crossed the network.

Using a service (e.g. rlogin). To use a service such as rlogin (remote login), the client gets a ticket for the rlogind server from the TGS, then sends that ticket together with a fresh authenticator. rlogind decrypts the ticket with its own key, checks the ticket's lifetime, and checks that the authenticator is fresh.

Use in NFS (Part VIII). Per-request Kerberos was too costly for stateless NFS, so NFS uses it differently: the user is authenticated with Kerberos at mount time, and the server records the user ID and client address. Each later request is checked against them, which assumes one user per client machine.

Tickets last about 12 hours, and each realm (administrative domain) has its own KDC.

Limitations exam

Check yourselfSelf-test Q11: explain Kerberos: its steps, ticket vs authenticator, and its limitations.

Kerberos runs in up to four steps. In step A, the AS issues a TGS ticket and K_CT. In step B, the TGS issues a server ticket and K_CS. In step C, the client sends the ticket, an authenticator and its request to the server. In the optional step D, the server authenticates itself to the client.

A ticket is reusable until it expires, whereas an authenticator is used once and proves freshness. The limitations: loosely synchronised (and securely synchronised) clocks; servers must keep lists of recent nonces, hard across failures; the ticket-lifetime trade-off; a single domain with pre-registered keys, unsuitable for open e-commerce; and the KDC holds every key, so it must be physically secure and is a bottleneck and single point of failure (replication helps).

Check yourselfWhich statement about Kerberos is correct?

1. The password is sent to the AS, encrypted with K_T.
2. The client can read its TGS ticket, because it holds K_CT.
3. A ticket can be reused until it expires; an authenticator is used once.
4. Step B happens once per transaction.

C. A is wrong: the password never crosses the network (message 1 is plaintext C, T, n). B is wrong: the TGS ticket is sealed under K_T, which the client does not have. D is wrong: step B is once per server session; step C is once per transaction.

Check yourselfAn attacker copies message 5 from the network and replays it to S ten minutes later. What stops it?

The authenticator {auth(C)}K_CS. It carries a timestamp and may be used only once; S keeps a list of recently seen authenticators and rejects a repeat (and rejects one whose time is no longer recent). The ticket inside message 5 is still valid, but that alone is not enough. The attacker cannot make a new authenticator, because that needs K_CS.

Check yourselfHow does Kerberos fix the Needham–Schroeder weakness, and what new requirement does the fix introduce?

It uses timestamps as nonces: tickets carry a validity period and authenticators carry the current time, so a replayed old ticket with an old key is rejected (this is the {K_AB, A, t}K_B fix). The new requirement is loosely synchronised clocks, with a secure clock protocol.

TLS / SSL exam

Kerberos works inside one organisation, where every key can be registered in advance. On the open web, a buyer and a shop have never met, which was requirement 4 of 10.3. TLS (Transport Layer Security) is the protocol that solves that case, and it is what the padlock in your browser means. It brings together nearly everything in this Part: certificates and chains, public-key key exchange, symmetric encryption, and MACs.

What it is, and its design features

SSL (Secure Sockets Layer) came from Netscape in 1994 and was standardised as TLS (RFC 2246). It secures HTTPS, Telnet, FTP and more. TLS is a hybrid protocol: it uses public keys for authentication and key exchange, and symmetric keys for the data.

• Negotiable algorithms. You cannot assume that all parties have the same software, so the algorithms are agreed in the handshake.
• Bootstrapped. No prior negotiation or third-party help is needed at connection time. Communication starts unencrypted, then moves to public-key cryptography, then to secret-key cryptography. Each switch is optional and negotiated, and each direction can be encrypted, authenticated, both, or neither.
• The only requirement is certificates issued by an authority that both sides recognise.

Two layers: record and handshake

TLS is organised in two layers. The Record protocol implements the secure channel itself, over TCP. Above it, the handshake layer contains three protocols: Handshake negotiates the cipher suite and exchanges certificates and keys; Change Cipher Spec switches to the newly agreed specification; and Alert reports errors. Applications such as HTTP sit beside them and send their data through the record layer. Session IDs can be cached, so that a later connection can resume a session without a full handshake.

The Record protocol takes outgoing data through five stages, and the receiver reverses them:

Cipher suites

A cipher suite is one choice of each of three things. One side lists the suites it supports and the other picks one. The sources differ on which side is which: CDK says the server offers and the client picks, whereas in the RFC the client offers and the server picks (which is what the handshake below shows).

The handshake

The handshake runs in eight steps. The message labels in the stepper carry the step numbers from this list.

1. ClientHello / ServerHello. The two sides agree the version, session ID, cipher suite and compression, and exchange random values.
2. The server sends its Certificate (an X.509 chain), an optional CertificateRequest, and then ServerHelloDone.
3. The client checks the server's certificate. It checks that the certificate chains to a root CA key pre-installed in the browser, that its dates are valid, and that the domain name matches the server being contacted.
4. The client sends its own Certificate, but only if one was requested.
5. The client sends a random pre-master secret, encrypted with the server's public key. Only the real server can decrypt it, which implicitly authenticates the server.
6. If the client has a certificate, it sends CertificateVerify, which is a signature made with its private key.
7. Both sides derive the write keys (one per direction) and the MAC secrets.
8. Each side sends ChangeCipherSpec + Finished. Finished is a MAC over the whole handshake, so it detects tampering. From here on, everything is encrypted and MACed.

What TLS gives, and what it does not

MITM defence. TLS defends against MITM in two ways: the root CA keys arrive by a separate channel (they are built into browsers), and the domain name is in the certificate, so Mallory's certificate (even a valid one for his own name) fails the name check.

Tutorial 9: the tutors' version official

The second half of Tutorial 9 introduced TLS informally, before an SSL code demo. Its framing makes a good opening sentence for an exam answer, which you can then follow with the full handshake above. The tutors described TLS as handling secure communication on the Internet for you, and noted that most traffic, such as HTTPS, uses it. A certificate, in their words, says: "here is my public key, and here is a signature from a trusted authority saying it really belongs to me." They told the handshake as a four-message story:

A lesson from WEP (brief)

802.11 WEP, the original Wi-Fi security, shows what happens when the design guidelines of 10.3 are broken. It used one key shared by all users (the opposite of limiting a secret's scope), did not authenticate base stations (so a fake one could masquerade), reused the keystream (fatal for a stream cipher), used 40-bit keys (breakable) and had a hard-wired cipher (no way to negotiate a better one, unlike TLS). It was replaced by WPA2, which uses AES.

Check yourselfSelf-test Q12: describe TLS's layers and handshake, and how it stops MITM.

TLS has a record layer (the secure channel over TCP: fragment, compress, MAC, encrypt, transmit) and a handshake layer (Handshake, Change Cipher Spec and Alert protocols). In the handshake, the Hellos negotiate the suite and exchange random values, the server sends its certificate, the client sends a pre-master secret under the server's public key, both sides derive keys, and each sends ChangeCipherSpec and Finished. MITM is stopped by the certificate chain to a pre-installed root, the name check, and the Finished MAC.

Check yourselfHow is the server authenticated in TLS, given that the certificate is public and anyone could resend it?

Sending the certificate proves nothing by itself. The client encrypts the pre-master secret with the public key in the certificate; only the holder of the matching private key can decrypt it and so derive the same keys. If the server then produces a correct Finished MAC, it must hold the private key: this is the "implicit" server authentication of step 5.

Check yourselfWhich of these does TLS not protect against?

1. An eavesdropper reading credit-card numbers.
2. A replayed record within a connection.
3. A customer later denying they placed an order.
4. A man in the middle presenting his own certificate.

C. TLS gives no non-repudiation: records are protected with MACs, and both ends know the MAC secrets. A is stopped by encryption, B by the sequence number in each record's MAC, D by the chain to a pre-installed root and the domain-name check.

Review: Defences, Pitfalls and Tutorials

This last section pulls the Part together. First the table that answers "how would you defend against X?", which is the shape of many 5-mark questions. Then the mistakes that most often cost marks, and finally the tutors' official answers to Tutorial 10, with the Week 11 Ed quiz.

Which mechanism defeats which attack exam

For each of the five methods of attack from 10.2, one family of mechanism is the main answer:

The full table adds the other threats from this Part.

Common pitfalls

Check yourselfA system encrypts every request with a strong session key. Name two attacks from the table it is still open to, and the fix for each.

Any two of: replay (fix: freshness, such as nonces, timestamps or sequence numbers); repudiation (fix: public-key signatures); traffic analysis (fix: information-flow control, padding); denial of service (fix: upstream filtering, QoS, replication); masquerading, if the session key was never tied to an authenticated identity (fix: authentication with certificates or challenge–response).

Tutorial 10 (Week 11): official answers official

These are the tutors' official answers from Ed, condensed; staff have confirmed tutorial content is examinable. Most restate material from earlier in this Part, but in the tutors' own words, which are the closest thing to what markers expect, so reuse them. Two parts go beyond the earlier sections: the field-by-field layout of an X.509 certificate (T10-7) and the steps for obtaining a certificate (T10-8). (The tutorial opened with a Q&A on Assignment 2, which is left out here.)

T10-1 · officialWhat are the different security threats and methods of attack in a distributed system?

The three broad classes of threat: leakage, the acquisition of information by unauthorised recipients; tampering, the unauthorised alteration of information; and vandalism, interference with the proper operation of a system. The five methods of attack:

• Eavesdropping is a form of leakage: obtaining private or secret information, or copies of messages, without authority.
• Masquerading is a form of impersonation: sending or receiving messages using the identity of another principal without their authority.
• Message tampering alters the content of messages in transit. The tutors equate it with the man-in-the-middle attack, which tampers with the secure-channel mechanism itself.
• Replaying means storing secure messages and sending them again at a later date.
• Denial of service is vandalism by flooding a channel or other resource, so that others are denied access to it.

T10-2 · officialList and briefly explain some worst-case assumptions when designing a secure system.

The tutors give four of the six guidelines of 10.3:

• Networks are insecure. Messages can be looked at, copied, modified and retransmitted; attackers can obtain information they should not have and pretend to be a legitimate party.
• The source code is known to the attacker, and knowing it helps the attacker discover vulnerabilities.
• Interfaces are exposed. Communication interfaces must be open so that clients can reach them, so attackers can send messages to any interface.
• The attacker has unlimited computing resources. Assume they have access to the largest and most powerful computers projected in the lifetime of the system.

T10-3 · officialDefine encryption and describe the two main types of keys used by encryption algorithms.

Encryption is the process of encoding a message in such a way as to hide its contents. With shared secret keys (symmetric), the sender and the recipient share knowledge of one key, and it must not be revealed to anyone else. With public/private key pairs (asymmetric), the sender encrypts with a public key, namely the recipient's, and the recipient decrypts with the matching private key; only the recipient can decrypt the message, because only they hold the private key. The price is speed: public-key algorithms typically need 100 to 1000 times as much processing power as secret-key ones.

T10-4 · officialHow can Alice authenticate and communicate secretly with Bob, assuming there is an authentication server that knows Alice's and Bob's secret keys?

This is Scenario 2 of 10.5, in five steps:

1. Alice sends the server her name and a ticket request, in the clear.
2. The server replies with {{Ticket}K_B, K_AB}K_A.
3. Alice decrypts the reply with K_A and stores the new shared key K_AB. She cannot read the ticket, because it is encrypted with Bob's key.
4. Alice sends Bob {Ticket}K_B, her name and her request.
5. Bob decrypts the ticket with K_B. It contains Alice's identity and the shared key K_AB, and from then on the two communicate using K_AB.

Keep the weakness in mind: nothing in the ticket is fresh, so the exchange can be replayed. Question 9 of the 2026 practice exam turns on exactly this point.

T10-5 · officialAssuming Bob has a public/private key pair, how can Alice and Bob establish a shared key to communicate secretly using a Key Distribution Service?

This is the hybrid approach of Scenario 3, which the tutors draw in six steps:

It works because only Bob holds K_privB, so only Bob can recover K_AB. The slow public-key operation is used just once, to carry the key, and the fast symmetric key K_AB then carries the data.

T10-6 · officialExplain how digital signatures work.

The tutors tell it as six steps between Bob, the signer, and Alice, the verifier. Their word "compress" means computing a secure digest (hash) of the document.

1. Bob compresses the message into a short digest.
2. Bob encrypts the digest with his private key. The result is the digital signature.
3. Bob appends the signature to the document. All the data that went into the digest has now been signed.
4. Bob sends the document to Alice.
5. Alice decrypts the signature with Bob's public key, which turns it back into a message digest.
6. Alice compresses the document herself. If her digest is the same as the decrypted one, she knows that the signed data has not been changed and that Bob signed it, because only Bob has his private key.

Their diagram is the same loop as the signing figure in 10.8.

T10-7 · officialWhat is a digital certificate and why do we need it?

A digital certificate is a digital form of identification, like a passport: it provides information about the identity of an entity. It is issued by a Certification Authority (CA), such as Verisign or Entrust, and the CA guarantees the validity of the information in it. We need certificates because distributing public keys is a big problem: they have to be distributed in a way that is both scalable and truthful. Without a trusted signature binding a key to its owner, anyone could publish a key under someone else's name, which is the man-in-the-middle problem.

Public Key Infrastructure (PKI) is the set of protocols, standards and services that lets users authenticate each other using certificates issued by CAs. A certificate is only useful if it is structured in a standard way, so that its information can be retrieved and understood whoever issued it. X.509, its PKI profile (PKIX) and the Public Key Cryptography Standards (PKCS) are the building blocks that define these formats and their use. The tutors lay out an X.509 certificate field by field:

Next comes a public-key certificate in CDK's five-field format (compare Alice's bank-account certificate in 10.6), with the tutors' three questions about it:

• What is the certificate saying? That Sara certifies that Bob's public key is K_Bpub.
• Why can't Sara deny that she attested to this? Because if the signature decrypts correctly with K_Spub, only someone who held K_Spriv could have made it. This is non-repudiation.
• What must anyone checking the certificate know? K_Spub. They must also know it authentically, which is the recursion that a certificate chain ends at a trusted root.

Their last picture shows how a certificate is made: the CA verifies the subject's identity, then signs the subject's identity information and public key with its own private key. The certificate is that information, a validity period and the CA's signature.

T10-8 · officialWhat is the process to obtain a digital certificate?

The tutors give seven steps between User-A and the CA:

1. Generate a key pair. User-A generates a public/private key pair, or is assigned one by an authority in her organisation.
2. Request the CA's certificate. User-A asks the CA server for its certificate.
3. The CA certificate is issued. The CA responds with its certificate, which contains its public key and its digital signature, made with its private key.
4. Gather information. User-A gathers everything the CA needs to be certain she is who she claims to be, such as her email address or fingerprints.
5. Send a certificate request. User-A sends the CA a request made up of her public key and the additional information.
6. The CA verifies User-A. The CA checks her identity and generates a certificate binding her identity to her public key. The CA's signature is what makes the certificate verifiable.
7. The CA issues the certificate to User-A.

Caveat on step 5

The slide for step 5 says the request is "signed by CA's Public Key", but a signature is always made with a private key. Read it as one of two standard practices: either the request is encrypted with the CA's public key, so that only the CA can read it, or, as in a standard certificate signing request (PKCS #10), it is signed with User-A's own private key, which proves that she holds the key she wants certified.

Code demo. The tutorial ended with a demo of a client and server encrypting their messages with AES under a shared secret key, the symmetric case of T10-3. The demo code was a separate Ed workspace and is not reproduced here.

Ed practice quiz (Week 11)

Ed does not show the answers to its practice quizzes, so these answers are worked out from the course material; they are not official.

Ed quiz Q1An attacker steals Alice's login credentials and submits a funds-transfer request that the bank's server believes comes from Alice. Which method of attack?

Masquerading: sending messages under another principal's identity without authority. The request is new rather than altered or copied, so it is neither tampering nor replay.

Ed quiz Q2An attacker captures an encrypted "transfer $500" message and, without decrypting or changing it, resends it a day later, so the server makes a second transfer. Which attack?

Replaying. The attacker never needs the key, which is why encryption alone does not stop replay; freshness (nonces, timestamps or sequence numbers) does.

Ed quiz Q3Priya and Sam use one key both to encrypt and to decrypt, so if it leaks, every past and future message is readable. What kind of encryption is this, and what is its core requirement?

Symmetric encryption, whose core requirement is that the shared secret key is never revealed to anyone else (T10-3). A new key per message is not the defining requirement, and the 100–1000× cost belongs to asymmetric algorithms.

Ed quiz Q4The authentication server gives Alice a ticket she cannot read and a separately encrypted new key that only she can open, and she forwards the ticket to Bob. What is true of the ticket?

The ticket is encrypted with Bob's key and contains the new shared key; Alice forwards it, and Bob decrypts it with his own key to recover the shared key (T10-4). Alice never learns K_B.

Ed quiz Q5Sam wants Priya to be sure a document came from him and was not altered, but does not need it kept secret. What should he do?

Sam encrypts a digest of the document with his own private key; Priya decrypts it with Sam's public key and compares it with a digest she computes herself (T10-6). Encrypting with Priya's public key gives secrecy, not proof of origin, and a plaintext digest can be recomputed by anyone who alters the document.