GTU 3170720 Information security (IS) Winter 2025 Solved Paper & Solutions

A substitution technique in cryptography is a method where letters, numbers, or symbols of a plaintext message are replaced by other letters, symbols, or groups of letters according to a predefined system or key.

1. Caesar Cipher (Shift Cipher) (Monoalphabetic)
2. Monoalphabetic Cipher (Arbitrary letter permutation)
3. Playfair Cipher (Digraphic substitution using a $5 \times 5$ matrix)
4. Hill Cipher (Polygraphic substitution using linear matrix algebra)
5. Polyalphabetic Cipher (Vigenère Cipher) (Multiple substitution alphabets driven by a keyword)
6. One-Time Pad (Vernam Cipher) (Unconditionally secure random key XOR)

• Mechanism: Each plaintext letter $p$ is replaced by the letter shifted $k$ positions down the alphabet:

• Example with Key $k = 3$:
• Plaintext: GTU
• G (6) $+ 3 = 9 \implies$ J
• T (19) $+ 3 = 22 \implies$ W
• U (20) $+ 3 = 23 \implies$ X
• Ciphertext: JWX

The primary objective of an adversary (cryptanalyst) is to:

1. Recover the original plaintext from the intercepted ciphertext.
2. Deduce the secret key $K$, allowing the adversary to decrypt all past and future communications encrypted with that key.

1. Cryptanalysis:

• Relies on the mathematical nature of the encryption algorithm, statistical characteristics of the plaintext language, and sample plaintext-ciphertext pairs.
• Types of Attacks:
• Ciphertext-Only: Adversary has only intercepted ciphertexts.
• Known-Plaintext: Adversary has matched pairs of plaintext and ciphertext.
• Chosen-Plaintext: Adversary can feed chosen plaintexts to the encryptor and observe outputs.
• Chosen-Ciphertext: Adversary can submit chosen ciphertexts to be decrypted.

2. Brute-Force Attack:

• Trying every possible key in the entire key space $\mathcal{K}$ on a piece of ciphertext until an intelligible English plaintext is produced.
• On average, half the key space must be searched ($2^{k-1}$ trials for a $k$-bit key). A 128-bit key ($2^{128} \approx 3.4 \times 10^{38}$ keys) renders brute force computationally infeasible.

Block ciphers operate on fixed-size blocks (e.g., 64 or 128 bits). For longer messages, standard NIST modes are:

1. Electronic Codebook (ECB)
2. Cipher Block Chaining (CBC)
3. Cipher Feedback (CFB)
4. Output Feedback (OFB)
5. Counter Mode (CTR)

• 1) Authentication:

The assurance that a communicating entity is genuine and who it claims to be. It guarantees that the sender of a message is indeed the claimed originator and that the transmission was not forged or replayed by an impersonator.

• 2) Data Integrity:

The assurance that data received is exactly as sent by an authorized party, without unauthorized alteration, modification, insertion, deletion, or reordering during transit. Implemented using cryptographic hashes (SHA-256) and MACs.

• 3) Data Confidentiality:

The protection of transmitted data from passive attacks and unauthorized disclosure to unauthorized individuals, entities, or processes. Implemented using symmetric and asymmetric encryption (AES, RSA).

1. Extract unique letters from keyword: e - n - g - i - r (omit duplicate e, n, g).
2. Note: I and J share the same cell.
3. Fill remaining letters of alphabet in alphabetical order:

• Remove spaces: TESTTHISPROCESS
• Pair into digrams:
• TE
• ST
• TH
• IS
• PR
• OC
• ES
• S $\to$ single letter at end, append filler X $\to$ SX

1. TE: $T(4,4)$ and $E(1,1)$ form a rectangle $\to$ corners are $P(4,1)$ and $I(1,4) \implies$ PI
2. ST: $S(4,3)$ and $T(4,4)$ are in the same row $\to$ shift right $\implies$ TU
3. TH: $T(4,4)$ and $H(3,1)$ form a rectangle $\to$ corners are $P(4,1)$ and $M(3,4) \implies$ PM
4. IS: $I(1,4)$ and $S(4,3)$ form a rectangle $\to$ corners are $G(1,3)$ and $T(4,4) \implies$ GT
5. PR: $P(4,1)$ and $R(1,5)$ form a rectangle $\to$ corners are $U(4,5)$ and $E(1,1) \implies$ UE
6. OC: $O(3,5)$ and $C(2,3)$ form a rectangle $\to$ corners are $L(3,3)$ and $F(2,5) \implies$ LF
7. ES: $E(1,1)$ and $S(4,3)$ form a rectangle $\to$ corners are $G(1,3)$ and $P(4,1) \implies$ GP
8. SX: $S(4,3)$ and $X(5,3)$ are in the same column $\to$ shift down (wrap around) $\implies$ XC

Diffie-Hellman enables two parties (Alice and Bob) to establish a shared secret key over an insecure public channel without sending the key itself.

