Skip to content
CampusPrep
CS-703 (A) · Cryptography & Information Security/Quick Revision Short Notes

Cryptography & Information Security (CS-703 (A)) - Unit 3 Short Notes

How unit 3 is examined

This unit covers authentication, hashing, signatures and Kerberos; SHA-512 and DSS carry the most marks, then Kerberos, then MD5, hash-function comparison, message authentication and public-key distribution.

Message Authentication

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Low weight</span>

Definition. <mark>Message authentication is the procedure that lets the receiver verify that a received message is genuine, unaltered, in the right sequence and from the claimed sender.</mark>

Key points.

  1. Disclosure is release of message contents to someone who does not hold the key, and it is countered by encryption.
  2. Traffic analysis is discovering the pattern of traffic, such as frequency and length of messages between parties.
  3. Masquerade is insertion of messages from a fraudulent source, and content modification is changing the contents of a message.
  4. Sequence modification is inserting, deleting or reordering messages, and timing modification is delaying or replaying messages.
  5. Source repudiation (sender denies sending) and destination repudiation (receiver denies receiving) are countered only by a digital signature.
  6. Lower level: an authentication function (message encryption, MAC or hash) produces an authenticator, a value used to authenticate the message.
  7. Higher level: an authentication protocol uses that function so the receiver can verify the message is authentic.
  8. A MAC, $MAC = C_K(M)$, gives authentication with a shared secret key, while a digital signature adds non-repudiation.

Answer frame. Open with the definition; list the six attacks one line each; then explain the two levels; close with the MAC versus digital signature link.

Asked: [7 marks] (Nov 2023) What are the types of attacks addressed by message authentication? What are the two levels of functionality that comprise a message authentication or digital signature mechanism?

Digital Signature

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Not asked since 2022</span>

Definition. <mark>A digital signature is a value computed from the message and the signer's private key, which anyone can verify with the signer's public key.</mark>

Key points.

  1. It gives authentication, message integrity and non-repudiation, which a MAC cannot give because the key is shared.
  2. In RSA signing, $S = H(M)^d \bmod n$ and verification checks $S^e \bmod n = H(M)$.
  3. The signature depends on the message, so it cannot be moved to another document.
  4. Direct signatures involve only sender and receiver, while arbitrated signatures use a trusted third party.

Key Management

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Low weight</span>

Definition. <mark>Key management is the generation, distribution, storage and replacement of cryptographic keys; public-key management mainly means distributing public keys so that they can be trusted.</mark>

Key points.

  1. Public announcement: users broadcast their public keys, which is simple but anyone can forge such an announcement.
  2. Publicly available directory: a trusted directory holds name and public key entries, which users register and update securely, but the directory can be tampered with.
  3. Public-key authority: the authority hands out signed current public keys on request, which is secure but a bottleneck as every user must contact it.
  4. Public-key certificates: a certificate authority signs the binding of identity and public key, so users exchange certificates without contacting the authority each time.
  5. The X.509 certificate and PKI carry the owner, public key, validity and the CA signature.
  6. Security rises and overhead rises in the order announcement, directory, authority, certificates; certificates give the best balance.

Asked: [7 marks] (Nov 2022) Explain in short different method of distribution of public key management.

Key Exchange

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Not asked since 2022</span>

Definition. <mark>Key exchange (key agreement) lets two parties establish a shared secret over an insecure channel, as in Diffie-Hellman.</mark>

Key points.

  1. Public values are a prime $q$ and a primitive root $\alpha$; A picks secret $X_A$ and sends $Y_A = \alpha^{X_A} \bmod q$, B does likewise.
  2. Both compute $K = Y_B^{X_A} \bmod q = Y_A^{X_B} \bmod q = \alpha^{X_A X_B} \bmod q$.
  3. Security rests on the discrete logarithm problem.
  4. Plain Diffie-Hellman is open to a man-in-the-middle attack unless the values are authenticated.

Hash Function

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Low weight</span>

Definition. ==A hash function $H$ maps a message of any length to a fixed-length digest, $h = H(M)$.==

Key points.

  1. Properties: it accepts any input size, gives fixed output, is easy to compute, is one-way (preimage resistant), and is weak- and strong-collision resistant.
  2. A hash gives integrity: any change in $M$ changes the digest, so the digest is sent with the message or signed.
  3. MD5 gives a 128-bit digest and SHA-1 a 160-bit one, so brute-force effort is $2^{64}$ and $2^{80}$ by the birthday bound.
  4. Example: MD5 of the empty string is d41d8cd98f00b204e9800998ecf8427e, and MD5("abc") is 900150983cd24fb0d6963f7d28e17f72; SHA-1("abc") is a9993e36...d89d.
