Cryptography & Network Security exam preparation.
Practice questions for every unit in the style of the R23 end exam, a model answer for each, and a one-page revision summary. Built on the official syllabus units.
- Practice questions in the exam's style
- Drafted with AI and checked by a second AI pass. Doubtful points were verified against public sources. Report a mistake
- Units
- 5
- Questions
- 60
- 2-mark
- 30
- 10-mark
- 30
- Done
- Checked on
Exam guide
Paper pattern
Semester-end theory paper, 70 marks, from the JNTUK B.Tech R23 Regulations, end-examination pattern for theory subjects.
- Question 1 · 20 marksTen compulsory short-answer questions of 2 marks each (two from every unit).
- Questions 2 to 6 · 50 marksFive either/or questions of 10 marks each, one per unit. You answer one of the two in each.
- The semester-end examination carries 70 marks; internal assessment carries 30.
- Mid-semester examinations are separate: a 20-minute objective paper (10 marks) and a 90-minute subjective paper with three either/or questions of 10 marks (condensed to 15 marks).
- The regulations text does not state the length of the end examination. Use the duration printed on your hall ticket or question paper.
How to split your time
This plan assumes a 3-hour paper. If yours is different, keep the same proportions. Marks per minute stay roughly even across Question 1 and the 10-mark answers.
- 10 minRead the paper and choose one option in each either/or question
- 30 minQuestion 1: ten short answers (about 3 minutes each)
- 130 minQuestions 2 to 6: one 10-mark answer per unit (about 26 minutes each)
- 10 minFinal check of numbering, calculations and diagrams
Study tips for Cryptography & Network Security
- Practise the number theory by hand with a calculator: the extended Euclidean algorithm as a table, modular inverses, linear congruences and the Chinese remainder theorem, checking each answer by multiplying back.
- Work one small RSA example end to end, choosing primes, computing n, phi(n), e and d, then encrypting and decrypting a number, and repeat the same for ElGamal and an elliptic-curve point addition.
- Draw the round structures of DES and AES and the message flows of Kerberos, SSL/TLS and IPsec from memory, numbering each message in order.
- Keep a table of the security services (confidentiality, integrity, authentication, non-repudiation, access control) against the mechanisms that provide each one, and add every algorithm you study to it.
Basic Principles and the Mathematics of Cryptography
Syllabus: Security goals; Cryptographic attacks; Security services and mechanisms; Integer arithmetic; Modular arithmetic; Matrices; Linear congruence
One-page revision summary
- The three security goals are confidentiality (keeping information secret), integrity (allowing only authorised changes) and availability (keeping information and services ready for authorised users).
- Snooping and traffic analysis threaten confidentiality; modification, masquerading, replaying and repudiation threaten integrity; denial of service threatens availability.
- Passive attacks only observe data and are mainly prevented by encipherment, while active attacks change data or harm the system and are mainly detected and recovered from.
- Cryptanalysis attacks are classed by what the attacker has: ciphertext only, known plaintext, chosen plaintext or chosen ciphertext; a brute-force attack simply tries every possible key.
- ITU-T X.800 defines five security services: data confidentiality, data integrity, authentication, non-repudiation and access control.
- Its eight specific mechanisms are encipherment, data integrity, digital signature, authentication exchange, traffic padding, routing control, notarization and access control.
- Non-repudiation relies on digital signatures, data integrity and notarization, and traffic padding protects against traffic analysis.
- In a = q × n + r the remainder is kept in 0 ≤ r < n, so when plain division of a negative a leaves a negative remainder, the quotient is lowered by 1 and n is added to the remainder.
- The Euclidean algorithm repeats gcd(a, b) = gcd(b, a mod b) until the second number is 0; the extended version also gives s and t with s × a + t × b = gcd(a, b).
- Two integers are relatively prime when their gcd is 1.
- Numbers may be reduced modulo n before adding, subtracting or multiplying without changing the final residue.
- In Zn every element has an additive inverse, but a has a multiplicative inverse only when gcd(a, n) = 1, and those elements form Zn*.
- Matrix multiplication needs the number of columns of the first matrix to equal the number of rows of the second, and it is not commutative.
- A residue matrix is invertible modulo n only when gcd(det A, n) = 1, and then A⁻¹ = det(A)⁻¹ × adj(A) mod n.
- ax ≡ b (mod n) has no solution when d = gcd(a, n) does not divide b, and exactly d solutions modulo n when it does.
- A set of linear congruences written as K × X ≡ B (mod n) is solved as X ≡ K⁻¹ × B (mod n) when K is invertible modulo n.
Learn these by heart
- Security goals (CIA): confidentiality, integrity, availability.
- Division relation: a = q × n + r with 0 ≤ r < n, and r = a mod n.
- gcd(a, 0) = a and gcd(a, b) = gcd(b, a mod b).
- Extended Euclid: s × a + t × b = gcd(a, b); if gcd(n, b) = 1, then b⁻¹ mod n = t mod n.
- a ≡ b (mod n) exactly when n divides a − b.
- (a + b), (a − b) and (a × b) mod n can each be found from a mod n and b mod n, then reduced mod n again.
- ax ≡ b (mod n): with d = gcd(a, n), solvable only if d divides b; then x = x0 + k(n/d) for k = 0, 1, ..., d − 1.
- 2 × 2 inverse mod n: for rows (a, b) and (c, d), A⁻¹ = (ad − bc)⁻¹ × [rows (d, −b) and (−c, a)] mod n.
2-mark questions
1 Distinguish between a security service and a security mechanism, giving one example of each. 2 marks
A security service is a protection that a system offers its users, such as confidentiality, integrity, authentication, non-repudiation or access control. A security mechanism is the technique that provides a service. For example, the data confidentiality service is provided by the encipherment mechanism, and non-repudiation is provided by a digital signature.
2 Name the four types of cryptanalysis attack based on what the attacker knows. 2 marks
In a ciphertext-only attack the attacker has only intercepted ciphertext. In a known-plaintext attack the attacker also holds some plaintext and ciphertext pairs. In a chosen-plaintext attack the attacker can have plaintexts of their choice encrypted, and in a chosen-ciphertext attack can have chosen ciphertexts decrypted. The aim in each is the key or the plaintext.
3 State the division relation for integers and find q and r when a = −38 is divided by n = 7. 2 marks
For integers a and n > 0 there are unique q and r with a = q × n + r and 0 ≤ r < n. Plain division of −38 by 7 gives q = −5 and r = −3; since r cannot be negative, subtract 1 from q and add 7 to r, giving q = −6 and r = 4. Check: (−6) × 7 + 4 = −38.
4 Define Zn* and list the elements of Z10* with their multiplicative inverses. 2 marks
Zn* is the set of elements of Zn = {0, 1, ..., n − 1} that are relatively prime to n; each of them has a multiplicative inverse modulo n. Z10* = {1, 3, 7, 9}, with 1⁻¹ = 1, 3⁻¹ = 7, 7⁻¹ = 3 and 9⁻¹ = 9, since 3 × 7 = 21 ≡ 1 and 9 × 9 = 81 ≡ 1 (mod 10).
5 When does a square matrix have a multiplicative inverse modulo n? Check whether the matrix A with rows (4, 2) and (1, 3) is invertible in Z26. 2 marks
A residue matrix, whose elements all lie in Zn, has an inverse modulo n only when its determinant has a multiplicative inverse in Zn, that is, when gcd(det A, n) = 1. Here det A = 4 × 3 − 2 × 1 = 10 and gcd(10, 26) = 2, so A has no inverse in Z26.
6 How many solutions does the linear congruence 21x ≡ 9 (mod 30) have? Find them. 2 marks
Here d = gcd(21, 30) = 3, and 3 divides 9, so there are exactly 3 solutions. Dividing a, b and n by 3 gives 7x ≡ 3 (mod 10). The inverse of 7 modulo 10 is 3, so x0 = 3 × 3 = 9. Adding n/d = 10 each time, the solutions are x = 9, 19 and 29 (mod 30).
10-mark questions
1 Explain the three security goals and the attacks that threaten each of them. Classify these attacks as passive or active. 10 marks
Information security protects data while it is stored and while it travels over a network. It has three goals, confidentiality, integrity and availability, and each goal has its own attacks.
1. Confidentiality means that information is kept secret from anyone who is not authorised to see it. It is threatened by:
- Snooping: the attacker reads or intercepts data meant for someone else, such as a file sent over the Internet. Encipherment makes the intercepted data useless to the attacker.
- Traffic analysis: even when the data is enciphered, the attacker studies the traffic itself, such as the addresses of the sender and receiver and the number and size of messages, to guess what is going on.
2. Integrity means that information is changed only by authorised parties and only in authorised ways. It is threatened by:
- Modification: the attacker intercepts a message and alters it, for example the amount or the account number in a payment message.
- Masquerading (spoofing): the attacker pretends to be someone else, for example by logging in with a stolen password as a genuine user.
- Replaying: the attacker captures a valid message and sends it again later, for example to repeat a payment or a login.
- Repudiation: the sender later denies having sent a message, or the receiver denies having received it. Unlike the others, this attack comes from one of the two communicating parties.
3. Availability means that information and services are ready for authorised users when they need them. It is threatened by:
- Denial of service (DoS): the attacker slows down or stops a service, for example by flooding a server with bogus requests, or by intercepting and dropping the messages between a client and the server.
4. Passive and active attacks:
- In a passive attack the attacker only obtains information and nothing is changed. Snooping and traffic analysis are passive. They are hard to detect, so the defence is to prevent them, mainly by encipherment.
- In an active attack the attacker changes data or harms the system. Modification, masquerading, replaying, repudiation and denial of service are active. They are easier to detect than to prevent, so systems detect them and recover.
In conclusion, the three goals state what security must protect, and the attacks against each goal show which security services and mechanisms are needed to defend it.
2 Explain the security services defined in ITU-T Recommendation X.800 and the security mechanisms that provide them. Show the relation between the services and the mechanisms. 10 marks
ITU-T Recommendation X.800, the security architecture for OSI, defines security services, which are the protections a system offers, and security mechanisms, which are the techniques that implement them. One service may need several mechanisms, and one mechanism may serve several services.
Security services: 1. Data confidentiality keeps data from being disclosed to an unauthorised party. It can protect a whole message, selected fields or, as traffic-flow confidentiality, the pattern of the traffic itself, so it defends against snooping and traffic analysis. 2. Data integrity ensures that data arrives exactly as sent, with no modification, insertion, deletion or replay. 3. Authentication confirms identity. Peer entity authentication checks the party at the other end of a connection, and data origin authentication checks the source of received data. 4. Non-repudiation protects against a sender who denies sending a message (proof of origin) and a receiver who denies receiving it (proof of delivery). 5. Access control prevents unauthorised use of resources and controls who may read, write or run them.
Security mechanisms: 1. Encipherment transforms data by encryption so that it cannot be read without the key. 2. Data integrity: the sender attaches a short check value computed from the data, and the receiver recomputes it from what arrived and compares the two. 3. Digital signature: the sender signs the data with a private key, and anyone can verify the signature with the matching public key. 4. Authentication exchange: two entities exchange messages to prove their identities, for example by showing knowledge of a shared secret. 5. Traffic padding: bogus data is inserted into the traffic to defeat traffic analysis. 6. Routing control: the route between sender and receiver is selected and changed so that an eavesdropper cannot follow the data. 7. Notarization: a trusted third party records the communication so that neither side can later deny it. 8. Access control: passwords, PINs and permission lists prove that a user may use a resource.
Relation between services and mechanisms:
- Data confidentiality: encipherment and routing control, with traffic padding for traffic-flow confidentiality.
- Data integrity: encipherment, digital signature and the data integrity mechanism.
- Authentication: encipherment, digital signature and authentication exchange.
- Non-repudiation: digital signature, the data integrity mechanism and notarization.
- Access control: the access control mechanism.
In conclusion, services state what must be protected and mechanisms state how. A real system combines several mechanisms, such as encryption together with digital signatures, to provide all five services.
3 Explain the Euclidean and extended Euclidean algorithms. Use them to find gcd(391, 299) and integers s and t such that s × 391 + t × 299 = gcd(391, 299). 10 marks
Integer arithmetic works on the set Z = {..., −2, −1, 0, 1, 2, ...}. For any integer a and positive integer n there are unique integers q and r with a = q × n + r and 0 ≤ r < n. When r = 0, n divides a, written n | a. If a | b and a | c, then a | (m × b + k × c) for any integers m and k. The greatest common divisor gcd(a, b) is the largest positive integer that divides both a and b; when it is 1, a and b are relatively prime.
1. Euclidean algorithm. It rests on two facts: gcd(a, 0) = a, and gcd(a, b) = gcd(b, r) where r = a mod b. Each step replaces (a, b) by (b, a mod b) until the second number becomes 0; the first number is then the gcd. For a = 391 and b = 299:
- 391 = 1 × 299 + 92
- 299 = 3 × 92 + 23
- 92 = 4 × 23 + 0
So gcd(391, 299) = 23. As a check, 391 = 17 × 23 and 299 = 13 × 23.
2. Extended Euclidean algorithm. Along with d = gcd(a, b), it finds integers s and t with s × a + t × b = d. Every remainder r is kept in the form r = s × a + t × b:
- The first two rows are 391 = 1 × 391 + 0 × 299 and 299 = 0 × 391 + 1 × 299.
- q is the quotient of the two previous r values.
- Each new row is the row two above minus q times the row above, applied to r, s and t alike.
- The algorithm stops when r = 0, and the row above that one gives d, s and t.
q r s t
- 391 1 0
- 299 0 1
1 92 1 -1
3 23 -3 4
4 0 13 -173. Result: d = 23, s = −3 and t = 4.
4. Check: (−3) × 391 + 4 × 299 = −1173 + 1196 = 23. The last row also checks the working, since 13 × 391 − 17 × 299 = 5083 − 5083 = 0.
In conclusion, the Euclidean algorithm needs only repeated division, so it is fast even for very large numbers. Its extended form is a basic tool of cryptography: when gcd(n, b) = 1, running it on n and b gives s × n + t × b = 1, so t mod n is the multiplicative inverse of b modulo n.
4 Explain the modulo operator, congruence and the set Zn, and state the properties of modular arithmetic. Find the additive and multiplicative inverses of 23 in Z100. 10 marks
Modular arithmetic keeps every result inside a fixed range of values, which is why ciphers are built on it.
1. Modulo operator. For an integer a and a positive modulus n, a mod n is the remainder r in a = q × n + r with 0 ≤ r < n. For example, 27 mod 5 = 2, and −18 mod 7 = 3 because −18 = (−3) × 7 + 3.
2. The set Zn. The results of the mod n operation form the set of least residues Zn = {0, 1, 2, ..., n − 1}; for example Z6 = {0, 1, 2, 3, 4, 5}.
3. Congruence. Two integers a and b are congruent modulo n, written a ≡ b (mod n), when a mod n = b mod n, that is, when n divides a − b. For example 2 ≡ 12 ≡ 22 (mod 10). All the integers congruent to a form its residue class [a]; modulo 10, [2] = {..., −8, 2, 12, 22, ...}.
4. Properties. For any integers a and b:
- (a + b) mod n = [(a mod n) + (b mod n)] mod n
- (a − b) mod n = [(a mod n) − (b mod n)] mod n
- (a × b) mod n = [(a mod n) × (b mod n)] mod n
With n = 7: 473 mod 7 = 4 and 891 mod 7 = 2, so (473 + 891) mod 7 = 6 and (473 × 891) mod 7 = (4 × 2) mod 7 = 1. Direct division agrees: 1364 mod 7 = 6 and 421443 mod 7 = 1.
5. Inverses. In Zn, b is the additive inverse of a when a + b ≡ 0 (mod n); every element has one, n − a (0 is its own). b is the multiplicative inverse of a when a × b ≡ 1 (mod n); it exists only when gcd(a, n) = 1 and is found by the extended Euclidean algorithm.
6. Inverses of 23 in Z100.
- Additive: 100 − 23 = 77, since 23 + 77 = 100 ≡ 0 (mod 100).
- Multiplicative: gcd(100, 23) = 1, so the inverse exists. Start with r1 = 100, r2 = 23, t1 = 0, t2 = 1; at each step q = r1 div r2, r = r1 − q × r2 and t = t1 − q × t2, and then (r1, r2) and (t1, t2) shift along.
q r1 r2 r t1 t2 t
4 100 23 8 0 1 -4
2 23 8 7 1 -4 9
1 8 7 1 -4 9 -13
7 7 1 0 9 -13 100
1 0 -13 100The final r1 = 1 confirms the gcd, and t1 = −13. So 23⁻¹ = −13 mod 100 = 87. Check: 23 × 87 = 2001 = 20 × 100 + 1 ≡ 1 (mod 100).
In conclusion, Zn with these properties and inverses is the arithmetic used by the additive, multiplicative and affine ciphers.
5 Explain how a linear congruence ax ≡ b (mod n) is solved. Solve 35x ≡ 10 (mod 55) and 4x + 5 ≡ 3 (mod 9), and show that 6x ≡ 7 (mod 15) has no solution. 10 marks
A linear congruence in one variable has the form ax ≡ b (mod n), where a, b and n are known and x is unknown. We cannot divide by a as in ordinary algebra; instead we multiply by a multiplicative inverse, which exists only under a gcd condition.
1. Method.
- Find d = gcd(a, n).
- If d does not divide b, there is no solution.
- If d divides b, there are exactly d solutions modulo n. Divide a, b and n by d to get a'x ≡ b' (mod n'), where n' = n/d and gcd(a', n') = 1.
- Multiply both sides by the inverse of a' modulo n': x0 = b' × a'⁻¹ mod n'.
- The d solutions are x = x0 + k(n/d) for k = 0, 1, ..., d − 1.
2. Solve 35x ≡ 10 (mod 55).
- d = gcd(35, 55) = 5, and 5 divides 10, so there are 5 solutions.
- Dividing by 5 gives 7x ≡ 2 (mod 11).
- The inverse of 7 modulo 11 is 8, because 7 × 8 = 56 = 5 × 11 + 1.
- x0 = (2 × 8) mod 11 = 16 mod 11 = 5.
- Adding n/d = 11 each time, the solutions are x = 5, 16, 27, 38 and 49 (mod 55).
- Check one of them: 35 × 16 = 560 = 10 × 55 + 10, so 560 ≡ 10 (mod 55).
3. Solve 4x + 5 ≡ 3 (mod 9).
- Move the constant: 4x ≡ 3 − 5 ≡ −2 ≡ 7 (mod 9).
- d = gcd(4, 9) = 1, so there is exactly one solution.
- The inverse of 4 modulo 9 is 7, because 4 × 7 = 28 = 3 × 9 + 1.
- x = (7 × 7) mod 9 = 49 mod 9 = 4.
- Check: 4 × 4 + 5 = 21 = 2 × 9 + 3, so 21 ≡ 3 (mod 9).
4. Show that 6x ≡ 7 (mod 15) has no solution.
- d = gcd(6, 15) = 3, and 3 does not divide 7, so there is no solution.
- Directly: 6x mod 15 can only be 0, 3, 6, 9 or 12, all multiples of 3, so it can never equal 7.
In conclusion, the gcd test decides at once whether a linear congruence is solvable and how many solutions it has, and the extended Euclidean algorithm supplies the inverse needed to find them.
6 What is a residue matrix, and when does it have an inverse modulo n? Find the inverse of the matrix K with rows (3, 5) and (2, 7) in Z26, and use it to solve 3x + 5y ≡ 15 (mod 26), 2x + 7y ≡ 7 (mod 26). 10 marks
A matrix is a rectangular array of elements in l rows and m columns (an l × m matrix). It is a row matrix when l = 1, a column matrix when m = 1 and a square matrix when l = m. The identity matrix I is square, with 1s on the main diagonal and 0s elsewhere.
1. Operations.
- Addition and subtraction: matrices of the same size are combined element by element.
- Multiplication: A (l × m) times B (m × p) gives C (l × p), where c_ij is the sum of the products of row i of A with column j of B. In general AB ≠ BA.
- Scalar multiplication: every element is multiplied by the same number.
2. Determinant and inverse. For a 2 × 2 matrix with rows (a, b) and (c, d), det = ad − bc; larger determinants are expanded by cofactors along a row. Over the real numbers a square matrix has an inverse, with A × A⁻¹ = A⁻¹ × A = I, only when its determinant is not zero. For a 2 × 2 matrix, A⁻¹ = (1/det) × adj(A), where adj(A) has rows (d, −b) and (−c, a).
3. Residue matrices. A residue matrix has all its elements in Zn, and all its arithmetic is done modulo n. It has a multiplicative inverse only when det(A) has a multiplicative inverse in Zn, that is, when gcd(det A, n) = 1. Then A⁻¹ = det(A)⁻¹ × adj(A) mod n. The Hill cipher needs a key matrix of this kind modulo 26, so that decryption is possible.
4. Inverse of K in Z26.
K = | 3 5 | adj(K) = | 7 -5 |
| 2 7 | | -2 3 |- det K = 3 × 7 − 5 × 2 = 11, and gcd(11, 26) = 1, so K is invertible.
- 11⁻¹ mod 26 = 19, because 11 × 19 = 209 = 8 × 26 + 1.
- 19 × adj(K) has rows (133, −95) and (−38, 57). Reducing each element mod 26 gives:
K⁻¹ = | 3 9 |
| 14 5 |- Check: K × K⁻¹ has rows (79, 52) and (104, 53), which reduce mod 26 to (1, 0) and (0, 1), the identity I.
5. Solving the set of congruences. In matrix form the equations are K × [x, y]ᵀ ≡ [15, 7]ᵀ (mod 26), so [x, y]ᵀ ≡ K⁻¹ × [15, 7]ᵀ (mod 26):
- x = 3 × 15 + 9 × 7 = 108 ≡ 4 (mod 26)
- y = 14 × 15 + 5 × 7 = 245 ≡ 11 (mod 26)
- Check: 3 × 4 + 5 × 11 = 67 ≡ 15 and 2 × 4 + 7 × 11 = 85 ≡ 7 (mod 26).
In conclusion, a set of linear congruences has a unique solution modulo n when its coefficient matrix is invertible modulo n, and multiplying by the inverse matrix gives it.
Symmetric Encryption
Syllabus: Algebraic structures; GF(2^n) fields; Modern block ciphers; Modern stream ciphers; DES structure; DES analysis and the security of DES; Multiple DES; AES transformations; AES key expansion; AES ciphers and the analysis of AES
One-page revision summary
- A group is a set with one operation that is closed and associative and has an identity and inverses; it is abelian when the operation is also commutative.
- A ring has two operations, is an abelian group under addition, and has an associative multiplication that distributes over addition; a field is a commutative ring that also gives every nonzero element a multiplicative inverse.
- Z_n is a field only when n is prime, and every finite field has p^n elements and is written GF(p^n).
- In GF(2^n) the elements are n-bit words read as polynomials, addition and subtraction are both XOR, and products are reduced modulo an irreducible polynomial of degree n.
- A modern block cipher is a product cipher built from P-boxes, S-boxes, XOR, circular shifts, swaps, splits and combines, repeated over several rounds.
- A Feistel cipher may use a non-invertible round function because decryption runs the same rounds with the round keys reversed, while a non-Feistel cipher such as AES uses only invertible components.
- A modern stream cipher XORs the data with a key stream; in a synchronous cipher the key stream is independent of the message, and in a nonsynchronous cipher it depends on earlier ciphertext.
- DES encrypts 64-bit blocks with a 56-bit effective key in 16 Feistel rounds placed between an initial and a final permutation.
- The DES function expands 32 bits to 48, XORs the round key, reduces the result to 32 bits through eight S-boxes and permutes it with a straight P-box.
- DES round keys come from parity drop (64 to 56 bits), left rotations of one or two bits per round and a compression P-box (56 to 48 bits).
- DES shows the avalanche and completeness effects, but it has weak and semi-weak keys, the key complement property and a key too short to resist exhaustive search.
- Double DES adds almost no strength, because the meet-in-the-middle attack needs only about 2^57 operations instead of 2^112.
- Triple DES with two keys (encrypt-decrypt-encrypt) has a 112-bit key and becomes single DES when K1 = K2, and with three keys its 168-bit key gives about 112 bits of strength.
- AES is a non-Feistel cipher with a 128-bit block, 128-, 192- or 256-bit keys and 10, 12 or 14 rounds on a 4 × 4 byte state.
- Each AES round applies SubBytes, ShiftRows, MixColumns and AddRoundKey, the last round leaves out MixColumns, and decryption applies the inverse transformations in reverse order.
- AES-128 key expansion makes 44 words; every fourth word uses RotWord, SubWord and a round constant, and the other words are XORs of earlier words.
- AES resists brute force, statistical, differential and linear attacks, and practical attacks target weak implementations through side channels rather than the algorithm.
Learn these by heart
- Feistel round: L(i) = R(i−1) and R(i) = L(i−1) ⊕ f(R(i−1), K(i)).
- AES field GF(2^8): modulus x^8 + x^4 + x^3 + x + 1; addition is XOR; multiplying by {02} is a left shift plus XOR with {1B} on overflow.
- DES sizes: 64-bit block, 56-bit key, 16 rounds, 48-bit round keys and eight S-boxes of 6 input and 4 output bits.
- Triple DES with two keys: C = E(K1, D(K2, E(K1, P))).
- AES rounds: 10, 12 and 14 for 128-, 192- and 256-bit keys, with 44, 52 and 60 key-expansion words.
- AES-128 key expansion: w(i) = w(i−4) ⊕ SubWord(RotWord(w(i−1))) ⊕ Rcon(i/4) when i is a multiple of 4, otherwise w(i) = w(i−4) ⊕ w(i−1).
2-mark questions
1 Define a field. Why is Z_n, with addition and multiplication modulo n, a field only when n is prime? 2 marks
A field is a set forming an abelian group under +, whose nonzero elements form an abelian group under ×, with × distributing over +. In Z_n, a has an inverse under × exactly when gcd(a, n) = 1, true for all nonzero a only if n is prime. Z_7 is a field; in Z_6, 2 has no inverse.
2 In GF(2^3) with the irreducible polynomial x^3 + x + 1, find the sum and the product of x^2 + 1 and x + 1. 2 marks
Sum: coefficients add modulo 2: (x^2 + 1) + (x + 1) = x^2 + x, or 101 ⊕ 011 = 110.
Product: (x^2 + 1)(x + 1) = x^3 + x^2 + x + 1. Since x^3 ≡ x + 1, this becomes (x + 1) + x^2 + x + 1 = x^2, or 100.
3 Distinguish between diffusion and confusion in a modern block cipher. 2 marks
Diffusion hides the relation between plaintext and ciphertext: changing one plaintext bit should change many ciphertext bits. P-boxes and mixing steps provide it. Confusion hides the relation between key and ciphertext: each ciphertext bit should depend on several key bits in a complex way. Nonlinear S-boxes provide it. A product cipher repeats both over many rounds.
4 What is a linear feedback shift register (LFSR)? Why is it not used alone as a key-stream generator? 2 marks
An LFSR has n bit cells. Each step outputs one key-stream bit, shifts, and feeds back the XOR of cells chosen by a feedback polynomial. A primitive polynomial gives the maximum period 2^n − 1 (15 for x^4 + x + 1). Being linear, it is predictable: 2n consecutive key-stream bits reveal the feedback, so nonlinear parts are added.
5 What are weak keys in DES? Give an example. 2 marks
A weak key is a DES key for which the key generator produces the same round key in all 16 rounds. Decryption differs from encryption only in the order of the round keys, so encrypting twice with a weak key returns the plaintext. DES has four weak keys; for example, 0101010101010101 (hexadecimal) gives all-zero round keys.
6 How many rounds and round keys does AES use for each key size, and how does its last round differ? 2 marks
AES-128 uses 10 rounds, AES-192 uses 12 and AES-256 uses 14. Key expansion gives Nr + 1 round keys of 128 bits (44, 52 or 60 words): one for the initial AddRoundKey and one per round. Every round applies SubBytes, ShiftRows, MixColumns and AddRoundKey, except the last, which omits MixColumns.
10-mark questions
1 Define groups, rings and fields with examples. Explain addition and multiplication in GF(2^n), and compute {57} + {83} and {57} × {83} in GF(2^8) with the modulus x^8 + x^4 + x^3 + x + 1. 10 marks
Ciphers such as AES work on bytes and need arithmetic in which bytes can be added, multiplied and divided. Algebraic structures state which operations a set supports.
1. Group. A group (G, •) is a set with one operation that satisfies closure, associativity, an identity element and an inverse for every element. If • is also commutative, the group is abelian. Example: (Z_6, + mod 6) is an abelian group with identity 0; the inverse of 4 is 2, because 4 + 2 = 6 ≡ 0.
2. Ring. A ring (R, +, ×) has two operations. It is an abelian group under +, × is closed and associative, and × distributes over +. If × is commutative, it is a commutative ring. Example: Z_n with + and × mod n. In Z_6, 2 × 3 = 0, and 2 has no multiplicative inverse.
3. Field. A field (F, +, ×) is a commutative ring in which every nonzero element has a multiplicative inverse. Z_p is a field when p is prime; in Z_7, 3 × 5 = 15 ≡ 1, so 3^-1 = 5. A finite field always has p^n elements and is written GF(p^n).
4. GF(2^n). Each element is a polynomial of degree less than n with coefficients 0 or 1, stored as an n-bit word. Addition adds coefficients mod 2, so it is bitwise XOR, and subtraction is the same as addition. Multiplication multiplies the polynomials and reduces the result modulo an irreducible polynomial of degree n, so the result stays n bits long. Every nonzero element has an inverse, found with the extended Euclidean algorithm.
5. Worked example in GF(2^8) with m(x) = x^8 + x^4 + x^3 + x + 1. Here {57} = x^6 + x^4 + x^2 + x + 1 and {83} = x^7 + x + 1.
Sum: {57} ⊕ {83} = 0101 0111 ⊕ 1000 0011 = 1101 0100 = {D4}.
Product: multiplying by x is a left shift, followed by XOR with {1B} when a 1 is shifted out of bit 7. Doubling {57} repeatedly:
{57}·{01} = {57}
{57}·{02} = {AE}
{57}·{04} = {47} (5C ⊕ 1B)
{57}·{08} = {8E}
{57}·{10} = {07} (1C ⊕ 1B)
{57}·{20} = {0E}
{57}·{40} = {1C}
{57}·{80} = {38}Since {83} = {80} ⊕ {02} ⊕ {01}, the product is {57}·{83} = {38} ⊕ {AE} ⊕ {57} = {C1}, that is x^7 + x^6 + 1.
Conclusion: GF(2^8) is a field whose 256 elements are exactly the byte values, which is why AES uses it in SubBytes (the inverse of {53} is {CA}) and in MixColumns.
2 Explain the components of a modern block cipher and the Feistel structure. How does a modern stream cipher differ, and what are synchronous and nonsynchronous stream ciphers? 10 marks
A modern block cipher encrypts an n-bit plaintext block into an n-bit ciphertext block under a k-bit key, for example n = 64 in DES and n = 128 in AES. A table that substitutes whole blocks would need 2^n entries, so the cipher is built from small components repeated in rounds.
1. Components.
- P-box: transposes bits. A straight P-box (n to n bits) is invertible; an expansion P-box (n to m bits, m > n) and a compression P-box (m < n) are not.
- S-box: an m × n substitution table that gives nonlinearity; it can be invertible only when m = n.
- Exclusive-or (XOR): mixes the round key into the data and is its own inverse.
- Circular shift, swap, split and combine: rearrange or divide the block, as with the halves in DES.
2. Product cipher. Rounds of substitution and permutation give diffusion (one plaintext bit affects many ciphertext bits) and confusion (each ciphertext bit depends on the key in a complex way).
3. Feistel cipher. The block is split into halves L and R, and each round computes:
L(i) = R(i−1)
R(i) = L(i−1) ⊕ f(R(i−1), K(i))Decryption uses the same structure with the round keys in reverse order, so the function f need not be invertible; DES is a Feistel cipher. A non-Feistel cipher, such as AES, uses only invertible components (S-boxes with m = n, straight P-boxes) and decrypts with their inverses.
4. Modern stream cipher. Instead of whole blocks, it encrypts r bits at a time, often one: c(i) = p(i) ⊕ k(i), where the key stream k(i) comes from a generator seeded by the key. It needs no padding and suits real-time data, but a key stream must never be reused.
- Synchronous: the key stream is independent of the plaintext and ciphertext. Examples are the one-time pad (a truly random key as long as the message) and feedback shift registers such as the LFSR. A flipped ciphertext bit spoils only one plaintext bit, but a lost bit breaks synchronisation.
- Nonsynchronous (self-synchronising): each key-stream bit depends on earlier ciphertext bits, so the receiver recovers by itself after a few bits, while an error spreads to the next few bits.
Conclusion: a block cipher gets its security from many rounds of S-boxes and P-boxes, and a stream cipher from the unpredictability of its key stream.
3 Describe the structure of DES with a neat diagram. Explain the DES round function and the generation of the round keys. 10 marks
DES (Data Encryption Standard) is a symmetric block cipher with a 64-bit block and a 64-bit key, of which 56 bits are used; every eighth bit is a parity bit. It is a Feistel cipher with 16 rounds.
1. Initial and final permutations. The plaintext first passes through the initial permutation (IP), a straight P-box. After round 16, the final permutation (FP), the inverse of IP, gives the ciphertext. Both are fixed and public, so they add no security.
2. Rounds. The 64-bit block is split into 32-bit halves L(0) and R(0). Each round i has a mixer and a swapper:
L(i) = R(i−1)
R(i) = L(i−1) ⊕ f(R(i−1), K(i))Round 16 has no swapper, so that decryption can use the same structure.
3. The DES function f(R, K) has four steps:
- Expansion P-box: the 32-bit R is split into eight 4-bit sections, and each section borrows the nearest bit of both neighbours, giving 48 bits.
- XOR with the 48-bit round key K(i).
- S-boxes: the 48 bits are cut into eight 6-bit pieces for S1 to S8. Bits 1 and 6 of a piece select the row (0 to 3) and bits 2 to 5 the column (0 to 15); each S-box outputs 4 bits, so 32 bits come out. For example, the input 110101 to S1 selects row 11 = 3 and column 1010 = 10, and the entry there is 3, so the output is 0011.
- Straight P-box: the 32 bits are permuted to give the output of f.
4. Round-key generation:
- Parity drop: the 8 parity bits are removed and the other 56 bits are permuted.
- The 56 bits are split into two 28-bit halves, and each half is shifted circularly left by one bit in rounds 1, 2, 9 and 16 and by two bits in the other rounds.
- Compression P-box: 48 of the 56 bits are selected as the round key K(i).
5. Decryption runs the same algorithm with the round keys in the order K16, K15, ..., K1.
Conclusion: the S-boxes are the only nonlinear part of DES and give confusion, while the expansion and straight P-boxes spread every bit across the S-boxes and give diffusion.
4 Explain the four transformations used in the rounds of AES with an example of each, and state how decryption reverses them. 10 marks
AES (Advanced Encryption Standard) is a non-Feistel block cipher that turns a 128-bit plaintext block into a 128-bit ciphertext block under a 128-, 192- or 256-bit key, using 10, 12 or 14 rounds. The 16-byte block is held as a 4 × 4 matrix of bytes called the state, filled column by column. Each byte is an element of GF(2^8) with the modulus x^8 + x^4 + x^3 + x + 1.
1. SubBytes (substitution). Every byte is replaced on its own through a 16 × 16 S-box: the left hex digit of the byte selects the row and the right digit the column. The table is built by taking the multiplicative inverse of the byte in GF(2^8) ({00} stays {00} in this step) and then applying a fixed affine transformation. Example: the inverse of {53} is {CA}, and the affine step turns {CA} into {ED}, so SubBytes changes {53} to {ED}. This is the only nonlinear step and gives confusion.
2. ShiftRows (permutation). Row r of the state is rotated left by r bytes: row 0 stays, row 1 moves one byte, row 2 two and row 3 three. Example: the row [01 05 09 0D] becomes [05 09 0D 01]. The four bytes of each column are thus spread over four columns.
3. MixColumns (mixing). Each column is multiplied in GF(2^8) by a fixed matrix:
|b0| |02 03 01 01| |a0|
|b1| = |01 02 03 01| |a1|
|b2| |01 01 02 03| |a2|
|b3| |03 01 01 02| |a3|Example: the column [1A 2B 3C 4D] becomes [38 45 9E A3]. For the first byte, {02}·{1A} ⊕ {03}·{2B} ⊕ {3C} ⊕ {4D} = {34} ⊕ {7D} ⊕ {3C} ⊕ {4D} = {38}. Each output byte depends on all four input bytes, which gives diffusion.
4. AddRoundKey. The state is XORed with the 128-bit round key, column by column. Example: a state byte {8E} with key byte {0F} gives {81}. This is the only step that uses the key.
Order: AddRoundKey with K0 comes before round 1, rounds 1 to Nr − 1 apply all four steps, and the last round omits MixColumns.
Decryption (the inverse cipher) applies the inverses in reverse order: after AddRoundKey with K(Nr), each round applies InvShiftRows, which rotates rows to the right, InvSubBytes, which uses the inverse S-box ({ED} back to {53}), AddRoundKey, which is its own inverse, and InvMixColumns, which multiplies by the matrix whose first row is 0E 0B 0D 09; the last round omits InvMixColumns. The round keys are used from last to first.
Conclusion: SubBytes gives confusion, ShiftRows and MixColumns give diffusion, and AddRoundKey brings in the key in every round.
5 Discuss the security of DES: its properties, weaknesses and attacks. Why is double DES not used, and how does triple DES improve security? 10 marks
DES has a 56-bit key and S-boxes chosen by its designers. Its analysis covers its good properties, its weaknesses and the attacks on it, which led to multiple DES.
1. Properties.
- Avalanche effect: a small change in the plaintext or the key changes many ciphertext bits. For example (in hexadecimal), under the key 1A2B3C4D5E6F7081 the plaintexts 0000000000000000 and 0000000000000001 encrypt to A2AFCD7213699BF1 and 5A4E38A45795C59D, which differ in 37 of the 64 bits.
- Completeness effect: every ciphertext bit depends on many plaintext bits.
2. Weaknesses.
- S-box design: the design criteria were not published at first, which raised fears of a hidden trapdoor; none has been found, and the S-boxes turned out to resist differential cryptanalysis.
- Weak keys: four keys, such as 0101010101010101, give the same round key in all 16 rounds, so encrypting twice returns the plaintext. Six pairs of semi-weak keys give only two different round keys, and one key of a pair decrypts what the other encrypts.
- Key complement: E(K', P') = (E(K, P))', where ' is the bitwise complement, so an exhaustive search needs to test only half the keys, 2^55.
- Key size: 56 bits is too short. DES has been broken by exhaustive key search on special-purpose hardware and is no longer secure.
3. Attacks. Besides brute force over 2^56 keys, differential cryptanalysis needs about 2^47 chosen plaintexts and linear cryptanalysis about 2^43 known plaintexts.
4. Double DES. C = E(K2, E(K1, P)) has a 112-bit key, but the meet-in-the-middle attack defeats it. With one known pair (P, C), the attacker encrypts P under all 2^56 values of K1 and stores the middle texts in a table, then decrypts C under every K2 and looks for a match. Each matching (K1, K2) is tested on a second (P, C) pair, and the pair that passes is the key found.
The work is about 2^56 + 2^56 = 2^57 operations and a table of 2^56 entries, not 2^112.
5. Triple DES.
- Two keys: C = E(K1, D(K2, E(K1, P))). The 112-bit key puts exhaustive search out of reach, and choosing K1 = K2 gives single DES, so it works with older equipment.
- Three keys: C = E(K3, D(K2, E(K1, P))). The key has 168 bits, but meet-in-the-middle cuts the effective strength to about 2^112.
Conclusion: triple DES fixed the short key but is three times slower than DES and keeps the 64-bit block. NIST has deprecated it and now allows it only for decrypting existing data, and AES has replaced it.
6 Explain AES-128 key expansion with an example of computing round-key words, and discuss the analysis of AES. 10 marks
AES needs a 128-bit round key for the initial AddRoundKey and one for each round, so AES-128 needs 11 round keys. Key expansion produces them as 44 words w0 to w43 of 4 bytes each; round key i is w(4i) to w(4i+3).
1. The cipher key gives the first four words w0, w1, w2 and w3.
2. For i = 4 to 43:
- If i is not a multiple of 4: w(i) = w(i−4) ⊕ w(i−1).
- If i is a multiple of 4: w(i) = w(i−4) ⊕ t, where t = SubWord(RotWord(w(i−1))) ⊕ Rcon(i/4).
RotWord rotates the four bytes of a word left by one byte, and SubWord replaces each byte using the AES S-box. Rcon(j) is the word [RC(j) 00 00 00], where RC = 01, 02, 04, 08, 10, 20, 40, 80, 1B, 36 for j = 1 to 10; each value is the previous one multiplied by {02} in GF(2^8).
3. Example. Take the cipher key 3C4FA107 92E85B16 D4702AC9 813EF56D, so w0 = 3C4FA107 and w3 = 813EF56D.
RotWord(w3) = 3EF56D81
SubWord = B2E63C0C
⊕ Rcon(1) = B3E63C0C = t
w4 = w0 ⊕ t = 8FA99D0B
w5 = w1 ⊕ w4 = 1D41C61D4. AES-192 and AES-256 start from 6 or 8 key words, apply the special step when i is a multiple of 6 or 8, and produce 52 or 60 words; AES-256 also applies SubWord alone when i mod 8 = 4.
5. Analysis of the key expansion.
- SubWord makes the expansion nonlinear, so round keys are not simple linear functions of the cipher key.
- Rcon gives each round a different constant, which removes symmetry between rounds; even an all-zero cipher key gives 11 different round keys.
- The expansion can be run backwards: the four words of any one AES-128 round key give the cipher key, so round keys must be kept as secret as the key itself.
6. Analysis of AES.
- Brute force: 2^128 or more keys are far beyond any search.
- Statistical, differential and linear attacks: the S-box and the spreading by ShiftRows and MixColumns were designed against them, and the best known attacks on the full cipher are only slightly faster than exhaustive search and are not practical.
- Implementation: timing and cache side-channel attacks target careless implementations, not the algorithm.
- Simplicity and cost: AES uses only table lookups, XOR, byte rotations and small GF(2^8) products, so it is fast in software and in hardware.
Conclusion: the key expansion is simple and fast, and AES is the standard block cipher used in new systems.
Asymmetric Encryption
Syllabus: Primes; Primality testing; Factorization; The Chinese remainder theorem (CRT); The RSA cryptosystem; The Rabin cryptosystem; The ElGamal cryptosystem; Elliptic curve cryptography (ECC)
One-page revision summary
- There are infinitely many primes, and the prime number theorem says about x/ln x primes lie below x; for example 168 primes lie below 1000 against an estimate of about 145.
- Euler's totient φ(n) counts the integers from 1 to n that are coprime to n; φ(p) = p − 1 for a prime p and φ(pq) = (p − 1)(q − 1) for distinct primes p and q.
- The Fermat test checks a^(n−1) ≡ 1 (mod n), but Carmichael numbers such as 561 = 3 × 11 × 17 pass it for every base coprime to n.
- Miller–Rabin is probabilistic: each round with a random base wrongly accepts a composite with probability at most 1/4, so many rounds make the error negligible.
- Deterministic polynomial-time primality tests such as AKS exist, but Miller–Rabin is preferred in key generation because it is much faster.
- Trial division needs at most √n divisions, Fermat's method is quick when the two factors are close to √n, and Pollard's rho finds a factor p in about √p steps.
- The general number field sieve is the fastest known classical method for factoring large RSA moduli, and even it is infeasible for moduli of 2048 bits.
- Testing a large number for primality is easy while factoring a large n = pq is believed hard, and RSA and Rabin depend on this gap.
- For pairwise coprime moduli the CRT matches each residue modulo M = m1·…·mk with one tuple of residues modulo the mi, so arithmetic can be split and rejoined.
- RSA needs gcd(e, φ(n)) = 1 so that d exists; 65537 is a common public exponent, and textbook RSA should be used with padding such as OAEP.
- Rabin encryption is a single squaring modulo n, faster than RSA encryption, but each ciphertext has four square roots and the plaintext needs redundancy.
- ElGamal is randomised: each encryption uses a new k, and the ciphertext (c1, c2) is twice as long as the plaintext.
- The points of an elliptic curve together with the point at infinity O form an abelian group, and k·G is easy to compute while finding k from k·G is the ECDLP.
- Hasse's theorem bounds the number of points N on a curve over F_p: |N − (p + 1)| ≤ 2√p; the 19-point curve over F13 satisfies |19 − 14| = 5 ≤ 7.2.
- Public-key encryption is much slower than symmetric encryption, so it is mainly used to exchange or protect a symmetric session key.
Learn these by heart
- RSA: n = pq, φ(n) = (p − 1)(q − 1), e·d ≡ 1 (mod φ(n)), C = M^e mod n and M = C^d mod n.
- Fermat's little theorem: a^(p−1) ≡ 1 (mod p) for a prime p and gcd(a, p) = 1.
- Miller–Rabin: write n − 1 = 2^s·d; n passes base a if a^d ≡ 1 or a^(2^j·d) ≡ n − 1 (mod n) for some j with 0 ≤ j < s.
- CRT: x = Σ ai·Mi·yi mod M, with M = m1·m2·…·mk, Mi = M/mi and yi = Mi^(−1) mod mi.
- Rabin: C = M^2 mod n; for p ≡ 3 (mod 4) the square roots of C modulo p are ±C^((p+1)/4) mod p.
- ElGamal: y = g^x mod p; c1 = g^k mod p, c2 = M·y^k mod p; M = c2·(c1^x)^(−1) mod p.
- EC points: λ = (y2 − y1)/(x2 − x1) to add, λ = (3x1^2 + a)/(2y1) to double; then x3 = λ^2 − x1 − x2 and y3 = λ(x1 − x3) − y1.
2-mark questions
1 Define a prime number and state the fundamental theorem of arithmetic with an example. 2 marks
A prime is an integer p > 1 whose only positive divisors are 1 and p. The fundamental theorem of arithmetic states that every integer n > 1 is a product of primes in exactly one way, apart from the order of the factors. Example: 360 = 2^3 × 3^2 × 5, and no other primes multiply to 360.
2 What is a Carmichael number? Show that 561 is one. 2 marks
A Carmichael number is a composite n with a^(n−1) ≡ 1 (mod n) for every a coprime to n, so it fools the Fermat test. 561 = 3 × 11 × 17 is square-free and each p − 1 (2, 10, 16) divides 560, so by Korselt's criterion a^560 ≡ 1 (mod 561) whenever gcd(a, 561) = 1.
3 Factorise n = 7571 using Fermat's factorization method. 2 marks
Fermat's method seeks x with x^2 − n a perfect square y^2, trying x upward from ⌈√n⌉; then n = (x − y)(x + y). √7571 ≈ 87.01: 88^2 − 7571 = 173, 89^2 − 7571 = 350, 90^2 − 7571 = 529 = 23^2. So 7571 = (90 − 23)(90 + 23) = 67 × 113.
4 Why does Rabin decryption give four possible plaintexts, and how is the right one chosen? 2 marks
Rabin encryption is C = M^2 mod n with n = pq. C has two square roots modulo p (±mp) and two modulo q (±mq); the Chinese remainder theorem combines them into four roots modulo n. The sender adds agreed redundancy, such as a repeated block of bits, and the receiver keeps the root showing it.
5 Why must a fresh random k be used for every ElGamal encryption? 2 marks
If k is reused, both ciphertexts share c1 = g^k and the same mask y^k, so c2 = M·y^k and c2′ = M′·y^k. An attacker who learns M then gets M′ = c2′·c2^(−1)·M mod p without the private key. A fresh k also makes repeated messages encrypt differently.
6 Why does ECC give the same security as RSA with much shorter keys? 2 marks
RSA rests on factoring, which has sub-exponential algorithms such as the number field sieve, so its modulus must be large. The best general attack on the elliptic curve discrete logarithm problem, Pollard's rho, needs about √n steps for a group of order n. So a 256-bit curve gives about 128-bit security, roughly that of 3072-bit RSA.
10-mark questions
1 Why do public-key systems need primality testing? Explain the Miller–Rabin test and apply it with base a = 2 to n = 561 and to n = 97. 10 marks
RSA, Rabin and ElGamal all need large random primes. A key generator picks a random odd number of the required size and tests it, repeating until a prime turns up. Trial division by every number up to √n is hopeless for a 1024-bit n, and the Fermat test (a prime n gives a^(n−1) ≡ 1 mod n) is fooled by Carmichael numbers such as 561. The Miller–Rabin test strengthens the Fermat test with one more fact: modulo a prime, the only square roots of 1 are 1 and n − 1.
Algorithm for one base:
1. Write n − 1 = 2^s · d with d odd. 2. Pick a base a with 1 < a < n − 1. 3. Compute x = a^d mod n. If x = 1 or x = n − 1, report "probably prime". 4. Square x up to s − 1 times. If x becomes n − 1, report "probably prime". 5. Otherwise report "composite": a is a witness that n is composite.
Example 1: n = 561, a = 2.
560 = 2^4 × 35, so s = 4 and d = 35. Repeated squaring gives 2^32 ≡ 103, so 2^35 = 2^32 × 2^2 × 2 ≡ 103 × 8 ≡ 263 (mod 561).
i value mod 561
0 2^35 263
1 263^2 166
2 166^2 67
3 67^2 1The value n − 1 = 560 never appears, so 561 is composite. The table also shows why: 67 is a square root of 1 other than ±1, which is impossible modulo a prime, and gcd(67 − 1, 561) = 33 and gcd(67 + 1, 561) = 17 even reveal factors. The Fermat test with the same base gives 2^560 ≡ 1 (mod 561) and would wrongly pass 561.
Example 2: n = 97, a = 2.
96 = 2^5 × 3, so s = 5 and d = 3, and x = 2^3 = 8. Squaring: 8^2 = 64, 64^2 = 4096 ≡ 22, 22^2 = 484 ≡ 96 (mod 97). Since 96 = n − 1, the test reports "probably prime", and 97 is indeed prime.
Error and use: for an odd composite n, at most a quarter of the possible bases are strong liars (bases that wrongly pass), so t rounds with independent random bases wrongly accept with probability at most (1/4)^t; 40 rounds bring this to at most 2^(−80). The test needs only modular exponentiation, so it is fast, which is why key generators use it. Real primes are hundreds of digits long; these small numbers are only for working by hand.
2 State the Chinese remainder theorem and solve x ≡ 2 (mod 5), x ≡ 3 (mod 7), x ≡ 4 (mod 11). How does the theorem speed up RSA decryption? 10 marks
The Chinese remainder theorem (CRT) replaces one congruence modulo a large number by several congruences modulo its coprime factors, and joins the answers back. Public-key systems use it to speed up RSA decryption and to decrypt Rabin ciphertexts.
Statement: let m1, m2, …, mk be pairwise coprime and M = m1·m2·…·mk. For any integers a1, …, ak, the system x ≡ ai (mod mi), i = 1, …, k, has exactly one solution modulo M:
x = (a1·M1·y1 + a2·M2·y2 + … + ak·Mk·yk) mod M, where Mi = M/mi and yi = Mi^(−1) mod mi.
Why it works: each yi exists because gcd(Mi, mi) = 1. Mi is a multiple of every mj with j ≠ i, so the term ai·Mi·yi is 0 modulo those mj, while modulo mi it is ai × 1 = ai. Hence the sum satisfies every congruence. If x and x′ are both solutions, every mi divides x − x′; since the mi are pairwise coprime, M divides x − x′, so the solution is unique modulo M.
Solving the system:
1. M = 5 × 7 × 11 = 385. 2. M1 = 385/5 = 77, M2 = 385/7 = 55, M3 = 385/11 = 35. 3. 77 ≡ 2 (mod 5) and 2 × 3 = 6 ≡ 1, so y1 = 3. 55 ≡ 6 (mod 7) and 6 × 6 = 36 ≡ 1, so y2 = 6. 35 ≡ 2 (mod 11) and 2 × 6 = 12 ≡ 1, so y3 = 6. 4. Add the terms:
mi ai Mi yi ai·Mi·yi
5 2 77 3 462
7 3 55 6 990
11 4 35 6 840
sum 22925. x = 2292 mod 385 = 2292 − 5 × 385 = 367.
Check: 367 = 73 × 5 + 2 = 52 × 7 + 3 = 33 × 11 + 4. So x ≡ 367 (mod 385), and every solution has the form 367 + 385t.
Use in RSA: the owner of the private key knows p and q. Instead of one exponentiation C^d mod n, she computes mp = C^(d mod (p − 1)) mod p and mq = C^(d mod (q − 1)) mod q (Fermat's little theorem allows the exponent to be reduced), then joins mp and mq with the CRT to get M modulo n. The exponents and moduli are about half the length of d and n, so decryption runs about four times faster. Rabin decryption uses the same joining step.
The CRT is therefore both a method for solving systems of congruences and a practical speed-up for public-key decryption.
3 Explain key generation, encryption and decryption in RSA. Illustrate with p = 13, q = 17, e = 5 and M = 10, and explain why the security of RSA rests on factorization. 10 marks
RSA is a public-key cryptosystem built on modular exponentiation. Anyone can encrypt with the public key (e, n); only the receiver, holding the private key d, can decrypt.
Key generation (receiver):
1. Choose two large distinct primes p and q. 2. Compute n = p·q and φ(n) = (p − 1)(q − 1). 3. Choose e with 1 < e < φ(n) and gcd(e, φ(n)) = 1. 4. Compute d = e^(−1) mod φ(n) with the extended Euclidean algorithm. 5. Publish (e, n); keep d, p and q secret.
Encryption (sender): C = M^e mod n, for a message 0 ≤ M < n.
Decryption (receiver): M = C^d mod n. This works because e·d = 1 + k·φ(n): Euler's theorem gives M^(e·d) ≡ M (mod n) when gcd(M, n) = 1, and the CRT extends this to every M.
Example:
- n = 13 × 17 = 221 and φ(n) = 12 × 16 = 192.
- gcd(5, 192) = 1, so e = 5 is allowed.
- Extended Euclid: 192 = 38 × 5 + 2 and 5 = 2 × 2 + 1, so 1 = 5 − 2 × 2 = 5 − 2(192 − 38 × 5) = 77 × 5 − 2 × 192. Hence d = 77; check: 5 × 77 = 385 = 2 × 192 + 1.
- Encryption: 10^2 = 100, 10^4 = 100^2 mod 221 = 55, 10^5 = 55 × 10 = 550 mod 221 = 108. The ciphertext is C = 108.
- Decryption: 77 = 64 + 8 + 4 + 1, and repeated squaring gives:
108^1 mod 221 = 108
108^2 mod 221 = 172
108^4 mod 221 = 191
108^8 mod 221 = 16
108^16 mod 221 = 35
108^32 mod 221 = 120
108^64 mod 221 = 35M = 35 × 16 × 191 × 108 mod 221 = 10, since 35 × 16 = 560 ≡ 118, 118 × 191 ≡ 217 and 217 × 108 ≡ 10.
Why security rests on factorization: an attacker sees e and n. If she can factor n, she computes φ(n) and d exactly as the receiver did. Here trial division finds 221 = 13 × 17 at once, so d = 77 falls out. For moduli of 2048 bits or more, no known classical method, even the general number field sieve, factors n in feasible time. Finding φ(n) or d from (e, n) is as hard as factoring, so RSA is never stronger than factoring (whether decryption itself needs the factors is unproved).
Practical RSA adds random padding such as OAEP, since textbook RSA is deterministic: equal messages give equal ciphertexts.
4 Explain the ElGamal cryptosystem. With p = 23, generator g = 5, private key x = 6 and random k = 3, encrypt M = 7 and decrypt the ciphertext. 10 marks
ElGamal is a public-key cryptosystem whose security rests on the discrete logarithm problem in Z_p*: given p, g and y = g^x mod p, finding x is believed infeasible when p is large. Unlike textbook RSA it is randomised, so the same message encrypts differently each time.
Key generation (receiver):
1. Choose a large prime p and a generator g of Z_p*. 2. Choose a private key x with 1 < x < p − 1. 3. Compute y = g^x mod p. The public key is (p, g, y); x stays secret.
Encryption (sender, message 1 ≤ M < p):
4. Choose a fresh random k with 1 < k < p − 1. 5. Compute c1 = g^k mod p and c2 = M·y^k mod p, and send (c1, c2).
Decryption (receiver):
6. Compute s = c1^x mod p. It equals y^k, since both are g^(xk). 7. Recover M = c2·s^(−1) mod p.
Correctness: c2·s^(−1) = M·g^(xk)·g^(−xk) = M (mod p).
Example:
- 5 is a generator of Z_23*: its powers run through all 22 nonzero residues.
- Public key: 5^2 = 25 ≡ 2, 5^4 ≡ 2^2 = 4, 5^6 = 5^4 × 5^2 ≡ 4 × 2 = 8. So y = 8 and the public key is (23, 5, 8).
- c1 = 5^3 = 125 = 5 × 23 + 10, so c1 = 10.
- y^k = 8^3 = 512 = 22 × 23 + 6, so y^k ≡ 6 and c2 = 7 × 6 = 42 ≡ 19 (mod 23).
- Ciphertext: (c1, c2) = (10, 19).
- Decryption: 10^2 = 100 ≡ 8, 10^4 ≡ 8^2 = 64 ≡ 18, 10^6 = 10^4 × 10^2 ≡ 18 × 8 = 144 ≡ 6. So s = 6, the same mask the sender used.
- s^(−1) mod 23 = 4, because 6 × 4 = 24 ≡ 1.
- M = 19 × 4 = 76 = 3 × 23 + 7, so M = 7, the original message.
Properties:
- The ciphertext is a pair of numbers modulo p, so it is twice as long as the plaintext.
- k must be fresh for every message. If k is reused, c2′·c2^(−1) ≡ M′·M^(−1) (mod p), so one known plaintext exposes the other.
- Anyone who could compute g^(xk) from g^x and g^k (the Diffie–Hellman problem) could decrypt, so real systems use primes of 2048 bits or more, not the toy value 23.
- The same scheme works in elliptic-curve groups.
ElGamal thus gives probabilistic public-key encryption whose strength depends on the hardness of discrete logarithms.
5 Explain the Rabin cryptosystem. With p = 7 and q = 11, encrypt M = 20 and find the four candidate plaintexts produced by decryption. 10 marks
The Rabin cryptosystem encrypts by squaring modulo n = p·q. Its attraction: decrypting is provably as hard as factoring n, which is not known for RSA.
Key generation (receiver):
1. Choose two large primes p and q with p ≡ q ≡ 3 (mod 4). 2. The public key is n = p·q; the private key is (p, q).
Encryption (sender): C = M^2 mod n, where the message carries agreed redundancy, such as a repeated block of bits.
Decryption (receiver):
3. Compute mp = C^((p+1)/4) mod p and mq = C^((q+1)/4) mod q. Because p and q are ≡ 3 (mod 4), these are square roots of C modulo p and q, and so are −mp and −mq. 4. Find yp and yq with yp·p + yq·q = 1 (extended Euclid). 5. Join the roots with the Chinese remainder theorem (CRT): r = (yp·p·mq + yq·q·mp) mod n and s = (yp·p·mq − yq·q·mp) mod n. 6. The four square roots are r, n − r, s and n − s. Keep the one with the redundancy.
Example:
- p = 7 and q = 11 are both ≡ 3 (mod 4), so n = 77.
- Encryption: 20^2 = 400 = 5 × 77 + 15, so C = 15.
- mp = 15^2 mod 7 = 1 (since 15 ≡ 1), and mq = 15^3 mod 11 = 4^3 mod 11 = 9 (since 15 ≡ 4).
- Extended Euclid on 11 and 7: 11 = 7 + 4, 7 = 4 + 3, 4 = 3 + 1, so 1 = 2 × 11 − 3 × 7, giving yp = −3 and yq = 2.
- yp·p·mq = −3 × 7 × 9 = −189 and yq·q·mp = 2 × 11 × 1 = 22.
- r = (−189 + 22) mod 77 = −167 mod 77 = 64, and s = (−189 − 22) mod 77 = −211 mod 77 = 20.
- The four candidates are 64, 77 − 64 = 13, 20 and 77 − 20 = 57.
root mod 7 mod 11 root^2 mod 77
13 6 2 15
20 6 9 15
57 1 2 15
64 1 9 15All four square to 15; the redundancy picks out M = 20.
Security and drawbacks:
- Two roots that are not negatives of each other reveal a factor: gcd(20 − 13, 77) = 7. So anyone who can find square roots modulo n can factor n, which is why breaking Rabin is equivalent to factoring.
- The same fact allows a chosen-ciphertext attack, so practical use needs padding.
Real moduli have 2048 bits or more.
6 Explain elliptic curve cryptography over a prime field: the curve, point addition and doubling, and elliptic curve Diffie–Hellman. Use y^2 = x^3 + 4x + 1 over F13 with base point G = (0, 1). 10 marks
Elliptic curve cryptography (ECC) builds public-key schemes on the points of an elliptic curve over a finite field. Its hard problem is the elliptic curve discrete logarithm problem (ECDLP): finding k from G and k·G.
Curve: over a prime p > 3, E: y^2 ≡ x^3 + ax + b (mod p) with 4a^3 + 27b^2 ≢ 0 (mod p), together with a point at infinity O, the identity. Here 4 × 64 + 27 × 1 = 283 ≡ 10 (mod 13), so the curve is valid. It has 19 points including O, and G = (0, 1) has order 19.
Point rules for P = (x1, y1) and Q = (x2, y2):
- Negation: −P = (x1, −y1); P + (−P) = O.
- Addition (P ≠ Q): λ = (y2 − y1)·(x2 − x1)^(−1) mod p.
- Doubling (P = Q): λ = (3x1^2 + a)·(2y1)^(−1) mod p.
- In both cases x3 = λ^2 − x1 − x2 and y3 = λ(x1 − x3) − y1 (mod p).
- k·G (G added to itself k times) is computed by double-and-add.
Working modulo 13:
1. 2G: λ = (3 × 0 + 4) × 2^(−1) = 4 × 7 = 28 ≡ 2. x3 = 4 − 0 − 0 = 4, y3 = 2(0 − 4) − 1 = −9 ≡ 4. So 2G = (4, 4). 2. 3G = G + 2G: λ = (4 − 1) × 4^(−1) = 3 × 10 = 30 ≡ 4. x3 = 16 − 0 − 4 = 12, y3 = 4(0 − 12) − 1 = −49 ≡ 3. So 3G = (12, 3).
ECDH key exchange:
3. Alice picks private nA = 2 and sends QA = 2G = (4, 4); Bob picks nB = 3 and sends QB = 3G = (12, 3). 4. Alice doubles QB: λ = (3 × 144 + 4) × 6^(−1) ≡ 7 × 11 = 77 ≡ 12, x = 144 − 24 = 120 ≡ 3, y = 12(12 − 3) − 3 = 105 ≡ 1. Her key is K = (3, 1). 5. Bob computes 3·QA = (3, 1) as well, because nA·QB = nB·QA = 6G.
An eavesdropper seeing G, QA and QB must solve the ECDLP to find nA or nB.
Why ECC: Pollard's rho, the best known general attack, needs about √n steps for a group of order n, so a 256-bit curve gives about 128-bit security, like 3072-bit RSA. Short keys save time and bandwidth, which suits phones and smart cards. Real curves use primes of about 256 bits or more; this 19-point toy curve falls to listing every multiple of G.
Data Integrity, Digital Signature Schemes and Key Management
Syllabus: Message integrity; The random oracle model; Message authentication; Cryptographic hash functions: Whirlpool; SHA-512; Digital signature: process, services and attacks; Digital signature schemes and applications; Symmetric key distribution; Kerberos
One-page revision summary
- Message integrity means the receiver can detect any change to a message; a hash digest acts as its fingerprint, but a keyless digest (MDC) must itself travel over a trusted channel.
- The random oracle model treats an ideal hash function as an oracle that returns a fresh random fixed-length digest for each new message and the recorded digest for a repeated one.
- By the pigeonhole principle collisions always exist for a fixed-length digest; a secure hash function only makes them infeasible to find, needing about 2^(n/2) trials for an n-bit digest.
- A MAC needs a shared secret key, so it gives integrity and sender authentication but not nonrepudiation, since the receiver could have computed the same MAC.
- HMAC uses any hash function as a black box with an inner and an outer keyed hash, while CMAC uses a block cipher such as AES in a CBC-style chain with two derived subkeys.
- Whirlpool uses 512-bit blocks, a 256-bit length field, an AES-like 10-round cipher W on an 8 × 8 byte state and the Miyaguchi–Preneel scheme to give a 512-bit digest.
- SHA-512 uses 1024-bit blocks, a 128-bit length field, eight 64-bit buffers, 80 expanded words and 80 rounds per block, and outputs a 512-bit digest.
- In a digital signature the signer uses the private key and the verifier uses the signer's public key, the reverse of the key roles in public-key encryption.
- Attacks on signatures are key-only, known-message or chosen-message attacks, and they aim at existential forgery (some message) or selective forgery (a message the attacker chooses).
- The ElGamal, Schnorr and DSS signature schemes need a fresh secret random number r for every message, because reusing r lets an attacker work out the private key.
- The Schnorr scheme signs a hash of the message joined with e1^r mod p, and DSS combines ElGamal and Schnorr ideas so that both signature parts are computed modulo a smaller prime q.
- The elliptic curve digital signature algorithm (ECDSA) is the elliptic curve version of DSS and gives comparable security with much shorter keys.
- Applications of digital signatures include public-key certificates, signed software, secure e-mail, time-stamped signatures that stop replay of old signed documents, and blind signatures for electronic voting.
- Needham–Schroeder and Otway–Rees are KDC protocols that use nonces so an old session key cannot be replayed, and large networks use flat or hierarchical multiple KDCs.
- Kerberos uses an authentication server, a ticket-granting server and the real server; tickets carry session keys and lifetimes, and timestamped authenticators stop replay.
Learn these by heart
- HMAC(K, M) = H[(K+ ⊕ opad) ‖ H[(K+ ⊕ ipad) ‖ M]], with ipad = 0x36 and opad = 0x5C repeated to the block size.
- SHA-512 padding: L + P + 128 is a multiple of 1024, where P is 1 to 1024 bits (one 1 bit, then zeros).
- Whirlpool (Miyaguchi–Preneel): Hi = W(Hi−1, Mi) ⊕ Hi−1 ⊕ Mi, with H0 = 0 and Hi−1 as the cipher key.
- Hash attack costs for an n-bit digest: preimage and second preimage about 2^n trials, collision about 2^(n/2).
- RSA signature: S = D^d mod n; the verifier accepts if S^e mod n equals the digest D.
- ElGamal signature verification: accept if e1^M ≡ e2^S1 × S1^S2 (mod p), where e2 = e1^d mod p.
- Pairwise secret keys for n users: n(n − 1)/2 without a KDC, n with a KDC.
2-mark questions
1 Distinguish between a modification detection code (MDC) and a message authentication code (MAC). 2 marks
An MDC is a keyless digest h(M). It reveals a change to the message only if the digest itself reaches the receiver safely, and it does not identify the sender.
A MAC is computed from the message and a secret key K shared by sender and receiver, for example h(K ‖ M), so it gives integrity and sender authentication over an insecure channel.
2 State the three security criteria that a cryptographic hash function must satisfy. 2 marks
- Preimage resistance: given a digest d, finding M with h(M) = d is infeasible.
- Second preimage resistance: given M, finding M' ≠ M with h(M') = h(M) is infeasible.
- Collision resistance: finding any pair M ≠ M' with h(M) = h(M') is infeasible.
For an ideal n-bit digest these attacks cost about 2^n, 2^n and 2^(n/2) trials.
3 How many padding bits does SHA-512 add to a 1500-bit message, and how many blocks does the padded message have? 2 marks
The message, the padding P and the 128-bit length field together must be a multiple of 1024 bits, so P = (−1500 − 128) mod 1024 = (−1628) mod 1024 = 420.
The padding is one 1 bit followed by 419 zeros. Total = 1500 + 420 + 128 = 2048 bits, that is two 1024-bit blocks.
4 Which security services does a digital signature provide, and which service does it not provide? 2 marks
A digital signature provides message authentication (only the holder of the private key could have signed), message integrity (any change makes verification fail) and nonrepudiation (with a trusted centre, the signer cannot deny signing).
It does not provide confidentiality: the message is readable unless it is also encrypted.
5 What is a blind digital signature? Give one application. 2 marks
In a blind signature the requester hides (blinds) the message with a random factor r, so the signer signs it without seeing its content; the requester then removes r and holds a valid signature on the original message.
With RSA: send M × r^e mod n, receive M^d × r mod n, multiply by r^(−1) mod n. It is used in electronic voting and digital cash.
6 Why is a key distribution centre (KDC) used? How many secret keys do 100 users need with and without one? 2 marks
Without a KDC every pair of users needs its own secret key: n(n − 1)/2 = 100 × 99 / 2 = 4,950 keys.
With a KDC each user shares one long-term key with the centre, so only 100 keys are needed, and the KDC creates a temporary session key whenever two users want to communicate.
10-mark questions
1 What is message integrity? Explain how a cryptographic hash function provides it, and describe the random oracle model and the attack costs it predicts. 10 marks
Message integrity means that the receiver can be sure the message has not been changed, by accident or by an attacker, after it left the sender. It is different from confidentiality: a message may be public and still need protection from change.
1. Message and digest. Alice passes the message M through a cryptographic hash function h and obtains a short, fixed-length digest h(M), the fingerprint of the message. She sends M over the insecure channel and makes sure the digest reaches Bob unchanged, for example over a trusted channel or by publishing it. Bob computes a new digest of the message he receives and compares it with the digest from Alice. He will accept if they are equal; otherwise he knows the message was changed. A digest used this way is called a modification detection code (MDC).
2. Why the digest must be protected. An MDC has no key, so anyone can compute it. An attacker who can change both M and its digest goes undetected. When no trusted channel exists, a keyed MAC (message authentication) is needed instead.
3. Security criteria. A hash function used for integrity must be:
- preimage resistant: given a digest d, finding any M with h(M) = d is infeasible;
- second preimage resistant: given M, finding M' ≠ M with h(M') = h(M) is infeasible;
- collision resistant: finding any pair M ≠ M' with the same digest is infeasible.
4. The random oracle model. This is an idealised model of a perfect hash function, used to judge real hash functions and to prove schemes secure. The oracle behaves as follows:
- given a new message of any length, it returns a fixed-length digest chosen at random and records the pair;
- given a message it has seen before, it returns the recorded digest;
- the digest of a new message is independent of all earlier digests, so no formula links them.
Because messages are unlimited while digests have only n bits, collisions must exist (the pigeonhole principle); the model says only that they cannot be found faster than by trying.
5. Attack cost in the model, for an n-bit digest:
- preimage or second preimage attack: about 2^n trials;
- collision attack: about 2^(n/2) trials, by the birthday paradox. With k ≈ 1.18 × 2^(n/2) random messages, the chance of a collision is about one half.
For a 512-bit digest, as in SHA-512 or Whirlpool, a collision search needs about 2^256 trials, far beyond any computer.
Conclusion: a hash function gives integrity only when its digest is protected, and the random oracle model shows how long the digest must be; the collision bound 2^(n/2) decides the digest length.
2 Explain message authentication. How does a MAC work? Describe HMAC and CMAC with a neat diagram. 10 marks
A plain digest (MDC) proves only that a message is unchanged, and only when the digest travels safely. Message authentication goes further: Bob must also be sure that the message came from Alice. A message authentication code (MAC) gives both by mixing a secret key K, shared by Alice and Bob, into the digest.
1. Basic MAC. Alice computes MAC = h(K ‖ M) and sends M with the MAC over the insecure channel. Bob, who holds K, recomputes the MAC from the received message and compares. Without K, an attacker who changes M should not be able to produce the matching MAC. A MAC gives integrity and data-origin authentication but not nonrepudiation, because Bob could have made the same MAC himself.
2. Nested MAC. With an iterated hash such as SHA-512, the single keyed hash h(K ‖ M) is open to a length-extension attack: an attacker can append the padding and extra blocks to M and compute a valid MAC without K. So the hashing is done twice: first h(K ‖ M), then a second hash of K joined to that result. HMAC is the standard form of this idea.
3. HMAC. HMAC works with any hash function H whose block size is b bits (b = 1024 for SHA-512):
- If K is longer than b bits, hash it first; then pad it with zeros to b bits, giving the padded key K+.
- Inner hash: XOR K+ with ipad (the byte 0x36 repeated) and hash (K+ ⊕ ipad) ‖ M to get the inner digest.
- Outer hash: XOR K+ with opad (the byte 0x5C repeated) and hash (K+ ⊕ opad) ‖ inner digest.
HMAC(K, M) = H[(K+ ⊕ opad) ‖
H[(K+ ⊕ ipad) ‖ M]]The output is as long as the hash digest (512 bits with SHA-512) and may be truncated. Because the hash function is used as a black box, a better hash function can be substituted later.
4. CMAC. CMAC builds a MAC from a block cipher such as AES instead of a hash function:
- Compute L = E_K(0…0), the encryption of an all-zero block, and derive two subkeys k1 = L·x and k2 = L·x² (in GF(2^128) for AES).
- Split M into blocks and chain them through the cipher as in CBC mode, starting from a zero block.
- Before the last encryption, XOR the last block with k1 if it is complete, or pad it with a 1 bit and zeros and XOR it with k2.
- The final ciphertext block, or its leftmost bits, is the MAC.
5. Security. Since an attacker may try every key or guess MAC values, the key and the MAC must both be long enough.
Conclusion: a MAC protects integrity and authenticates the sender with a shared key; HMAC (hash-based) and CMAC (cipher-based) are the two standard constructions.
3 Describe SHA-512: message padding, word expansion, and the compression function with its round function. 10 marks
SHA-512 is a member of the SHA-2 family of hash functions standardised by NIST. It produces a 512-bit digest from a message of fewer than 2^128 bits, processing it in 1024-bit blocks. It follows the iterated (Merkle–Damgård) design: a compression function is applied to each block in turn, carrying a 512-bit intermediate digest from one block to the next.
1. Padding and length field. Append a single 1 bit and then 0 bits until the length is 896 mod 1024, then append the original length L as a 128-bit number. The padding is P = (−L − 128) mod 1024 bits; if this gives 0, a full 1024 bits are added, because the 1 bit is always present. For L = 1500, P = 420 and the total is 2048 bits, two blocks.
2. Initialisation. Eight 64-bit buffers A, B, C, D, E, F, G and H hold the digest. Their initial values are the first 64 bits of the fractional parts of the square roots of the first eight primes (2 to 19); for example A starts as 6A09E667F3BCC908 (hex).
3. Word expansion. Each 1024-bit block gives sixteen 64-bit words W0 to W15. The other 64 words are made from earlier ones, so that 80 words feed the 80 rounds (ROTRn is a right rotation by n bits, SHRn a right shift by n bits):
Wt = σ1(Wt−2) + Wt−7
+ σ0(Wt−15) + Wt−16 (mod 2^64)
σ0(x) = ROTR1 ⊕ ROTR8 ⊕ SHR7
σ1(x) = ROTR19 ⊕ ROTR61 ⊕ SHR64. Compression function. The previous digest is loaded into A to H and 80 rounds, numbered 0 to 79, run. Round t uses word Wt and a constant Kt; the 80 constants are the first 64 bits of the fractional parts of the cube roots of the first 80 primes (2 to 409). Each round computes, using the values from before the round:
T1 = H + Σ1(E) + Ch(E,F,G) + Kt + Wt
T2 = Σ0(A) + Maj(A,B,C)
H=G G=F F=E E=D+T1
D=C C=B B=A A=T1+T2Here Ch(E,F,G) = (E AND F) ⊕ (NOT E AND G), Maj(A,B,C) = (A AND B) ⊕ (A AND C) ⊕ (B AND C), Σ0(A) = ROTR28 ⊕ ROTR34 ⊕ ROTR39 and Σ1(E) = ROTR14 ⊕ ROTR18 ⊕ ROTR41. All additions are mod 2^64.
5. Final addition. After round 79, each buffer is added (mod 2^64) to its value from the previous digest; this feed-forward gives the new digest that is passed to the next block. After the last block, the eight buffers joined together form the 512-bit digest.
Conclusion: with 1024-bit blocks, 80 rounds and a 512-bit digest, SHA-512 has a collision (birthday) bound of about 2^256 trials.
4 Explain the Whirlpool hash function: its overall structure, the block cipher W with its round functions, and its key expansion. 10 marks
Whirlpool is a 512-bit cryptographic hash function designed by Vincent Rijmen (a co-designer of AES) and Paulo Barreto, and adopted in the ISO/IEC 10118-3 standard. Unlike SHA-512, it is built from a dedicated block cipher, called W, whose design closely follows AES.
1. Preparation. The message is padded with a 1 bit and then 0 bits until its length is 256 mod 512, and a 256-bit field holding the original length is appended. The result is split into 512-bit blocks M1, M2, …, Mt. For a 1000-bit message the padding is 280 bits and the total is 1536 bits, three blocks.
2. Iteration (Miyaguchi–Preneel scheme). The initial digest H0 is 512 zero bits. For each block:
Hi = W(Hi−1, Mi) ⊕ Hi−1 ⊕ MiThe previous digest Hi−1 is the cipher key, the message block Mi is the plaintext, and the ciphertext is combined with both by XOR. The last Hi is the 512-bit digest.
3. The state. Cipher W treats a 512-bit block as an 8 × 8 matrix of bytes (AES uses 4 × 4). The plaintext block is first XORed with the key (an initial AddRoundKey) and then goes through 10 rounds.
4. The round function. Each round applies four transformations:
- SubBytes: every byte is replaced through one 8-bit S-box (256 entries), built from small 4-bit boxes (E, its inverse and R), giving nonlinearity.
- ShiftColumns: column j is rotated cyclically down by j positions (j = 0 to 7), so each row then holds one byte from each of the eight original rows.
- MixRows: each row is multiplied by a fixed circulant matrix whose first row is (01, 01, 04, 01, 08, 05, 02, 09), in GF(2^8) with the irreducible polynomial x^8 + x^4 + x^3 + x^2 + 1, so each output byte depends on all eight bytes of its row.
- AddRoundKey: the state is XORed with the 512-bit round key.
5. Key expansion. The round keys come from the same round function applied to the key, with round constants in place of round keys: K0 is the cipher key (Hi−1) and Kr = round(Kr−1, RCr) for r = 1 to 10. Row 0 of the constant RCr holds eight successive S-box entries, S[8(r−1)] to S[8(r−1)+7]; its other rows are zero.
6. Comparison with AES. Whirlpool uses a 64-byte state, MixRows in place of MixColumns, ShiftColumns in place of ShiftRows, and a fixed 10 rounds with a key schedule that reuses the round function.
Conclusion: Whirlpool combines an AES-like cipher with the Miyaguchi–Preneel construction to give a 512-bit digest; like SHA-512, its collision bound is about 2^256 trials.
5 Explain the digital signature process, the services it provides and the attacks on it. Illustrate the RSA signature scheme with p = 13, q = 17, e = 5 and a digest value of 19. 10 marks
A digital signature binds a message to its signer so that anyone can check who signed it. Unlike a MAC, it uses a key pair: only the signer can create it, but everyone can verify it.
1. Process.
- Alice computes the digest D = h(M), because public-key operations on a long message would be slow.
- She signs the digest with her private key, giving the signature S, and sends M and S to Bob.
- Bob hashes the received message, verifies S with Alice's public key and compares the two results; he will accept if they match, otherwise he will reject.
The key roles are the reverse of encryption: the private key signs and the public key verifies.
2. Services.
- Message authentication: only the holder of Alice's private key could produce S.
- Message integrity: a changed message gives a different digest, so verification fails.
- Nonrepudiation: Alice cannot later deny signing; a trusted centre that keeps signed records settles disputes.
- Confidentiality is not provided; M must be encrypted separately if it is secret.
3. Attacks. By what Eve has: a key-only attack (only Alice's public key), a known-message attack (some message–signature pairs) or a chosen-message attack (Alice signs messages Eve chooses). By the result: existential forgery (a valid pair for some message Eve cannot choose) or selective forgery (a valid signature on a message Eve chose).
4. RSA signature example (small numbers; real moduli are thousands of bits long).
- Keys: n = 13 × 17 = 221, φ(n) = 12 × 16 = 192, e = 5 (gcd(5, 192) = 1) and d = 77, since 5 × 77 = 385 = 2 × 192 + 1.
- Signing the digest D = 19: S = 19^77 mod 221. By CRT and Fermat's little theorem: 19 ≡ 6 (mod 13) and 6^(77 mod 12) = 6^5 = 7776 ≡ 2 (mod 13); 19 ≡ 2 (mod 17) and 2^(77 mod 16) = 2^13 = 8192 ≡ 15 (mod 17). The number below 221 that is 2 mod 13 and 15 mod 17 is S = 15.
- Verifying: 15^2 = 225 ≡ 4, 15^4 ≡ 4^2 = 16 and 15^5 ≡ 16 × 15 = 240 ≡ 19 (mod 221). This equals D, so Bob accepts. If an altered message has digest 20, then 19 ≠ 20 and he rejects.
- Raw RSA without hashing allows existential forgery by a key-only attack: Eve picks S = 10 and computes 10^5 mod 221 = 108, so the pair (message 108, signature 10) verifies. Signing the digest defeats this, because Eve cannot find a message whose digest is 108.
Conclusion: a digital signature gives authentication, integrity and nonrepudiation; RSA, ElGamal, Schnorr, DSS and ECDSA (elliptic curve DSA) are the main schemes.
6 How are symmetric keys distributed with a key distribution centre? Explain Kerberos, its servers and its message exchange. 10 marks
Symmetric-key encryption needs a shared secret key for every pair of users: n(n − 1)/2 keys for n users (4,950 for 100 users). A key distribution centre (KDC) removes this burden. Each user shares one long-term key with the KDC (n keys in all); when Alice wants to talk to Bob, the KDC creates a fresh session key, delivers it to both under their KDC keys, and the key is discarded when the session ends. Large networks use several KDCs, flat or in a hierarchy, and protocols such as Needham–Schroeder and Otway–Rees add nonces so that an old session key cannot be replayed.
Kerberos, developed at MIT, is an authentication protocol that also works as a KDC. It uses three servers:
- Authentication server (AS): the KDC; it holds every user's password-derived key and issues the ticket-granting ticket.
- Ticket-granting server (TGS): issues tickets for real servers, so the password is needed only once per login.
- Real server (Bob): provides the service, such as file storage or printing.
Operation (Alice, the client, wants a service from Bob):
1. Alice sends her identity and the TGS name to the AS in plaintext, a request for a ticket-granting ticket (TGT). 2. The AS replies with a message encrypted under Alice's long-term key. It holds a session key K(A-TGS) and the TGT, which is encrypted under the TGS key. Alice's workstation turns her password into that key and decrypts, so the password never crosses the network. 3. Alice sends the TGT, Bob's name and an authenticator (a timestamp encrypted with K(A-TGS)) to the TGS. The timestamp stops replay. 4. The TGS checks them and sends a new session key K(A-B) encrypted with K(A-TGS), and a ticket for Bob holding K(A-B), encrypted under Bob's key. 5. Alice sends Bob his ticket with a new authenticator, a timestamp encrypted with K(A-B). 6. Bob decrypts the ticket, recovers K(A-B), checks the timestamp and returns timestamp + 1 encrypted with K(A-B), which proves he is genuine (mutual authentication).
Within its lifetime the TGT can be reused to obtain tickets for other servers without the password.
Realms and versions: a realm is one organisation's AS and TGS, and the TGS of one realm can issue a ticket for the TGS of another. Version 4, now obsolete, used only DES and short ticket lifetimes; Version 5 allows other encryption algorithms and longer lifetimes, and encodes messages in ASN.1.
Conclusion: Kerberos turns a KDC into single sign-on: the password-derived key is used once to obtain a TGT, and short-lived session keys protect everything after it.
Network Security and System Security
Syllabus: Security at the application layer: PGP and S/MIME; Security at the transport layer: SSL and TLS; IPsec: its two modes and two security protocols; Security association, IKE and ISAKMP; Users, trust and trusted systems; Buffer overflow; Malicious software: worms and viruses; Intrusion detection systems (IDS); Firewalls
One-page revision summary
- PGP gives five services: authentication (a signed hash), confidentiality (a one-time session key wrapped with the receiver's public key), compression (ZIP), e-mail compatibility (radix-64) and segmentation.
- PGP relies on a web of trust in which users sign one another's public keys, while S/MIME relies on X.509 certificates issued by certificate authorities.
- An SSL/TLS session is created by the handshake and can be shared by many connections; each connection is a transient link that belongs to one session.
- SSL 2.0, SSL 3.0, TLS 1.0 and TLS 1.1 are deprecated, and TLS 1.2 and TLS 1.3 are the versions in current use.
- HTTPS is HTTP carried over TLS, by default on TCP port 443.
- AH authenticates a packet but does not encrypt it, ESP encrypts it and can also authenticate it, and both carry an SPI and a sequence number for anti-replay.
- Transport mode protects the payload between two hosts (AH also authenticates the IP header fields that do not change), and tunnel mode wraps the whole packet in a new IP header, as in a VPN between gateways.
- The Security Policy Database (SPD) decides for each packet whether to discard it, bypass IPsec or protect it, and the Security Association Database (SAD) holds the parameters of each active SA.
- In IKEv1, main mode uses six messages and protects the peers' identities, aggressive mode uses three messages and exposes them, and quick mode uses three messages to create the IPsec SAs.
- IKE uses Diffie-Hellman with cookies against clogging attacks and nonces against replay, ISAKMP messages travel over UDP port 500, and IKEv2 has replaced IKEv1.
- Access control relates users (subjects) to objects through an access matrix, stored by column as access control lists or by row as capability tickets.
- A trusted system is one whose reference monitor can be verified to enforce the security policy, and its audit file records security-relevant events such as detected violations.
- Multilevel security with no read up and no write down defeats a Trojan horse that tries to copy sensitive data into a file that a lower-level user can read.
- Stack buffer overflows come from unchecked copies such as gets() or strcpy(), and stack canaries, non-executable stacks and ASLR make them much harder to exploit.
- A virus needs a host program and user action to spread, while a worm is a standalone program that spreads by itself across a network.
- Polymorphic viruses change their appearance with every copy and metamorphic viruses rewrite their own code, so plain signature scanning struggles against both.
- Anomaly detection can find new attacks but raises more false alarms, while signature detection is precise for known attacks but misses new ones.
- Because intrusions are rare, even a 1% false-alarm rate can make most alarms false, and a honeypot helps because any activity on it is suspicious.
- Packet filters check headers only, stateful firewalls also track connections, application-level gateways (proxies) inspect content, and circuit-level gateways such as SOCKS relay TCP connections.
- A firewall cannot stop attacks that bypass it, threats from insiders or content it cannot inspect, so it is combined with intrusion detection.
Learn these by heart
- PGP sender order: sign (hash + A's private key) → compress (ZIP) → encrypt with session key Ks (Ks under B's public key) → radix-64.
- Radix-64: every 3 bytes become 4 printable characters, a 33% expansion.
- An SA is one-way and is identified by SPI + destination IP address + security protocol identifier (AH or ESP).
- AH = IP protocol 51, integrity and authentication only; ESP = IP protocol 50, confidentiality plus optional integrity.
- TLS record steps: fragment (at most 2^14 bytes) → optional compression → MAC → encrypt → 5-byte header.
- Reference monitor: complete mediation, isolation, verifiability. Bell-LaPadula: no read up, no write down.
- Virus phases: dormant → propagation → triggering → execution.
- P(intrusion | alarm) = P(alarm | intrusion) × P(intrusion) / P(alarm).
2-mark questions
1 What is S/MIME, and which four kinds of protected message can it create? 2 marks
S/MIME (Secure/Multipurpose Internet Mail Extensions) adds security to MIME e-mail using X.509 certificates and the Cryptographic Message Syntax. It can create enveloped data (encrypted content plus an encrypted session key), signed data, clear-signed data (still readable without S/MIME software) and signed-and-enveloped data. Its trust rests on certificate authorities, unlike the web of trust in PGP.
2 What is a security association in IPsec, and how is it identified? 2 marks
A security association (SA) is a one-way agreement between a sender and a receiver that fixes the protocol (AH or ESP), algorithms, keys, mode and lifetime used to protect their traffic. It is identified by three parameters: the Security Parameters Index (SPI), the destination IP address and the security protocol identifier. Two-way traffic needs two SAs.
3 How are IKE and ISAKMP related, and what are the two phases of IKE? 2 marks
ISAKMP is the framework that defines the message formats and procedures for creating, negotiating and deleting SAs; IKE is the Diffie-Hellman-based key exchange protocol that runs inside it. In IKEv1, phase 1 (main or aggressive mode) builds a protected IKE SA, and phase 2 (quick mode) uses it to set up the IPsec SAs for AH or ESP.
4 What is a reference monitor? State its three required properties. 2 marks
A reference monitor is the controlling element in the hardware and operating system of a trusted system that checks every access by a subject (a user or process) to an object (a file, memory area or device) against their security parameters. Its properties are complete mediation (every access is checked), isolation (it is tamper-proof) and verifiability (its correctness can be proved).
5 State the two rules of the Bell-LaPadula multilevel security model. 2 marks
Every subject and object has a security level.
- No read up (simple security property): a subject may read only objects at or below its own level.
- No write down (*-property): a subject may write only to objects at or above its own level.
Together they stop information flowing from a higher level to a lower one, so even a Trojan horse cannot leak data downward.
6 What is a buffer overflow attack? Give two defences against it. 2 marks
A buffer overflow occurs when a program writes more data into a fixed-size buffer than it can hold, overwriting adjacent memory. On the stack, an attacker overwrites the saved return address so that the function returns into injected code. Defences: bounds-checked input functions and stack canaries; a non-executable stack and address space layout randomisation (ASLR) also help.
10-mark questions
1 Explain how PGP provides authentication and confidentiality for an e-mail message. Why does PGP sign before compressing and compress before encrypting? 10 marks
Pretty Good Privacy (PGP) is an e-mail and file security scheme that combines a hash function, public-key cryptography and a symmetric cipher. It gives five services: authentication, confidentiality, compression, e-mail compatibility and segmentation.
Sender side, when user A sends message M to user B:
1. Authentication: A computes a hash of M (for example with SHA-256) and signs the hash with A's private key, using RSA or DSA. This digital signature is prefixed to M.
2. Compression: the signature and M together are compressed with ZIP.
3. Confidentiality: A generates a random one-time session key Ks and encrypts the compressed block with a symmetric cipher such as AES, CAST-128, IDEA or 3DES. Ks itself is encrypted with B's public key (RSA or ElGamal) and prefixed to the ciphertext.
4. E-mail compatibility: radix-64 conversion turns the binary block into printable ASCII, every 3 bytes becoming 4 characters, a 33% expansion. For example, the bytes 48 69 21 (hex, the text "Hi!") become SGkh.
5. Segmentation: a very long result is broken into segments that fit mail size limits.
Receiver side: B reverses the radix-64 conversion, uses B's private key to recover Ks, decrypts and decompresses the block, then uses A's public key to check the signature against a fresh hash of M. A valid signature proves that M came from A and was not altered.
Why this order:
- Sign before compressing: the signature is computed on the uncompressed message, so B can store M with its signature and verify it later without compressing it again. Different versions of ZIP may also compress the same message differently, which would break verification.
- Compress before encrypting: compression removes redundancy, which makes cryptanalysis harder, and less data has to be encrypted.
Public keys are kept in key rings (a private-key ring and a public-key ring) and are vouched for through the web of trust, in which users sign one another's public keys instead of relying on a central certificate authority.
In short, PGP signs for authentication, encrypts with a one-time session key for confidentiality, and adds compression and radix-64 conversion so that the result travels safely through ordinary e-mail.
2 Describe the SSL/TLS protocol stack. Explain the operation of the Record Protocol and the four phases of the Handshake Protocol. 10 marks
Secure Sockets Layer (SSL) and its standardised successor, Transport Layer Security (TLS), provide a secure channel between two applications over TCP, with confidentiality, message integrity and server (optionally client) authentication. SSL 2.0, SSL 3.0, TLS 1.0 and TLS 1.1 are deprecated; current systems use TLS 1.2 or TLS 1.3, but the structure below is common to them.
Protocol stack: TLS runs above TCP (which runs over IP) and below the application. The Record Protocol is the lower layer; above it run the Handshake, Change Cipher Spec and Alert protocols and the application data, such as HTTP (which gives HTTPS).
A session is an association created by the Handshake Protocol that fixes the cipher suite and the master secret, and several connections can share it. A connection is one transient transport link, and each connection belongs to one session.
Record Protocol, at the sender:
1. Fragment the application data into blocks of at most 2^14 = 16384 bytes.
2. Optionally compress (disabled in practice, and removed in TLS 1.3).
3. Compute a MAC (HMAC in TLS) over the sequence number, the header fields and the fragment.
4. Encrypt the fragment and the MAC with the symmetric key agreed in the handshake.
5. Prepend a 5-byte header: content type, protocol version and length.
The receiver decrypts, verifies the MAC, decompresses and reassembles.
Handshake Protocol (TLS 1.2 style), in four phases:
1. Establish security capabilities: client_hello (version, client random, session ID, offered cipher suites) and server_hello (chosen suite, server random).
2. Server authentication and key exchange: certificate, server_key_exchange if needed, an optional certificate_request, then server_hello_done.
3. Client authentication and key exchange: the client's certificate if it was requested, client_key_exchange (the pre-master secret encrypted with the server's RSA key, or a Diffie-Hellman value) and, after a client certificate, certificate_verify.
4. Finish: each side sends change_cipher_spec and then finished, the first message protected with the new keys, which proves that both sides computed the same master secret.
Change Cipher Spec is a single one-byte message that makes the pending security state current. An Alert message carries two bytes, a level (warning or fatal) and a code such as bad_record_mac; a fatal alert ends the connection.
TLS 1.3 cuts the handshake to one round trip, drops RSA key transport so that a full handshake uses (EC)DHE for forward secrecy, allows only AEAD ciphers such as AES-GCM, and encrypts every handshake message after server_hello.
Thus the handshake authenticates the server and agrees on keys, and the Record Protocol then uses those keys to protect every message.
3 Explain the transport and tunnel modes of IPsec and its two security protocols, AH and ESP, showing how each one protects an IP packet. 10 marks
IPsec protects traffic at the network layer, so every application above IP is protected without being changed. It offers two security protocols, and each can be used in two modes. The algorithms and keys for a flow are held in a security association (SA), which every IPsec packet names by its 32-bit Security Parameters Index (SPI).
Two modes:
1. Transport mode protects the payload of the IP packet (the TCP or UDP segment). The IPsec header is inserted between the original IP header and the payload, so the original addresses stay visible. It is used end to end between two hosts, such as host A and host B in the figure.
2. Tunnel mode protects the whole original IP packet, which becomes the payload of a new IP packet with a new outer header, usually carrying the addresses of two security gateways. It is used for gateway-to-gateway or host-to-gateway VPNs, as between gateway G1 and gateway G2 serving host C and host D: C sends a plain IP packet to G1, G1 wraps it for G2, and G2 unwraps it and delivers the plain IP packet to D. With ESP it also hides the real source and destination.
Two security protocols:
1. Authentication Header (AH, IP protocol 51) gives data integrity, data origin authentication and anti-replay protection, but no confidentiality. Its fields are next header, payload length, SPI, sequence number and the integrity check value (ICV). The ICV covers the payload and the IP header fields that do not change in transit, so AH fails through NAT, which rewrites addresses.
2. Encapsulating Security Payload (ESP, IP protocol 50) gives confidentiality by encryption and, optionally, integrity, origin authentication and anti-replay. It adds an ESP header (SPI, sequence number), an ESP trailer (padding, pad length, next header) and an optional ICV. Its ICV does not cover the outer IP header.
Packet layouts (NewIP = new outer IP header, Data = the TCP or UDP segment, Trl = ESP trailer):
AH, transport mode:
IP | AH | Data
AH, tunnel mode:
NewIP | AH | IP | Data
ESP, transport mode:
IP | ESP | Data | Trl | ICV
(encrypted: Data and Trl)
ESP, tunnel mode:
NewIP | ESP | IP | Data | Trl | ICV
(encrypted: IP, Data and Trl)The sequence number in both headers, checked against a sliding window at the receiver, rejects replayed packets.
In short, AH proves origin and integrity, ESP adds secrecy, transport mode suits host-to-host links and tunnel mode builds VPNs. Because ESP can also authenticate, it is the more widely used of the two.
4 What is a firewall? Explain the types of firewall and the screened-subnet (DMZ) firewall configuration. 10 marks
A firewall is a device or program placed between a trusted internal network and an untrusted network such as the Internet. All traffic in both directions must pass through it, only traffic allowed by the local security policy may pass, and the firewall itself must resist attack.
Types of firewall:
1. Packet-filtering firewall: applies rules to each IP packet using the source and destination IP addresses, the protocol, the source and destination ports and the TCP flags, then forwards or discards it. It is fast and simple, but it does not examine application data and keeps no memory of earlier packets. It is open to IP address spoofing, source-routing attacks and tiny-fragment attacks.
2. Stateful inspection firewall: also keeps a table of open TCP connections, so an inbound packet is accepted only if it belongs to a connection that an inside host started. Replies to high-numbered client ports are then allowed without opening those ports to everyone.
3. Application-level gateway (proxy): the user connects to the proxy, which authenticates the user and relays the request, for example HTTP or SMTP, to the real server. It can inspect and log content and allow only chosen commands, at the cost of extra processing for each connection.
4. Circuit-level gateway: sets up two TCP connections, one with the inside host and one with the outside host, and relays bytes between them without examining content; SOCKS is an example. It suits outbound connections from trusted internal users.
A bastion host is a hardened system, running only the necessary proxy services, that acts as the strong point of the firewall.
Screened-subnet (DMZ) configuration:
An outer firewall faces the Internet and an inner firewall guards the internal network. Between them lies the demilitarised zone (DMZ), a separate subnet holding the public web server and mail server. The outer firewall admits only web and mail traffic into the DMZ, and the inner firewall lets very little pass from the DMZ to the internal network. An attacker who takes over a DMZ server still faces a second firewall, and internal addresses stay hidden from the Internet. A simpler screened-host configuration uses one packet-filtering router and a single bastion host.
Limitations: a firewall cannot stop attacks that bypass it (an infected laptop carried inside, or an unmanaged wireless link), threats from insiders, or harmful content it cannot inspect, such as encrypted traffic. It is therefore combined with intrusion detection and host security.
In summary, packet filters and stateful firewalls work on network and transport headers, gateways work at the application or session level, and a DMZ places public servers between two layers of defence.
5 Distinguish a virus from a worm. Explain the phases and types of viruses, and describe how a worm spreads, including its use of a buffer overflow. 10 marks
Malicious software (malware) is code inserted into a system to harm its confidentiality, integrity or availability. Viruses and worms are its two classic self-replicating kinds.
Virus versus worm:
- A virus is a fragment of code that attaches itself to a host program, document or boot sector and runs only when the host runs, so it needs human action, such as opening a file, to spread.
- A worm is a complete, standalone program that copies itself from computer to computer over a network on its own, usually by exploiting a software flaw, with no host program or user action.
A virus has three parts: an infection mechanism (how it spreads), a trigger (the event that activates it) and a payload (what it does besides spreading).
Phases of a virus:
1. Dormant: the virus is idle, waiting for an event such as a date (not every virus has this phase).
2. Propagation: it places copies of itself into other programs or disk areas.
3. Triggering: the chosen event activates it.
4. Execution: the payload runs, anything from a harmless message to deleting files.
Types of virus:
- By target: boot sector infector, file infector (executable programs) and macro virus (inside documents, run by the application's macro language).
- By concealment: encrypted virus (body encrypted with a changing key), stealth virus (hides its changes from antivirus software), polymorphic virus (changes its appearance with every copy) and metamorphic virus (rewrites its own code with every copy).
How a worm spreads: it scans for targets (network addresses or e-mail contacts), exploits a flaw to get in, copies itself over and runs on the new host, which then repeats the cycle. Many worms exploit a buffer overflow. A network service copies attacker-supplied input into a fixed-size stack buffer without checking its length; the extra bytes overwrite the saved return address, so the function returns into the attacker's code and the worm runs with the service's privileges. The Morris worm used such an overflow in the fingerd daemon, and Code Red used one in Microsoft's IIS web server.
Countermeasures: patch known flaws; use bounds-checked functions, stack canaries, non-executable stacks and address space layout randomisation; and run antivirus software that combines signature scanning, heuristics and behaviour blocking. Firewalls and intrusion detection limit worm traffic.
In short, a virus needs a host and a user, while a worm travels by itself, often through a buffer overflow.
6 What is an intrusion detection system? Explain anomaly and signature detection, host-based and network-based IDS, and why false alarms matter. 10 marks
An intruder is someone who gains, or tries to gain, unauthorised access to a system: a masquerader (an outsider using a stolen identity), a misfeasor (an insider misusing privileges) or a clandestine user (one who seizes supervisory control to evade auditing). An intrusion detection system (IDS) monitors host and network activity, detects such intrusions and raises alerts, on the assumption that an intruder behaves measurably differently from a legitimate user.
Components:
1. Sensors collect data: audit records on a host or packets on a network.
2. Analyzers examine the data and decide whether an intrusion has occurred.
3. A user interface (manager) shows alerts to the security administrator and lets the administrator configure the system.
Detection approaches:
1. Statistical anomaly detection builds a profile of normal behaviour from data gathered over a training period. Threshold detection counts events, such as failed logins per hour, and alarms above a limit; profile-based detection compares each user's current activity with that user's own profile. It can catch new attacks but raises more false alarms.
2. Rule-based (signature or misuse) detection matches activity against signatures of known attacks, such as the packet pattern of a known worm. It gives few false alarms for known attacks but misses new ones until the signature database is updated.
Host-based versus network-based:
- A host-based IDS (HIDS) runs on one computer and watches its audit records, system calls and file changes; it sees data that arrived encrypted once the host has decrypted it.
- A network-based IDS (NIDS) places sensors on network segments, for example in the DMZ and on the internal network, and examines packets in real time; one sensor watches many hosts, but it cannot read encrypted traffic.
False alarms and the base rate: suppose 1 event in 10,000 is an intrusion, the IDS detects 99% of intrusions and wrongly flags 1% of normal events. In 1,000,000 events there are 100 intrusions, giving 99 true alarms, and 999,900 normal events, giving 9,999 false alarms. So P(intrusion | alarm) = 99 / (99 + 9,999) = 99 / 10,098 ≈ 0.98%: fewer than 1 alarm in 100 is real. An IDS must therefore keep its false-alarm rate very low.
A honeypot, a decoy system with no real users, complements an IDS: any activity on it is suspicious, so it gathers information about attackers while diverting them from real systems.
Thus an IDS is a second line of defence behind the firewall, detecting intrusions that prevention did not stop.
Public sources that settled doubtful points
Only the points the second AI pass doubted were looked up. These are the pages that confirmed or contradicted them; nothing here is copied from them.
44 pages
- FIPS 197 Advanced Encryption Standard (AES), NIST
- RFC 7748: Elliptic Curves for Security
- NIST SP 800-57 Part 1 Rev. 5, Recommendation for Key Management
- Length extension attack - Wikipedia
- RFC 5246: The Transport Layer Security (TLS) Protocol Version 1.2
- NIST to Withdraw Special Publication 800-67 Revision 2 (NIST CSRC)
- ITU-T Recommendation X.800: Security architecture for Open Systems Interconnection for CCITT applications
- CCITT Recommendation X.800 text (MIT copy)
- Attack model - Wikipedia
- Passive attack - NIST CSRC Glossary
- Hill cipher - Wikipedia
- Solving Linear Congruences - Number Theory: In Context and Interactive (Gordon College)
- Modular multiplicative inverse - Wikipedia
- Data Encryption Standard (Wikipedia)
- Meet-in-the-middle attack (Wikipedia)
- Triple DES (Wikipedia)
- Advanced Encryption Standard (Wikipedia)
- Rauzy and Guilley, Formal Analysis of CRT-RSA Vigilant's Countermeasure Against the BellCoRe Attack (arXiv 1401.8172)
- Miller-Rabin primality test - Wikipedia
- Carmichael number - Wikipedia
- Rabin cryptosystem - Wikipedia
- Hasse's theorem on elliptic curves - Wikipedia
- Whirlpool (hash function) - Wikipedia
- Kerberos Version 4 End of Life Announcement - MIT Kerberos
- Kerberos V5 - Raj Jain, CSE 571, Washington University in St. Louis
- RFC 1510: The Kerberos Network Authentication Service (V5)
- Kerberos (protocol) - Wikipedia
- SHA-2 - Wikipedia
- RFC 2104: HMAC: Keyed-Hashing for Message Authentication
- RFC 4493: The AES-CMAC Algorithm
- Random oracle - Wikipedia
- Bellare and Rogaway, Random Oracles are Practical (abstract)
- RFC 6176: Prohibiting Secure Sockets Layer (SSL) Version 2.0
- RFC 7568: Deprecating Secure Sockets Layer Version 3.0
- RFC 8996: Deprecating TLS 1.0 and TLS 1.1
- RFC 2409: The Internet Key Exchange (IKE)
- RFC 4306: Internet Key Exchange (IKEv2) Protocol
- RFC 9395: IKEv1 Deprecation
- RFC 7296: Internet Key Exchange Protocol Version 2 (IKEv2)
- Internet Security Association and Key Management Protocol (Wikipedia)
- Internet Key Exchange (Wikipedia)
- Reference monitor (Wikipedia)
- Morris worm (Wikipedia)
- Buffer overflow (Wikipedia)
Further reading
Titles only, for your own study. Nothing on this page is copied from them. The units follow the official JNTUK R23 CSE syllabus (PDF) ↗.
- Cryptography and Network Security · Behrouz A. Forouzan and Debdeep Mukhopadhyay
- Cryptography and Network Security: Principles and Practice · William Stallings
- Everyday Cryptography · Keith M. Martin
- Network Security and Cryptography · Bernard Menezes