Traditional Symmetric Key Cryptography and Mathematics Study Guide

Introduction to Traditional Symmetric Key Ciphers

• Definition of Cryptography: Cryptography is the science and art of securing information by converting it into a form that is unreadable to unauthorized users.
• Primary Objective: To protect data during storage and transmission from unauthorized access, modification, or misuse.
• Assumptions: Cryptography assumes the presence of adversaries who may attempt to intercept or tamper with information.
• Digital Foundation: In the modern digital world, cryptography is the foundation of secure communication systems, including online banking, e-commerce, email systems, cloud computing, and blockchain technologies.
• Usage Scenarios: These techniques are essential whenever sensitive data (e.g., passwords, credit card details, or confidential messages) is transmitted over the internet, ensuring only the intended recipient can read it.

Security Goals: Confidentiality, Integrity, and Availability

• Confidentiality:
  • Ensures information is kept secret from unauthorized users.
  • Protects data such as military secrets, business plans, and bank accounts.
  • Applies to both stored data and data in transmission.
• Integrity:
  • Ensures information is accurate and not altered improperly.
  • Allows changes only by authorized users and approved processes.
  • Prevents errors caused by malicious attacks or system failures.
• Availability:
  • Ensures information is accessible when needed.
  • Allows authorized users to access data without interruption.
  • Prevents harm caused by system downtime or denial of service.

Security Attacks and Threats

• Threats to Confidentiality:
  • Snooping: Refers to unauthorized access or interception of data (e.g., intercepting a file sent over the internet). This is prevented by encryption (encipherment).
  • Traffic Analysis: Occurs even when data is encrypted. The attacker studies communication patterns (sender/receiver addresses and message timing) to infer the nature of transactions.
• Threats to Integrity:
  • Modification: The attacker alters intercepted data for personal benefit (e.g., changing a bank transaction amount). They may also delete or delay messages.
  • Masquerading (Spoofing): The attacker impersonates a legitimate entity (e.g., stealing a bank card PIN or pretending to be a bank server to steal user data). This threatens both authentication and confidentiality.
  • Replaying: The attacker captures a valid message and retransmits it later (e.g., recording a payment request to receive multiple payments). The contents are not altered, only resent.
  • Repudiation: Performed by a legitimate participant; a sender may deny sending a message, or a receiver may deny receipt. This threatens non-repudiation in electronic transactions.
• Threats to Availability:
  • Denial of Service (DoS): Aims to slow down or disrupt services. Strategies include:
    1. Sending many bogus requests to overload and crash a server.
    2. Intercepting and deleting server responses.
    3. Blocking client requests to cause retransmissions that overload the system.

Passive Versus Active Attacks

• Passive Attacks:
  • Goal: Obtain information only. There is no data modification or system disruption.
  • Examples: Snooping and Traffic Analysis.
  • Difficulty: Very difficult to detect because no visible damage occurs. Prevention via data encipherment is the primary defense.
• Active Attacks:
  • Goal: Change data or harm the system. They threaten integrity and availability.
  • Examples: Modification, Masquerading, Replaying, Repudiation, and Denial of Service.
  • Difficulty: Normally easier to detect than to prevent because of the varied ways they can be launched.

Security Services and Mechanisms

• ITU-T Standards: The International Telecommunication Union-Telecommunication Standardization Sector provides security services and mechanisms.
• Mechanisms: Security mechanisms include encipherment, digital signature, access control, data integrity, authentication exchange, traffic padding, routing control, and notarization.
• Relation Between Services and Mechanisms:
  • Data Confidentiality: Implemented via encipherment and routing control.
  • Data Integrity: Implemented via encipherment, digital signature, and data integrity mechanisms.
  • Authentication: Implemented via encipherment, digital signature, and authentication exchanges.
  • Nonrepudiation: Implemented via digital signature, data integrity, and notarization.
  • Access Control: Implemented via access control mechanisms.

Security Techniques: Cryptography and Steganography

• Cryptography: Derived from Greek for “secret writing.” It is the science of transforming messages to make them secure. Modern cryptography includes:
  • Symmetric-key encipherment.
  • Asymmetric-key encipherment.
  • Hashing.