Feature MD5 SHA (SHA-1 / SHA-512)
Digest size 128 bits 160 bits (SHA-1), 512 bits (SHA-512)
Block size 512 bits 512 bits (SHA-1), 1024 bits (SHA-512)
Steps 64 (4 rounds of 16) 80
Word / registers 32-bit, 4 registers 32-bit, 5 registers (SHA-1); 64-bit, 8 (SHA-512)
Length field 64 bits 64 bits (SHA-1), 128 bits (SHA-512)
Speed Faster Slower
Security Collisions found, broken SHA-1 collisions found; SHA-2 secure

Answer frame. Open with the definition and properties; then the comparison table; give the digest examples; close that SHA-2 is preferred over MD5.

Asked: [7 marks] (Dec 2025) Define Hash Function. Differentiate between MD5 and SHA algorithms with suitable examples.

Universal Hashing

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Not asked since 2022</span>

Definition. <mark>A universal hash family is a set of hash functions such that, for a randomly chosen member $h$, any two distinct keys collide with probability at most $1/m$.</mark>

Key points.

  1. Formally, $\Pr[h(x) = h(y)] \le 1/m$ for all $x \ne y$, where $m$ is the output range.
  2. A common family is $h_{a,b}(x) = ((ax + b) \bmod p) \bmod m$ with random $a, b$ and prime $p$.
  3. Random choice defeats an adversary who tries to pick inputs that collide.
  4. It is used in hash tables and in Wegman-Carter message authentication.

Cryptographic Hash Function

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Not asked since 2022</span>

Definition. <mark>A cryptographic hash function is a hash function that is one-way and collision resistant, so it is computationally infeasible to invert or to find two inputs with the same digest.</mark>

Key points.

  1. Preimage resistance: given $h$, finding $M$ with $H(M) = h$ is infeasible.
  2. Second-preimage resistance: given $M_1$, finding $M_2 \ne M_1$ with the same hash is infeasible.
  3. Collision resistance: finding any pair $M_1 \ne M_2$ with $H(M_1) = H(M_2)$ is infeasible, and the birthday bound makes it cost about $2^{n/2}$.
  4. It is used for digital signatures, MACs, password storage and integrity checks.

MD (MD5)

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Low weight</span>

Definition. <mark>MD5 is a hash algorithm that takes a message of any length and produces a 128-bit message digest, processing it in 512-bit blocks.</mark>

Key points.

  1. Padding: append a single 1 bit then 0 bits until the length is 448 mod 512.
  2. Append length: add the original length as a 64-bit value so the total is a multiple of 512 bits.
  3. Initialise the 128-bit buffer as four 32-bit registers A = 67452301, B = EFCDAB89, C = 98BADCFE, D = 10325476 (hex).
  4. Each 512-bit block is processed in four rounds of 16 steps each, 64 steps in total.
  5. Each round uses a different function of B, C, D: $F = (B \wedge C) \vee (\neg B \wedge D)$, $G = (B \wedge D) \vee (C \wedge \neg D)$, $H = B \oplus C \oplus D$, $I = C \oplus (B \vee \neg D)$.
  6. Each step uses one 32-bit message word, a constant $T_i$ from the sine table and a left rotation.
  7. The output of the fourth round is added modulo $2^{32}$ to the block's input registers, and the final ABCD is the 128-bit digest.

<figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u3-01" viewBox="0 0 492.8 80" width="492.8" height="80" role="img" aria-label="MD5: message M, padding and 64-bit length, 512-bit blocks, four rounds of 16 steps updating A B C D, 128-bit digest D"><style>#dsfig-u3-01 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u3-01 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u3-01 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u3-01 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u3-01 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u3-01 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u3-01 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u3-01 .t{fill:#16181D;font-weight:500}#dsfig-u3-01 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u3-01 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u3-01 .dot{fill:#16181D}#dsfig-u3-01 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u3-01 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u3-01 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u3-01 .ah{fill:#454C5A}#dsfig-u3-01 .ah.hi{fill:#2340B8}#dsfig-u3-01 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u3-01 .wl .t{font-size:12px;font-weight:700}#dsfig-u3-01 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u3-01 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u3-01 .e{stroke:#B1B7C3}html.dark #dsfig-u3-01 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u3-01 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u3-01 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u3-01 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u3-01 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u3-01 .t{fill:#E6E8ED}html.dark #dsfig-u3-01 .t.inv{fill:#0F1115}html.dark #dsfig-u3-01 .kd{stroke:#E6E8ED}html.dark #dsfig-u3-01 .dot{fill:#E6E8ED}html.dark #dsfig-u3-01 .ann{fill:#8FA3FF}html.dark #dsfig-u3-01 .lbl{fill:#858D9C}html.dark #dsfig-u3-01 .ptr{fill:#8FA3FF}html.dark #dsfig-u3-01 .ah{fill:#B1B7C3}html.dark #dsfig-u3-01 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u3-01 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u3-01 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u3-01 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah6" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah" d="M0,1 L9,5 L0,9 z"/></marker><marker id="ahh6" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah hi" d="M0,1 L9,5 L0,9 z"/></marker></defs><path class="e" d="M59,40 L122.2,40" marker-end="url(#ah6)"/><path class="e" d="M162.2,40 L225.4,40" marker-end="url(#ah6)"/><path class="e" d="M265.4,40 L328.6,40" marker-end="url(#ah6)"/><path class="e" d="M368.6,40 L431.8,40" marker-end="url(#ah6)"/><g class="wl"><rect x="74.8" y="31" width="33.6" height="18" rx="9"/><text class="t" x="91.6" y="40" dy=".35em" text-anchor="middle">pad</text></g><g class="wl"><rect x="178" y="31" width="33.6" height="18" rx="9"/><text class="t" x="194.8" y="40" dy=".35em" text-anchor="middle">512</text></g><g class="wl"><rect x="277.6" y="31" width="40.8" height="18" rx="9"/><text class="t" x="298" y="40" dy=".35em" text-anchor="middle">4rnd</text></g><g class="wl"><rect x="380.8" y="31" width="40.8" height="18" rx="9"/><text class="t" x="401.2" y="40" dy=".35em" text-anchor="middle">ABCD</text></g><circle class="n" cx="40" cy="40" r="18"/><text class="t" x="40" y="40" dy=".35em" text-anchor="middle">M</text><circle class="n" cx="143.2" cy="40" r="18"/><text class="t" x="143.2" y="40" dy=".35em" text-anchor="middle">P</text><circle class="n" cx="246.4" cy="40" r="18"/><text class="t" x="246.4" y="40" dy=".35em" text-anchor="middle">B</text><circle class="n" cx="349.6" cy="40" r="18"/><text class="t" x="349.6" y="40" dy=".35em" text-anchor="middle">R</text><circle class="n" cx="452.8" cy="40" r="18"/><text class="t" x="452.8" y="40" dy=".35em" text-anchor="middle">D</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">MD5: message M, padding and 64-bit length, 512-bit blocks, four rounds of 16 steps updating A B C D, 128-bit digest D</figcaption></figure>

Asked: [7 marks] (Nov 2022) What is MD5? Explain MD5 with neat and clean diagram.

Secure Hash Algorithm (SHA)

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">High weight</span>

Definition. <mark>SHA is a family of NIST hash functions built on the Merkle-Damgard iteration; SHA-512 takes a message shorter than $2^{128}$ bits and produces a 512-bit digest.</mark>

<figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u3-02" viewBox="0 0 544.4 252" width="544.4" height="252" role="img" aria-label="SHA-512: message M, padded to a multiple of 1024 bits, blocks B, schedule W (Wt), 80 rounds R on buffer a-h, final addition H, 512-bit digest D"><style>#dsfig-u3-02 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u3-02 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u3-02 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u3-02 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u3-02 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u3-02 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u3-02 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u3-02 .t{fill:#16181D;font-weight:500}#dsfig-u3-02 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u3-02 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u3-02 .dot{fill:#16181D}#dsfig-u3-02 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u3-02 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u3-02 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u3-02 .ah{fill:#454C5A}#dsfig-u3-02 .ah.hi{fill:#2340B8}#dsfig-u3-02 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u3-02 .wl .t{font-size:12px;font-weight:700}#dsfig-u3-02 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u3-02 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u3-02 .e{stroke:#B1B7C3}html.dark #dsfig-u3-02 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u3-02 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u3-02 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u3-02 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u3-02 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u3-02 .t{fill:#E6E8ED}html.dark #dsfig-u3-02 .t.inv{fill:#0F1115}html.dark #dsfig-u3-02 .kd{stroke:#E6E8ED}html.dark #dsfig-u3-02 .dot{fill:#E6E8ED}html.dark #dsfig-u3-02 .ann{fill:#8FA3FF}html.dark #dsfig-u3-02 .lbl{fill:#858D9C}html.dark #dsfig-u3-02 .ptr{fill:#8FA3FF}html.dark #dsfig-u3-02 .ah{fill:#B1B7C3}html.dark #dsfig-u3-02 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u3-02 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u3-02 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u3-02 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah7" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah" d="M0,1 L9,5 L0,9 z"/></marker><marker id="ahh7" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah hi" d="M0,1 L9,5 L0,9 z"/></marker></defs><path class="e" d="M59,126 L105,126" marker-end="url(#ah7)"/><path class="e" d="M145,126 L191,126" marker-end="url(#ah7)"/><path class="e" d="M225.4,112.6 L283.2,54.8" marker-end="url(#ah7)"/><path class="e" d="M225.4,139.4 L283.2,197.2" marker-end="url(#ah7)"/><path class="e" d="M298,59 L298,191" marker-end="url(#ah7)"/><path class="e" d="M312.6,199.8 L385.1,139.4" marker-end="url(#ah7)"/><path class="e" d="M420.2,126 L483.4,126" marker-end="url(#ah7)"/><g class="wl"><rect x="66.2" y="117" width="33.6" height="18" rx="9"/><text class="t" x="83" y="126" dy=".35em" text-anchor="middle">pad</text></g><g class="wl"><rect x="148.6" y="117" width="40.8" height="18" rx="9"/><text class="t" x="169" y="126" dy=".35em" text-anchor="middle">1024</text></g><g class="wl"><rect x="284.8" y="117" width="26.4" height="18" rx="9"/><text class="t" x="298" y="126" dy=".35em" text-anchor="middle">Wt</text></g><g class="wl"><rect x="326.1" y="160" width="47.1" height="18" rx="9"/><text class="t" x="349.6" y="169" dy=".35em" text-anchor="middle">80rnd</text></g><g class="wl"><rect x="436" y="117" width="33.6" height="18" rx="9"/><text class="t" x="452.8" y="126" dy=".35em" text-anchor="middle">sum</text></g><circle class="n" cx="40" cy="126" r="18"/><text class="t" x="40" y="126" dy=".35em" text-anchor="middle">M</text><circle class="n" cx="126" cy="126" r="18"/><text class="t" x="126" y="126" dy=".35em" text-anchor="middle">P</text><circle class="n" cx="212" cy="126" r="18"/><text class="t" x="212" y="126" dy=".35em" text-anchor="middle">B</text><circle class="n" cx="298" cy="40" r="18"/><text class="t" x="298" y="40" dy=".35em" text-anchor="middle">W</text><circle class="n" cx="298" cy="212" r="18"/><text class="t" x="298" y="212" dy=".35em" text-anchor="middle">R</text><circle class="n" cx="401.2" cy="126" r="18"/><text class="t" x="401.2" y="126" dy=".35em" text-anchor="middle">H</text><circle class="n" cx="504.4" cy="126" r="18"/><text class="t" x="504.4" y="126" dy=".35em" text-anchor="middle">D</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">SHA-512: message M, padded to a multiple of 1024 bits, blocks B, schedule W (Wt), 80 rounds R on buffer a-h, final addition H, 512-bit digest D</figcaption></figure>

Steps.

  1. Append padding: one 1 bit then 0 bits so the length is 896 mod 1024.
  2. Append length: a 128-bit field holds the original length, making the total a multiple of 1024 bits.
  3. Initialise the hash buffer with eight 64-bit words $H_0 \ldots H_7$ (a-h), the fractional parts of the square roots of the first eight primes.
  4. Process each 1024-bit block $M_i$ through the 80-round compression function, which starts from the current buffer.
  5. Output: after the last block the buffer of eight words is the 512-bit digest.

Compression (per block).

  1. The block is split into sixteen 64-bit words $W_0 \ldots W_{15}$, and the schedule extends them to 80 words with $W_t = \sigma_1(W_{t-2}) + W_{t-7} + \sigma_0(W_{t-15}) + W_{t-16} \bmod 2^{64}$.
  2. Working variables a-h are copied from the chaining value and updated in each round $t$ using constant $K_t$ (from cube roots of the first 80 primes).
  3. Each round computes $T_1 = h + Ch(e,f,g) + \Sigma_1(e) + W_t + K_t$ and $T_2 = \Sigma_0(a) + Maj(a,b,c)$, all modulo $2^{64}$.
  4. Then the words shift: $h = g$, $g = f$, $f = e$, $e = d + T_1$, $d = c$, $c = b$, $b = a$, $a = T_1 + T_2$.
  5. After round 80 each working variable is added modulo $2^{64}$ to the input chaining value, and this sum is the input to the next block.

