01. Introduction

Lecturer: Clementine Gritti.

Course weighting:

• Quizzes: 20%
  • 9 quizzes, 10 multi-choice questions with 4 options and 1 correct answer
• Assignment: 20%
  • Released a week before the term break, due the week after
• Lab attendance: 10%
  • If lab is missed, report can be emailed to course coordinator and TA by the following Friday
• Final Exam: 50%

CIA Triad:

• Loss of Confidentiality: when unauthorized people can access the data
• Loss of Integrity: when unauthorized changes can be made to the data
• Loss of Availability: when authorized users cannot access the data

02. Course Overview

What is Cyber security?

The NIST (National Institute of Standards and Technology) computer security handbook defines it as protections afforded to an information system to preserve confidentiality, integrity, availability (CIA) of system resources.

Terminology:

• Threat: potential security harm to an asset/system resource
• Attack: thread that is carried out. If successful, leads to undesirable violation of security
• Countermeasure: means taken to deal with attacks (prevention, detection, recovery)
• Vulnerabilities:
  • Leaky: access to information given when it should not
  • Corrupted: does the wrong thing or gives wrong answers
  • Unavailable: impossible/impractical to access

Key questions:

• What assets need to be protected
• How are the assets threatened
• How can the threats be countered

Assets include:

• Hardware
• Software: OS, system utilities, applications
• Data: files, DB
• Networks: local/wide area network links, bridges, routers etc.

Types of Attacks

Passive:

• Does not alter information or resources in the system
• Hard to detect, easy to prevent
• Types of passive attacks:
  • Eavesdropping/interception: attacker directly accesses sensitive data in transit
  • Traffic analysis/inference: observations of the amount of traffic between the source and destination

Active:

• Alters information or system resources
• Hard to prevent, easy to detect
• Types of active attacks:
  • Masquerade: attacker claims to be a different entity
  • Message modification (falsification): message modified in transit
  • DDoS (misappropriation): attacker prevents legitimate users from accessing resources

Inside:

• Initiated by entity inside the security perimeter
• Authorized to use the systems, but used in a malicious way
• Types of inside attacks:
  • Exposure: sensitive data intentionally released to outsider
  • Falsification: data altered or replaced

Outside:

• Initiated from outside the perimeter by an unauthorized or illegitimate user
• Types of outside attacks:
  • Obstruction: communication links disabled, or communication control information altered
  • Intrusion: attacker gains unauthorized access to sensitive data

Fundamental Requirements

Information security management requires:

1. Threat identification
2. Classification by likelihood and severity
3. Security controls applied based on cost-benefit analysis

Countermeasures to threats and vulnerabilities:

• Computer security technical measures (access control, authentication etc.)
• Management measures (awareness, training)

What is Information Security?

ISO security architecture defines:

• Security: when vulnerabilities in assets/resources are minimized
• Asset: anything of value
• Vulnerability: any weakness that could be exploited to violate a system or its information
• Threat: potential security violation

Hence, information security is security where the assets/resources are information systems

Security Services and Mechanisms

OSI Security Architecture X.800: dated, but most definitions/terminology still relevant. Defines security threats, services, and mechanisms.

Security Services

A security service is processing/communication service that gives a specific kind of protection to system resources.

Security services include:

• Peer entity authentication: confirms entity is who they claim to be
• Data origin authentication: confirms origin of data unit/message
• Access control: protects against unauthorized use of resources
• Data confidentiality: protects data against unauthorized disclosure
• Traffic flow confidentiality: protects disclosure of data that can be derived from knowledge of traffic flow
• Data integrity: detects modification/reply of data in messages
• Non-repudiation: protects against the message creator falsely denying to creating the data
• Availability: protects against DDoS
• Encipherment: transforms data to hide its content
• Digital signature: mechanism to transform data using a signing key

From Stack Exchange:

• Non-repudiation: entity cannot deny to having sent/signed the message
• Message (or data origin) authentication: entity originally made the message
• Entity authentication: entity involved in current communication session

Security Mechanisms

A security mechanism is a method of implementing one or more security services.

Security mechanisms include:

• Data integrity: corruption-detection techniques
  • Message Authentication Codes
• Authentication exchange: protocols to ensure identify of participants
  • TLS
• Traffic padding: spurious traffic generated to protect against traffic analysis; usually used in combination with encipherment
• Control lists, passwords, tokens which indicate access rights
• Routing control: use of specific secure routes
• Notarization: use of trusted third party to assure source/receipt of data

03. Number Theory and Finite Fields

Discrete mathematics: cyroptology deals with finite objects (e.g. alphabets, blocks of characters)

Modular arithmetic; deals with finite number of values.

Basic Number Theory

Factorization

$\mathbb{Z} = \{ \dots, -3, -2, -1, 0, 1, 2, 3, \dots \}$ is the set of integers.