• Public Global Parameters:
• A large prime number $q$.
• An integer $\alpha$ that is a primitive root of $q$.

1. Alice:

• Chooses private key $X_A < q$.
• Computes public key: $Y_A = \alpha^{X_A} \pmod q$.
• Sends $Y_A$ publicly to Bob.

2. Bob:

• Chooses private key $X_B < q$.
• Computes public key: $Y_B = \alpha^{X_B} \pmod q$.
• Sends $Y_B$ publicly to Alice.

3. Shared Secret Key Calculation:

• Alice computes: $K = (Y_B)^{X_A} \pmod q = (\alpha^{X_B})^{X_A} \pmod q = \alpha^{X_A X_B} \pmod q$.
• Bob computes: $K = (Y_A)^{X_B} \pmod q = (\alpha^{X_A})^{X_B} \pmod q = \alpha^{X_A X_B} \pmod q$.
• Both obtain the exact same secret key $K$.
• Security Basis: Eavesdroppers intercepting $Y_A$ and $Y_B$ cannot calculate $K$ due to the intractability of the Discrete Logarithm Problem for large $q$.

• Vulnerability: Standard Diffie-Hellman provides no entity authentication.
• Attack Mechanism:

1. Adversary Darth intercepts Alice's public key $Y_A$ and sends his own key $Y_{D1}$ to Bob, pretending to be Alice.
2. Darth intercepts Bob's public key $Y_B$ and sends his own key $Y_{D2}$ to Alice, pretending to be Bob.
3. Alice establishes secret key $K_1 = \alpha^{X_A X_{D2}} \pmod q$ with Darth.
4. Bob establishes secret key $K_2 = \alpha^{X_B X_{D1}} \pmod q$ with Darth.
5. When Alice sends an encrypted message, Darth decrypts it with $K_1$, reads/alters it, re-encrypts it with $K_2$, and forwards it to Bob undetected.

• Prevention: Diffie-Hellman must be combined with Digital Signatures or Public Key Certificates (PKI) to authenticate public keys before exchange.

In the Advanced Encryption Standard (AES), the State Array is a two-dimensional $4 \times 4$ matrix of bytes that holds the intermediate cryptographic results throughout all transformation rounds:

• For AES-128, the 128-bit (16-byte) input block is loaded into the State array column by column.
• All round transformations (SubBytes, ShiftRows, MixColumns, AddRoundKey) operate directly on this State array in-place.

• The ShiftRows transformation shifts the rows of the $4 \times 4$ State array cyclically to the left:
• Row 0: Not shifted (0 bytes affected).
• Row 1: 1-byte circular left shift (4 bytes shifted).
• Row 2: 2-byte circular left shift (4 bytes shifted).
• Row 3: 3-byte circular left shift (4 bytes shifted).
• Total bytes affected:

(Only the 4 bytes of Row 0 remain in their original positions).

• Definition: Given a cryptographic hash value $h$, it is computationally infeasible to find any message $x$ such that:

• Significance: Ensures password security. Even if an attacker steals the stored hash database, they cannot reverse the hashes to recover users' plain passwords.

• Definition: Given a specific message $x$, it is computationally infeasible to find another distinct message $y \ne x$ such that they produce the exact same hash:

• Significance: Essential for digital signatures. An attacker who intercepts a digitally signed document $x$ cannot forge another malicious document $y$ that produces the identical hash.

AES is a symmetric non-Feistel block cipher operating on a 128-bit block with variable key lengths:

• AES-128: 10 rounds, 128-bit key.
• AES-192: 12 rounds, 192-bit key.
• AES-256: 14 rounds, 256-bit key.

Each round (except the final round) executes four transformation functions on the $4 \times 4$ State array.

1. SubBytes (Non-linear Byte Substitution):

• Uses an S-box lookup table constructed from multiplicative inverses in finite field $GF(2^8)$ followed by affine transformation. Provides confusion.

2. ShiftRows (Row Permutation):

• Cyclically shifts row $i$ by $i$ bytes to the left ($0, 1, 2, 3$). Provides diffusion across columns.

3. MixColumns (Linear Column Mixing):

• Each column of the State is multiplied by a fixed matrix in $GF(2^8)$. Omitted in the final round.

4. AddRoundKey (Key Whitening):

• The 128-bit State is XORed with a 128-bit Round Key derived from the Key Expansion schedule.

• Takes the original 128-bit (4-word) key $K$ and generates 44 words ($W[0]$ to $W[43]$) to supply 11 round keys (initial round + 10 rounds):
• For words where $i$ is not a multiple of 4:

• For words where $i$ is a multiple of 4:

• The complex function $g()$ performs:

1. RotWord: Circular left byte shift of the 4-byte word: $[b_0, b_1, b_2, b_3] \to [b_1, b_2, b_3, b_0]$.
2. SubWord: S-box substitution on all 4 bytes.
3. Round Constant XOR ($Rcon[j]$): XORs with round constant $[RC[j], 0, 0, 0]$.

