Cryptography

Monoalphabetic vs polyalphabetic cipher

A monoalphabetic cipher (Caesar, general substitution) maps each plaintext letter to one fixed ciphertext letter throughout the message. A polyalphabetic cipher (Vigenere, Vernam) uses several substitution alphabets chosen by the key, so the same plaintext letter can become different ciphertext letters.

The monoalphabetic cipher is more vulnerable. Justification:

• It preserves the letter frequency distribution of the language. In English, E, T, A, O are the most common; the most frequent ciphertext letter is probably E, the next T, and so on. Frequency analysis, together with digraph/trigraph patterns (TH, HE, THE), breaks it quickly.
• The key space of a simple Caesar cipher is only 25, and even the general substitution (26! keys) falls to frequency analysis.
• In a polyalphabetic cipher the frequencies are flattened, because one plaintext letter is spread over several ciphertext letters. It can still be attacked (Kasiski test, index of coincidence) but only after finding the key length, so it is much harder.

Weak keys in DES

DES derives 16 subkeys from the 56-bit key. A key is weak if all 16 subkeys are identical. Then encryption equals decryption: $E_K(E_K(m)) = m$. There are 4 weak keys (in hex, with parity bits):

• 0101010101010101
• FEFEFEFEFEFEFEFE
• E0E0E0E0F1F1F1F1
• 1F1F1F1F0E0E0E0E

They arise when the two 28-bit halves $C_0$, $D_0$ are all 0s or all 1s, so the rotations never change them. Semi-weak keys (12 keys, 6 pairs) are also avoided: they generate only two distinct subkeys, and one key of a pair decrypts what the other encrypts, $E_{K_1}(E_{K_2}(m)) = m$.

Round operation in IDEA

IDEA works on 64-bit blocks with a 128-bit key and has 8 identical rounds plus an output transformation. The block is split into four 16-bit sub-blocks $X_1, X_2, X_3, X_4$. Each round uses six 16-bit subkeys $K_1 \dots K_6$ and three incompatible operations: XOR ($\oplus$), addition mod $2^{16}$ ($\boxplus$), and multiplication mod $2^{16}+1$ ($\odot$).

1. $A = X_1 \odot K_1$
2. $B = X_2 \boxplus K_2$
3. $C = X_3 \boxplus K_3$
4. $D = X_4 \odot K_4$
5. $E = A \oplus C$
6. $F = B \oplus D$
7. $G = (F \boxplus (E \odot K_5)) \odot K_6$
8. $H = (E \odot K_5) \boxplus G$
9. Output of the round: $(A \oplus G,\; C \oplus G,\; B \oplus H,\; D \oplus H)$. The two middle blocks are swapped before the next round (not after the last round).

Steps 5 to 8 form the multiplication-addition (MA) structure. After round 8 the output transformation uses four more subkeys: $Y_1 = X_1 \odot K_1$, $Y_2 = X_2 \boxplus K_2$, $Y_3 = X_3 \boxplus K_3$, $Y_4 = X_4 \odot K_4$. In total $8 \times 6 + 4 = 52$ subkeys are used. They come from the 128-bit key: the first 8 subkeys are the key split into 16-bit pieces, then the key is rotated left by 25 bits and split again, and so on.

Fermat's little theorem

If $p$ is prime and $a$ is an integer not divisible by $p$, then $a^{p-1} \equiv 1 \pmod p$ Equivalently $a^p \equiv a \pmod p$ for every integer $a$.

Example: $p = 7$, $a = 3$: $3^6 = 729 = 104 \times 7 + 1$, so $3^6 \equiv 1 \pmod 7$.

ElGamal encryption

Given $p = 29$, $g = 8$, private key $X = 9$, random $K = 11$, message $m = 13$.

Public key: $Y = g^X \bmod p = 8^9 \bmod 29$.

$8^2 = 64 \equiv 6$, $8^4 \equiv 36 \equiv 7$, $8^8 \equiv 49 \equiv 20$, so $8^9 \equiv 20 \times 8 = 160 \equiv 160 - 145 = 15$.

$Y = 15$

Ciphertext pair $(C_1, C_2)$:

$C_1 = g^K \bmod p = 8^{11} \bmod 29$ $8^{11} = 8^8 \cdot 8^2 \cdot 8 \equiv 20 \times 6 \times 8 = 960 \equiv 960 - 957 = 3$. So $C_1 = 3$.

$C_2 = m \cdot Y^K \bmod p = 13 \times 15^{11} \bmod 29$ $15^2 = 225 \equiv 22$, $15^4 \equiv 484 \equiv 20$, $15^8 \equiv 400 \equiv 23$, so $15^{11} = 15^8 \cdot 15^2 \cdot 15 \equiv 23 \times 22 \times 15$. $23 \times 22 = 506 \equiv 506 - 493 = 13$; $13 \times 15 = 195 \equiv 195 - 174 = 21$. So $Y^K = 21$.

$C_2 = 13 \times 21 = 273 \equiv 273 - 261 = 12$.

Ciphertext = (3, 12).

Check by decryption: $K_s = C_1^X = 3^9 = 19683 \equiv 21 \pmod{29}$ (same as $Y^K$). $21^{-1} \bmod 29 = 18$ since $21 \times 18 = 378 = 13 \times 29 + 1$. $m = 12 \times 18 = 216 \equiv 216 - 203 = 13$. Correct.