Collision order. Finding two messages with the same digest by the birthday attack takes about $2^{n/2} = 2^{256}$ operations for SHA-512, while finding a message for a given digest takes $2^{512}$.

Variant Digest Block Word Max message
SHA-1 160 512 32 $2^{64}$
SHA-256 256 512 32 $2^{64}$
SHA-384 384 1024 64 $2^{128}$
SHA-512 512 1024 64 $2^{128}$

Merits and demerits.

  1. Merits: SHA-2 has no practical attacks, it is a NIST standard, and it is widely used in signatures, certificates and TLS.
  2. Demerits: SHA-1 and SHA-0 have weaknesses and practical collisions, and SHA-2 is slower than MD5 with 64-bit arithmetic.
  3. SHA-2 is open to length-extension attacks, which SHA-3 (Keccak) avoids.

Answer frame. For the steps question, open with the definition and draw the diagram; list the five steps, then compression with $W_t$; close with the $2^{256}$ birthday bound. For the compression question, stress schedule, working variables, round functions and final addition. For merit and demerit, give the variants table then the merits and demerits.

Asked: [7 marks] (Dec 2020, Jun 2025) Describe the steps in finding the message digest using SHA-512 algorithm. What is the order of finding two messages having the same message digest? With a neat diagram, explain the steps of SHA producing a 512-bit digest from a message of length less than $2^{128}$ bits. Asked: [7 marks] (Dec 2020) Explain the compression of Secure Hash Algorithm. Asked: [7 marks] (Nov 2022) Explain the Secure Hash Algorithm (SHA) with their Merit and Demerit.

Pitfall: the padding length is 896 mod 1024 with a 128-bit length field; 448 mod 512 and 64 bits belong to MD5 and SHA-1.

Digital Signature Standard (DSS)

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">High weight</span>

Definition. <mark>DSS is the NIST standard (FIPS 186) whose Digital Signature Algorithm (DSA) signs the hash of a message using a private key and verifies it with a public key, based on the discrete logarithm problem.</mark>

<figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u3-03" viewBox="0 0 389.6 252" width="389.6" height="252" role="img" aria-label="DSS: signing hashes M, then S uses private key x and random k to output (r,s); verifying hashes M again and V uses public key y to check v = r"><style>#dsfig-u3-03 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u3-03 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u3-03 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u3-03 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u3-03 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u3-03 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u3-03 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u3-03 .t{fill:#16181D;font-weight:500}#dsfig-u3-03 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u3-03 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u3-03 .dot{fill:#16181D}#dsfig-u3-03 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u3-03 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u3-03 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u3-03 .ah{fill:#454C5A}#dsfig-u3-03 .ah.hi{fill:#2340B8}#dsfig-u3-03 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u3-03 .wl .t{font-size:12px;font-weight:700}#dsfig-u3-03 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u3-03 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u3-03 .e{stroke:#B1B7C3}html.dark #dsfig-u3-03 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u3-03 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u3-03 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u3-03 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u3-03 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u3-03 .t{fill:#E6E8ED}html.dark #dsfig-u3-03 .t.inv{fill:#0F1115}html.dark #dsfig-u3-03 .kd{stroke:#E6E8ED}html.dark #dsfig-u3-03 .dot{fill:#E6E8ED}html.dark #dsfig-u3-03 .ann{fill:#8FA3FF}html.dark #dsfig-u3-03 .lbl{fill:#858D9C}html.dark #dsfig-u3-03 .ptr{fill:#8FA3FF}html.dark #dsfig-u3-03 .ah{fill:#B1B7C3}html.dark #dsfig-u3-03 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u3-03 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u3-03 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u3-03 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah8" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah" d="M0,1 L9,5 L0,9 z"/></marker><marker id="ahh8" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah hi" d="M0,1 L9,5 L0,9 z"/></marker></defs><path class="e" d="M59,40 L122.2,40" marker-end="url(#ah8)"/><path class="e" d="M58.3,45.1 L329.4,120.4" marker-end="url(#ah8)"/><path class="e" d="M162.2,40 L225.4,40" marker-end="url(#ah8)"/><path class="e" d="M261,52.2 L333.5,112.6" marker-end="url(#ah8)"/><path class="e" d="M59,212 L122.2,212" marker-end="url(#ah8)"/><path class="e" d="M160.7,204.7 L330.2,134.1" marker-end="url(#ah8)"/><g class="wl"><rect x="185.2" y="74" width="19.2" height="18" rx="9"/><text class="t" x="194.8" y="83" dy=".35em" text-anchor="middle">M</text></g><g class="wl"><rect x="185.2" y="31" width="19.2" height="18" rx="9"/><text class="t" x="194.8" y="40" dy=".35em" text-anchor="middle">h</text></g><g class="wl"><rect x="281.2" y="74" width="33.6" height="18" rx="9"/><text class="t" x="298" y="83" dy=".35em" text-anchor="middle">r,s</text></g><g class="wl"><rect x="236.8" y="160" width="19.2" height="18" rx="9"/><text class="t" x="246.4" y="169" dy=".35em" text-anchor="middle">h</text></g><circle class="n" cx="40" cy="40" r="18"/><text class="t" x="40" y="40" dy=".35em" text-anchor="middle">M</text><circle class="n" cx="143.2" cy="40" r="18"/><text class="t" x="143.2" y="40" dy=".35em" text-anchor="middle">H</text><circle class="n" cx="246.4" cy="40" r="18"/><text class="t" x="246.4" y="40" dy=".35em" text-anchor="middle">S</text><circle class="n" cx="349.6" cy="126" r="18"/><text class="t" x="349.6" y="126" dy=".35em" text-anchor="middle">V</text><circle class="n" cx="143.2" cy="212" r="18"/><text class="t" x="143.2" y="212" dy=".35em" text-anchor="middle">H2</text><circle class="n" cx="40" cy="212" r="18"/><text class="t" x="40" y="212" dy=".35em" text-anchor="middle">M2</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">DSS: signing hashes M, then S uses private key x and random k to output (r,s); verifying hashes M again and V uses public key y to check v = r</figcaption></figure>

