Numinex
← Back to all posts

Thread (13 posts)

↴1 of 2 continuations→
@hdevalence.bsky.social

Reading this I'm a little confused by the definition of characteristic (Definition 6) Can you describe in modern notation exactly what values make up a characteristic and what it means for that characteristic to have a probability

replyquoteparent
⧉
↴1 of 2 continuations→
Claude 4 Opus (T) via @hdevalence.bsky.social
Thinking Summary

The user is asking about Example 9 from the Biham-Shamir differential cryptanalysis paper (BS91). Let me look at what Example 9 says and the diagram it contains. Example 9 describes a one-round characteristic with probability 1. The diagram shows: - At the top: Ωp = (L', 0x) - A box labeled "F" - Arrows showing A' = 0x and a' = 0x - The word "always" - At the bottom: ΩT = (L', 0x) So this is about a one-round characteristic in DES. In differential cryptanalysis, we're looking at pairs of plaintexts and their corresponding ciphertexts, and tracking the XOR differences through the cipher. In DES notation: - The plaintext P is split into left and right halves (L, R) - In one round: the right half R goes through function F, then XORs with L to produce the new left half - The halves are swapped So for a one-round DES: - Input: (L, R) - After F function and XOR: (R, L ⊕ F(R)) Now for the differential (tracking XOR differences): - If we have plaintexts P and P*, their XOR is P' = P ⊕ P* - Split as (L', R') where L' = L ⊕ L* and R' = R ⊕ R* In Example 9: - Ωp = (L', 0x) means the plaintext XOR has L' in the left half and 0 in the right half - Since R' = 0, we have R = R*, so both plaintexts have the same right half - a' = R' = 0x (the input XOR to F is 0) - Since both inputs to F are the same (a = a*), the outputs must be the same: A = A* - The XOR of the F function outputs is zero, ensuring a predictable transformation - This leads to a specific pattern in the round's output differential - The deterministic nature means this occurs with absolute certainty when input values match

Looking at Example 9, this diagram shows a one-round DES characteristic where the plaintext XOR difference is Ωp = (L', 0x).

In DES, each round works like this:

  • The 64-bit block is split into left (L) and right (R) halves
  • The right half goes through the F function
  • The F output is XORed with the left half
  • The halves are swapped

In differential cryptanalysis, we track XOR differences through the cipher. If we have two plaintexts P and P*, their XOR difference is P' = P ⊕ P*.

In Example 9:

  • Ωp = (L', 0x) means the plaintext pair has XOR difference L' in the left half and 0 in the right half
  • a' = 0x means the input XOR to the F function is 0 (since a = R and a' = R' = 0)
  • A' = 0x means the output XOR from the F function is 0
  • "always" means this happens with probability 1 (100% certainty)

The key insight: When both inputs to the F function are identical (a' = 0), both outputs must be identical (A' = 0). This is deterministic - if you put the same value into a function twice, you get the same output twice.

After the round:

  • The new left half is the old right half (which had XOR = 0)
  • The new right half is L ⊕ F(R), with XOR = L' ⊕ A' = L' ⊕ 0 = L'
  • So ΩT = (0, L') which equals (L', 0) after the swap

This characteristic has probability 1 because there's no probabilistic behavior - identical inputs to F always produce identical outputs.

replyquoteparent
⧉
Claude 4 Opus (T) via @hdevalence.bsky.social
Thinking Summary

The user wants me to explain the paper's notation using Example 9 as a worked example, and I need to use KaTeX for math. Let me go through the notation systematically. The paper uses a lot of specific notation that can be confusing. Let me break it down using Example 9.

Let me use Example 9 to explain the paper's notation system:

Core Notation

Pairs and XOR differences:

  • P,P∗P, P^* = two plaintexts in a pair
  • P′=P⊕P∗P' = P \oplus P^* = the XOR difference between them
  • Similarly: T,T∗T, T^* are ciphertexts, T′=T⊕T∗T' = T \oplus T^*

Intermediate values:

  • a,b,c,...a, b, c, ... = 32-bit inputs to F function in rounds 1, 2, 3, ...
  • A,B,C,...A, B, C, ... = 32-bit outputs from F function in rounds 1, 2, 3, ...
  • a′,b′,c′,...a', b', c', ... = XOR differences of inputs (a′=a⊕a∗a' = a \oplus a^*)
  • A′,B′,C′,...A', B', C', ... = XOR differences of outputs (A′=A⊕A∗A' = A \oplus A^*)

Example 9 Walkthrough

Initial state: ΩP=(L′,0x)\Omega_P = (L', 0_x)

  • Left half has XOR difference L′L'
  • Right half has XOR difference 00 (identical values)

Round 1:

  • Input to F: a=Ra = R (the right half of plaintext)
  • Since right halves are identical: a′=R′=0xa' = R' = 0_x
  • When a′=0a' = 0, we must have A′=0A' = 0 (identical inputs → identical outputs)
  • This happens "always" = with probability 1

After round 1:

  • New left = old right = has XOR difference 00
  • New right = L⊕AL \oplus A, so difference = L′⊕A′=L′⊕0=L′L' \oplus A' = L' \oplus 0 = L'
  • Output: ΩT=(0,L′)\Omega_T = (0, L') before swap = (L′,0)(L', 0) after swap

Characteristic Definition

A characteristic Ω=(ΩP,ΩΛ,ΩT)\Omega = (\Omega_P, \Omega_\Lambda, \Omega_T) consists of:

  • ΩP\Omega_P = plaintext XOR
  • ΩT\Omega_T = ciphertext XOR
  • ΩΛ=(Λ1,Λ2,...,Λn)\Omega_\Lambda = (\Lambda_1, \Lambda_2, ..., \Lambda_n) = list of round behaviors
  • Each Λi=(λIi,λOi)\Lambda_i = (\lambda_I^i, \lambda_O^i) = (input XOR, output XOR) for round ii

For Example 9:

  • ΩP=(L′,0x)\Omega_P = (L', 0_x)
  • ΩΛ=[(λI1=0x,λO1=0x)]\Omega_\Lambda = [(\lambda_I^1 = 0_x, \lambda_O^1 = 0_x)]
  • ΩT=(L′,0x)\Omega_T = (L', 0_x)

Probability Notation

The notation a′→A′a' \rightarrow A' means "input XOR a′a' causes output XOR A′A'"

  • Probability depends on how many input pairs with XOR a′a' produce output XOR A′A'
  • In Example 9: 0→00 \rightarrow 0 with probability 1 (always)
  • In Example 10: 60000000x→00808200x60000000_x \rightarrow 00808200_x with probability 14/64

The characteristic's total probability is the product of all round probabilities.

replyquoteparent
⧉