Given $a, b \in \mathbb{Z}$, $a$ divides $b$ if there exists $k \in \mathbb{Z}$ such that $ak = b$. In this case, $a$ is a factor of $b$: $a|b$.

An integer $p > 1$ is prime iff its only divisors are $1$ and $p$.

Properties

If $a|b$ and $a|c$, then $a|(b+c)$.

If $p$ is prime and $p|ab$, $p|a$ OR $p|b$.

Division algorithm

Given $a, b \in \mathbb{Z}$ such that $a > b$, then there exists $q, r \in \mathbb{Z}$ such that:

$q$ is the quotient and $0 \ge r \gt b$ is the remainder. $r \lt \frac{a}{2}$.

Greatest Common Divisor

$d$ is the GCD of $a$ and $b$; $gcd(a, b) = d$ if:

• $d|a$ and $|b$
• If $c|a$ and $c|b$, then $c|d$
• $d \gt 0$

$a$ and $b$ are relatively prime if $gcd(a, b) = 1$

Euclidean Algorithm

To find $d = gcd(a, b)$:

Hence, $d = r_k = gcd(a, b)$.

In psuedo-code:

def gcd(a, b):
  r[-1] = a
  r[0] = b
  k = 0
  while r[k] != 0:
    q[k] = floor(r[k - 1]/r[k])
    r[r + 1] = r[k - 1] - q[k]r[k]
    k = k + 1
  
  k = k - 1
  return r[k]

Back-Substitution

Find $x$, $y$ in $ax + by = d = r_k$.

Can be rewritten as:

$r_{k - 2} = r_{k - 1}q_k + r_k$ can be rewritten as $r_k = r_{k - 2} - r_{k - 1}q_k$. $r_{k - 1}$ can be substituted with the value above. Hence, this process can be repeated until you have $r_{k - 1}$ in terms of the original values.

Example: $gcd(17, 3)$:

Back-substitution:

The result shows that $3^{-1} \equiv 6 \pmod{17}$.

Modular Arithmetic

$b$ is a residue of $a \pmod n$ if $a - b = kn$ for some integer $k$:

Given $a \equiv b \pmod n$ and $c \equiv d \pmod n$:

$b \pmod n$ denotes the unique value $a$ in the complete set of residues $\{ 0, 1, \dots, n-1\}$ such that:

In other words, $b \pmod n$ is the remainder after dividing $a$ by $n$.

Residue Class

The set $\{ r_0, r_1, \dots, r_{n - 1}\}$ is a complete set of residues modulo $n$ if for every $a \in \mathbb{N}$, $a \equiv r_i \pmod n$ for exactly one $r_i$.

The set $\{ 0, 1, \dots, n - 1\}$ is denoted as $\mathbb{Z}_n$.

Groups

A group $\mathbb{G}$ is a set with binary operation $\cdot$ and:

• Closure: $a \cdot b \in \mathbb{G}$ for any and all $a, b \in \mathbb{G}$
• Identity: there is an element $1$ such that $a \cdot 1 = 1 \cdot a = a$ for any and all $a \in \mathbb{G}$
• Inverse: there is an element $b$ such that $a \cdot b = 1$ for any and all $a \in \mathbb{G}$
• Associativity: $(a \cdot b) \cdot c = a \cdot (b \cdot c)$ for any and all $a, b, c \in \mathbb{G}$

A group is abelian when it is the operation is commutative; $a \cdot b = b\cdot a$ for $a, b \in \mathbb{G}$.

Cyclic Groups

The order $|\mathbb{G}|$ of a group $\mathbb{G}$ is the number of elements in $\mathbb{G}$.

$g^k$ denotes the repeated application of $g \in \mathbb{G}$ using the group operation. e.g. $g^3 = g \cdot g \cdot g$.

The order $|g|$ of $g \in \mathbb{G}$ is the smallest integer $k$ such that $g^k = 1$.

$g$ is a generator for $\mathbb{G}$ if $|g| = |\mathbb{G}|$.

A group is cyclic if it has a generator.

Computing Inverses Modulo $n$

The inverse if $a$ (if it exists) is a value $x$ such that $ax \equiv 1 \pmod n$; it is written as $a^{-1} \pmod n$. This means that $a$ must be coprime to $n$.

Theorem: let $0 \gt a \gt n$; $a$ has an inverse modulo $n$ iff $gcd(a, n) = 1$.

The Euclidean algorithm can be used to find the inverse of $a$.

If $x$ such that $ax \equiv 1 \pmod n$, there is an integer $y$ such that $ax = 1 + yn$.

Hence, starting from $gcd(a, n) = 1$, use back substitution to find $x$ and $y$ in the equation $ax + ny = 1$. the $y$ value gives the inverse.

Group of Primes Modulus $\mathbb{Z}^*_p$

