Exam 5

Character Substitution

Definition: A cipher technique where each character in the plaintext is replaced with another character according to a rule or key.

ROT13

Definition: A simple substitution cipher that shifts each letter by 13 places in the alphabet.

Additional Info:

• Not secure — easily reversible by applying ROT13 again.

• Brute force possibilities: For 7-bit ASCII (128 values):

  • Best case: 0 tries

  • Worst case: 128 tries

  • Average case: 64 tries

Substitution Cipher

Definition: Replaces each letter of the plaintext with another letter based on a permutation of the alphabet.

Additional Info:

• Total possible keys: (Alphabet size - 1)! = 25! for 26-letter alphabet.

• Vulnerable to frequency analysis (e.g., common letters like E, T, A…).

Two-Letter Substitution – Playfair Cipher

Definition: A digraph substitution cipher that encrypts pairs of letters using a 5x5 matrix of the alphabet.

Additional Info:

• More secure than monoalphabetic substitution.

• Still easy to break with modern analysis tools.

• Key space: (25 × 25) combinations for each digraph.

Kerckhoffs’s Principle

Definition: A foundational principle in cryptographic system design emphasizing security should rely solely on key secrecy.

Key Points:

• The system must be indecipherable even if known.

• Key must be memorable and changeable without written notes.

• Must be usable over telegraph systems, portable, and user-friendly.

• No secrecy of the algorithm is required.

Stream Cipher

Definition: Encrypts plaintext one bit or byte at a time, typically by XORing it with a keystream.

Additional Info:

• Keystream must be non-repeating and pseudorandom.

• Suitable for real-time encryption (e.g., video, audio streams).

• Symmetric encryption.

Block Cipher

Definition: Encrypts fixed-size blocks of plaintext (e.g., 64 or 128 bits) by mixing it with a key.

Additional Info:

• Processes one block at a time, using complex substitutions and permutations.

• Examples: AES, DES

• Requires padding for partial blocks.

Attack Models 

Ciphertext-Only Attack (COA)

Definition: The attacker has access only to ciphertexts, not the corresponding plaintext.

Additional Info:

• Hardest model to attack.

• Often requires statistical or brute force methods.

Known-Plaintext Attack (KPA)

Definition: The attacker has both plaintext and matching ciphertext samples.

Additional Info:

• Can be used to deduce the key or the cipher structure.

Chosen-Plaintext Attack (CPA)

Definition: The attacker can choose arbitrary plaintexts and obtain their ciphertexts.

Additional Info:

• Useful in analyzing how specific patterns are encrypted.

• Used in block cipher testing and analysis.

Chosen-Ciphertext Attack (CCA)

Definition: The attacker can choose ciphertexts and obtain their decrypted plaintexts.

Additional Info:

• Dangerous for systems without proper validation or padding protections.

Block Ciphers

Block Ciphers

Definition: A method of encrypting data in fixed-size blocks (e.g., 64, 128 bits), rather than bit-by-bit or character-by-character.

Additional Info:

• Symmetric encryption: Uses the same secret key for encryption and decryption.

• Operation: Plaintext is divided into blocks → each block is scrambled using an algorithm and key → ciphertext is produced.

• Padding: If plaintext doesn’t perfectly fit the block size, extra bits are added.

• Applications: Encrypt any digital data – text, images, audio, video.

• Design notes: Typically operate on bits, not characters; modern ones can handle arbitrary data.

DES (Data Encryption Standard)

Definition: A symmetric block cipher developed in the 1970s using 64-bit blocks and a 56-bit key.

Additional Info:

• Method: 16 rounds of:

  • Expansion (32 to 48 bits),

  • Key mixing (XOR with subkeys),

  • Substitution (via S-boxes),

  • Permutation (P-boxes).

• Historical importance: Used globally, though now considered insecure.

• Vulnerabilities: Small block and key sizes → easily breakable by brute force.

• Real-world break: EFF’s “Deep Crack” hardware broke DES in ~56 hours.

• Educational value: Helps understand block cipher design principles.

3DES (Triple DES)

Definition: An enhancement of DES applying it three times to increase security.

Additional Info:

• Modes:

  • 2TDES: Uses two keys (K1, K2, K1).

  • 3TDES: Uses three different keys (K1, K2, K3).