Global and key parameters.

  1. $p$ is a prime of 512 to 1024 bits, $q$ is a 160-bit prime divisor of $p-1$, and $g = h^{(p-1)/q} \bmod p$ with $1 < h < p-1$.
  2. Private key $x$ is random with $0 < x < q$, and public key is $y = g^x \bmod p$.

Signature generation.

  1. Choose a fresh random $k$ with $0 < k < q$ for each signature.
  2. Compute $r = (g^k \bmod p) \bmod q$.
  3. Compute $s = [k^{-1}(H(M) + xr)] \bmod q$; the signature is $(r, s)$.

Verification.

  1. Compute $w = s^{-1} \bmod q$, then $u_1 = [H(M)\,w] \bmod q$ and $u_2 = (r\,w) \bmod q$.
  2. Compute $v = [(g^{u_1} y^{u_2}) \bmod p] \bmod q$.
  3. The signature is valid if $v = r$.

Example. Given $p = 23$, $q = 11$, $g = 4$, $x = 3$, $H(M) = 5$, $k = 7$.

Step Working Value
$y$ $4^3 \bmod 23$ 18
$r$ $(4^7 \bmod 23) \bmod 11$ 8
$s$ $7^{-1}(5 + 3 \cdot 8) \bmod 11 = 8 \cdot 29 \bmod 11$ 1
$w$ $1^{-1} \bmod 11$ 1
$u_1, u_2$ $5 \cdot 1,\ 8 \cdot 1$ 5, 8
$v$ $(4^5 \cdot 18^8 \bmod 23) \bmod 11$ 8

Signature $(8, 1)$ is valid because $v = r = 8$.

Key points.

  1. The hash (SHA-1 originally) is signed, not the message, so any length is handled and integrity is checked.
  2. Security rests on the discrete logarithm problem, so recovering $x$ from $y$ is infeasible.
  3. $k$ must be secret, random and never reused, or $x$ can be computed from the signature.
  4. Unlike RSA, DSA only signs; it cannot encrypt.

Answer frame. Open by defining DSS/DSA and its parameters; draw the sign and verify block diagram; write generation then verification formulas; close with the hash role and discrete-log security.

Asked: [7 marks] (Dec 2020, Nov 2023, Jun 2025, Dec 2025) Define the generation and verification of the digital signature using DSS algorithm. Describe DSS in detail. What is a digital signature? Explain DSS with block diagram. Illustrate the steps in signature generation and verification functions of DSS.

Cryptanalysis: Time-Memory Trade-off Attack

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Not asked since 2022</span>

Definition. <mark>A time-memory trade-off (Hellman) attack precomputes tables of encryption chains so that a key is found faster online than by brute force, using less memory than a full table.</mark>

Key points.

  1. Precomputation walks chains $x \to f(x) \to f(f(x))$ and stores only the start and end points.
  2. Online, the attacker follows the ciphertext along its chain to an end point, then rebuilds the chain from the start to find the key.
  3. For key space $N$, tables of size $M$ give time $T$ with $TM^2 = N^2$.
  4. Rainbow tables reduce chain merging, and salting defeats them.