$\mathbb{Z}^*_p = {1, 2, \dots, p - 1}$ is a complete set of residues modulo the prime $p$ with the value $0$ removed.

Properties:

• $|\mathbb{Z}^*_p| = p - 1$
• $\mathbb{Z}^*_p$ is cyclic
• $\mathbb{Z}^*_p$ has many generators (in general)

It can be thought of as the multiplicative group of integers $1, 2, \dots, p - 1$ which have inverses modulo $p$.

Finding Generators

A generator of $\mathbb{Z}^*_p$ is an element of order $p - 1$

Lagrange theorem: the order of any element must exactly divide $p - 1$.

To find a generator of $\mathbb{Z}^*_p$:

• Compute all distinct prime factors $f_1, f_2, \dots, f_r$ of $p - 1$
• $g$ is a generator iff $g^\frac{p - 1}{f_i} \neq 1 \pmod p$ for all $i = 1, 2, \dots, r$

Example

Find a generator for $\mathbb{Z}_{11}^*$.

$|\mathbb{Z}_{11}^*|$ is $10$ as $11$ is prime. $10 = 2 \cdot 5$, so to check if $g \in \mathbb{Z}_{11}^*$ is a generator, check if $g^2 \not\equiv 1 \pmod{11}$, $g^5 \not\equiv 1 \pmod{11}$:

• $1$: not a generator as $1^n \equiv 1 \pmod{11}$
• $2$: $2^5 \equiv 32 \equiv 2 \not\equiv 1 \pmod{11}$ and $2^2 \equiv 4 \not\equiv 1 \pmod{11}$ so $2$ is a generator

Groups of Composite Modulus $\mathbb{Z}^*_p$

For any non-prime $n$, $\mathbb{Z}_n^*$ is a group of residues that have an inverse under multiplication.

Properties:

• $\mathbb{Z}_n^*$ is a group
• $\mathbb{Z}_n^*$ is not cyclic in general
• Finding its order is difficult

e.g. $\mathbb{Z}_6^* = \{1, 5\}$ (elements coprime to $6$).

Example

Find a generator for $\mathbb{Z}_9^*$.

$\mathbb{Z}_9^* = \{ 1, 2, 4, 5, 7, 8, \}$ so $|\mathbb{Z}_9^*| = 6$

• $1$: not a generator as $1^n \equiv 1 \pmod 9$
• $2$:
  • $2^2 \equiv 4 \pmod 9$
  • $2^3 \equiv 8 \pmod 9$
  • $2^4 \equiv 16 \equiv 7 \pmod 9$
  • $2^5 \equiv 32 \equiv 5 \pmod 9$
  • $2^6 \equiv 64 \equiv 1 \pmod 9$
  • $2^7 \equiv 128 \equiv 2 \pmod 9$
  • Hence, the order of $2$ is equal to $|\mathbb{Z}_9^*|$, cycling through all elements in the group before repeating
  • NB: every element is guaranteed to be in $\mathbb{Z}_9^*$ as it is a group and hence has closure over the multiplication operation

Fields

A field $\mathbb{F}$ is a set with two binary operations, $+$ and $\cdot$, with the properties such that:

• $\mathbb{F}$ is an abelian group under the operation $+$ with the identity element $0$
• $\mathbb{F} \backslash \{ 0 \}$ is an abelian group under the operation $\cdot$ with identity element $1$
• Distributivity: $a \cdot (b + c) = (a \cdot b) + (a \cdot c)$ for $a, b, c \in \mathbb{F}$

Theorem: only finite fields of size $p^n$ exist, where $p$ is a prime and $n$ is any positive integer.

Finite Field $GF(p)$

For a finite field $GF(p) = \mathbb{Z}_p$:

• Multiplication and addition are done modulo $p$
• Its multiplicative group is exactly $\mathbb{Z}_p^*$

Finite Field $GF(2)$

$GF(2)$ is the simplest field with two elements, $0$ and $1$:

• Addition modulo $2$: XOR ($\oplus$)
• Multiplicative group: $\{ 1 \}$

Finite Field $GF(2^8)$

$GF(2^8)$ is the field used for calculations in AES (block cipher).

Arithmetic in this field is considered as polynomial arithmetic where the field elements are polynomials with binary coefficients. e.g. $0010 1101 \leftrightarrow x^5 + x^3 + x^2 + 1$

Properties:

• Polynomial division can be done easily using shift registers
• Adding two strings: add their coefficients modulo $2$ (XOR)
• Multiplication with respect to a generator polynomial
  • AES uses $m(x) = x^8 + x^4 + x^3 + x + 1$
• Multiplying two strings: multiply them as polynomials, then take remainder of division by $m(x)$

03. Classical Encryption

Terminology