• Steps: Encrypt with K1 → Decrypt with K2 → Encrypt with K3.

• Security: Significantly more secure than DES.

• Drawback: Much slower than modern alternatives.

• Use case: Still used in hardware and legacy systems due to familiarity.

Attack Models

Definition: Strategies adversaries use to compromise encrypted data.

Additional Info (types):

• COA (Ciphertext Only Attack): Only ciphertext is available.

• KPA (Known Plaintext Attack): Attacker knows some plaintext-ciphertext pairs.

• CPA (Chosen Plaintext Attack): Attacker can encrypt plaintexts of choice.

• CCA (Chosen Ciphertext Attack): Attacker can decrypt selected ciphertexts.

• Why it matters: Block cipher modes and design must account for these to stay secure.

Why Use Block Ciphers?

• Consistency: Fixed-size blocks make encryption and decryption predictable and easier to implement.

• Generality: Modern block ciphers can encrypt any data—text, images, audio, video—because they treat everything as bitstreams.

• Security: When implemented properly (e.g., with padding and block modes), they resist various attack models.

Padding in Block Ciphers

• Necessity: Ensures that plaintext fits block size (e.g., 64-bit blocks).

• Padding Schemes: Multiple schemes exist, e.g., PKCS#7.

• Must be reversible: The amount of padding must be known or derivable so it can be removed after decryption.

Block Cipher Modes of Operation

• Purpose: Prevent patterns in ciphertext when the same plaintext blocks repeat.

• Examples (not detailed in slides, but implied):

  • ECB (Electronic Code Book) – not secure.

  • CBC (Cipher Block Chaining)

  • CTR (Counter Mode)

  • OFB, CFB, etc.

• See: Block Cipher Modes

Cryptanalysis Techniques

 (briefly mentioned)

• Brute Force: Try every key – feasible for DES.

• Differential Cryptanalysis: Analyze how differences in plaintext affect ciphertext.

• Meet-in-the-middle: Optimized brute force for multiple encryptions like 2DES.

• General note: Even strong algorithms can become weak over time due to new attacks or computational advances.

Feistel Network Structure

• Used by: DES and many others (including Blowfish, Twofish).

• Advantage: Simplifies encryption/decryption logic – only one function needed, just applied in reverse for decryption.

Evolution of Block Ciphers

• From DES to AES: AES uses 128-bit blocks and keys of 128/192/256 bits.

• Other successors: Blowfish, Twofish, Serpent – typically larger key sizes, more rounds, faster, and stronger.

• Optimization: Many modern ciphers are designed for speed and software/hardware efficiency.

Why Old Ciphers are Still Around

• Legacy Systems: Old standards like DES still used in older systems or embedded hardware.

• Simplicity: Easier to implement and verify.

• But: Not recommended for new designs.

Passwords

Definition: A common form of authentication where a user inputs a secret (the password) to prove their identity.

Additional Info:

• Easy to use and implement, though not always secure.

• Typically 6–16 characters, often including letters (both cases), numbers, and sometimes symbols.

• Strength ≈ alphabet size ^ length → e.g., for 62-character alphabet (26 upper + 26 lower + 10 digits), 8 characters yields ≈ 2.18 × 10¹⁴ possibilities.

• Entropy formula: log₂(alphabet size) × password length (e.g., ≈ 48 bits for 8-character mixed password).

Password Security Concepts

• Time-based protection: Limit time between login attempts (e.g., 3 seconds) or max number of attempts.

• Dictionary attacks: Try passwords from pre-made lists of common choices.

• Rainbow tables: Precomputed tables of hash outputs to speed up reverse lookup of passwords.

  • Mitigated using salts.

Salt (in password hashing)

Definition: A unique, random value added to passwords before hashing, to prevent use of rainbow tables.

Additional Info:

• Typically 16–32 bits now; 8 bits considered too small.

• Acts like a nonce (used once).

• For each user: store username, salt, and hashed(password + salt).

• Prevents two users with the same password from having the same hash.

Hash Collisions (Why to Avoid)

Definition: When two different inputs produce the same hash output.

Why it’s bad: It means a different password could be accepted, breaking the system’s security.

Biometrics