Comparison of SHA-1 and SHA-2 parameters

SHA-1 is considered broken for collision resistance, so SHA-2 is preferred. SHA-2 has a larger digest, a more complex message schedule and round function.

Hill cipher decryption of DRJI

Key $K = \begin{pmatrix}7 & 8\\ 11 & 11\end{pmatrix}$.

$\det K = 7 \cdot 11 - 8 \cdot 11 = -11 \equiv 15 \pmod{26}$. Since $\gcd(15, 26) = 1$ the key is invertible. $15^{-1} \bmod 26 = 7$ because $15 \times 7 = 105 = 4 \times 26 + 1$.

$K^{-1} = 7 \begin{pmatrix}11 & -8\\ -11 & 7\end{pmatrix} = \begin{pmatrix}77 & -56\\ -77 & 49\end{pmatrix} \equiv \begin{pmatrix}25 & 22\\ 1 & 23\end{pmatrix} \pmod{26}$

Check: first row of $K$ times first column of $K^{-1}$: $7 \cdot 25 + 8 \cdot 1 = 183 = 7 \times 26 + 1 \equiv 1$. Correct.

Ciphertext pairs: DR = (3, 17), JI = (9, 8).

$P = K^{-1} C$ (column vectors):

• DR: $25 \cdot 3 + 22 \cdot 17 = 75 + 374 = 449 \equiv 449 - 442 = 7$ (H); $1 \cdot 3 + 23 \cdot 17 = 394 \equiv 394 - 390 = 4$ (E).
• JI: $25 \cdot 9 + 22 \cdot 8 = 225 + 176 = 401 \equiv 401 - 390 = 11$ (L); $1 \cdot 9 + 23 \cdot 8 = 193 \equiv 193 - 182 = 11$ (L).

Plaintext = HELL

Discrete logarithm

Let $p$ be prime and $g$ a primitive root of $p$. For any $y$ with $1 \le y \le p-1$ there is a unique exponent $x$ ($0 \le x \le p-2$) such that $y \equiv g^x \pmod p$ The exponent $x$ is the discrete logarithm of $y$ to base $g$ modulo $p$, written $x = \mathrm{dlog}_{g,p}(y)$. Computing $y$ from $x$ is easy (fast modular exponentiation), but finding $x$ from $y$ is computationally hard for large $p$. This one-way property secures Diffie-Hellman, ElGamal and DSA.

Diffie-Hellman key exchange

Public parameters: a large prime $p$ and a primitive root $g$ of $p$.

1. Alice picks a secret $X_A < p$ and computes the public value $Y_A = g^{X_A} \bmod p$.
2. Bob picks a secret $X_B < p$ and computes $Y_B = g^{X_B} \bmod p$.
3. They exchange $Y_A$ and $Y_B$ over the open channel.
4. Alice computes $K = Y_B^{X_A} \bmod p$; Bob computes $K = Y_A^{X_B} \bmod p$.

Both get the same key since $Y_B^{X_A} = g^{X_B X_A} = g^{X_A X_B} = Y_A^{X_B} \pmod p$.

Example: $p = 23$, $g = 5$, $X_A = 6$, $X_B = 15$. $Y_A = 5^6 \bmod 23 = 8$, $Y_B = 5^{15} \bmod 23 = 19$. $K = 19^6 \bmod 23 = 2$ and $8^{15} \bmod 23 = 2$.

An eavesdropper sees $p, g, Y_A, Y_B$ but would need a discrete logarithm to get $X_A$ or $X_B$. The basic protocol does not authenticate the parties, so it is open to a man-in-the-middle attack.

Stream cipher vs block cipher

Rail fence encryption (4 rails)

Plaintext without spaces: WEAREINSAMERACEUNTILLOVERLIVEEND (32 letters).

Writing the letters in a zigzag over 4 rails:

• Rail 1: W N A I R N (positions 1, 7, 13, 19, 25, 31)
• Rail 2: E I S R C T L E L E D
• Rail 3: A E A E E N L V I E
• Rail 4: R M U O V

Reading the rails one after another:

WNAIRN + EISRCTLELED + AEAEENLVIE + RMUOV

Ciphertext = WNAIRNEISRCTLELEDAEAEENLVIERMUOV

Digital signature

A digital signature is a value computed from a message and the signer's private key which lets anyone check, with the signer's public key, that the message came from the signer and was not changed. It gives authentication, integrity and non-repudiation.

Approaches of the Digital Signature Standard (DSS)

DSS (FIPS 186) uses the SHA hash with a public-key signature algorithm. It specifies two approaches.

1. RSA approach. The message is hashed with SHA to a fixed-length digest. The digest is encrypted (signed) with the sender's private RSA key. The receiver recomputes the hash of the received message, decrypts the signature with the sender's public key, and compares the two. A match means the signature is valid. This follows the generic hash-then-sign model.

2. DSA approach (Digital Signature Algorithm). DSA is based on the discrete logarithm problem (ElGamal and Schnorr ideas) and can only sign, not encrypt. Global parameters are a prime $p$, a prime divisor $q$ of $p-1$, and $g = h^{(p-1)/q} \bmod p$. The private key is $x < q$ and the public key is $y = g^x \bmod p$.

   • Signing: pick a random $k < q$; compute $r = (g^k \bmod p) \bmod q$ and $s = k^{-1}(H(M) + xr) \bmod q$. The signature is $(r, s)$.
   • Verifying: compute $w = s^{-1} \bmod q$, $u_1 = H(M)\,w \bmod q$, $u_2 = r\,w \bmod q$, $v = (g^{u_1} y^{u_2} \bmod p) \bmod q$. The signature is valid if $v = r$.