• Cryptography: the study of designing systems
• Cryptoanalysis: the study of breaking systems
• Steganography; the study of concealing information; not covered in this course

Cryptography transforms data based on a secret called the key. It provides confidentiality and authentication:

• Confidentiality: key needed to read the message
• Authentication: key needed to write the message

Cryptosystems:

• A set of plaintexts holding the original message
• A set of ciphertexts holding the encrypted message
  • Sometimes called cryptogram
• A set of keys
• A function called the encryption or encipherment which transforms the plaintext into a ciphertext
• An inverse function called the decryption or decipherment which transforms the ciphertext into the plaintext

Symmetric key cipher (secret key cipher):

• Encryption/decryption keys known only to the sender/receiver
• Secure channel required for transmission of keys

Asymmetric key cipher (public key cipher):

• Each participant has a public and private key
• Can be used to both encrypt messages and create digital signatures

Notation for Symmetric Encryption Algorithms

• Encryption function $E$
• Decryption function $D$
• Message/plaintext $M$
• Cryptogram/ciphertext $C$
• Shared secret key $K$

Encryption: $C = E(M, K)$

Decryption: $M = D(C, K)$

Methods of Cryptanalysis

What resources are available to the adversary? Computational capabilities, inputs/outputs to the systems, etc.

What is the adversary aiming to achieve? Retrieving the whole secret key? Distinguishing between two messages?

Exhaustive Key Search

Adversary tries all possible keys. Impossible to prevent such attacks; can only ensure there are enough keys to make exhaustive search too difficult computationally.

Note that the adversary may find the key without exhaustive search or even break the cryptosystem without finding the key.

Preventing exhaustive key search is a minimum standard.

Attack Classification

Ciphertext only attack: the attacker has access only to intercepted ciphertexts.

A cryptosystem is highly insecure if it can be practically attacked using only intercepted ciphertexts.

Known plaintext attack: the attacker knows a small amount of plaintexts and their corresponding ciphertexts.

Chosen plaintext attack: the attacker can obtain the ciphertext from some plaintext it has selected (attacker has ‘inside encryptor’).

Chosen ciphertext attack: the attacker can obtain the plaintext from some ciphertext it has selected (attacker has ‘inside decryptor’).

A cryptosystem should be secure against chosen plaintext and ciphertext attacks.

Kerckhoff’s Principle

Kerckoff’s Principle states the that the attacker has complete knowledge of the cipher; the decryption key is the only item unknown to the attacker.

Secret, non-standard algorithms are often flawed, providing mainly security through obscurity.

Alphabets

Historical ciphers: define alphabet for the plaintext and ciphertext

Roman alphabet: $A, B, C, \dots, Z$

• Sometimes it includes spaces, upper/lowercase characters, punctuation
• Sometimes maps the alphabet to numbers: $A = 0, B = 1, \dots, Z = 25$

Statistical attacks depend on using the redundancy of the alphabet:

• Distribution of single letters, digrams, trigrams are used
• Exact statistics vary by sample

Basic Cipher Operations

Transposition: characters in plaintext are mixed up with each other (permutations)

Substitution: each character is replaced by a different character

Transposition Cipher

Permuting characters in a fixed period $d$ and permutation $f$.

The plaintext is seen as a matrix with $d$ columns. For each row, the characters are mixed up in the order given by $f$. The same permutation is used by each row.

Key is $(d, f)$, each block of $d$ characters being re-ordered using the permutation $f$.

There are $d!$ permutations of length $d$.

Cryptanalysis

Frequency distribution of ciphertext and plaintext characters are the same.

If $d$ is small, transposition ciphers can be solved by hand using anagramming.

Knowledge of plaintext language digram/trigrams can help to optimize trials.

Simple Substitution Ciphers

Each character in plaintext alphabet replaced by character in ciphertext alphabet using a substitution table.

This is called a monoaphabetic substitution cipher.

Caesar cipher:

• $i$th letter of the alphabet mapped to the $(i + j)$th letter using the key $j$
• Encryption: $C_i = (M_i + j) \pmod n$
• Decryption: $M_i = (C_i - j) \pmod n$
• Guess $j$ by finding the most frequent character in the ciphertext and mapping it to the most frequent character in the language (e.g. $\Delta$ (space), ‘e’)

Random simple substitution cipher:

• Each character assigned to a random character of the alphabet
• Encryption/decryption done using substitution table
• If the alphabet has $26$ characters, there are $26!$ keys
  • One-to-one mapping, so second character can only be assigned to $n - 1$ characters
• Caesar cipher is a special case of the random simple substitution cipher
• Frequency analysis: use the most frequent characters, common di/trigrams such as ‘the’

Polyalphabetic Substitution

Multiple mappings from plaintext to ciphertext: smoothens frequency distribution.

Typically periodic substitution ciphers based on a period $d$.