Definition: Authentication using biological traits like fingerprints, retina scans, voice, etc.

Additional Info:

• Concern: Once leaked, biometric data can’t be “changed” like passwords.

• Suggestion: Store only partial data (e.g., every other bit) to reduce risk.

Digital Signature

Definition: A cryptographic technique to verify the authenticity and integrity of a message.

Additional Info:

• Authentication: Confirms the sender.

• Integrity: Confirms message wasn’t altered.

• Non-repudiation: Sender can’t deny having sent the message.

• Involves public-key cryptography:

  • Sign: Encrypt with private key.

  • Verify: Decrypt with public key.

• Algorithms: DSA, RSA (use modular arithmetic, factorization, elliptic curves, etc.).

Key Pair (Public & Private)

Definition: Asymmetric cryptographic keys used in digital signatures and encryption.

Additional Info:

• Public Key: Shared freely (websites, directories).

• Private Key: Kept secret by the owner.

• Ensures only the private key owner could have signed the message.

Integrity

Definition: Assurance that a message has not been changed in transit or storage.

Additional Info:

• Critical component of both password storage and digital signatures.

Block Ciphers

Definition: Encrypts data in fixed-size blocks using a symmetric key.

Reinforced Concepts from Quiz Slides:

• Padding: Needed when data isn’t a perfect multiple of block size.

  • Example: If block size is 8 bits and data is 1100 1010 1001, padding is added to form a second complete block: 1001 1000.

• Initialization Vector (IV): Random/unique data used in the first block to ensure identical plaintexts encrypt differently.

• Block Modes of Operation:

  • Purpose: Avoid patterns in ciphertext for repeated blocks.

  • Examples: ECB (insecure), CBC, CTR.

• Block & Key Sizes (Examples):

  • DES: 64-bit blocks, 56-bit key.

  • AES: 128-bit blocks, keys of 128, 192, or 256 bits.

  • Playfair: 25-letter alphabet, operates on digraphs (not bitwise).

DES (Data Encryption Standard)

Reinforced Concepts:

• Basic structure includes: expansion → key mixing → substitution → permutation (done 16 times).

• 2DES (Same key): No real security gain — susceptible to known attacks like meet-in-the-middle.

• 2DES (Different keys): Adds some security, but better to use 3DES or modern alternatives.

Attack Models

Reiterated Quiz Concepts:

• COA: Ciphertext-only attack.

• KPA (on Playfair example): Given encrypted text and known plaintext, attacker can deduce key matrix.

• CPA & CCA: Require access to encryption/decryption service.

• Application: Understanding these models is key to evaluating the strength of a block cipher setup.

Passwords

Expanded Quiz Concepts:

• Difference from cryptographic keys:

  • Passwords: User-chosen, typically shorter and less random.

  • Keys: Usually system-generated, longer, high entropy.

• Common Password Issues:

  • Too short, common words → vulnerable to dictionary attacks.

  • Poor entropy or reuse → easy targets for rainbow tables unless salted.

Brute Force Attack

Definition: Trying every possible key until the correct one is found.

Key Notes:

• Effective if key length is short (e.g., DES).

• Computationally expensive for longer keys (e.g., AES-256).

Birthday Attack

Definition: Targets hash functions by exploiting probability of hash collisions (two inputs with the same output).

Key Notes:

• Named after the birthday paradox.

• Probability of collision becomes significant at about 2ⁿ/² attempts for an n-bit hash.

• Used to forge digital signatures or certificates.

Meet-in-the-Middle Attack

Definition: Used against encryption schemes like double DES by precomputing encryptions from one end and decryptions from the other.

Key Notes:

• Efficient in reducing brute-force time complexity.

• Time-space tradeoff: requires a large amount of memory.

Length Extension Attack

Definition: Exploits certain hash functions (like MD5, SHA-1, SHA-2) to append data to a hashed message without knowing the original input.

Key Notes:

• Only works on hash constructions vulnerable to this flaw (Merkle–Damgård).

• Can lead to forged message authentication codes (MACs).

Hashing

Definition: One-way transformation of data into a fixed-size string (hash or digest).

Important Notes:

• Not encryption: it’s irreversible.

• Used for integrity, fingerprinting, and authentication.

• Must avoid collisions: different inputs producing the same output.