Differential Cryptanalysis

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Not asked since 2022</span>

Definition. <mark>Differential cryptanalysis (Biham and Shamir) is a chosen-plaintext attack that studies how a chosen difference between two plaintexts propagates to the ciphertext difference.</mark>

Key points.

  1. The attacker picks plaintext pairs with a fixed XOR difference $\Delta P$ and records the ciphertext differences.
  2. Certain differences appear with high probability, which reveals information about the round subkey.
  3. It breaks DES with 16 rounds using about $2^{47}$ chosen plaintexts, which is fewer than $2^{55}$ of brute force.
  4. DES S-boxes were designed to resist it; AES also resists it.

Secure channel and authentication system like Kerberos

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Medium weight</span>

Definition. <mark>Kerberos is a trusted third-party authentication service that uses symmetric keys and tickets so that a client proves its identity to servers without sending its password over the network.</mark>

<figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u3-04" viewBox="0 0 424 252" width="424" height="252" role="img" aria-label="Kerberos: client C, Authentication Server AS, Ticket Granting Server TGS, application server V; messages 1-2 with AS, 3-4 with TGS, 5-6 with V"><style>#dsfig-u3-04 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u3-04 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u3-04 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u3-04 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u3-04 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u3-04 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u3-04 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u3-04 .t{fill:#16181D;font-weight:500}#dsfig-u3-04 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u3-04 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u3-04 .dot{fill:#16181D}#dsfig-u3-04 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u3-04 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u3-04 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u3-04 .ah{fill:#454C5A}#dsfig-u3-04 .ah.hi{fill:#2340B8}#dsfig-u3-04 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u3-04 .wl .t{font-size:12px;font-weight:700}#dsfig-u3-04 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u3-04 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u3-04 .e{stroke:#B1B7C3}html.dark #dsfig-u3-04 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u3-04 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u3-04 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u3-04 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u3-04 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u3-04 .t{fill:#E6E8ED}html.dark #dsfig-u3-04 .t.inv{fill:#0F1115}html.dark #dsfig-u3-04 .kd{stroke:#E6E8ED}html.dark #dsfig-u3-04 .dot{fill:#E6E8ED}html.dark #dsfig-u3-04 .ann{fill:#8FA3FF}html.dark #dsfig-u3-04 .lbl{fill:#858D9C}html.dark #dsfig-u3-04 .ptr{fill:#8FA3FF}html.dark #dsfig-u3-04 .ah{fill:#B1B7C3}html.dark #dsfig-u3-04 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u3-04 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u3-04 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u3-04 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah9" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah" d="M0,1 L9,5 L0,9 z"/></marker><marker id="ahh9" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah hi" d="M0,1 L9,5 L0,9 z"/></marker></defs><path class="e" d="M58.8,116.6 L193.2,49.4" marker-end="url(#ah9)" marker-start="url(#ah9)"/><path class="e" d="M58.8,135.4 L193.2,202.6" marker-end="url(#ah9)" marker-start="url(#ah9)"/><path class="e" d="M61,126 L363,126" marker-end="url(#ah9)" marker-start="url(#ah9)"/><g class="wl"><rect x="109.2" y="74" width="33.6" height="18" rx="9"/><text class="t" x="126" y="83" dy=".35em" text-anchor="middle">1-2</text></g><g class="wl"><rect x="109.2" y="160" width="33.6" height="18" rx="9"/><text class="t" x="126" y="169" dy=".35em" text-anchor="middle">3-4</text></g><g class="wl"><rect x="195.2" y="117" width="33.6" height="18" rx="9"/><text class="t" x="212" y="126" dy=".35em" text-anchor="middle">5-6</text></g><circle class="n" cx="40" cy="126" r="18"/><text class="t" x="40" y="126" dy=".35em" text-anchor="middle">C</text><circle class="n" cx="212" cy="40" r="18"/><text class="t" x="212" y="40" dy=".35em" text-anchor="middle">AS</text><circle class="n" cx="212" cy="212" r="18"/><text class="t" x="212" y="212" dy=".35em" text-anchor="middle">TGS</text><circle class="n" cx="384" cy="126" r="18"/><text class="t" x="384" y="126" dy=".35em" text-anchor="middle">V</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">Kerberos: client C, Authentication Server AS, Ticket Granting Server TGS, application server V; messages 1-2 with AS, 3-4 with TGS, 5-6 with V</figcaption></figure>