• Steganography: Derived from Greek for “covered writing.” Unlike cryptography, which conceals a message’s content, steganography conceals the existence of the message itself by covering it with something else.

Mathematics of Cryptography: Integer Arithmetic

• Integer Set ($Z$): Contains all integral numbers (no fractions) from negative to positive infinity: $Z = \{ \dots, -2, -1, 0, 1, 2, \dots \}$.
• Binary Operations: Cryptography commonly uses addition, subtraction, and multiplication.
• Integer Division: If we divide $a$ by $n$, we get a quotient $q$ and a remainder $r$: $a = q \times n + r$.
  • Restrictions in Cryptography: The divisor must be a positive integer ($n > 0$) and the remainder must be a nonnegative integer ($r \geq 0$).
  • Example: If $a = 255$ and $n = 11$, then $q = 23$ and $r = 2$.
• Greatest Common Divisor (GCD): The largest integer that divides two positive integers.

The Euclidean Algorithms

• Standard Euclidean Algorithm: Efficiently finds the GCD of two large integers based on two facts:
  • Fact 1: $\text{gcd}(a, 0) = a$
  • Fact 2: $\text{gcd}(a, b) = \text{gcd}(b, r)$, where $r$ is the remainder of $a/b$.
  • Example: $\text{gcd}(36, 10) = \text{gcd}(10, 6) = \text{gcd}(6, 4) = \text{gcd}(4, 2) = \text{gcd}(2, 0) = 2$.
  • Trace Example: For $\text{gcd}(2740, 1760)$, the final result is $20$.
  • Trace Example: For $\text{gcd}(25, 60)$, the steps are $\text{gcd}(60, 25) \rightarrow \text{gcd}(25, 10) \rightarrow \text{gcd}(10, 5) \rightarrow \text{gcd}(5, 0) = 5$.
• Extended Euclidean Algorithm: Given integers $a$ and $b$, this finds integers $s$ and $t$ such that: $s \times a + t \times b = \text{gcd}(a, b)$.
  • Example: Given $a = 161$ and $b = 28$, find $gcd(161, 28)$ and values for $s$ and $t$.

Modular Arithmetic and Residues

• Modulo Operator: The binary operator $mod$ focuses only on the remainder $r$ from the division $a = q \times n + r$.
  • Terminology: $n$ is the modulus, and $r$ is the residue.
• Residue Result Examples:
  • $27 \pmod{5} = 2$
  • $36 \pmod{12} = 0$
  • $-18 \pmod{14} \rightarrow -4 + 14 = 10$
  • $-7 \pmod{10} \rightarrow -7 + 10 = 3$
• Set of Residues ($Z_n$): The result is always an integer between $0$ and $n - 1$.
• Congruence ($\equiv$): Used to show two integers are congruent modulo $n$.
• Modular Operations in $Z_n$:
  • Add $7$ to $14$ in $Z_{15}$: $(7 + 14) \pmod{15} = 6$
  • Subtract $11$ from $7$ in $Z_{15}$: $(7 - 11) \pmod{15} = -4 \rightarrow 11$
  • Multiply $11$ by $7$ in $Z_{20}$: $(11 \times 7) \pmod{20} = 77 \pmod{20} = 17$

Traditional Symmetric-Key Ciphers

• Overview: While simpler and less secure than modern ciphers, they demonstrate the basic foundations of cryptography. They are easily broken by modern computers.
• General Components:
  • Plaintext: The original message (e.g., from Alice to Bob).
  • Ciphertext: The message converted into an unreadable form for transmission.
  • Cipher: The encryption and decryption algorithms.
  • Key: A shared secret value or set of values operated on by the algorithm.
• Mechanics:
  1. Alice uses an encryption algorithm $E_k(x)$ and shared key $K$ on plaintext $P$ to create ciphertext $C$.
  2. Bob uses a decryption algorithm $D_k(x)$ and the same key $K$ on $C$ to recover $P$.
  3. $E_k$ and $D_k$ are mathematical inverses.
• Kerckhoff’s Principle: One must assume the adversary (Eve) knows the algorithm. Resistance to attack must rely solely on the secrecy and domain size of the key.

Cryptanalysis: Traditional Attacks

