Skip to main content

Week - 10

TITLE

Lecture 46:
Cryptoanalysis​

Cryptology​

  • Two parts:

    • Cryptography (design)
    • Cryptanalysis (attack)

Attack Models​

1. Ciphertext-Only Attack (COA)​

  • Attacker knows:

    CC

  • Goal:

    • Recover: P or KP \text{ or } K

2. Known-Plaintext Attack (KPA)​

  • Attacker knows:

    (P,;C)(P,; C)

  • From previous communications

3. Chosen-Plaintext Attack (CPA)​

  • Attacker can choose:

    PiP_i

  • Gets corresponding:

    CiC_i

  • Goal:

    • Break encryption
    • Predict new plaintext

4. Chosen-Ciphertext Attack (CCA)​

  • Attacker chooses:

    CiC_i

  • Gets:

    PiP_i

  • Strongest attack model

Attacker Goal​

  • Find: KK

OR

  • Given: C∗C^*

Find:

P∗P^*

Generic Attacks​

1. Exhaustive Search (Brute Force)​

  • Try all keys:

    K1,K2,...,KnK_1, K_2, ..., K_n

  • Until correct one found

2. Table Lookup Attack​

  • Precompute table:
(P,;C)(P,; C)

  • Store mappings

  • On intercept:

    C→lookup PC \rightarrow \text{lookup } P

✔ Very fast at runtime

One-Way Function​

Function:

f:A→Bf: A \rightarrow B

Properties​

  1. Easy to compute:

    y=f(x)y = f(x)

  2. Hard to invert:

    x=f−1(y)x = f^{-1}(y)

In Cryptography​

  • Encryption:

    C=EK(P)C = E_K(P)

  • Hard to recover:

    P or KP \text{ or } K

Table-Based Attack Idea​

  • Precompute: EK(P)E_K(P)

for many keys

  • Store results

  • Match with intercepted:

    CC

Trade-off​

  • Time ↓ (fast lookup)
  • Memory ↑ (large table)

Key Insight​

  • Strong systems must resist:

    • CPA
    • CCA

✔ Security defined against strongest attacker

Final Note​

  • Cryptanalysis evaluates:

    • Strength of system
    • Weakness under attack models
TITLE

Lecture 47:
Time- Memory Trade- off Attack​

Time–Memory Trade-Off (TMTO)​

Goal​

  • Invert one-way function:

    y=f(x)y = f(x)

  • Find:

    xx

Problem​

  • Brute force:

    • Time: O(N)O(N)
    • Memory: O(1)O(1)

  • Table lookup:

    • Time: O(1)O(1)
    • Memory: O(N)O(N)

Idea​

  • Balance: Time↔Memory\text{Time} \leftrightarrow \text{Memory}

✔ Reduce both partially

Hellman Method​

Precomputation Phase​

  • Choose chains of length:

    tt

  • Start with random:

    x0x_0

  • Generate chain:

x1=f(x0),;x2=f(x1),;...,;xt=f(xt−1)x_1 = f(x_0),; x_2 = f(x_1),; ...,; x_t = f(x_{t-1})

Storage​

  • Store only:

    (start,;end)(\text{start},; \text{end})

  • Not full chain

✔ Saves memory

Table Size​

  • Number of chains:

    mm

  • Total covered space:

    ≈m⋅t\approx m \cdot t

Online Phase (Attack)​

Given:

y=f(x)y = f(x)

Step 1: Check Endpoints​

  • Compare: y with stored endpointsy \text{ with stored endpoints}

Step 2: If no match​

  • Compute:

    f(y),;f(f(y)),;...f(y),; f(f(y)),; ...

  • Up to:

    t stepst \text{ steps}

Step 3: If match found​

  • Recompute chain from start
  • Locate exact: xx

Maximum Work​

≤t operations\le t \text{ operations}

Trade-off Relation​

Let:

  • (N) = key space

Then:

T⋅M2≈N2T \cdot M^2 \approx N^2

Balanced Case​

T=M=N2/3T = M = N^{2/3}

Success Probability​

  • Depends on:

    m⋅tN\frac{m \cdot t}{N}

  • More chains → higher success

Key Insight​

  • Do heavy work offline
  • Fast lookup online

