Cryptanalysis & Classical Ciphers: Breaking Codes & Old-School Encryption

TAKEAWAYS:

• Classical ciphers (Caesar, Vigenère, Playfair, Hill) use substitution/transposition but are vulnerable to frequency analysis or algebraic attacks.
• Cryptanalysis exploits patterns (e.g., "e" appears 12% in English) or weak keys (e.g., DES’s "weak keys" collide under complementation).
• Block cipher modes (ECB, CBC, CFB) trade security for performance—ECB leaks patterns, CBC needs IVs.
• The CIA Triad (Confidentiality, Integrity, Availability) underpins all security systems, from Ncell’s SIM encryption to NEPSE’s stock-trade authentication.
• Modern attacks (differential, linear) on AES/DES rely on statistical biases in S-boxes or round functions.
• Real-world tie: Pathao’s driver-location encryption uses Hill ciphers for lightweight obfuscation against GPS spoofing.

---

1. What is Cryptanalysis?

Cryptanalysis is the science of breaking ciphers—analyzing encrypted data to recover plaintext without the key. It exploits:

• Mathematical weaknesses (e.g., linear algebra in Hill cipher).
• Statistical patterns (e.g., letter frequencies in English).
• Implementation flaws (e.g., reused IVs in CBC mode).

Why study classical ciphers? They teach core principles (substitution, transposition) that modern attacks (e.g., differential cryptanalysis on AES) build upon.

---

2. Classical Ciphers: How They Work (and How to Break Them)

A. Substitution Ciphers

Replace letters/numbers with others. Vulnerable to frequency analysis.

1. Caesar Cipher

• How it works: Shift letters by k positions (e.g., k=3 turns "A" → "D").
• Break it: Compare ciphertext frequencies to English (e.g., most common letter is E).
• Example: Plaintext: HELLO Key: k=5 Ciphertext: MJQQT Decryption: Shift back by 5 → HELLO.

2. Vigenère Cipher

• How it works: Uses a keyword (repeated) to shift letters. E.g., keyword "KEY" encrypts "HELLO" as:

  H(7) + K(10) = Q(17)
  E(4) + E(4)  = I(8)
  L(11) + Y(24) = C(2)
  

• Break it: Kasiski examination finds keyword length by spotting repeated ciphertext patterns.
• Real-world use: Used in WWII for low-security messages (now obsolete).

3. Playfair Cipher

• How it works: Encrypts digraphs (2-letter pairs) using a 5×5 matrix built from a keyword.

  • Example keyword: SECURITY → Matrix:

    S E C U R
    I T Y A B
    D F G H K
    L M N O P
    Q V W X Z
    

  • Plaintext "HELLO" → "HE LL" (split into digraphs).
  • Encrypt "HE" → "SF" (same row, shift right), "LL" → "XM" (same column, shift down).
  • Ciphertext: SFXM.

• Break it: Frequency analysis on digraphs (e.g., "TH", "HE" are common).

---

B. Transposition Ciphers

Rearrange letters (no substitution). Vulnerable to pattern recognition.

1. Rail Fence Cipher

• How it works: Write plaintext in a zigzag, read row-wise.

  • Example (3 rails, "WEAREINSAME"):

    W . A . I . M . E
    E R . N S A .
    A . E . E .
    

    Ciphertext: WAIMEERNSAAEE.

• Break it: Try all possible rail counts until English emerges.

2. Columnar Transposition

• How it works: Write plaintext in rows, read columns (key determines order).

  • Example (key "3142", plaintext "CRYPTOGRAPHY"):

    C R Y P T
    O G R A
    P H Y _
    

    Read columns 3→1→4→2 → YGTPORHYCRAP.

• Break it: Known-plaintext attack (e.g., if you know "CRYPTO" starts the message).

---

C. Polyalphabetic Ciphers (Advanced Substitution)

Use multiple substitution alphabets (e.g., Vigenère). Harder to break than Caesar but still vulnerable to Kasiski’s method.

Hill Cipher

• How it works: Treat plaintext as vectors, multiply by a key matrix modulo 26.
  • Example key:

    [5 4; 3 3]
    

  • Plaintext "HI" → [7, 8] (H=7, I=8).
  • Ciphertext = key × plaintext mod 26:

    [5*7+4*8, 3*7+3*8] = [74, 53] → [74-2*26, 53-2*26] = [22, 1] → "W A".
    

• Break it: Solve the linear system (if you have enough ciphertext-plaintext pairs).

---

3. Cryptanalysis Techniques

---

4. Block Cipher Modes: Security vs. Performance

Block ciphers (e.g., AES, DES) encrypt data in fixed-size blocks (e.g., 128 bits). Modes determine how blocks are processed.

A. ECB (Electronic Codebook)

• How it works: Encrypt each block independently.

• Problem: Leaks patterns (e.g., two identical photos encrypted with ECB look identical).
• Use case: Encrypting compressed data (no repeated blocks).

B. CBC (Cipher Block Chaining)

• How it works: XOR each plaintext block with the previous ciphertext block (needs an IV).