A monoalphabetic cipher is a substitution cipher where each letter of the plaintext alphabet is mapped to a fixed, unique letter of the ciphertext alphabet throughout the entire encryption process.

• The substitution alphabet remains constant from the first letter to the last.

• Key Space: Any permutation of the 26 letters of the English alphabet:

• Vulnerability: Despite having an enormous key space immune to brute force, monoalphabetic ciphers are easily broken using Frequency Analysis because they preserve the natural statistical frequency distribution of the underlying language (e.g., in English, 'E', 'T', 'A' remain the most frequent letters).

• Choose a large prime $q$ and a primitive root $\alpha$ modulo $q$.
• Private Key: Select random integer $X_A$ such that $1 < X_A < q-1$.
• Public Key: Compute $Y_A = \alpha^{X_A} \pmod q$.

To sign a message $M$ (or hash $m = H(M)$):

1. Choose a secret random integer $K$ such that $\gcd(K, q-1) = 1$.
2. Compute:

3. Compute $S_2$:

• The signature is the pair: $(S_1, S_2)$.

The receiver verifies the signature using public key $\{q, \alpha, Y_A\}$:

1. Compute:

2. Compute:

3. Accept the signature if and only if $V_1 \equiv V_2 \pmod q$.

Kerberos is a trusted third-party centralized network authentication protocol developed by MIT. It uses symmetric-key cryptography to allow clients and servers to authenticate each other over an insecure network without transmitting passwords in cleartext.

1. Client / User: Requests access to a network application service.
2. Authentication Server (AS):

• Verifies user credentials against a secure central database.
• Issues a Ticket Granting Ticket (TGT) encrypted with the TGS master key.

3. Ticket Granting Server (TGS):

• Receives TGT and authenticator from client.
• Issues a Service Ticket granting access to the requested application server.

4. Key Distribution Center (KDC):

• The trusted authority hosting both the AS and TGS.

5. Application / Service Server:

• Validates the service ticket presented by the client and delivers the requested service.

• The Threat: An eavesdropper intercepts a valid ticket and attempts to reuse it later to gain unauthorized access.
• Kerberos Defense Mechanism:

1. Short-Lived Timestamps in Authenticators: The client sends an Authenticator containing the client ID and current timestamp $T$, encrypted with the shared session key:

2. Replay Cache: The server checks that $|T - T_{\text{server}}| < \text{Tolerance}$ (typically $\le 5$ minutes). The server also logs recently received $(T, \text{ID}_C)$ pairs in a replay cache to discard duplicate packets.
3. Ticket Lifetime Expiration: Tickets contain explicit lifetime windows ($8 - 10$ hours), after which they automatically expire.

A Nonce ("number used once") is a random or non-repeating value generated for a specific protocol exchange. It acts as a challenge to verify that a communication exchange is fresh and to prevent Replay Attacks.

DES takes a 64-bit input key and generates sixteen 48-bit subkeys ($K_1$ to $K_{16}$), one for each Feistel round.

1. Permuted Choice 1 (PC-1):

• Discards 8 parity bits (bits 8, 16, 24, 32, 40, 48, 56, 64) from the 64-bit key.
• Permutes the remaining 56 bits and splits them into two 28-bit halves: $C_0$ and $D_0$.

2. Circular Left Shifts:

• For each round $i = 1$ to 16, $C_{i-1}$ and $D_{i-1}$ are cyclically left-shifted by:
• 1 bit: in rounds 1, 2, 9, 16.
• 2 bits: in rounds 3, 4, 5, 6, 7, 8, 10, 11, 12, 13, 14, 15.
• Total shift across 16 rounds = $4 \times 1 + 12 \times 2 = 28$ bits (restoring original orientation).

3. Permuted Choice 2 (PC-2):

• Combines $C_i$ and $D_i$ (56 bits total) and selects 48 bits via compression permutation to form round subkey $K_i$.

The SHA family consists of cryptographic hash functions standardized by NIST:

1. Padding: Append a '1' bit followed by '0' bits until length $\equiv 896 \pmod{1024}$.
2. Append Length: Append a 128-bit unsigned integer representing original message length.
3. Initialize Hash Buffer: Initialize working variables with fixed hex constants derived from square roots of primes.
4. Compression Function: Processes each 1024-bit block through 80 rounds of non-linear logical functions ($Ch, Maj, \Sigma, \sigma$), updating the hash state.

1. Data Integrity: Any single bit alteration in the original message produces an entirely unpredictable change in the hash (Avalanche Effect).
2. Digital Signatures: Instead of encrypting the entire multi-megabyte document with slow asymmetric keys, the sender signs the compact SHA-256 digest:

3. HMAC (Hash-based Message Authentication Codes): Combines a secret key with SHA to authenticate network packets in IPsec and SSL/TLS.
4. Password Storage: Systems store $\text{SHA-256}(\text{Password} \parallel \text{Salt})$ rather than plaintext passwords.