Limitation​

  • Chains may merge → collisions
  • Reduces coverage

Improvement​

  • Use multiple tables
  • Different reduction functions

Summary​

  • TMTO reduces:

    • Time from (O(N))
    • Memory from (O(N))

✔ Achieves practical balance for attacks

TITLE

Lecture 48:
Differential Cryptoanalysis​

Differential Cryptanalysis​

Basic Idea​

  • Study how input difference affects output difference

Definitions​

  • Input pair:

    x1=x,x2=x⊕αx_1 = x,\quad x_2 = x \oplus \alpha

  • Input difference:

    x1⊕x2=αx_1 \oplus x_2 = \alpha

  • Output:

    y1=F(x1),y2=F(x2)y_1 = F(x_1),\quad y_2 = F(x_2)

  • Output difference:

    y1⊕y2=βy_1 \oplus y_2 = \beta

Differential​

  • Pair:

    (α,;β)(\alpha,; \beta)

  • If:

    α→β with high probability\alpha \rightarrow \beta \text{ with high probability}

✔ Useful for attack

Attack Strategy​

  1. Choose many plaintext pairs:

    (x,;x⊕α)(x,; x \oplus \alpha)

  2. Encrypt → get:

    (c1,;c2)(c_1,; c_2)

Last Round Attack​

  • Guess subkey: krk_r

For each guess​

  • Partially decrypt: y1=F−1(c1,;kr)y_1 = F^{-1}(c_1,; k_r)
y2=F−1(c2,;kr)y_2 = F^{-1}(c_2,; k_r)

Check condition​

y1⊕y2=βy_1 \oplus y_2 = \beta

Count matches​

  • Maintain counter for each: krk_r

✔ Correct key → highest count

Key Space Example​

  • For DES:
∣K∣=248 (last round)|K| = 2^{48} \text{ (last round)}

Finding Good Differentials​

  • Use S-box analysis

Difference Distribution Table (DDT)​

For each:

α\alpha

  • Compute all:

    x,;x⊕αx,; x \oplus \alpha

  • Evaluate:

    β=S(x)⊕S(x⊕α)\beta = S(x) \oplus S(x \oplus \alpha)

  • Count frequency

Goal​

  • Find: (α,β) with high probability(\alpha,\beta) \text{ with high probability}

Example (4-bit S-box)​

  • Choose:

    α=4\alpha = 4

  • For all inputs:

    • Compute output differences
    • Build frequency table

✔ Highest frequency → best differential

Multi-Round Extension​

  • Combine round-wise differentials
  • Multiply probabilities

Key Insight​

  • Exploits non-random behavior of cipher

  • Works well on:

    • SPN
    • Feistel structures

Summary​

  • Input difference → predictable output difference
  • Use statistics to recover key

✔ Powerful non-generic attack on block ciphers

TITLE

Lecture 49:
More on Differential Cryptoanalysis​

Differential Attack (r-round)​

Step 1: Find Differential​

  • Find high-probability: α→β for (r−1) rounds\alpha \rightarrow \beta \text{ for } (r-1) \text{ rounds}

Step 2: Initialize​

  • For all subkeys:

    KrK_r

  • Set counter:

    count(Kr)=0\text{count}(K_r) = 0

Step 3: Chosen Plaintexts​

  • Select:

    P1,;P2 such that P1⊕P2=αP_1,; P_2 \text{ such that } P_1 \oplus P_2 = \alpha

  • Encrypt:

    C1,;C2C_1,; C_2

Step 4: Partial Decryption​

  • For each guess:

    KrK_r

  • Compute:

    y1=F−1(C1,;Kr)y_1 = F^{-1}(C_1,; K_r)
y2=F−1(C2,;Kr)y_2 = F^{-1}(C_2,; K_r)

Step 5: Check​

  • If:

    y1⊕y2=βy_1 \oplus y_2 = \beta

  • Then:

    count(Kr)++\text{count}(K_r)++

Step 6: Repeat​

  • Until one key has significantly high count

✔ That is likely correct subkey

Impossible Differential Attack​

  • Instead of high probability:
α↛β(impossible)\alpha \nrightarrow \beta \quad (\text{impossible})

Idea​

  • If a key produces: β\beta

