Last updated on Apr 7, 2025

How do you measure the bias and the probability of linear and differential characteristics for a cipher?

Encryption is a vital skill for protecting data and communication from unauthorized access and manipulation. However, no cipher is perfect, and some may be vulnerable to certain types of attacks that exploit their weaknesses. Two common methods of analyzing the security of a cipher are linear cryptanalysis and differential cryptanalysis, which use statistical techniques to find correlations or differences between the plaintext, ciphertext, and key bits. In this article, you will learn how to measure the bias and the probability of linear and differential characteristics for a cipher, and how they affect the complexity and success rate of the attacks.

1 Linear characteristics

A linear characteristic is a linear equation that relates some bits of the plaintext, ciphertext, and key with a certain bias. The bias is the deviation of the equation from being balanced, or having equal probabilities of being true or false. For example, if a linear characteristic holds for 60% of the inputs, then the bias is 0.2, or 20%. The bias measures how useful the equation is for guessing the key bits, since a higher bias means a stronger correlation. To find the bias of a linear characteristic, you can use the following formula:

bias = 2^(-n) * sum(P(C) XOR P(P) XOR P(K))

where n is the number of bits involved, C is the ciphertext, P is the plaintext, K is the key, and the sum is taken over all possible inputs.

Add your perspective

Kailash Parshad

Ethical Hacker | Penetration Tester | Cybersecurity Enthusiast | YouTube Educator
Report contribution
Understanding the bias in linear characteristics is crucial for evaluating the security of a cipher. In practice, ciphers with a low bias tend to offer stronger resistance to linear cryptanalysis. For instance, during an analysis of a lightweight block cipher, we observed that one of the linear characteristics had a bias of 0.1, indicating a lower correlation between plaintext and ciphertext. This made key recovery significantly harder. However, in another cipher with a bias closer to 0.25, the linear approximation was stronger, and fewer plaintext-ciphertext pairs were required to reveal key bits. These practical insights show how bias directly influences the vulnerability of a cipher to linear attacks.

Like
Randy Hall

🛡️ CEO | Trusted Leader in Cybersecurity for SMBs | 🏆 2024 Most Trusted MSP in North America (Soteria Award)
Report contribution
Measuring bias in cryptographic ciphers involves statistical techniques used in linear and differential cryptanalysis. The probability of a linear characteristic is measured by calculating how much a linear approximation deviates from a random function, while differential characteristics analyze how differences in input pairs propagate through the cipher. These methods help evaluate a cipher’s strength against attacks, ensuring it meets modern security standards.

Like

2 Differential characteristics

A differential characteristic is a difference pattern that propagates through the rounds of a cipher with a certain probability. The difference pattern is the XOR of two inputs or outputs, and it indicates how they change after applying the cipher. For example, if two plaintexts have a difference of 0010, and their corresponding ciphertexts have a difference of 1100, then the differential characteristic is 0010 -> 1100. The probability measures how likely the difference pattern is to occur, or how predictable the cipher is. For example, if a differential characteristic occurs for 25% of the inputs, then the probability is 0.25, or 25%. The probability affects how many pairs of inputs and outputs are needed to recover the key bits, since a higher probability means a more consistent behavior. To find the probability of a differential characteristic, you can use the following formula:

probability = product(P(D_in -> D_out))

where D_in and D_out are the input and output differences for each round, and the product is taken over all the rounds.

Add your perspective

3 Attack complexity

The attack complexity is a measure of how difficult it is to perform a linear or differential attack on a cipher, based on the bias or probability of the characteristics and the key size. The attack complexity depends on the number of plaintext-ciphertext pairs that are required to collect enough information to guess the key bits, and the number of key bits that can be guessed from each pair. The lower the attack complexity, the more efficient the attack. To estimate the attack complexity, you can use the following formulas:

linear attack complexity = (key size / number of guessed bits per pair) * (1 / bias^2)

differential attack complexity = (key size / number of guessed bits per pair) * (1 / probability)

Add your perspective

Kailash Parshad

Ethical Hacker | Penetration Tester | Cybersecurity Enthusiast | YouTube Educator
Report contribution
While analyzing the AES algorithm, we found that linear and differential attack complexities were too high to be practical due to its strong diffusion and confusion properties. In contrast, some older ciphers had much lower attack complexities, making them more susceptible to differential attacks. The complexity is heavily influenced by the number of guessed key bits per pair and the bias or probability of the characteristics. For example, a cipher with a bias of 0.05 requires significantly more pairs to launch a successful linear attack compared to one with a bias of 0.15. This shows the importance of tuning a cipher's design to increase attack complexity and make cryptanalysis more difficult.

Like

4 Attack success rate

The attack success rate is a measure of how likely it is to recover the correct key from a linear or differential attack on a cipher, based on the bias or probability of the characteristics and the number of available pairs. The attack success rate depends on the confidence level that is desired, and the statistical distribution of the bias or probability. The higher the attack success rate, the more reliable the attack. To calculate the attack success rate, you can use the following formulas:

linear attack success rate = erf(sqrt(number of pairs * bias^2 / 2))

differential attack success rate = 1 - e^(-2 * number of pairs * probability)

where erf is the error function and e is the base of the natural logarithm.

Add your perspective

5 Here’s what else to consider

This is a space to share examples, stories, or insights that don’t fit into any of the previous sections. What else would you like to add?

Add your perspective

Kailash Parshad

Ethical Hacker | Penetration Tester | Cybersecurity Enthusiast | YouTube Educator
Report contribution
When evaluating the security of a cipher, it’s also important to consider the trade-offs between performance and resistance to cryptanalysis. For example, lightweight ciphers designed for IoT devices often sacrifice some security for faster processing and lower resource consumption. However, these ciphers may have higher biases or lower differential probabilities, making them more vulnerable to attacks. In one case, we found that a cipher designed for low-power devices was vulnerable to differential attacks due to its simplistic key schedule, leading us to recommend more rigorous cryptanalysis during the design phase. Balancing these factors can help in selecting or designing ciphers that are both efficient and secure.

Like

How do you measure the bias and the probability of linear and differential characteristics for a cipher?

1

2

3

4

5

1 Linear characteristics

2 Differential characteristics

3 Attack complexity

4 Attack success rate

5 Here’s what else to consider

Encryption

Rate this article

Thanks for your feedback

More articles on Encryption

More relevant reading