Question 4 of 6: Security

Question 4: 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) The two main classes of encryption algorithms. 1. Symmetric (secret-key) algorithms (e.g. DES, IDEA, AES) use the same secret key for both encryption and decryption: the two communicating parties must each hold a copy of the same key, kept secret from everyone else, and the algorithm's security rests entirely on that key remaining secret. Symmetric algorithms are computationally cheap (they operate on plaintext via fast bit-level substitutions/permutations/XOR rounds) and are used for the bulk encryption of message content, but they raise a key-distribution problem: the two parties need some already-secure channel to agree on the shared key in the first place before they can use it to secure their main channel. 2. Asymmetric (public-key) algorithms (e.g. RSA) use a mathematically related pair of keys per party — a public key that can be freely published and a private key kept secret — where data encrypted with one key of the pair can only be decrypted with the other. This solves the key-distribution problem (a sender needs only the recipient's already-public key, with no prior shared secret required) and additionally enables digital signatures (signing with the private key, verifiable by anyone with the public key), but at a much higher computational cost per byte than symmetric algorithms, which is why real systems typically use a hybrid scheme: asymmetric encryption to securely exchange a short, random symmetric session key, then fast symmetric encryption for the actual message content.

(b) Defences against man-in-the-middle attacks on public-key exchange. The vulnerability arises because a public key received over an untrusted channel could have been substituted in transit by an attacker who then relays (and can read/modify) all subsequent traffic while impersonating each party to the other; the defences all work by giving each party an independent, attacker-resistant way to confirm a received key genuinely belongs to the claimed owner. 1. Certificate authorities (CAs) and public-key certificates. A trusted third party (the CA) verifies an entity's identity out-of-band and then digitally signs a certificate binding that entity's name to its public key; a recipient who already trusts the CA's own (widely pre-distributed) public key can verify the signature on any certificate it receives and thereby trust the bound key without ever having contacted the owner directly — this is the model used by TLS/HTTPS. 2. Web of trust. Instead of one centralized CA, other users who have already verified a key sign it with their own private key; a recipient trusts a key that carries enough signatures from people the recipient already trusts (used by PGP), decentralizing the trust decision but still requiring some initial chain of verified signatures to exist. 3. Out-of-band fingerprint verification. The two parties compare a short cryptographic hash ("fingerprint") of each other's public key over a separate, independently-trusted channel (in person, by phone, by reading it aloud) that the attacker is assumed not to control; a substituted key produces a different fingerprint, exposing the attack immediately. 4. Key-continuity / trust-on-first-use (TOFU). A client remembers the key it first saw for a given server/peer and warns (or refuses to connect) if a different key is presented on a later connection (used by SSH); this does not prevent an attack on the very first connection, but it prevents an attacker from silently substituting keys on every subsequent session once a trusted baseline has been recorded. Common to every defence is the same underlying requirement: some anchor of trust established outside the channel being secured, since a channel that is itself compromised cannot be used to verify its own integrity.

(c) 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); an attacker computer of 2000 MIPS.

Find. The estimated wall-clock time to brute-force a 56-bit DES key and a 128-bit IDEA key at 2000 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}=\dfrac{3.6029\times10^{17}}{2\times10^{9}}\approx1.8014\times10^{8}\ \text{s}\approx5.71\ \text{years}}$$ IDEA: $$\boxed{t_{IDEA}=\dfrac{1.7014\times10^{39}}{2\times10^{9}}\approx8.507\times10^{29}\ \text{s}\approx2.696\times10^{22}\ \text{years}}$$

Roughly 5.7 years is well within reach of a well-resourced attacker, an organized group, or a parallel/distributed cracking effort (splitting the key space across many machines divides this time roughly linearly with the number of machines) — 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 within any practical timeframe: doubling the key length squares the size of the search space rather than merely doubling it, so IDEA's search space is $2^{72}$ times larger than DES's despite being only a little over twice the key length.