15 votes
Accepted

Understanding the wide trail design strategy

Given the importance of the wide-trail strategy in modern symmetric-key cryptography, this question really deserves an answer (and a much better score). Since nobody else has tried, I'll give a brief ...
user avatar
  • 1,786
11 votes
Accepted

Why is the DES s-box non-linear? Why does it make the cracking of the cipher more difficult?

It is of course possible to write DES or any block cipher as a system of non-linear equations involving the plaintext bits, the ciphertext bits, and the key bits, which hold with probability 1. In ...
user avatar
  • 4,345
9 votes
Accepted

Selection of rotation constants in ARX design

Leaving besides that the designers (NSA) of Simon and Speck did not provide an initial design rational for their ciphers/parameter choices, they added some notes later after pressure from the ...
user avatar
7 votes
Accepted

Does hashing require non-linearity?

Does hashing require non-linear components as well? Yes How would a hash built from a linear psuedo-random permutation be vulnerable to collision/preimage search? You could find a preimage by ...
user avatar
  • 134k
5 votes
Accepted

Linear Related Message Attack on RSA

The ability to recover $x$ in the latter case is a direct consequence of RSA's homomorphic property and the ability to recover $x$ in the former case. Suppose you are given the equations (with $c_i,...
user avatar
  • 44.7k
5 votes

Is the following s-box more linear or more non-linear?

Yes, your table is perfectly linear: The output is the sum of the inner four bits plus left outer bit*0101 plus right outer bit*1010.
user avatar
  • 51
4 votes
Accepted

Matsui's Linear attack on DES P box

We need to get back to Matsui's notations. X is represented as X[31].... X[0] K is represented as K[47]......K[0] In X[15] ⨁ F5(X,K)[7,18,24,29] = K[22] X[15] is actually the round input before ...
user avatar
4 votes

Why is the DES s-box non-linear? Why does it make the cracking of the cipher more difficult?

The S-Boxes are lossy. They map 6-bit inputs to 4-bit outputs, so for a given 4-bit output there are several possible inputs. Considering that there are 8 S-boxes, that's 16 bits of information lost ...
user avatar
4 votes

Last Sbox of a block cipher for Linear Cryptanalysis

If you include a key addition layer ($K_1$) at the output as well the key addition layer ($K_0$) at the input of the Sbox then you can perform linear cryptanalysis on this simple cipher. You shall ...
user avatar
  • 16.7k
4 votes

What is an advantage of MDS matrices in block ciphers?

They said that, one goal of MDS matrices is to protect the block ciphers against linear and differential attacks. That would probably depend on the cipher, but in generally, pretty accurate. is ...
user avatar
  • 134k
4 votes
Accepted

What is the meaning of Maximum Expected Differential/Linear Probability (MEDP/MELP)?

The paper you link to gives precise definitions for the MEDP and MELP. I will attempt to explain the definitions more expansively & clearly. First, the differential probability (DP) function ...
user avatar
  • 4,345
4 votes

Matsui's paper on linear cryptanalysis - unexplained formula in Lemma 2

This is a type of "Gaussian approximation", assuming the wrong key randomization hypothesis, and given the bias $|p-1/2|$, the success probability depends on the order statistics of the "sample bias" ...
user avatar
  • 16.7k
4 votes
Accepted

Differential and Linear trail propagation in Noekeon

This is due to the duality between linear and differential trails. Let $L$ be an invertible linear map on $\mathbb{F}_2^n$, think of it as a matrix for convenience. In general, a nonzero differential $...
user avatar
  • 1,786
4 votes

LAT of an SBox, values are even

