Security: 25-Comp-B10 Distributed Systems, May 2015, Q5

Question 5: Security

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 setup steps for privacy and authenticity. Before Alice and Bob can exchange email with both confidentiality and authenticity guarantees, the following must be in place: (1) Key-pair generation. Each user generates their own public/private key pair (traditionally RSA or a similar asymmetric scheme) and keeps the private key secret, protected locally by a passphrase. (2) Public-key distribution. Each user makes their public key available to the other — via a public key server, attaching it to an email, or direct exchange. (3) Authenticity verification of the received key (the critical, often-skipped step). Because a key obtained over an untrusted channel is vulnerable to a man-in-the-middle substitution, each user must verify the other's public key genuinely belongs to them before trusting it — PGP's usual mechanism is the web of trust: other users who have already verified a key (e.g. by comparing its fingerprint in person) sign it with their own private key, and Bob trusts Alice's key if it carries enough such signatures from people Bob already trusts, or Alice and Bob verify each other's key fingerprint directly out-of-band. Only once this is done can messages that follow be trusted to actually be exchanged with the intended party rather than an imposter.

With both keys generated, distributed and verified, an actual message is protected as follows, achieving both properties the question asks for: privacy is provided by the sender generating a random one-time session key, encrypting the message body with that session key using fast symmetric encryption, then encrypting the (short) session key itself with the recipient's public key and attaching it — only the recipient's private key can recover the session key and hence the message; authenticity is provided by the sender computing a hash (digest) of the message and signing that digest with their own private key before sending it, so the recipient can verify (using the sender's already-trusted public key) that the message truly came from the claimed sender and was not altered in transit. PGP performs both operations together on outgoing mail (sign-then-encrypt), so a single exchanged message carries both guarantees simultaneously.

(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 15 instructions per key value (this figure is taken to already include the work of encrypting the 8-byte test plaintext with the candidate key, as no separate per-block instruction count is given); attacker computers of 3000 MIPS and (after extrapolation) 300,000 MIPS.

Given data
Quantity	Value
DES key length	56 bits
IDEA key length	128 bits
Instructions per key trial	15
Attacker computer speed (case 1)	3000 MIPS
Attacker computer speed (case 2)	300,000 MIPS

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

Approach. Take the expected number of keys a brute-force search must try before finding the right one as half the key space, $2^{n-1}$ for an $n$-bit key (the attacker is expected to find the key on average halfway through an exhaustive, non-repeating search); multiply by 15 instructions per trial to get total instructions, then divide by the computer's instruction rate.

Check — average-case assumption. "Estimate the time required to crack" is read here as the expected (average-case) time, i.e. $2^{n-1}$ trials, which is the standard convention for brute-force key-search estimates; a worst-case estimate (trying the full $2^{n}$ key space) would simply double every figure below.

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

Final Results — Q5(b)
Key / attacker	3000 MIPS	300,000 MIPS
56-bit DES	≈ 5.71 years	≈ 20.85 days
128-bit IDEA	≈ 2.70×10²² years	≈ 2.70×10²⁰ 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: even a further hundred-fold speed-up beyond 300,000 MIPS would still leave a cracking time many orders of magnitude longer than the age of the universe, because doubling the key length squares the size of the search space rather than merely doubling it.

Topic: Man-in-the-middle defences for public-key exchange and PGP's hybrid encryption model; estimating symmetric-key brute-force cracking time.

Key relations: PGP message: $E_{K_{session}}(\text{message})$ for privacy, $K_{session}$ itself sent as $E_{Bob_{pub}}(K_{session})$; authenticity via $Sign_{Alice_{priv}}(\text{hash}(\text{message}))$, verified with $Alice_{pub}$. Brute-force time $\approx \dfrac{2^{n-1}\times(\text{instructions per trial})}{\text{instructions/second}}$; each extra key bit doubles the search space.

Why this works: PGP's web-of-trust converts "can I trust this key I just received over the network" into "can I trust this key given an anchor (a signature chain or an out-of-band fingerprint check) the attacker cannot forge." Brute-force cost grows exponentially with key length while attacker speed only grows linearly (or, generously, geometrically over years) with better hardware, which is why adding a handful of key bits vastly outpaces any realistic hardware speed-up — exactly what the DES-vs-IDEA comparison demonstrates numerically.

Common pitfall: Believing PGP's encryption alone is sufficient without the key-verification step; for the crack-time estimate, using the full key space $2^n$ instead of the expected $2^{n-1}$ (overstates time by 2×, immaterial to the qualitative conclusion but not to the exact figure), or forgetting that a 100× faster machine divides time by exactly 100 regardless of key length, so it never closes the gap between a crackable 56-bit key and an uncrackable 128-bit one.

Source: Coulouris, Dollimore, Kindberg & Blair, Distributed Systems: Concepts and Design, ch. 11 (Security, §11.4–11.5 cryptographic algorithms, certificates and case studies incl. PGP; symmetric key length and brute-force resistance).

Question 5 of 7: Security

Question 5: Security