In DSA the hash and a fresh random $k$ are fed into the signing function, so the same message gives different signatures each time. $k$ must never be reused or revealed.

Task of a firewall

A firewall is a system placed between a trusted internal network and an untrusted external network (the Internet). It forces all traffic in both directions to pass through it, and only traffic allowed by the local security policy is passed. Its tasks are:

• Filter packets by IP address, port and protocol (access control).
• Block unauthorized access and hide internal network structure (NAT).
• Log and audit traffic, and raise alarms for suspicious activity.
• Provide a single point for enforcing security policy and for VPN or proxy services.

A firewall itself should be immune to penetration. It cannot protect against attacks that bypass it (dial-up modems, infected laptops) or against insiders.

Elements of an X.509 certificate

• Version
• Certificate serial number
• Signature algorithm identifier (algorithm and parameters used to sign)
• Issuer name (the certification authority)
• Validity period (not before, not after)
• Subject name (the owner of the public key)
• Subject public key information (algorithm, parameters, key)
• Issuer unique identifier (optional, version 2)
• Subject unique identifier (optional, version 2)
• Extensions (version 3)
• Signature (the CA's digital signature over all the above fields)

Worms vs viruses

Public Key Infrastructure (PKI)

PKI is the set of hardware, software, people, policies and procedures needed to create, manage, distribute, use, store and revoke digital certificates, so that public keys can be bound to identities and trusted.

PKI architecture model

• End entities (subscribers): users, servers or devices that hold certificates and use them.
• Registration Authority (RA): verifies the identity of the applicant and forwards the request to the CA.
• Certification Authority (CA): issues, signs and revokes X.509 certificates. CAs form a hierarchy with a trusted root CA at the top and subordinate CAs below, each certified by its parent.
• Repository (directory, such as LDAP): stores certificates and Certificate Revocation Lists (CRLs) so that they can be retrieved.
• Certificate Revocation List / OCSP: tells relying parties which certificates are no longer valid.
• Relying party: verifies a certificate by checking the CA signature up the chain to a trusted root, and checks validity and revocation.

Process: the user generates a key pair and sends a request to the RA, the RA verifies identity, the CA issues a signed certificate and publishes it in the repository, and others use it to verify signatures or encrypt data for the user.

MixColumns transformation in AES

MixColumns operates on each of the four columns of the state independently. Each column is treated as a vector of four bytes and is multiplied by a fixed matrix, with arithmetic in $GF(2^8)$ using the irreducible polynomial $x^8 + x^4 + x^3 + x + 1$ (hex 11B):

$\begin{pmatrix} s'_0\\ s'_1\\ s'_2\\ s'_3 \end{pmatrix} = \begin{pmatrix} 02 & 03 & 01 & 01\\ 01 & 02 & 03 & 01\\ 01 & 01 & 02 & 03\\ 03 & 01 & 01 & 02 \end{pmatrix} \begin{pmatrix} s_0\\ s_1\\ s_2\\ s_3 \end{pmatrix}$

Addition is XOR. Multiplication by 01 leaves the byte unchanged. Multiplication by 02 is a left shift by one bit, followed by XOR with 1B if the top bit of the original byte was 1. Multiplication by 03 is $(02 \cdot a) \oplus a$. MixColumns gives diffusion: each output byte depends on all four input bytes of its column. It is omitted in the last round.

Example. Column $(DB, 13, 53, 45)$.

• $02 \cdot DB$: $DB = 1101\,1011$, top bit is 1, shift gives $1011\,0110 = B6$, XOR 1B gives $AD$. $03 \cdot DB = AD \oplus DB = 76$.
• $02 \cdot 13 = 26$, $03 \cdot 13 = 26 \oplus 13 = 35$.
• $02 \cdot 53 = A6$, $03 \cdot 53 = A6 \oplus 53 = F5$.
• $02 \cdot 45 = 8A$, $03 \cdot 45 = 8A \oplus 45 = CF$.

First output byte: $s'_0 = 02 \cdot DB \oplus 03 \cdot 13 \oplus 53 \oplus 45 = AD \oplus 35 \oplus 53 \oplus 45 = 8E$.

Likewise $s'_1 = DB \oplus 02\cdot13 \oplus 03\cdot53 \oplus 45 = 4D$, $s'_2 = DB \oplus 13 \oplus 02\cdot53 \oplus 03\cdot45 = A1$, $s'_3 = 03\cdot DB \oplus 13 \oplus 53 \oplus 02\cdot45 = BC$.

Output column: $(8E, 4D, A1, BC)$.

Role of the prime number in Euler's totient function

Euler's totient $\phi(n)$ is the count of integers in $1 \dots n$ that are relatively prime to $n$.

• For a prime $p$, every number $1 \dots p-1$ is coprime to $p$, so $\phi(p) = p - 1$.
• For $n = pq$ with distinct primes, $\phi(n) = (p-1)(q-1)$.
• For a prime power, $\phi(p^k) = p^k - p^{k-1}$.

Because of this, $\phi(n)$ is easy to compute when the prime factors are known and hard when they are not. RSA relies on this: $e\,d \equiv 1 \pmod{\phi(n)}$ with $\phi(n) = (p-1)(q-1)$, and Euler's theorem $a^{\phi(n)} \equiv 1 \pmod n$ makes decryption work. Fermat's theorem is the special case $n = p$.

GCD(12, 16) by the Euclidean algorithm

$16 = 1 \times 12 + 4$ $12 = 3 \times 4 + 0$

The last non-zero remainder is 4.

$\gcd(12, 16) = 4$

Two limitations of MAC (message authentication code)

1. No non-repudiation. The MAC key is shared by sender and receiver, so either could have produced the tag. A third party cannot tell who created the message, which a digital signature can show.
2. Key distribution and management. Both parties must share a secret key in advance, and for $n$ users $n(n-1)/2$ keys are required. A compromised key lets an attacker forge messages. (A MAC also gives authentication and integrity but not confidentiality.)

Policy and mechanism

• A security policy states what is allowed and what is not: it defines the secure and non-secure states of a system. It says "what" is to be protected.
• A security mechanism is the method, tool or procedure used to enforce the policy, for example encryption, passwords, access control lists, firewalls. It says "how".

Scenario: a university's policy says "only the registered teacher of a course may change the marks of its students, and students may only view their own marks". The mechanisms that enforce this are user login with password or OTP (authentication), an access control list on the marks database (authorization), encryption of the connection with TLS, and audit logs. If a mechanism cannot enforce the policy (for example any logged-in user can edit any marks), the system is not secure with respect to the policy.

1. Classes of intruder

Anderson classified intruders into three classes:

• Masquerader: an outsider (not authorized to use the system) who penetrates access controls and uses a legitimate user's account, for example with a stolen password.
• Misfeasor: a legitimate user who accesses data, programs or resources they are not authorized for, or who misuses their privileges.
• Clandestine user: a person (inside or outside) who seizes supervisory control of the system and uses it to evade auditing and access control, or to suppress audit collection.

2. SSL (Secure Sockets Layer)

SSL (now succeeded by TLS) is a protocol that gives secure communication between client and server on top of TCP, widely used with HTTPS. It provides confidentiality (symmetric encryption), message integrity (MAC), and server (optionally client) authentication using X.509 certificates. It has two layers: the Record Protocol (fragmentation, compression, MAC, encryption) and the upper protocols (Handshake, Change Cipher Spec, Alert). The handshake negotiates the cipher suite, authenticates the server, and establishes a shared session key.

3. DoS attack

A Denial of Service attack tries to make a system, service or network unavailable to its legitimate users by exhausting resources such as bandwidth, memory or CPU. Common forms are SYN flooding (half-open TCP connections), ping flood or smurf (ICMP amplification), and UDP flood. In a Distributed DoS (DDoS) the traffic comes from many compromised machines (a botnet), which makes it hard to block. Countermeasures include rate limiting, ingress filtering, SYN cookies, firewalls/IPS and traffic scrubbing services.

CIA triad

The CIA triad is the three core goals of information security:

• Confidentiality: information is disclosed only to authorized parties (encryption, access control).
• Integrity: information and systems are modified only in authorized ways, and changes are detectable (hashes, MACs, digital signatures).
• Availability: information and services are accessible to authorized users when needed (redundancy, backups, DoS protection).

Double DES

Two DES stages with two independent 56-bit keys $K_1, K_2$: $C = E_{K_2}(E_{K_1}(P)), \qquad P = D_{K_1}(D_{K_2}(C))$ The effective key length looks like 112 bits, but the meet-in-the-middle attack (encrypt $P$ with all $K_1$, decrypt $C$ with all $K_2$, look for a match) needs only about $2^{57}$ operations. So double DES gives about 57 bits of security.

Triple DES (3DES)

Three DES operations in encrypt-decrypt-encrypt (EDE) order with keys $K_1, K_2, K_3$ (or $K_3 = K_1$ for the two-key version): $C = E_{K_3}(D_{K_2}(E_{K_1}(P))), \qquad P = D_{K_1}(E_{K_2}(D_{K_3}(C)))$ With $K_1 = K_2 = K_3$ it reduces to single DES, giving backward compatibility. The effective strength is 112 bits (168 bits nominal).

S-box in DES

After the expansion permutation, the 48-bit value is XORed with the 48-bit round subkey and split into eight 6-bit groups. Each group enters one of eight S-boxes ($S_1 \dots S_8$), each of which maps 6 bits to 4 bits, giving 32 bits. The S-boxes are the only non-linear step of DES and give confusion.

Method: the outer two bits (first and last) select the row (0 to 3) and the middle four bits select the column (0 to 15).

Example: input $011011$ to $S_1$. Row bits $0\,1 \to 01 = 1$. Column bits $1101 = 13$. Row 1 of $S_1$ is 0 15 7 4 14 2 13 1 10 6 12 11 9 5 3 8; entry 13 is 5. Output $= 5 = 0101$. So the 6-bit input $011011$ becomes the 4-bit output $0101$.

Generic model of the digital signature process

1. Signing (sender A). The message $M$ is passed through a hash function to get a fixed-length digest $H(M)$. The digest is encrypted with A's private key to give the signature $S = E_{PR_A}(H(M))$. A sends $M$ together with $S$ (optionally, $M$ is also encrypted for confidentiality).
2. Verification (receiver B). B hashes the received message to get $H(M')$. B also decrypts $S$ with A's public key to recover $H(M)$. If the two digests are equal, the signature is valid.

Thus B knows that the message came from A (authentication), that it was not altered (integrity), and A cannot deny sending it (non-repudiation). Only A's private key could produce a signature that A's public key verifies.

RSA

$p = 7$, $q = 19$, so $n = pq = 133$ and $\phi(n) = 6 \times 18 = 108$. Public key $e = 29$, private key $d = 41$. Check: $29 \times 41 = 1189 = 11 \times 108 + 1$, so $ed \equiv 1 \pmod{108}$. Valid.

Encrypt plaintext 4: $C = 4^{29} \bmod 133$.

$4^2 = 16$; $4^4 = 256 \equiv 256 - 133 = 123 \equiv -10$; $4^8 \equiv 100$; $4^{16} \equiv 10000 \bmod 133$: $133 \times 75 = 9975$, so $25$.

$29 = 16 + 8 + 4 + 1$: $4^{29} \equiv 25 \times 100 \times (-10) \times 4 \pmod{133}$. $25 \times 100 = 2500 \equiv 2500 - 2394 = 106 \equiv -27$. $-27 \times -10 = 270 \equiv 270 - 266 = 4$. $4 \times 4 = 16$.

$C = 16$

Decrypt ciphertext 3: $M = 3^{41} \bmod 133$.

$3^2 = 9$; $3^4 = 81$; $3^8 = 6561 \equiv 6561 - 6517 = 44$ ($133 \times 49 = 6517$); $3^{16} = 1936 \equiv 1936 - 1862 = 74$; $3^{32} = 5476 \equiv 5476 - 5453 = 23$ ($133 \times 41 = 5453$).

$41 = 32 + 8 + 1$: $3^{41} \equiv 23 \times 44 \times 3 = 3036$. $133 \times 22 = 2926$, $3036 - 2926 = 110$.

$M = 110$

Galois field

A Galois field $GF(n)$ is a finite set of $n$ elements in which addition, subtraction, multiplication and division (by non-zero elements) are defined and satisfy the field axioms. It exists only when $n = p^m$ for a prime $p$. For $m = 1$, $GF(p)$ is the integers $\{0, 1, \dots, p-1\}$ with arithmetic mod $p$. For $m > 1$ the elements are polynomials of degree below $m$ with coefficients in $GF(p)$, with arithmetic mod an irreducible polynomial.

Example: $GF(7) = \{0, \dots, 6\}$: $5 + 4 = 9 \equiv 2$, $3 \times 5 = 15 \equiv 1$, so $3^{-1} = 5$. AES uses $GF(2^8)$ with the irreducible polynomial $x^8 + x^4 + x^3 + x + 1$.

Two modes of block cipher encryption

1. Electronic Codebook (ECB). Each plaintext block is encrypted independently with the same key: $C_i = E_K(P_i)$. Decryption: $P_i = D_K(C_i)$. It is simple and parallelizable, and an error affects only one block. But identical plaintext blocks give identical ciphertext blocks, so patterns leak; it is suitable only for short data such as keys.

2. Cipher Block Chaining (CBC). Each plaintext block is XORed with the previous ciphertext block before encryption: $C_i = E_K(P_i \oplus C_{i-1}), \quad C_0 = IV$ $P_i = D_K(C_i) \oplus C_{i-1}$ The IV is random and sent with the message. Identical plaintext blocks give different ciphertext, so patterns are hidden. Encryption is sequential; a bit error in $C_i$ garbles $P_i$ and flips the same bit in $P_{i+1}$.

Quadratic residues of 7

$a$ is a quadratic residue mod 7 if $x^2 \equiv a \pmod 7$ has a solution with $\gcd(a,7)=1$.

The quadratic residues of 7 are $\{1, 2, 4\}$; the non-residues are $\{3, 5, 6\}$.

Intrusion

An intrusion is an unauthorized attempt to access, misuse or damage a system or network, or to violate its security policy. It can be an outsider breaking in, or an insider abusing privileges (masquerader, misfeasor, clandestine user).

How a system detects intrusion

An Intrusion Detection System (IDS) works on the assumption that intruder behaviour differs from legitimate behaviour. Two main approaches:

1. Statistical anomaly detection: a profile of normal behaviour (login times, commands used, resources consumed) is built for each user. Activity that deviates significantly from the profile is flagged. It can detect new attacks, but may give false positives.
2. Rule-based (signature / misuse) detection: audit records are compared with a set of known attack signatures or rules (for example, repeated failed logins, known exploit patterns). It is accurate for known attacks but cannot detect new ones.

Detectors can be host-based (HIDS, using audit logs and file changes on one machine) or network-based (NIDS, monitoring traffic). Honeypots are also used to attract and study intruders.

Four types of firewall

1. Packet-filtering firewall (filters on IP addresses, ports, protocol)
2. Stateful inspection firewall (tracks connection state)
3. Application-level gateway (proxy firewall)
4. Circuit-level gateway

Key $K = \begin{pmatrix}3 & 7\\ 5 & 12\end{pmatrix}$, ciphertext GVPJ.

$\det K = 3 \cdot 12 - 7 \cdot 5 = 36 - 35 = 1$, and $1^{-1} = 1$, so $K^{-1} = \begin{pmatrix}12 & -7\\ -5 & 3\end{pmatrix} \equiv \begin{pmatrix}12 & 19\\ 21 & 3\end{pmatrix} \pmod{26}$

Check: $3 \cdot 12 + 7 \cdot 21 = 36 + 147 = 183 \equiv 1 \pmod{26}$ (since $183 = 7 \times 26 + 1$), and $3 \cdot 19 + 7 \cdot 3 = 78 \equiv 0$. Correct.

Ciphertext pairs: GV = (6, 21), PJ = (15, 9).

• GV: $12 \cdot 6 + 19 \cdot 21 = 72 + 399 = 471 \equiv 471 - 468 = 3$ (D); $21 \cdot 6 + 3 \cdot 21 = 126 + 63 = 189 \equiv 189 - 182 = 7$ (H).
• PJ: $12 \cdot 15 + 19 \cdot 9 = 180 + 171 = 351 \equiv 351 - 338 = 13$ (N); $21 \cdot 15 + 3 \cdot 9 = 315 + 27 = 342 \equiv 342 - 338 = 4$ (E).

Plaintext = DHNE

PKI trust model

In a Public Key Infrastructure, a trust model describes how users decide to trust the public key certificate of another party, that is, how certification authorities (CAs) are organized and how trust is passed along a chain of certificates. The main models are:

1. Hierarchical (rooted) model. A single root CA sits at the top and is trusted by everyone. It issues certificates to subordinate CAs, which in turn certify other CAs or end users. To verify a certificate, a user follows the chain up to the root, checking each signature. This is the model used by the web (X.509). If the root is compromised, the whole tree fails.

2. Single CA model. One CA issues all certificates; simple but a single point of failure, and not scalable.

3. Mesh (cross-certification) model. Several independent CAs trust each other by issuing cross-certificates. There is no single root; a user trusts their own CA and reaches others through certificate paths. It is flexible but path building is complex.

4. Bridge CA model. A bridge CA cross-certifies with the root of each separate hierarchy, so the hierarchies can interoperate without a full mesh.

5. Web of trust (PGP). There are no CAs. Each user signs the keys of others they know, and trusts a key if it is signed by introducers they trust. Trust is decentralized and personal.

Validation in all models checks the signatures along the path, validity dates, and revocation status (CRL or OCSP).

Authentication system

An authentication system verifies the claimed identity of a user, device or message source before access is granted. Evidence can be something the user knows (password, PIN), has (smart card, token, OTP device) or is (fingerprint, face), and the system combines such factors with an authentication protocol and a store of credentials. The aim is to be sure that "the entity is who it claims to be".

One-way vs mutual authentication

In one-way authentication only one party (usually the client) proves its identity to the other (the server). The client cannot be sure the server is genuine.

In mutual authentication both parties authenticate each other, typically with a challenge-response exchange (nonces) using shared keys or certificates.

Need for mutual authentication, with an example

Consider an internet banking customer who logs in with username and password. With only one-way authentication, an attacker can set up a fake website (phishing, DNS spoofing or a man-in-the-middle). The customer, who has no means of checking the server, enters the password and the attacker captures it, then uses it on the real bank.

With mutual authentication (for example TLS with a server certificate checked by the browser in addition to the user's login, or Kerberos where the client sends an authenticator and the server returns $timestamp + 1$ encrypted with the session key), the client first verifies that the server holds a valid certificate or the right key, and only then sends credentials. The fake server fails this check, so man-in-the-middle and impersonation of the server are prevented. The same applies to a mobile phone and base station, or two servers talking to each other, where each must trust the other.

$7^{2019} \bmod 13$ using Fermat's little theorem

Since 13 is prime and $\gcd(7, 13) = 1$, Fermat gives $7^{12} \equiv 1 \pmod{13}$.

Divide the exponent: $2019 = 12 \times 168 + 3$ (as $12 \times 168 = 2016$).

$7^{2019} = (7^{12})^{168} \cdot 7^3 \equiv 1^{168} \cdot 7^3 = 343 \pmod{13}$

$343 = 13 \times 26 + 5$, so $7^{2019} \bmod 13 = 5$

Euler totient function

$\phi(n)$ is the number of positive integers less than $n$ that are relatively prime to $n$ (with $\phi(1) = 1$). For prime $p$, $\phi(p) = p - 1$; for primes $p \ne q$, $\phi(pq) = (p-1)(q-1)$; in general $\phi(n) = n\prod_{p \mid n}\left(1 - \frac1p\right)$.

Example: $n = 10$. The numbers coprime to 10 are 1, 3, 7, 9, so $\phi(10) = 4$. Check: $\phi(10) = \phi(2)\phi(5) = 1 \times 4 = 4$.

Properties of a hash function

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

1. Applicable to a block of data of any size.
2. Produces a fixed-length output.
3. Easy to compute $H(M)$ for any $M$ (practical in hardware and software).
4. Preimage resistance (one-way): given $h$, it is computationally infeasible to find $M$ with $H(M) = h$.
5. Second preimage resistance (weak collision resistance): given $M_1$, it is infeasible to find $M_2 \ne M_1$ with $H(M_2) = H(M_1)$.
6. Collision resistance (strong): it is infeasible to find any pair $M_1 \ne M_2$ with $H(M_1) = H(M_2)$.
7. Pseudorandom output (avalanche effect: a one-bit change flips about half the output bits).

First pass (round) of MD4

MD4 processes the message in 512-bit blocks split into sixteen 32-bit words $X[0..15]$, and uses a 128-bit state of four registers $(A, B, C, D)$ (initial values 67452301, EFCDAB89, 98BADCFE, 10325476 in hex). Each block goes through three passes of 16 steps each.

In the first pass:

• The auxiliary function is $F(X,Y,Z) = (X \wedge Y) \vee (\neg X \wedge Z)$ (bitwise "if X then Y else Z").
• No additive constant is used.
• The words are taken in order $k = 0, 1, \dots, 15$.
• Each step is $a = (a + F(b,c,d) + X[k]) \lll s$, and the roles of the registers rotate with each step.
• The left-rotation amounts repeat as $s = 3, 7, 11, 19$ for each group of four steps.

For example, the first four steps are $A = (A + F(B,C,D) + X[0]) \lll 3$ $D = (D + F(A,B,C) + X[1]) \lll 7$ $C = (C + F(D,A,B) + X[2]) \lll 11$ $B = (B + F(C,D,A) + X[3]) \lll 19$ and this pattern is repeated for $X[4..7]$, $X[8..11]$ and $X[12..15]$. The result of the third pass is added to the input registers to give the chaining value.

Symmetric vs asymmetric cipher

Vernam cipher: HELL with key FAIL

Each letter is encoded A=0, ..., Z=25 and the key letter is added mod 26 (equivalent to XOR in the binary form).

Ciphertext = METW

Divide $f(x) = 3x^2 + 4x + 3$ by $g(x) = 5x + 6$ over $GF(7)$.

In $GF(7)$, $5^{-1} = 3$ because $5 \times 3 = 15 \equiv 1$.

Step 1. Leading terms: $3x^2 \div 5x = 3 \cdot 3\,x = 9x \equiv 2x$. $2x \cdot (5x + 6) = 10x^2 + 12x \equiv 3x^2 + 5x$. Subtract: $(3x^2 + 4x + 3) - (3x^2 + 5x + 0) = -x + 3 \equiv 6x + 3$.

Step 2. $6x \div 5x = 6 \cdot 3 = 18 \equiv 4$. $4 \cdot (5x + 6) = 20x + 24 \equiv 6x + 3$. Subtract: $(6x + 3) - (6x + 3) = 0$.

$\text{Quotient} = 2x + 4, \qquad \text{Remainder} = 0$

Check: $(2x+4)(5x+6) = 10x^2 + 12x + 20x + 24 = 10x^2 + 32x + 24 \equiv 3x^2 + 4x + 3 \pmod 7$. Correct.

SSL protocol

Secure Sockets Layer (SSL) is a protocol, developed by Netscape and standardised as TLS, that provides secure communication between a client and a server over TCP. It sits between the application layer and TCP and is used by HTTPS, secure mail and other protocols. It provides:

• Confidentiality, by symmetric encryption of the data with a session key negotiated during the handshake.
• Message integrity, by a MAC on each record.
• Authentication of the server (and optionally the client) with X.509 certificates.

It consists of the Record Protocol (fragmentation, compression, MAC, encryption) and the Handshake, Change Cipher Spec and Alert protocols.

Services provided by PGP (Pretty Good Privacy)

1. Authentication (digital signature): the message hash (SHA) is signed with the sender's private key (RSA/DSS).
2. Confidentiality: the message is encrypted with a one-time symmetric session key (CAST-128, IDEA, 3DES), and the session key is encrypted with the recipient's public key (RSA/ElGamal).
3. Compression: the message is compressed (ZIP) after signing and before encryption, saving space and adding redundancy.
4. E-mail compatibility: binary output is converted to ASCII using radix-64 (Base64) encoding.
5. Segmentation and reassembly: large messages are split to meet e-mail size limits.
6. Key management: public key rings and private key rings, and key signing via a web of trust.

Security policy and mechanism

A security policy is a statement of what is and is not allowed in a system; it divides states into authorized (secure) and unauthorized (non-secure). A security mechanism is a method, tool or procedure that enforces the policy. The policy says what to protect and from whom; the mechanism says how.

Example: a hospital's policy says "only the treating doctor may read or change a patient's record; patients may read their own." Mechanisms that enforce it are login with password and OTP (authentication), role-based access control lists on the records database (authorization), encryption of stored and transmitted records, and audit logs. If any logged-in nurse could open every record, the mechanism would not meet the policy.

Block cipher vs stream cipher

Key expansion in AES

The key expansion routine turns the cipher key into a key schedule of round keys, each 128 bits (four 32-bit words). The number of round keys is $N_r + 1$: 11 for AES-128 ($N_r = 10$), 13 for AES-192, 15 for AES-256. For AES-128, 44 words $w_0 \dots w_{43}$ are produced.

1. The first four words $w_0 \dots w_3$ are the 16 bytes of the cipher key itself (used in the initial AddRoundKey).
2. For each later word $w_i$ ($i \ge 4$):
   • If $i$ is not a multiple of 4: $w_i = w_{i-4} \oplus w_{i-1}$.
   • If $i$ is a multiple of 4: $w_i = w_{i-4} \oplus g(w_{i-1})$, where $g$ does three things:
     1. RotWord: cyclic left shift of the word by one byte, $[b_0, b_1, b_2, b_3] \to [b_1, b_2, b_3, b_0]$.
     2. SubWord: each of the four bytes is replaced using the AES S-box.
     3. Round constant: the result is XORed with $Rcon[i/4] = (RC_{i/4}, 00, 00, 00)$, where $RC_1 = 01$ and $RC_j = 02 \cdot RC_{j-1}$ in $GF(2^8)$ (01, 02, 04, 08, 10, 20, 40, 80, 1B, 36).
3. For AES-256, an extra SubWord (without rotation or Rcon) is applied to $w_{i-1}$ when $i \bmod 8 = 4$.

Words $w_{4r} \dots w_{4r+3}$ form the round key for round $r$. The non-linear S-box and the round constants remove symmetry between rounds and make recovering the cipher key from a round key hard.

(Properties of hash functions)

A hash function $H$ maps a message $M$ of arbitrary length to a fixed-length output $h = H(M)$ called the hash value or message digest. A cryptographic hash function should have:

1. Variable input size: $H$ can be applied to a block of data of any size.
2. Fixed output size: $H$ produces a fixed-length output (160 bits for SHA-1).
3. Efficiency: computing $H(M)$ is easy and fast for any $M$, in hardware and software.
4. Preimage resistance (one-way): for a given $h$, it is computationally infeasible to find $y$ with $H(y) = h$.
5. Second preimage resistance (weak collision resistance): for a given $x$, it is infeasible to find $y \neq x$ with $H(y) = H(x)$.
6. Collision resistance (strong collision resistance): it is infeasible to find any pair $(x, y)$, $x \neq y$, with $H(x) = H(y)$.
7. Pseudorandomness: the output satisfies standard randomness tests, and a one-bit change in the input changes about half the output bits (avalanche effect).

(SHA-1 hash generation)

SHA-1 takes a message of length less than $2^{64}$ bits and produces a 160-bit digest. It processes the message in 512-bit blocks.

Step 1: Padding. Append a single bit 1, then enough 0 bits so that the length is $448 \bmod 512$. Padding is always added, even if the message already has that length.

Step 2: Append length. Append the original message length as a 64-bit big-endian integer. The padded message is now a multiple of 512 bits, split into blocks $Y_1, \dots, Y_L$.

Step 3: Initialise the buffer. Five 32-bit registers are set to:

$A = \text{67452301},\; B = \text{EFCDAB89},\; C = \text{98BADCFE},\; D = \text{10325476},\; E = \text{C3D2E1F0}$

Step 4: Process each 512-bit block with the compression function of 80 steps (four rounds of 20 steps).

• Split the block into sixteen 32-bit words $W_0, \dots, W_{15}$ and expand to 80 words: $W_t = (W_{t-3} \oplus W_{t-8} \oplus W_{t-14} \oplus W_{t-16}) \lll 1, \quad 16 \le t \le 79$
• For each step $t = 0, \dots, 79$: $\text{TEMP} = (A \lll 5) + f_t(B, C, D) + E + W_t + K_t$ $E = D,\; D = C,\; C = B \lll 30,\; B = A,\; A = \text{TEMP}$ (all additions are modulo $2^{32}$).

• After the 80 steps, add the results to the chaining values: $H_0 = H_0 + A$, $H_1 = H_1 + B$, and so on for $C, D, E$ (mod $2^{32}$). These become the input for the next block.

Step 5: Output. After the last block, the concatenation $H_0 \| H_1 \| H_2 \| H_3 \| H_4$ is the 160-bit message digest.

(Z$_5$ is a field)

$Z_5 = \{0,1,2,3,4\}$ with addition and multiplication modulo 5. It is a field if it is a commutative ring with unity in which every non-zero element has a multiplicative inverse.

• Under addition mod 5: closure, associativity and commutativity hold; the identity is 0; the inverse of $a$ is $5-a$ (0 for 0). So it is an abelian group.
• Under multiplication mod 5: closure, associativity, commutativity hold; the identity is 1; and multiplication distributes over addition.
• Inverses of the non-zero elements:

$1\cdot1 = 1,\quad 2\cdot3 = 6 \equiv 1,\quad 3\cdot2 \equiv 1,\quad 4\cdot4 = 16 \equiv 1 \pmod 5$

Every non-zero element has an inverse, so $Z_5$ is a field. This holds because 5 is prime, so $\gcd(a,5)=1$ for every $a \ne 0$.

(ElGamal encryption)

Public key: $q = 101$, $\alpha = 2$, $Y_A = 14$. Random $k = 4$.

Message CSIT with A=0, ..., Z=25: C = 2, S = 18, I = 8, T = 19.

One-time key: $K = Y_A^{\,k} \bmod q = 14^4 \bmod 101$ $14^2 = 196 \equiv 95$, and $95^2 = 9025 = 89\cdot101 + 36$, so $K = 36$.

$C_1 = \alpha^k \bmod q = 2^4 = 16$

$C_2 = M \cdot K \bmod 101$ for each letter:

Ciphertext: $(16, 72),\ (16, 42),\ (16, 86),\ (16, 78)$.

(Decryption: $K = C_1^{X_A} \bmod q$ and $M = C_2 K^{-1} \bmod q$, using the same $K = 36$.)