Let $N(\alpha,\beta)$ be the number of times the equation $$ \alpha\cdot x \oplus \beta \cdot y=0 \tag{0} \label{0} $$ holds. Then the LAT matrix entry is $$ L(\alpha\cdot x \oplus \beta \cdot y )= N(\...
user avatar
  • 16.7k
4 votes
Accepted

Why is the nonlinearity of this Boolean function evaluating to $\frac12$?

In this formulation you need to convert your function's output range to $\{-1,+1\}$ via $$f`(x)=(-1)^{f(x)}$$ and apply the Walsh Hadamard to the new function $f`(x)$. Using the zero one formulation ...
user avatar
  • 16.7k
4 votes
Accepted

Why the differential cryptanalysis complexity is linear with inverse of the probability while linear cryptanalysis is quadratic with the bias inverse?

What I don’t get is why the complexity became quadratic in linear case? Well, in linear cryptanalysis, for each input, we get a bit with a bias of $0.5 \pm \epsilon$, and we need to determine if that ...
user avatar
  • 134k
3 votes
Accepted

Non-Linearity of an Sbox

Consider a linear 8-bit s-box $S$: $$ c=S\cdot p, $$ where $c$ and $p$ are 8-bit vectors, and thus $S$ is an $8\times8$ matrix. This means we can pick 64 different s-boxes in our design. This ...
user avatar
3 votes
Accepted

FEAL-4 Linear Cryptanalysis - Prevention

By convention: LC = Linear Cryptanalysis DC = Differential Cryptanalysis There are multiple ways to increase the security of a block cipher. The first one (and usually applied) is to increase the ...
user avatar
  • 9,829
3 votes
Accepted

What is the complexity for attacking 3DES in linear or differential cryptanalysis?

"Not vulnerable" is not how I would describe it, but my understanding is that the existing attacks on DES cannot directly not work with 3DES. At the moment, the best attack against single DES is a ...
user avatar
  • 3,367
3 votes
Accepted

What is the “Walsh Function” about?

The function $L_a(x)=\langle a,x\rangle=a_1 x_1+\cdots+a_n x_n$ is a linear multivariate function of $(x_1,\ldots,x_n)$. The function $$f(x)+\langle a,x\rangle=f(x_1,\ldots,x_n)+a_1 x_1+\cdots+a_n ...
user avatar
  • 16.7k
3 votes
Accepted

Why is not there any ideal S-Box?

It is important to understand that although a very large random function will only have linear biases with very low probability, this is simply not true of small random functions. If you choose a ...
user avatar
3 votes
Accepted

Non Linearity of huge Sbox

Table construction would require 148 Exabytes of RAM, so it would be hard to store all at once. This also means that you can't have a predefined S box that you might have developed either to be a ...
user avatar
3 votes
Accepted

When it comes to linear cryptanalysis, is there always a key that could work for every possible input/output?

Regarding your first question, we assume (for known plaintext attacks such as Linear cryptanalysis) that we can obtain a large number of inputs and the corresponding outputs under the unknown key. The ...
user avatar
  • 16.7k
3 votes
Accepted

How do you calculate the linear approximation of an S-BOX?

You might want to check out this stackoverflow question: What is Bit Masking? Basically, the mask selects certain bits from the words, where a word is a vector (a row) of bits. The input mask selects ...
user avatar
  • 19.3k
3 votes
Accepted

Compression function cryptanalysis

Are there any standard/general techniques for determining an unknown compression function, given the input-output pairs? This appears to fall under the realm of reverse-engineering rather than ...
user avatar
  • 19.3k
3 votes
Accepted

Correlation of linear trail

This is due to the modelling approach called Markov Ciphers, by Jim Massey (I think). Basically the hypothesis is that round by round independence applies and correlations can be concatenated by ...
user avatar
  • 16.7k
3 votes

What does it mean : "Canonical representative of Sbox is 0123468A5BCF79DE"? and How can we calculate this representative for Sbox?

Let's start with the basics: a bijective 4×4 bit S-box is a permutation of the set $\{0,1\}^4$ of 4-bit bitstrings. These bitstrings can be viewed as the binary representations of the integers ...
user avatar
3 votes

Is this permutation secure?

This is problematic as stated. You need to specify a probability distribution for that complex matrix, but the complex field is infinite. This then implies that you need to also carefully define some ...
user avatar
  • 16.7k

Only top scored, non community-wiki answers of a minimum length are eligible