Introduction to Cryptography

Overview of Cryptography

• Cryptography is the scientific study of techniques for securing digital information.
• Goals of cryptography include secret communication, authentication, secret/key management, and proof of security.

Actors in Classical Cryptography

• Alice: Message/Secret sender
• Bob: Message/Secret receiver
• Eve: Eavesdropper (wants to listen/intercept)

Terms in Classical Cryptography

• Plaintext (message) m: Original message
• Ciphertext c: Encrypted message
• Key k: Secret information
• Encryption function E(k, m): Converts a plaintext message into a ciphertext
• Decryption function D(k, c): Converts a ciphertext back into its plaintext

Types of Ciphers

• Symmetric (secret key) cryptography: Uses the same key for encryption and decryption
• Asymmetric (public key) cryptography: Uses different keys for encryption and decryption
• Block cipher: Processes data in blocks of, e.g., multiple bytes
• Stream cipher: Processes data character by character (or bit by bit)

Security Assumptions

• Perfect security does not exist in practice
• Some people always need to have access (inherent risk)
• Human factor is a risk in addition to technical aspects
• Any system is only as strong as its weakest link
• Threat model: Security only against certain attacks → How powerful is the attacker?

Kerckhoffs' Principle

• The security of a cipher only depends on the secrecy of the key
• Must not rely on the cipher/algorithm being secret
• Modern ciphers/algorithms are public

The Vernam Cipher

• Also called one-time pad (OTP)
• Provably secure if message m and key k have exactly the same length
• Key never reused
• Key bit string is uniformly distributed
• Ciphertext does not reveal anything about plaintext since all plaintexts are equally likely under a random key

Overview of Classical Ciphers

• Susceptible to various kinds of attacks
• No longer secure (do not use them)
• Examples of classical ciphers include Caesar cipher, Vigenère cipher, and Enigma

Caesar Cipher

• General idea: Shifting the alphabet by a constant offset (with rollover)
• Offset is the (cipher) key
• Poly-alphabetic substitution cipher

Vigenère Cipher

• General idea: Shifting the alphabet by a position-dependent offset (with rollover), repeated in regular intervals if necessary
• For individual characters: Caesar cipher with position-dependent key
• Poly-alphabetic substitution cipher
• Key length determines how many different shifts/position-dependent keys exist

Enigma

• Complex substitution cipher with multiple variants
• Machine-assisted encryption and decryption with code books

Overview of Cryptanalysis

• Dictionary definition: “the solving of [ciphers] or cryptographic systems”
• Old threat model: The cipher/algorithm is not known
• Modern threat model: The cipher is known
• Recap: Security only against certain attacks → How powerful is the attacker?
• Different attack scenarios
• Examples of simple cryptanalysis include frequency analysis and attacks on the Vigenère cipher

Attack Scenarios

• Different potential goals of an attacker
• Recover/decrypt plaintext from a particular ciphertext
• Recover key to recover plaintexts from arbitrary ciphertexts (stronger attacker)

Brute-Force Search Attack

• Try all possible keys until the correct one is found
• More work (processing power) for longer keys
• Key space: The set of all possible keys
• Infeasible key space sizes for attackers (e.g., 256 bits)

Simple Cryptanalysis Example: Frequency Analysis

• Assumption: Plaintext is a message in natural language, e.g., English
• The letter frequencies in natural-language texts are known
• Frequent characters in the English language are E, T, A,...### Simple Cryptanalysis Example: Frequency Analysis
• For mono-alphabetic substitution ciphers (e.g., Caesar), frequencies are expected to be similar, with corresponding letters being shifted.
• Consistent shift (in the alphabet) between similarly frequent characters allows offset/key recovery (some margin of error is useful!).
• Example: Most frequent letter (G vs. E) → Difference of +2 (C); Second-most frequent letter (V vs. T) → Difference of +2 (C)...→ Key is C.
• Caveat: Longer text required, as character frequencies only converge for longer, language-typical texts; foreign words harm analysis.

Attacks on the Vigenère Cipher: Frequency Analysis Attempt

• For poly-alphabetic substitution ciphers like Vigenère, frequency analysis on the whole ciphertext does not work.
• Same plaintext letter is mapped to different ci at different positions → Character frequencies are “smeared” (more for longer keys).

Attacks on the Vigenère Cipher: Modified Frequency Analysis

• Vigenère cipher is Caesar cipher with position-dependent key → slide 15.
• Key repeats every ||k|| positions: Vigenere(k, mi) = Caesar (ki mod ||k|| , mi) → slide 16.
• A Vigenère ciphertext is a merge of ||k|| Caesar ciphertexts: C0 = {ci : i mod ||k|| = 0}, ..., C||k||−1 = {ci : i mod ||k|| = ||k|| − 1}.
• If the key length ||k|| is known, perform frequency analysis on each Caesar ciphertext Cn individually and determine shift/key for each Caesar ciphertext.
• Combine keys of Caesar ciphertexts into Vigenère key.

Attacks on the Vigenère Cipher: Kasiski’s Method

• Key repeats every ||k|| positions → same plaintext words result in same ciphertext words if they are an integer multiple of ||k|| apart.
• In long texts, the same bigram/trigram/etc. appears at positions which are an integer multiple of ||k||.
• Differences in positions are very likely multiples of the key length → Greatest common divisor (gcd) of the position differences is very likely the key length or a multiple thereof.

Attacks on the Vigenère Cipher: Kasiski’s Method (continued)

• Example: WS bigram from example (→ slide 29): At positions 126, 294, 470, and 550 → Position differences 168, 80, and 80.
• Example: OQH trigram from example (→ slide 30): At positions 93 and 313 → Position difference 220.
• gcd(168, 80, 80, 220) = 4 → Key length is likely 4 or a multiple of 4.
• Alternative approach: Perform frequency analysis of the factors of the position differences (e.g., of all bigrams) → More/most frequent factors are very likely factors of the key length.

Attacks on the Vigenère Cipher: Auto-correlation

• Key repeats every ||k|| positions → Ciphertext characters which are an integer multiple of the key length apart are more likely to be the same.
• Compute incidence of identical characters (coincidence) at ciphertext character positions i + l for all ciphertext characters ci with any plausible key length l.
• Compute incidence Il for all plausible key lengths l ∈ N+ → Key length arg maxl Il with highest incidence is very likely the key length or a multiple thereof.
• Illustration of character coincidence (reference: R at position 2): Assuming key length of l = 4 → 3 out of 15 matches (20%); Assuming key length of l = 3 → 0 out of 20 matches (0%); Expected coincidence: ≈ 4% (in longer texts).