Given $d$ ciphertext alphabets $C_0, C_1, \dots, c_{d - 1}$, let $f_i: A \rightarrow C_i$.

A plaintext message:

it is encrypted to:

If $d = 1$, the cipher is monoalphabetic - a simple substitution cipher.

Key generation:

• Select block length $d$
• Generate $d$ random simple substitution ciphers

Encryption: encrypt the $i$th character using the $j$th substitution table such that $i \equiv j \pmod d$.

Decryption: use the same substitution table as encryption.

Vigenère Cipher

Based on shifted alphabets.

The key $K$ is a sequence of characters $K = K_0 K_1 \dots K_{d - 1}$.

Let $M$ be the plaintext character. for $0 \le i \le d - 1$, $K$ gives the amount of shift in the $i$th character e.g. $f_i(M) = (M + K_i) \bmod n$.

e.g. if $K= LOCK = \{ 11, 14, 2, 10 \}$, the first character is shifted by $11$, the second is shifted by $14$, …, the fifth is shifted by $11$.

Cryptanalysis

Identifying period length:

• Kasiski method
• Cryptool uses autocorrelation to automatically estimate period

Once period identified, the $d$ substitution tables can be attacked separately - there needs to be sufficient ciphertext to do this.

Autocorrelation

Given ciphertext $C$, computed the correlation between $C$ and its shift $C_i$ for all values $i$ of the period.

English is non-random; there is better correlation between two texts with the same shift size.

Find peaks in the value of $C_i$ when $i$ is a multiple of the period; results can be plotted on a histogram.

Kasiski Method

If you identify sequences of characters that occur multiple times, find the distance between them; the period is likely to be a multiple of the period.

If you find multiple sequences with different distances, the period is likely to be a common divisor.

Once the period is found, the separate alphabets can be attacked separately; at this point, it is just a Caesar cipher.

Other Ciphers (for use by hand)

Beaufort cipher: like Vigenère, but $f_i(M) = (K_i - M) \bmod n$

Autokey: starts off as the Vigenère cipher, but the plaintext defines the subsequent alphabet. Hence, the cipher is not periodic.

Running key cipher: practically infinite set of alphabets generated from a shared key. This is ofen an extract from a book called the book cipher.

Rotor Machines

Enigma: each character encrypted with a different alphabet with a period of ~17,000; would never repeat in the same message (in practice).

Hill Cipher

Polygram/polygraphic cipher: simple substitution of an extended alphabet consisting of multiple characters.

Has linearity, making known plaintext attacks easy.

Given $d$ plaintext characters:

Encryption: multiplying the $d \times d$ matrix $K$ by the block of plaintext $M$: $C = KM$.

Decryption: multiplying the matrix $K^{-1}$ by the block of ciphertext $C$: $M = K^{-1}C$.

Example

$d = 2$; takes digrams as input/output blocks.

Each plaintext pair written as column vector. If there are insufficient letters, they are filled with uncommon letters (e.g. $Z$).

Plaintext:

Encryption:

Decryption:

Cryptanalysis

Known plaintext attacks possible given $d$ plaintext-ciphertext matching blocks: given blocks (column vectors) $M_i$ and $C_i$, $0 \le i \le d - 1$:

• $C = [C_0 C_1 \dots C_{d-1}]$
• $M = [M_0 M_1 \dots M_{d - 1}]$
• $C = KM$, so $K = CM^{-1}$

$C$ , $M$ and $K$ are all $d \times d$ vectors

Then $K^{-1}$ can be found to decrypt the ciphertext.

Comments:

• The plaintext message $M$ may not be invertible
• Ciphertext-only attacks follow known plaintext attacks with the extra task of finding probable blocks of matching plaintext-ciphertext
  • e.g. if $d = 2$, the frequency distribution of non-overlapping pairs of ciphertext characters can be compared with the distribution of pairs of plaintext characters
• Cryptool defaults to an alphabet of $A = 1, B = 2, \Delta = 27$ (where $\Delta$ is space)

05. Block Ciphers

Main bulk encryption algorithms used in commercial applications. AES is one example of such algorithm.

Principles

Block ciphers are symmetric key ciphers where each block of plaintext encrypted with the same key.

A block is a set of plaintext symbols of a fixed size, typically 64 to 256 bits in modern ciphers.

They are used in configurations called modes of operation.

Notation

• $P$: plaintext block of length $n$ bits
• $C$: ciphertext block of length $n$ bits
• $K$: key of length $k$ bits
• Encryption: $C = E(P, K)$
• Decryption: $P = D(C, K)$

Criteria

Shannon defined two encryption techniques:

• Confusion: substitution used to make the relationship between $K$ and $C$ as complex as possible.
• Diffusion: transformations used to dissipate the statistical properties of $P$ across $C$.

Repeated use of techniques can be used using the concept of a product cipher.

