Question 5 of 7: Security

Question 5: Security (20 marks)

Question text not reproduced: the examination questions are © Engineers and Geoscientists BC. Open the official past paper (linked at the top of this page) to read the question, then follow the worked solution below.

(a) PGP key negotiation for POP-based email. POP itself only retrieves mail from a mailbox server and provides no privacy or authenticity guarantees for message content; those guarantees come from applying PGP to the message before it is submitted and after it is retrieved, which requires a preliminary key-negotiation phase between the two users: (1) Key-pair generation. Each user generates their own public/private key pair, keeping the private key secret and protected by a local passphrase. (2) Public-key distribution. Each user makes their public key available to the other, e.g. via a public key server or attached to an ordinary email. (3) Authenticity verification (the critical step). Because a key obtained over an untrusted channel could have been substituted by an attacker (a man-in-the-middle), each user must verify the other's public key genuinely belongs to them before trusting it — PGP's usual mechanism is a web of trust: other users who have already verified a key sign it with their own private key, and a recipient trusts a key that carries enough such signatures from people they already trust, or the two users verify each other's key fingerprint directly out-of-band (e.g. by phone or in person). Only once this is done can subsequent messages be trusted as genuinely from the claimed sender.

Once both keys are generated, distributed and verified, PGP's hybrid scheme protects each message: privacy is achieved by generating a random one-time session key, encrypting the message body with it under fast symmetric encryption, then encrypting that short session key itself with the recipient's public key and attaching it; authenticity is achieved by hashing the message and signing the hash with the sender's private key. Scope for making the key negotiation invisible to users. Steps (1) and (2) can be made fully automatic and invisible — key generation on first use, and automated lookup/publication against a key-server directory keyed by email address, exactly as many modern mail clients already do. Step (3), however, resists full automation in principle: verifying that a key genuinely belongs to the claimed owner is precisely the step that defeats a man-in-the-middle attacker, and an attacker who can intercept and substitute keys can equally intercept and substitute any *automated* verification channel the users rely on. In practice, systems reduce (rather than eliminate) user visibility here by trusting a small number of already-verified introducers (the web of trust) or a centrally-run certificate authority, so an individual pair of users need not manually verify each other directly — but some anchor of trust, established outside the channel being secured, can never be fully automated away without reintroducing exactly the vulnerability the verification step exists to close.

(b) Estimating DES and IDEA brute-force cracking time.

Given. A 56-bit DES key and a 128-bit IDEA key; a brute-force trial costs 10 instructions per key value (taken to already include the cost of encrypting the 8-byte test plaintext, since no separate per-block instruction count is given); attacker computers of 2000 MIPS and (after extrapolation) 200,000 MIPS.

Find. The estimated wall-clock time to brute-force a 56-bit DES key and a 128-bit IDEA key, at 2000 MIPS and at 200,000 MIPS.

Approach. Take the expected number of trials before finding the key as half the key space, $2^{n-1}$ for an $n$-bit key (the attacker finds the key on average halfway through an exhaustive search); multiply by 10 instructions per trial to get total instructions, then divide by the computer's instruction rate.

1. Keys to try. DES: $\dfrac{2^{56}}{2}=2^{55}\approx3.6029\times10^{16}$ keys. IDEA: $\dfrac{2^{128}}{2}=2^{127}\approx1.7014\times10^{38}$ keys.
2. Total instructions. DES: $2^{55}\times10\approx3.6029\times10^{17}$ instructions. IDEA: $2^{127}\times10\approx1.7014\times10^{39}$ instructions.
3. Cracking time at 2000 MIPS ($2000\times10^{6}=2\times10^{9}$ instructions/s). DES: $$\boxed{t_{DES,2000}=\dfrac{3.6029\times10^{17}}{2\times10^{9}}\approx1.8014\times10^{8}\ \text{s}\approx5.71\ \text{years}}$$ IDEA: $$\boxed{t_{IDEA,2000}=\dfrac{1.7014\times10^{39}}{2\times10^{9}}\approx8.507\times10^{29}\ \text{s}\approx2.696\times10^{22}\ \text{years}}$$
4. Extrapolate to 200,000 MIPS (a factor of 100 faster, so every time above simply divides by 100). $$\boxed{t_{DES,200000}\approx1.8014\times10^{6}\ \text{s}\approx20.85\ \text{days}}$$ $$\boxed{t_{IDEA,200000}\approx8.507\times10^{27}\ \text{s}\approx2.696\times10^{20}\ \text{years}}$$

The hundred-fold speed-up moves 56-bit DES from a multi-year effort to a matter of weeks — well within reach of a well-resourced attacker or consortium, which is exactly the historical argument for retiring DES in favour of longer keys (Triple-DES, then AES). By contrast, no realistic increase in computing power makes 128-bit IDEA brute-forceable: doubling the key length squares the size of the search space rather than merely doubling it, so a further hundred-fold speed-up beyond 200,000 MIPS would still leave a cracking time many orders of magnitude longer than the age of the universe.