Block Cipher Modes of Operation

Classical Ciphers (Character-based)

• Caesar Cipher / ROT-N: Shift characters by N positions in alphabet.

• Vigenère Cipher: Uses a repeating key to shift letters — polyalphabetic substitution.

• Substitution Cipher: Replace each character based on a key mapping.

• Playfair Cipher:

  • Block cipher with digraphs (2-letter blocks) using a 5x5 key matrix.

  • Handles padding, duplicates, and corner swaps.

• Scytale Cipher:

  • Transposition cipher using a wrapped strip on a rod (used in Sparta).

  • Breakable via brute-force on “diameter” or wrap width.

Foundational Cryptographic Theories

• Kerckhoffs’ Principle: The security of a system should rely only on the secrecy of the key, not the algorithm.

• Shannon’s Maxim: “The enemy knows the system” — assume adversaries know everything but the key.

Character Encodings in Cryptography

• Fixed Length (historical):

  • Baudot (5 bits), BCD (6 bits), ASCII (7 bits), EBCDIC (8 bits)

• Variable Length (modern):

  • UTF-8, UTF-16, UTF-32

Hashing & Cryptographic Roles

• Used for integrity: verifying that content hasn’t changed.

• Key for digital signatures, certificate verification.

• Must be collision-resistant, efficient, and irreversible.

Principles of Secure Systems

• Should be usable, modifiable, portable, and non-reliant on secrecy of the algorithm.

• Prefer larger blocks, added randomness, and robust key distribution.

Attack Enhancements

• Chosen-Plaintext Attacks (CPA): Encrypt carefully chosen inputs (e.g., AA, AB, AC…ZZ for Playfair).

• Padding as a defense/enhancement: Adds unpredictability, prevents pattern recognition.

Block Ciphers

• Definition: Encrypts fixed-size blocks of bits (e.g., 64 or 128 bits) using a symmetric key.

• Use Cases: Encrypt text, files, multimedia, etc.

• Needs: Padding (to fit block size), and a mode of operation.

Modes of Operation

DES (Data Encryption Standard)

• Block Size: 64 bits

• Key Size: 56 bits (+ 8 parity bits)

• Structure: 16 rounds using expansion, substitution (S-boxes), permutation (P-boxes).

• Status: Deprecated — vulnerable to brute force.

• Historical Note: Designed by IBM, adopted by NIST.

3DES (Triple DES)

• Method: EDE (Encrypt, Decrypt, Encrypt)

• Keys:

  • 1-Key = Original DES

  • 2-Key = Obsolete

  • 3-Key = Most secure

• Slower, but more secure than DES.

Attack Models

Cryptographic Attacks

Hashing

• Definition: Irreversible mapping of data to a fixed-size digest.

• Use Cases: Password storage, integrity checks, digital signatures.

• Must be:

  • Collision-resistant

  • Preimage-resistant

  • Fast but secure

Hash Attacks

Salt

• Purpose: Adds randomness to passwords before hashing.

• Avoids: Rainbow table attacks.

• Stored with: Username and hashed password.

Passwords

• Strength: Entropy = log₂(alphabet size) × length.

• Issues:

  • Reuse

  • Weak entropy

  • Dictionary and rainbow table attacks

Biometrics

• Examples: Fingerprint, retina, voice.

• Issue: Cannot be changed if leaked.

• Tip: Store partial data (e.g., alternate bits).

Digital Signatures

• Provides: Authentication, integrity, non-repudiation.

• Method: Sign with private key, verify with public key.

• Algorithms: RSA, DSA, ECDSA

Theoretical Foundations

Classical Ciphers

User Authentication

• Users can be added, removed, or authenticated using passwords or other personal data.

• Hashing is used for password storage with SHA-2 or SHA-3 (inferred best practice).

Key Generation & Sharing

• Symmetric keys: Used for AES or 3DES encryption.

• Asymmetric keys (e.g., RSA): Used for file encryption/decryption and secure key sharing.

• DH-style key exchange lets two parties compute a shared key over the network.

File Upload and Encryption Flow

1. User uploads a file (text/image).

2. Chooses encryption method: AES or 3DES.

3. Optionally selects:

   • Key size (AES-128, 192, or 256).

   • Mode (e.g., CBC, ECB, CFB, etc.).

   • Random IV generation.

4. Encrypted file is returned or stored.

Decryption

• User supplies key or public/private pair.

• Decrypted file is generated.

File Hashing & Comparison

• User hashes files (with SHA-2 or SHA-3).

• File integrity can be checked by comparing hashes (e.g., upload the same file again).

AES vs. 3DES

• AES is newer, faster, and more secure — used for modern secure applications.

• 3DES is included for educational/historical reasons and compatibility.

Block Modes

• CBC (Cipher Block Chaining): More secure than ECB — uses IV and previous ciphertext block to XOR.

• CTR (Counter): Allows parallel encryption/decryption — converts block cipher into stream-like cipher.

Key Handling

• Symmetric: Same key used to encrypt and decrypt.

• Asymmetric (RSA):

  • Encrypt with public key → only private key can decrypt.

  • Sign with private key → verify with public key (authenticity check).

Hashing

• SHA-2 (e.g., SHA-256): Common and strong — used in Bitcoin, HTTPS, etc.

• SHA-3: Based on Keccak — offers similar strength with a different internal structure.

RSA (Rivest-Shamir-Adleman)

Type: Asymmetric encryption (uses a public/private key pair)

How it works:

1. Key Generation:

   • Choose two large prime numbers: p and q.

   • Compute n = p × q — this is used as the modulus.

   • Compute Euler’s totient: φ(n) = (p-1)(q-1).

   • Choose an encryption exponent e (commonly 65537) such that e and φ(n) are coprime.

   • Calculate the decryption exponent d such that: d × e ≡ 1 mod φ(n).

2. Keys:

   • Public key: (e, n) — anyone can use this to encrypt.

   • Private key: (d, n) — only you know this to decrypt.

3. Encryption:

   • Convert message M into a number < n.

   • Compute C = M^e mod n.

4. Decryption:

   • Compute M = C^d mod n.

Uses:

• Encrypt small messages or keys.

• Sign messages (reverse: sign with private key, verify with public).

• Key exchange in secure websites (TLS/SSL).

AES (Advanced Encryption Standard)

Type: Symmetric block cipher

How it works:

1. Key Sizes: 128, 192, or 256 bits.

2. Block Size: Always 128 bits.

3. Rounds:

   • 10 rounds (AES-128), 12 (AES-192), 14 (AES-256).

4. Each round includes:

   • SubBytes: Substitute bytes using S-box.

   • ShiftRows: Rotate rows.

   • MixColumns: Mix column bytes (except last round).

   • AddRoundKey: XOR with part of the expanded key.

5. Encryption & Decryption:

   • Uses the same key.

   • In decryption, reverse the transformations.

Uses:

• File and disk encryption.

• TLS, VPNs, encrypted messaging apps.

• Extremely fast and secure when used with proper key/mode.

Diffie-Hellman Key Exchange

Type: Key exchange protocol (NOT encryption itself)

How it works:

1. Shared Public Info:

   • A large prime number p and a base g (primitive root modulo p).

2. Private secrets:

   • Alice chooses secret a, computes A = g^a mod p.

   • Bob chooses secret b, computes B = g^b mod p.

3. Exchange:

   • Alice sends A to Bob.

   • Bob sends B to Alice.

4. Shared secret:

   • Alice computes: K = B^a mod p.

   • Bob computes: K = A^b mod p.

Result: Both end up with the same K, the shared secret key, without ever sending it directly.

Uses:

• To safely agree on a symmetric key over an insecure channel.

• Often used in TLS (HTTPS), VPNs, Signal protocol (end-to-end encryption).

Summary Chart

OTR (Off-the-Record Messaging):

A cryptographic protocol for instant messaging that provides encryption, authentication, forward secrecy, and deniability, allowing secure and private conversations without creating verifiable transcripts.

Deniable Authentication:

A property of secure communication where a message can be authenticated between sender and receiver, but neither party can prove to a third party that the message was sent — ensuring privacy and plausible deniability.

Forward Secrecy (Perfect Forward Secrecy):

A security feature that ensures past encrypted communications remain secure even if the long-term keys (like private keys) are later compromised. It achieves this by using ephemeral session keys that are generated and discarded for each session.