Product & Iterated Ciphers

Product Cipher

Cryptosystem where encryption performed by applying/composing several sub-encryption algorithms: output of one block used as input to next block.

Often composed of simple functions $f_i$ for $1 \le i \le r$ such that each $f_i$ has its own key $K_i$.

Iterated Cipher

Special product ciphers called iterated ciphers where:

• Encryption divided into $r$ similar rounds
• Sub-encryption functions are the same function $g$: the round function
• Each round key/subkey $K_i$ is derived from the master key $K$ using a process called key schedule

Encryption

Given plaintext block $P$, round function $g$, round keys $K-1, K_2, \dots, K_r$, the ciphertext block $C$ is derived through $r$ rounds:

Decryption

There must be an inverse function $g^{-1}$ such that $g^{-1}(g(W, K_i), K_i) = W$ for all keys $K_i$ and blocks $W$.

Types of Iterated Ciphers

Substitution-Permutation Network (SPN) e.g. Advanced Encryption Standard (AES).

Feistel Cipher e.g. Data Encryption Standard (DES).

Substitution-Permutation Network

Block length $n$ must allow each block to be split into $m$ sub-blocks of length $l$: $n = lm$.

Substitution $\pi_S$ (called substitution box or S-box) operates on sub-blocks of length $l$ bits:

i.e. mapping some binary number of size $l$ bits to another.

Permutation $\pi_P$ (called permutation-box or P-box) swaps the inputs from $\{ 1, \dots, n \}$:

i.e. swapping the order of bits in the entire block around.

Operation

1. Round key $K_i$ XORed with current state block $W_i$: $K_i \oplus W_i$
2. Each sub-block substituted applying $\pi_S$
3. The whole block permuted using $\pi_P$

Example

• 4 round keys
• 4 S-boxes
• 1 P-box
• Last round does have a P-block

Feistel Cipher

Round function swaps the two halves of the block to form a new right hand half.

Encryption

Plaintext block $P = W_0$ split into two halves $(L_0, R_0)$.

For each round:

• $L_i = R_{i - 1}$
• $R_i = L_{i - 1} \oplus f(R_{i - 1}, K_i)$

The output is the ciphertext block $C = W_R = (L_r, R_r)$.

Decryption

Split $C$ into two halves, $(L_r, R_r)$.

For each round:

• $L_{i - 1} = R_i \oplus f(L_i, K_i)$
• $R_{i - 1} = L_i$

$f$ does not need to be inverted: $x \oplus x = 0$, so applying by applying $f$ twice it can be decrypted.

The choice of $f$ is critical for security; is is the only non-linear part of the encryption.

Differential and Linear Cryptanalysis

Differential cryptanalysis: chosen plaintext attack using correlation in the differences between two input plaintexts and their corresponding ciphertexts.

Liner cryptanalysis: known plaintext attack that theoretically break DES.

Modern block ciphers normally immune to both attacks.

Avalanche Effects

Key avalanche: a small change in key (with the same plaintext) should result in a large change in ciphertext.

Plaintext avalanche: a small change in plaintext should result in a large change in ciphertext: changing one bit should change all bits in the ciphertext with a probability of $1/2$.

Key avalanche is related to Shannon’s notion of confusion, plaintext avalanche to Shannon’s notion of diffusion.

DES

Designed by IBM researchers, became US standard in 1976. 16-round Feistel cipher with key length of 56 bits and data block length of 64 bits.

The key length is actually 64 bits, but the last bit of every byte is redundant.

Encryption

$P$ is an input plaintext block of 64 bits:

1. All bits of $P$ permuted using an initial fixed permutation of $IP$
2. 16 rounds of Feistel operations applied, denoted by function $f$
   • Each round uses a different 48-bit subkey
   • The subkey is defined by a series of permutations and shifts
3. A final fixed inverse permutation $IP^{-1}$ is applied

The 64-bit ciphertext block $C$ is the output.

Decryption requires only reversing the order in which the subkeys are applied.

Feistel Operation

1. 32 bits expanded to 48 bits using a padding scheme which repeats some bits
2. XOR the 48 bits with the 48-bit subkey
3. Break 48 bits into 8 blocks of 6 bits
4. Each block $W_i$ transformed using substitution table $S_i$, resulting in blocks of length $4$ and hence a total of 32 bits.
   • A transformation table is used to determine the output value
   • If the input block is $W = x_1x_2x_3x_4x_5x_6$, the row number is given by $x_1x_6$ and the column number by $x_2x_3x_4x_5$
5. A permutation is applied to the result

Brute Force Attacks

Testing all the possible $2^k$ keys (where $k$ is the size of the key $K$). $k = 56$ is fairly small, requiring only $2^{k}/2 = 2^{55}$ trials on average - this was criticized from the start.

