Questions tagged [linear-cryptanalysis]
Linear cryptanalysis is a known plaintext attack and uses a linear approximation to describe the behavior of the block cipher. Given sufficient pairs of plaintext and corresponding ciphertext, bits of information about the key can be obtained and increased amounts of data will usually give a higher probability of success.
113
questions
2
votes
2
answers
163
views
Lemma 5 in Matsui's Paper about Linear Cryptanalysis
I have a problem about the formula in Matsui's paper about linear cryptanalysis.
Let $N$ be the number of given random plaintexts, p be the probability that equation $P[i_1,i_2,\cdots,i_a]\oplus C[...
- 63
0
votes
0
answers
56
views
Is there a square matrix with applications in Cryptography such that the determinant of this matrix is 0 and all its sub minors are non-singular?
I am looking for a square matrix whose determinant is 0, however, all sub-minors of this matrix are non singular. This matrix needs to have applications in Cryptography. The matrix may be over any ...
0
votes
1
answer
84
views
Custom linear random number generator
I've made an implementation of a linear RNG. It has two constants: b and p. Every time new value of ...
- 1
0
votes
0
answers
69
views
How to estimate the bias of linear cryptanalysis given the input and output masks
Assume the input linear mask is $a$, and output mask is $b$，for a block cipher $F$ with $r$ round,How to accurately and quickly estimate the bias of linear cryptanalysis? which is
\begin{equation*}
...
3
votes
1
answer
84
views
Midori block cipher design: importance of $S_b$ as the S-box
With a use of almost MDS the Midori cipher provides a good diffusion. But why $S_b$ is used as S-box and what is its actual importance?
- 31
1
vote
1
answer
102
views
Biasedness of the XOR variable of two independent biased boolean variable
My question is very basic one. Suppose there are two independent boolean variable $X_1$ and $X_2$. It is given that $X_1$ is biased towards $0$ and $X_2$ is biased towards $1$ with same amount of bias....
- 145
0
votes
1
answer
277
views
Linear approximation table of AES S-Box
I am trying to create linear approximation table of AES SBox to better understand linear cryptanalysis, I have followed the formula in this paper (page 7 of pdf file) to be able to generate the linear ...
- 117
2
votes
1
answer
44
views
Threshold of resistance against Linear Cryptanalysis
In the AES proposal, the last sentence on page 30 it is said:
To be resistant against LC, it is a necessary condition that there are no linear trails with a correlation coefficient higher than 2^(n/2)...
- 21
1
vote
1
answer
115
views
Is product of two linear combinations over a finite field information hiding?
Suppose we have a 32-bit message $ M=(m_1,..m_{32}) \in \{0, 1\}^{32} $ and we have secrets $ F_{i, b} $ and $ G_{i, b} $ (2x32+2x32=128 secrets in total).
$$ \forall 1 \leq i \leq 32, b \in \{0, 1\} :...
- 11
3
votes
1
answer
540
views
Non-Linearity of an S-Box [duplicate]
This should be pretty simple question I presume. So let's say I have an 8x8 S-Box. I can easily treat it as 8 different boolean functions for each of the 8 input bits. Is the non-linearity the lowest ...
- 123
0
votes
0
answers
125
views
Can a modulo function be linearized or alternatively expressed?
In order to try to simplify or alternatively express cryptographic functions I wonder if the modulo function can be alternatively expressed. Could for example a Fourier series of a sawtooth wave or ...
- 123
1
vote
1
answer
681
views
Linear cryptanalysis resistance of AES Sbox
If you look at the AES Linear Approximation Table (computed for example with Sage) you will see there are many entries with what looks like a high bias of -16 ("absolute bias" scale).
I ...
- 67
2
votes
1
answer
92
views
How do I find an equivalent permutation of AES S-box which sends $0$ in $0$?
I am testing the quality of AES S-box and using the lookup table I built a function from GF($2^8$) to GF($2^8$) seen as vector spaces. I was wondering if there is a transformation that I can use to ...
- 23
3
votes
1
answer
114
views
Linearization attack on group with automorphism
Recently, I've had an exchange with Lorenz Panny about Xifrat. He says, that the quasigroup that I use can be linearized and then attacked, and he provided a script that linearized the quasigroup. His ...
- 9,672
2
votes
0
answers
81
views
Linear approximation of modular addition of a constant?
In Linear Approximations of Additions Modulo $2^n$, Wallén shows how to compute the correlation of the modular addition of two binary bit vectors. A simple recursive procedure was given by Schulte-...
- 171
3
votes
2
answers
282
views
How to find the optimal trail in linear cryptanalysis
I'm reading and implementing this tutorial, the author explains everything pretty clearly, the only thing I'm missing is how he decides which trail to use (pg. 12). I understand that one should prefer ...
- 135
1
vote
0
answers
54
views
How does one produce this in the linear cryptanalysis of DES
I understand how this linear approximation board below is produced,
but I can't understand how this second board is produced using the first one
and finally how the pilling-up lemma values are ...
- 11
4
votes
1
answer
575
views
Matsui's linear attack on 5-round DES
I'm trying to understand Mitsuru Matsui's "Linear Cryptanalysis Method for DES Cipher", specifically the attack he describes at the end of section 5, on 5-round DES. I followed the attack on ...
- 171
1
vote
1
answer
168
views
Solving system of linear equtions over binary field with error
I have system of linear equations $f_1, \ldots, f_m$ over binary variables $x_1,\ldots,x_n$
where $m$ is much larger than $n$. We know if all equations are correct, we can find solution easily using ...
- 229
1
vote
0
answers
120
views
How does an attacker decrypt a hash function by looking for linearity?
Reading the selected answer to Designing a hash function from first principles rather than depending on heuristics is very insightful.
The section on "nonlinearity" suggests that making ...
- 171
1
vote
1
answer
68
views
Statistical Cryptanalysis. Would one "reverse" weak key schedule algorithms or peel off each one of internal rounds?
The context is iterated ciphers.
Regarding Differential and Linear Cryptanalysis, the methods seem to make a cryptanalyst able to do an educated guess on a partial subkey (e.g. bits from the last ...
2
votes
2
answers
293
views
How do we find differentials in differential cryptanalysis when we don't the details about the S-boxes
I m new to cryptanalysis and trying to understand differential cryptanalysis. I have read the paper by Howard M. Heys. I understood the concept of differentials but I m not able to understand how to ...
-1
votes
1
answer
103
views
LAT of sboxes, sum of coloms and rows
let we have sbox s: Vn -> Vn.
If we make LAT table for s, fix any row and get a sum by columns, that sum would be $+-2^{n-1}$.
And vice versa, if we fix any column and get a sum by rows, that sum ...
- 1
2
votes
1
answer
90
views
Checking Independence of combination of uniform random variables to use pilling up lemma
My question is very basic one. Suppose $a_0, a_1, a_2, a_3, a_4, b_0, b_1, b_2, b_3, b_4$ are $10$ uniform random variables from $\{0,1\}$ independent of each other. Now there are expressions of the ...
- 145
0
votes
1
answer
248
views
Problems with Matsui's Linear Cryptanalysis on round reduced DES
I'm trying to understand the known plaintext attack that is briefly explained in the paper Linear Cryptanalysis Method for DES Cipher by Mitsuru Matsui. I've almost understood it (since I'm ...
- 3
2
votes
1
answer
106
views
Why the differential cryptanalysis complexity is linear with inverse of the probability while linear cryptanalysis is quadratic with the bias inverse?
I am trying to understand the analysis of the complexity of Differential Cryptanalysis versus the complexity of linear cryptanalysis.
In differential cryptanalysis the number of required texts is $\...
- 23
2
votes
1
answer
285
views
How to choose the linear approximations to build a path through a SPN in Linear cryptanalysis?
so I am reading up on Linear Cryptanalysis using Heys' Tutorial. I understood how to get "good" linear approximations of the S-boxes though I cannot seem to find a reasonable approach to ...
user71275
2
votes
1
answer
210
views
Truth table for the Boolean function $f(x,y) = x \oplus xy$ - Conflict with answer computed by sagemath
By hand, I computed $f(x,y) = x \oplus xy = (0, 0, 1, 0)$ since, in ascending (lexicographical) order,
$f(0,0) = 0 \\ f(0,1) = 0 \\f(1,0) = 1 \\ f(1,1) = 0$
However, using the following code on ...
- 175
3
votes
2
answers
287
views
Why is the nonlinearity of this Boolean function evaluating to $\frac12$?
I am using the method presented in this paper to find the nonlinearity of the function
$$ f: \mathbb{F}^1_2 \to \mathbb{F}^1_2 \\ f(x) = x$$
The truth table is $f = [0 \space \space 1]$. Now, I read ...
- 175
0
votes
2
answers
307
views
Differential and Linear Cryptanalysis on Random Sbox
Assume that we use the key to perform a uniform permutation to generate a sbox. The literature is rich supporting the statement that a random Sbox can make any cryptographic scheme weaker. I have ...
- 187
0
votes
1
answer
124
views
Differential-linear attack on DES
Is there any known differential-linear attack on full round DES? I couldn't found any and couldn't work on this due to time restriction.
- 96
2
votes
0
answers
57
views
(Enhancing Linear-Differential Cryptanalysis - Biham et al.) Diff-Lin Extension Characteristic and Characteristic Probability
I studied Langford and Hellman's Differential-Linear Cryptanalysis and moved on to Biham, Dunkelman and Keller's Enhancing Linear-Differential Cryptanalysis.
In the paper, although I've read many ...
- 96
2
votes
1
answer
562
views
Getting to understand the linear approximation of DES
I will make a presentation about Linear approximation (Matsui's paper 1993 Linear Cryptanalysis Method for DES Cipher ) of DES and I don't understand some parts of it.
Here my questions :
In the ...
- 45
3
votes
1
answer
228
views
LAT of an SBox, values are even
This is probably a silly question, but I could not find any reference. For the DDT of an SBox, it is easy to see why all the values are even. Is there any related result for LAT (i.e., all its values ...
- 603
2
votes
2
answers
289
views
Is this permutation secure?
Let vector ${\bf d} \in \{ \pm 1 \}^n$ be the message we want to send. In my system, ${\bf d}$ is multiplied by an $n \times n$ Fourier matrix ${\bf F}$, as follows
$$ {\bf x} = {\bf F} {\bf d} $$
...
- 35
0
votes
2
answers
405
views
Is the linear and differential cryptanalysis only dependent on Sbox?
While performing the linear and differential cryptanalysis a Linear Approximation Table(LAT) and a Different Distribution Table(DDT) is required which is created exploiting the S-box of the cipher ...
- 187
3
votes
0
answers
307
views
Understanding Linear Cryptanalysis
I'm reading about the linear cryptanalysis of an SPN and I have some questions about the practicality of this. The example I'm looking at is from 3.3.3 of Stinson's Book and I believe the same example ...
- 141
2
votes
0
answers
49
views
Linear approximattion of $(x+y) \bmod 2^n$ in FSM of SNOW 2.0 where $x,y$ in $F_{2}^n$
I would like to understand the linear approximation of $(x+y) \bmod 2^n$ by linear masking method in the paper refereed ""Improved Linear Distinguis'hers for SNOW 2.0" by Kaisa Nyberg and Johan Wall´...
4
votes
0
answers
80
views
Help with cryptanalysis of branching in schemes based on Multivariate Public Key Cryptography
I'm familiarized with the structure of branching found in Multivariate Cryptography, as it allows us to partition a $n$-tuple over $F_{q}$ into a $k$-tuple where the $i$-th element is in $F_{q^{\...
- 898
3
votes
0
answers
327
views
Linear cryptanalysis of FEAL-4
I am trying to find the sub keys of a FEAL-4 cipher. I am able to get a number of possibilities for $K_0$ after using Michael Stamps formula using a as a constant and going through $2^{32}$ keys. The ...
- 31
2
votes
0
answers
118
views
Enhancing Differential-Linear Cryptanalysis
I'm studying Differential-Linear Cryptanalysis, and I'm trying to understand the context from the article Enhancing Differential-Linear Cryptanalysis by Eli Biham et al. There are some difficult ...
- 325
1
vote
0
answers
77
views
In DES : Matsui's notation(LC) vs Biham's notation(DC)
I'm doing linear attack for 8 rounds DES. And I just wondering about the difference between Matsui's notation and Biham's notation. In Matsui's paper, numbers bits from 0 to 63 from right to left. In ...
- 325
0
votes
2
answers
867
views
Is the following s-box more linear or more non-linear?
I am trying to figure out whether the following simple s-box configuration I created is more linear than non-linear or vice versa more non-linear than linear?
The parameters for this 16*4 table of ...
- 401
3
votes
1
answer
222
views
What does it mean : "Canonical representative of Sbox is 0123468A5BCF79DE"? and How can we calculate this representative for Sbox?
In paper :Cryptographic Analysis of All 4 × 4-Bit S-Boxes Saarinen has classified $4 \times 4$ S-Boxes and defined Canonical representative for each class of S-Boxes.
What does "Canonical ...
- 336
6
votes
1
answer
191
views
Differential and Linear trail propagation in Noekeon
In the Noekeon Cipher Specification they write the following :
The propagation through Lambda is denoted by $(a \rightarrow A)$, also called a
step. Because of the linearity of Lambda it is fully ...
- 163
3
votes
0
answers
59
views
Finding maximal $n$-affine subset
We obtained $l$ vectors $B_i$ of $c$ bits $b_{i,j}$. These are an altered form of vectors $A_i$ where the last $n$ bits of each $A_i$ are an affine function of the other bits of that $A_i$.
We want ...
- 144k
3
votes
1
answer
158
views
Correlation of linear trail
When I am studying about linear cryptanalysis, I have a question about correlation of linear trail.
Let $U=(u_0, u_1 , ...,u_n)$ be a linear trail
Then we can compute a correlaton of linear trail $...
- 129
1
vote
1
answer
80
views
Correlation of an approximation over a random permutation
I read a paper of linear cryptanalysis that is J.Daemen et al's Probability distribution of correlation and differentials in block cipher.
In this paper's lemma 8's proof, I can't understand this ...
- 129
1
vote
2
answers
59
views
Relation between the correlation coefficients $\widehat F(w) = C(f(a), w^ta)$ and $(-1)^{f(a)}$
In the paper Correlation Matrices by Joan Daemen et. al., the authors state (on page 3) that if the correlation coefficients $C(f(a),w^ta)$ of a Boolean function $f$ are denoted by $\widehat F(w)$ ...
- 129
3
votes
1
answer
219
views
Matsui's Linear Cryptanalysis Lemma 1
In Matsui's paper (Linear Cryptanalysis Method for DES cipher), lemma 1.
$NS(a, b)$ is even
if $a=1,32$,or $33$, then $NS(a,b)=32$ for all $b$
He said that the following lemma is now trivial from ...
- 129