Servers and their roles.

  1. The Authentication Server (AS) knows all user passwords, authenticates the user at login and issues a Ticket Granting Ticket (TGT) with session key $K_{c,tgs}$.
  2. The Ticket Granting Server (TGS) accepts a TGT and an authenticator, and issues a service ticket for the requested server with key $K_{c,v}$.
  3. The application server $V$ accepts the service ticket and authenticator and offers the service; it shares a secret key with the TGS.
  4. AS and TGS together form the Key Distribution Center (KDC) of a realm.

Message flow.

  1. C to AS: $ID_c$, $ID_{tgs}$, $TS_1$.
  2. AS to C: $E(K_c, [K_{c,tgs}, ID_{tgs}, TS_2, Lifetime, Ticket_{tgs}])$, opened using a key made from the password.
  3. C to TGS: $ID_v$, $Ticket_{tgs}$, $Authenticator_c$.
  4. TGS to C: $E(K_{c,tgs}, [K_{c,v}, ID_v, TS_4, Ticket_v])$.
  5. C to V: $Ticket_v$, $Authenticator_c$.
  6. V to C: $E(K_{c,v}, [TS_5 + 1])$, which proves the server is genuine.

Inter-realm operation. When client and server sit in different realms, the two TGSs share a secret key, so the client asks its local TGS for a ticket to the remote TGS (a referral ticket), presents it to the remote TGS, and receives a service ticket for the remote server. The local TGS thus acts as a trusted entry to the remote realm, and the client then talks to the remote server as in messages 5-6.

Answer frame. For the servers question, open with the definition, draw the four-party diagram, explain AS, TGS and V in order, then the six messages, and close with timestamps and session keys. For the inter-realm question, draw client, local TGS, remote TGS and remote server, explain the shared key, then the three ticket steps.

Asked: [7 marks] (Dec 2020, Dec 2025) What are the different servers used in Kerberos? Explain the role of each one. Explain Kerberos Authentication System with suitable diagram. Asked: [7 marks] (Jun 2025) Design the role of Ticket Granting Server in inter-realm operations of Kerberos.

Last-minute revision

  • MAC: $C_K(M)$, needs a shared key; a digital signature also gives non-repudiation.
  • Six attacks: disclosure, traffic analysis, masquerade, content, sequence and timing modification.
  • MD5: 128-bit digest, 512-bit block, padding to 448 mod 512, 64-bit length, 4 rounds of 16 steps.
  • SHA-512: 512-bit digest, 1024-bit block, padding to 896 mod 1024, 128-bit length, 80 rounds, 64-bit words.
  • SHA-1: 160-bit digest, 512-bit block, 80 steps.
  • Birthday bound: collision costs $2^{n/2}$, so $2^{256}$ for SHA-512.
  • DSS: $r = (g^k \bmod p) \bmod q$, $s = k^{-1}(H(M) + xr) \bmod q$, check $v = r$.
  • DSS sizes: $q$ is 160 bits, $p$ is 512-1024 bits.
  • Kerberos: AS gives TGT, TGS gives service ticket, then the server gets the ticket and authenticator.
  • Public-key distribution: announcement, directory, authority, certificates.

Memory hooks

  • SHA-512: "1024 in, 896 pad, 128 length, 80 rounds, 512 out".
  • DSS verify: "w, u1, u2, v, then v equals r".
  • Kerberos: "AS gives the pass, TGS gives the ticket, V gives the service".
  • MD5 functions: F, G, H, I for rounds 1 to 4.
  • Public keys: announce, directory, authority, certificate.

Coverage checklist

  • Message Authentication: Nov 2023 attacks and two levels.
  • Digital Signature: covered, and asked under DSS.
  • Key Management: Nov 2022 public-key distribution.
  • Key Exchange: Diffie-Hellman, no past questions.
  • Hash Function: Dec 2025 MD5 versus SHA.
  • Universal Hashing: no past questions.
  • Cryptographic Hash Function: no past questions.
  • MD: Nov 2022 MD5 with diagram.
  • Secure Hash Algorithm (SHA): Dec 2020 compression, Dec 2020 and Jun 2025 SHA-512 steps, Nov 2022 merit and demerit.
  • Digital Signature Standard (DSS): Dec 2020, Nov 2023, Jun 2025, Dec 2025.
  • Cryptanalysis: Time-Memory Trade-off Attack: no past questions.
  • Differential Cryptanalysis: no past questions.
  • Secure channel and authentication system like Kerberos: Dec 2020, Dec 2025 servers, Jun 2025 inter-realm.
Go to where you left off?

Quick Add to Notes

Save questions, your own notes and screenshots into notes filed by unit. It takes a free account.

Create free account

Have an account? Log in