The key can be identified by using a small number of ciphertext blocks and looking for low entropy in the decrypted plaintext.

Double Encryption

Let $K_1$ and $K_2$ be two block cipher keys.

Encryption: $C = E(E(P, K_1), K_2)$.

If both keys have length $k$, exhaustive attacks require $2^{2k - 1}$ trials on average.

Meet-in-the-Middle Attack

Let $(P, C)$ is a single plaintext-ciphertext pair:

1. For each key $K$, store $C' = E(P, K)$ in memory
2. For any key $K'$, check if $D(C, K') = C'$ (i.e. matches any ciphertext stored in memory)
   • If this is found, $K$ is $K_1$ and $K'$ is $K_2$
   • Check if key values work for other $(P, C)$ pairs

Requirements:

• Storing one plaintext block for every key: $2^{56}$ 64-bit blocks
• An encryption operation for every key
• A decryption operation for every key

Expensive but still much cheaper than brute-forcing $2^{111}$ keys.

Triple Encryption

Requires three keys: $C = E(D(E(P, K_1), K_2), K_3)$. (symmetric so decryption/encryption doesn’t matter? TODO)

This increases the computational requirements enough to make it secure against MITM attacks.

NIST SP 800-131A (2015) approves two-key triple DES, where $K_1 = K_3$, only for legacy use. three-key triple DES is approved.

OpenSSL removed triple DES in 2016. Office 365 stopped using triple DES in 2018.

AES

Designed in an open competition after controversy over DES. Winning submission is ‘Rijndael’.

• 128-bit data block
• 128-, 192- or 256-bit master key
• Byte-based design
• Substitution-permutation network
  • Initial round key addition
  • 10, 12, or 14 rounds (depending on key size)
  • Final round

Algorithm

State Matrix

16-byte data block size arranged in a $4 \times 4$ matrix.

Mixture of finite field operations in $GF(2^8)$ and bit string operations.

Round Transformation

Each round has four basic operations:

1. ByteSub (non-linear substitution): substitute each byte wth a different value using a substitution table
2. ShiftRow (permutation): rotate first row right by zero bytes, second row right by one byte… (bytes wrap to left)
3. MixColumn (diffusion): each column is replaced with result of it being multiplied by a matrix
4. AddRoundKey: XORs array with round key

Substitution-permutation network with block length of $n = 128$ and sub-block length of $l - 8$.

S-box uses look-up table.

Key Schedule

Master key is 128/192/256 bits.

Each of the 10/12/14 rounds uses a 128-bit subkey. There is one subkey per round plus one initial subkey, all derived from the master key.

Security

Some weaknesses but no significant break; most serious real attacks can reduce effective key size by around two bits.

Vulnerable to related-key attack: attacker obtains a ciphertext encrypted with a key related to an actual key in a specified way.

Comparisons with DES

• Data block size: 64 vs 128 bits
• Key size: 56 vs 128/192/256 bits
• Design:
  • Both iterated ciphers
  • DES uses Feistel; AES uses SPN
  • AES substantially faster in both hardware and software

06. Block Cipher Modes of Operation

Block ciphers encrypt single blocks of data, but many applications require multiple blocks to be encrypted sequentially and breaking the plaintext into blocks and encrypting them separately can be insecure.

Modes of operation are standardized with different security and efficiency characteristics.

NIST has many standards (e.g. SP 800-38 series) for this.

Important Features of Different Modes

Different modes can provide confidentiality, authentication (and integrity) or both.

Modes for confidentiality normally include randomization.

Different modes have different efficiency and communication properties.

Randomized Encryption

Problem: the same plaintext block is encrypted to the same ciphertext block every time - allows patterns to be found in long ciphertexts.

Prevention: randomizing encryption schemes by using an initialization vector (IV) which propagates through the entire ciphertext. It may need to be either random or unique.

Alternatively, there could be a variable state which is updated with each block.

Efficiency

Parallel processing: encrypting/decrypting multiple plaintext/ciphertext blocks in parallel.

Error propagation: a bit error in the ciphertext which results in multiple bit errors in the plaintext after decryption.

Padding

Requiring the plaintext to consist of complete blocks.

NIST suggested padding method: append a single $1$ bit to the data string, then with $0$s until the last block is completed.

Notation

• Plaintext message $P$ of length $n$ blocks
• $t$-th plaintext block $P_t$ for $1 \le t \le n$
• Ciphertext message $C$
• $t$-th ciphertext block $C_t$ for $1 \le t \le n$
• Key $K$
• Initialization vector $IV$

Modes can be applied to any block cipher.

Confidentiality Modes

Electronic Code Book (ECB) Mode

A basic mode of a block cipher; each block is encrypted with a key, IV is not used.

Encryption

Decryption

Properties

Error propagation: within blocks.

Cipher Block Chaining (CBC) Mode

