16
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 ...
- 1,836
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 ...
- 4,405
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 ...
- 116
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 ...
- 145k
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,...
- 45.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.
- 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 ...
- 146
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 ...
- 21.2k
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 ...
- 642
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 ...
- 145k
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 ...
- 4,405
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" ...
- 21.2k
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 $...
- 1,836
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(\...
- 21.2k
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 ...
- 21.2k
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 ...
- 145k
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 ...
- 15.1k
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 ...
- 2,320
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 ...
- 9,969
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 ...
- 27.6k
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 ...
- 21.2k
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 ...
- 19.5k
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 ...
- 19.5k
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 ...
- 21.2k
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 ...
- 45.9k
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 ...
- 21.2k
3
votes
Accepted
Getting to understand the linear approximation of DES
Definition: $$NS_a(\alpha,\beta) = \# \{x| 0 \leq x < 64, (\oplus_{s=0}^{5}(x[s] \bullet \alpha[s])) = (\oplus_{t=0}^{3}(S_{a}(x)[t] \bullet \beta[t]))\}$$
Here, $x$ is your input to the S-box, ...
- 96
3
votes
Accepted
Solving system of linear equtions over binary field with error
The Learning Parity with Noise (LPN) problem is as follows
Let $\vec s\in\mathbb{F}_2^n$ be a fixed secret, and $\mathcal{O}_{\vec s}$ be an oracle that samples $\vec a_i\gets \mathcal{U}(\mathbb{F}...
- 11.6k
Only top scored, non community-wiki answers of a minimum length are eligible