• Ciphertext-Only Attack: Eve has only the ciphertext. She uses:
  • Brute-Force Attack: Testing all possible keys in the key domain until the plaintext makes sense.
  • Statistical Attack: Analyzing the frequency of characters (e.g., in English, 'e' is the most common).
  • Pattern Attack: Identifying repeated patterns within the ciphertext.
• Known-Plaintext Attack: Eve has access to previous plaintext/ciphertext pairs to analyze current messages.
• Chosen-Plaintext Attack: Eve chooses specific plaintext and intercepts the resulting ciphertext (e.g., accessing Alice's computer).
• Chosen-Ciphertext Attack: Eve chooses ciphertext and decrypts it to form a pair (e.g., accessing Bob's computer).

Categories of Traditional Ciphers

1. Substitution Ciphers

Replace one symbol with another.

Monoalphabetic Ciphers

A character in plaintext is always changed to the same character in ciphertext, regardless of position.

• Additive (Shift/Caesar) Cipher: $(P + k) \pmod{26}$.
  • Example: Encrypt "hello" with $k=15$.
    • h (07) + 15 = 22 (W)
    • e (04) + 15 = 19 (T)
    • l (11) + 15 = 00 (A)
    • l (11) + 15 = 00 (A)
    • o (14) + 15 = 03 (D)
    • Result: WTAAD.
• Multiplicative Cipher: $(P \times k) \pmod{26}$.
  • Key Domain: Key must be in $Z_{26}^* = \{1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23, 25\}$.
  • Example: Encrypt "hello" with $k=7$.
    • h (07) * 7 = 49 ≡ 23 (X)
    • e (04) * 7 = 28 ≡ 02 (C)
    • l (11) * 7 = 77 ≡ 25 (Z)
    • o (14) * 7 = 98 ≡ 20 (U)
    • Result: XCZZU.
• Affine Cipher: Combines additive and multiplicative ciphers.
  • Encryption: $C = (P \times k_1 + k_2) \pmod{26}$.
  • Example: "hello" with key pair (7, 2) results in ZEBBW.

Polyalphabetic Ciphers

Each occurrence of a character may have a different substitute based on its position.

• Autokey Cipher: The first subkey is a secret value; subsequent subkeys are values taken from the previous plaintext characters.
• Vigenere Cipher: Uses a repeating keyword (length $m$) as a key stream.
  • Example: "She is listening" with keyword "PASCAL".
  • Key Stream (15, 0, 18, 2, 0, 11) repeats.
  • Ciphertext: HHWKSWXSLGNTCCG.
• Playfair Cipher: Uses a $5 \times 5$ matrix of letters (I/J are same). Encrypts pairs (digraphs). Rules include sliding right (same row), sliding down (same column), or forming rectangles.
  • Example: "hello" becomes "he, lx, lo" (adding bogus 'x' to separate same-letter pair). Ciphertext: ECQZBX.
• Hill Cipher: A block cipher using an $m \times m$ matrix as a key. Plaintext blocks must have a multiplicative inverse matrix for decryption.
• One-Time Pad: Perfect secrecy achieved by using a random key as long as the message. Impossible to break but difficult to implement commercially due to key distribution.
• Rotor Cipher: Uses rotating machinery to change mapping for every character. Example: rotating once for each letter converts "bee" into something like "BCA".

2. Transposition Ciphers

Do not substitute symbols; they change the location (reorder/permute) of symbols.

• Keyless Transposition:
  • Rail Fence Cipher: Write plaintext in a zigzag pattern and read row by row.
    • Example: "Meet me at the park" becomes MEMATEAKETETHPR.
  • Columnar: Write row by row, read column by column.
• Keyed Transposition: Divide plaintext into blocks and use a permutation key to reorder characters within each block.
  • Example: For groups of 5 with key (3, 1, 4, 5, 2), the 3rd character moves to the 1st position, 1st to 2nd, etc.

Stream and Block Ciphers

• Stream Ciphers: Encryption and decryption occur one symbol (character or bit) at a time. The key stream can be predetermined or algorithmically generated (potentially dependent on previous symbols).
• Block Ciphers: Symbols are grouped into blocks (size $m > 1$). A single key encrypts the whole block together. The ciphertext block depends on every character in the plaintext block.