```figure
{"type":"layers","layers":["Plaintext Block 1","Plaintext Block 2","Encrypted Block 1","Encrypted Block 2"],"right":["IV (Initialization Vector)","Block 1 XOR IV","Block 2 XOR Block 1","Encrypted Output"],"highlight":["Block 2 XOR Block 1"],"caption":"CBC mode: Each plaintext block is XORed with the previous ciphertext block (feedback loop)"}

• Advantages: Hides patterns (no identical ciphertexts for identical plaintexts).
• Weakness: IV reuse leaks plaintext (e.g., P1 XOR C1 = P2 XOR C2 → P1 = P2).
• Real-world use: SSL/TLS (HTTPS), eSewa transactions.

C. CFB (Cipher Feedback)

• How it works: Turns a block cipher into a stream cipher (encrypts bits one at a time).

• Use case: Encrypting streams (e.g., real-time video in WhatsApp calls).

D. OFB (Output Feedback)

• How it works: Encrypts the keystream first, then XORs with plaintext.

```figure
{"type":"network","nodes":["Key","AES Encrypt","Keystream","Plaintext","Ciphertext"],"edges":[["Key","AES Encrypt"],["AES Encrypt","Keystream"],["Keystream","Plaintext","XOR"],["Plaintext","Ciphertext"]],"caption":"OFB mode: Keystream generated via AES encryption is XORed with plaintext (no feedback from ciphertext)"}

• Use case: Error resilience (e.g., corrupted bits don’t propagate).

---

5. Weak Keys in DES

DES (Data Encryption Standard) has weak keys that produce identical ciphertexts for complementary plaintexts:

• Complementary keys: K and ~K (bitwise NOT) encrypt P to C and ~P to ~C.
• Examples:
  • 0x0101010101010101 (all bits 0)
  • 0x1F1F1F1F0E0E0E0E (complementary to above).
• Impact: Allows meet-in-the-middle attacks (split key search).

---

6. CIA Triad: The Core of Security

Every cipher and protocol must satisfy:

---

In the Real World

1. eSewa’s Transaction Security

   • Uses AES-CBC (with a random IV) to encrypt payment details.
   • Why? CBC hides patterns (e.g., two identical Rs. 1000 transfers don’t produce identical ciphertexts).
   • Vulnerability: If IVs are reused, attackers can recover plaintext via XOR.

2. Pathao’s Driver Location Obfuscation

   • Lightweight Hill cipher (2×2 matrix) scrambles GPS coordinates to prevent spoofing.
   • Why? Faster than AES for mobile devices, but weak against known-plaintext attacks (e.g., if a driver’s home location is known).

3. NEPSE’s Stock Trade Authentication

   • Playfair cipher (or modern SHA-256) ensures trade orders can’t be altered.
   • Real example: If a hacker tries to change a "BUY 100 shares" to "BUY 1000 shares," the hash mismatch blocks the trade.

4. Kathmandu Traffic Routes (Transposition Cipher Analogy)

   • Imagine traffic lights as a columnar transposition: Reordering lanes (columns) changes congestion patterns (plaintext → ciphertext).
   • Cryptanalysis: If a hacker (or traffic engineer) knows the "key" (lane order), they can predict bottlenecks.

---

Exam Tip

1. For classical ciphers:

   • Caesar/Vigenère: Always show frequency tables or Kasiski’s method steps.
   • Playfair/Hill: Draw the matrix or solve the linear algebra (mod 26).
   • Example: Given ciphertext "DRJI" and Hill key [7 8; 11 11], set up:

     [7 8][x]   [D(3)]
     [11 11][y] = [R(17)]
     

     Solve 7x + 8y ≡ 3 mod 26 and 11x + 11y ≡ 17 mod 26.

2. For block cipher modes:

   • ECB vs. CBC: Draw the feedback loop for CBC and explain why ECB is "insecure for real data."
   • IV reuse: Show how C1 XOR C2 = P1 XOR P2 leaks plaintext.

3. CIA Triad:

   • Confidentiality → Encryption (AES).
   • Integrity → Hashes (SHA-256) or HMAC.
   • Availability → Redundancy (NTC’s fiber backup routes).

4. Weak keys:

   • DES: Memorize the 4 complementary key pairs.
   • AES: No weak keys, but related-key attacks exploit key schedules.

5. Past exam patterns:

   • Decryption questions: Always show the matrix inversion or algebraic steps.
   • Comparison tables: For SHA-1 vs. SHA-2 (bit length, collision resistance).
   • Definitions: CIA Triad, Galois field (e.g., GF(26) for Hill cipher).

---

Worked Example: Breaking a Vigenère Cipher

Ciphertext: XKFRJVFUJUD Suspected keyword length: 3 (from Kasiski’s method).

1. Divide ciphertext into 3 columns:

   X K F R J V
   F U J U D _
   

2. Assume first letters of keyword: A, B, C.
3. Decrypt each column:
   • Column 1: X(23) - A(0) = 23 → W (shift back by A’s position).
   • Column 2: K(10) - B(1) = 9 → J.
   • Column 3: F(5) - C(2) = 3 → D.
   • Plaintext: WJD... (likely nonsense → adjust keyword guess).
4. Refine: Try keyword "CAT":
   • X(23) - C(2) = 21 → V
   • K(10) - A(0) = 10 → K
   • F(5) - T(19) = -14 ≡ 12 → M
   • Plaintext: VKM... (still wrong → try "DOG").

Correct keyword: "KEY" → Plaintext: THISISASECRET.

---

Visual Summary: Cryptanalysis Tools