→ Reject that key

✔ Eliminate wrong keys

Higher-Order Differential​

  • Use multiple differences

Example:

  • Second-order: Δ2x\Delta^2 x

✔ Captures complex patterns

Differential Composition​

Given:

α→β with prob p\alpha \rightarrow \beta \text{ with prob } p β→δ with prob q\beta \rightarrow \delta \text{ with prob } q

Combined​

α→δ with prob p⋅q\alpha \rightarrow \delta \text{ with prob } p \cdot q

Attack Using Composition​

Step 1​

Choose:

P1,;P2 with P1⊕P2=αP_1,; P_2 \text{ with } P_1 \oplus P_2 = \alpha

Step 2​

Get:

C1,;C2C_1,; C_2

Construct:

C3=C1⊕δ,C4=C2⊕δC_3 = C_1 \oplus \delta,\quad C_4 = C_2 \oplus \delta

Step 3​

Decrypt:

P3,;P4P_3,; P_4

Step 4​

Check:

P3⊕P4=αP_3 \oplus P_4 = \alpha

Step 5​

Repeat → count valid patterns

Key Insight​

  • Break cipher by:

    • Tracking differences
    • Using probability bias

Applications​

  • Effective on:

    • DES (reduced rounds)
    • SPN ciphers

Summary​

  • Uses:

    input difference→output difference\text{input difference} \rightarrow \text{output difference}

  • Types:

    • Standard differential
    • Impossible differential
    • Higher-order differential

✔ Powerful statistical cryptanalysis technique

TITLE

Lecture 50:
Linear Cryptoanalysis​

Attack Model​

  • Uses:

    • Known plaintext pairs: (Pi ,Ci)(P_i\ , C_i)

  • Goal:

    Recover key K\text{Recover key } K

Idea​

  • Approximate cipher using linear relations

Linear Approximation​

For bits:

a1p1⊕a2p2⊕⋯⊕b1k1⊕⋯⊕c1c1⊕⋯=0a_1 p_1 \oplus a_2 p_2 \oplus \cdots \oplus b_1 k_1 \oplus \cdots \oplus c_1 c_1 \oplus \cdots = 0
  • Holds with probability: p>12p > \frac{1}{2}

Bias​

Define:

ϵ=p−12\epsilon = p - \frac{1}{2}
  • If: ϵ≠0\epsilon \ne 0

✔ Useful relation

Boolean Function​

  • Input:

    (s1,s2,...,sn)(s_1, s_2, ..., s_n)

  • Output:

    0,1{0,1}

  • Linear form:

    ⨁aisi\bigoplus a_i s_i

Combining Approximations (Piling-Up Lemma)​

Let biases:

ϵ1,;ϵ2,;...,;ϵk\epsilon_1,; \epsilon_2,; ...,; \epsilon_k

Combined Bias​

ϵ=2k−1∏j=1kϵj\epsilon = 2^{k-1} \prod_{j=1}^{k} \epsilon_j

Combined Probability​

P=12+ϵP = \frac{1}{2} + \epsilon

Special Case (2 variables)​

ϵi,j=2ϵiϵj\epsilon_{i,j} = 2 \epsilon_i \epsilon_j

Key Observation​

  • If any: ϵj=0\epsilon_j = 0

Then:

ϵ=0\epsilon = 0

❌ No useful information

Attack Steps​

Step 1: Find Linear Approximation​

  • For S-box / round function

Step 2: Collect Data​

  • Gather many: (P,;C)(P,; C)

Step 3: Evaluate Expression​

  • Compute LHS for all pairs

Step 4: Count Bias​

  • Count how often: expression=0\text{expression} = 0

Step 5: Guess Key Bits​

  • Try key candidates
  • Select one with highest bias

✔ Likely correct key

Application​

  • Applied to:

    • DES (Eurocrypt 1993)

  • Needs:

    • Large number of plaintext-ciphertext pairs

Key Insight​

  • Cipher ≠ perfectly random
  • Linear patterns exist

Summary​

  • Uses:

    linear relation between P,C,K\text{linear relation between } P, C, K

  • Exploits:

    bias (ϵ)\text{bias } (\epsilon)

✔ Powerful statistical attack on block ciphers