Blocks chained together: the plaintext XORed with previous ciphertext (or IV for the first block) and then encrypted.

Encryption

for $1 \le t \le n$ where $C_0 = IV$.

Decryption

Where $C_0 = IV$.

Properties

Error propagation: within blocks and into specific bits in the next block.

Parallel decryption means that decryption does not require the plaintext of previous block. However, it does require the ciphertext of the previous block.

Commonly used for bulk encryption, was often used in TLS up to TLS 1.2.

Counter (CTR) Mode

Synchronous stream cipher mode.

Encryption

The counter and a nonce (IV) are initialized using a random value $N$:

That is, $T_t$ is the concatenation of the nonce $N$ with the block number $t$.

Then, this result is encrypted with the key $K$:

Finally, it is XORed with the plaintext block $P_t$:

Decryption

Properties

A one-bit change in ciphertext produces one-bit change in the plaintext at the same location.

This allows access to specific plaintext blocks without decrypting the whole stream.

CTR mode is the basis for authenticated encryption in TLS 1.2.

Authentication Mode

Message Integrity

Ensuring messages are not altered in transmission: preventing an adversary from re-ordering, replacing, replication and deleting message blocks to alter the received message.

Message integrity and authentication are treated as the same thing.

Proving message integrity is independent from using encryption for confidentiality.

Message Authentication Code (MAC)

Where $M$ is an arbitrary-length message and $K$ a secret key $K$.

The output $T$ is a short, fixed-length tag.

Given both parties share the key $K$:

• The sender computes $T = (M, K)$
• The message $M$ and tag $T$ are sent
• The receiver computes $T' = \mathrm{MAC}(M', K)$ on the received message $M'$ and checks that $T' = T$

MAC Properties

Only the sender and receiver can produce $T$ from $M$.

If $T' = T$, the receiver can conclude the message received is from the expected sender and has not been modified in transit. Otherwise, the receiver can conclude $(M', T)$ was not sent by the expected sender.

It has the basic security property of unforgeability: it is infeasible to produce $M$ and $T$ such that $T = \mathrm{MAC}(M, K)$ without knowledge of $K$.

Basic CBC-MAC

Using block cipher to create a MAC providing message integrity (but not confidentiality).

If $P$ is the message with $n$ blocks:

For $1 \le t \le n$ such that $C_0 = IV$.

$T = \mathrm{CBC\text{-}MAC}(P, K)$ is the last cyphertext: $T = C_n$.

It is unforgeable as long as the message length is fixed.

$IV$ must be fixed and public (e.g. all zeroes): CBC-MAC with a random IV is NOT secure:

• If the IV is random, the IV needs to be sent along with the MAC
• $C_0 = E(P_t \oplus IV, K)$
• Hence, the attacker can modify $P_t$ and $IV$ together such that XORing them gives the same result. As $C_0$ is not modified, none of the subsequent ciphertexts (and hence the tag) stays unchanged

Cipher-based MAC (CMAC)

Standardized, NIST version of CBC-MAC. The IV is all zeroes. The below is as per RFC4493.

Two keys $K_1$ and $K_2$ are derived from the original key $K$.

$K_1$ OR $K_2$ is XORed with $M_n$ (with padding as necessary).

For $1 \le t \le n - 1$ and $C_0 = IV = 00\dots00$:

For the final block:

(That is, $P_n$ concatenated with 1 and then enough zeros to fill up a block)

Then do the same operation as with the previous blocks , except that $P_n'$ is used:

Finally, $\mathrm{CMAC}(P, K) = \mathrm{MSB}_{Tlen}(C_n)$​​

NIST allows the length of the tag, $Tlen$,​ to be any number of bits, although 64 bits or greater is recommended.

The standard recommends the MAC tag $T$ to be of at least length $\mathrm{log}_2(lim/R)$ where:

• $lim$ is a limit on how many invalid messages are detected before $K$ is changed
• $R$ is the acceptable probability that a false message is accepted

Authenticated Encrypted Mode

Two types of input data:

• Payload: both encrypted and authenticated
• Associated data: only authenticated

NIST specifies two modes:

• NIST SP-800-38C (2004) for Counter with CBC-MAC
• NIST SP-800-38D (2007) for Galois/Counter (GCM)

Both use CTR mode but add integrity in different ways.

Both are used in TLS 1.2 and 1.3.

Counter with CBC-MAC (CCM) Mode

CBC-MAC for authentication of all data, CTR mode encryption for the payload.

Inputs:

• Nonce $N$ for CTR mode
• Payload $P$​​ of $Plen$​ bits
• Associated data $A$

Compute the CBC-MAC tag, getting $T$ with length $Tlen$.

Split the message $M$ into blocks of $128$ bits. That is, into $m = \lceil Plen/128 \rceil$ blocks: