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.

Filter by
Sorted by
Tagged with
2 votes
1 answer
57 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 ...
user avatar
0 votes
0 answers
18 views

Fast implementations in c++ to find linearity of 16! sboxes?

I have to analize 16! of 16 bytes sboxes but my code is to slow to handle it. Anyone have any fast implementation on that? Thank you.
user avatar
2 votes
1 answer
66 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 ...
user avatar
  • 6,541
2 votes
0 answers
51 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-...
user avatar
2 votes
2 answers
91 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 ...
user avatar
1 vote
0 answers
36 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 ...
user avatar
4 votes
1 answer
123 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 ...
user avatar
1 vote
1 answer
123 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 ...
user avatar
  • 219
1 vote
0 answers
49 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 ...
user avatar
  • 161
1 vote
1 answer
51 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 ...
user avatar
2 votes
2 answers
84 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 ...
user avatar
-1 votes
1 answer
58 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 ...
user avatar
  • 1
0 votes
0 answers
68 views

¿Can it be proved that both AES's ShiftRows and MixColumns are linear transformation? (if we leave out subBytes and key addition)

I've been researching a bit and found that the mixColumns step could be expressed as matrix multiplication like this: But I'm not sure what's the mathematical proof for it and I can't find an example ...
user avatar
2 votes
1 answer
60 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 ...
user avatar
0 votes
1 answer
122 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 ...
user avatar
  • 3
2 votes
1 answer
64 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 $\...
user avatar
  • 23
2 votes
1 answer
84 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 ...
user avatar
  • 175
2 votes
1 answer
138 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 ...
user avatar
  • 175
3 votes
2 answers
182 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 ...
user avatar
  • 175
0 votes
2 answers
186 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 ...
user avatar
  • 157
0 votes
1 answer
53 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.
user avatar
2 votes
0 answers
41 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 ...
user avatar
2 votes
1 answer
234 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 ...
user avatar
3 votes
1 answer
99 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 ...
user avatar
  • 593
2 votes
2 answers
275 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} $$ ...
user avatar
  • 35
0 votes
2 answers
161 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 ...
user avatar
  • 157
3 votes
0 answers
183 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 ...
user avatar
  • 141
2 votes
0 answers
44 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´...
user avatar
4 votes
0 answers
71 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^{\...
user avatar
  • 878
3 votes
0 answers
164 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 ...
user avatar
2 votes
0 answers
94 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 ...
user avatar
  • 89
1 vote
0 answers
69 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 ...
user avatar
  • 89
1 vote
2 answers
544 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 ...
user avatar
3 votes
1 answer
159 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 ...
user avatar
6 votes
1 answer
157 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 ...
user avatar
  • 153
3 votes
0 answers
57 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 ...
user avatar
  • 122k
3 votes
1 answer
113 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 $...
user avatar
  • 129
1 vote
1 answer
68 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 ...
user avatar
  • 129
1 vote
2 answers
53 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)$ ...
user avatar
  • 129
3 votes
1 answer
146 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 ...
user avatar
  • 129
3 votes
2 answers
181 views

Stream cipher example for an introductory cryptography course

I am looking for an easily defined stream cipher to illustrate two basic principles in an undergraduate cryptography course: not every bit of the internal state should be used in the keystream; ...
user avatar
1 vote
1 answer
126 views

Matsui's paper on Linear Cryptanalysis of DES

I am trying to derive the best linear approximation for one round DES. I read the question and answer Regarding matsui's Paper on Linear Cryptanalysis of DES several times but still could ...
user avatar
  • 21
16 votes
1 answer
534 views

Selection of rotation constants in ARX design

My question is about choosing the rotation values in ARX design such as SIMON-like or SPECK-like ciphers to provide optimal differential and linear immunity. According to this, the selection of $a$ ...
user avatar
  • 1,980
2 votes
2 answers
1k views

How does linear vs. non-linear operations relate to cryptographic security and differential cryptanalysis?

I understand what a linear operation is and what a non-linear operation is, but I would like an explanation of specifically how a non-linear operation on input data mitigates differential crytanalysis ...
user avatar
-1 votes
1 answer
218 views

Compression function cryptanalysis

A compression function converts a fixed-sized input into a smaller fixed size output. Suppose that one has a large collection of input-output pairs for an unknown compression function. We can assume ...
user avatar
3 votes
1 answer
187 views

Linear cryptanalysis and number of linear approximations

I try to understand the linear cryptanalysis. Now I am reading as a secondary reference the book "Cryptanalysis of Block Ciphers: A Survey" by Standaert , Piret and Quisquater. In the first step, the ...
user avatar
2 votes
1 answer
1k views

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

I've been following this very good tutorial on linear cryptanalysis, and I'm stuck at the linear approximation part. I have no idea what input and output masks are. I don't understand what he's doing ...
user avatar
3 votes
1 answer
262 views

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

Until now every tutorial I've seen about linear cryptanalysis, is written on the basis that we have all possible inputs/outputs. Is that a condition? And if not, how many should we have as a minimum? ...
user avatar
4 votes
1 answer
220 views

it is possible to use quantum algorithm search (Grover's algorithm) for new searching strategies for differential and linear attacks

I am trying to use Grover's algorithm to find Differential characteristic of Feistel and SPN structures block ciphers. basically, which is Finding a good differential characteristic with high ...
user avatar
15 votes
1 answer
2k views

Understanding the wide trail design strategy

I am trying to understand the wide trail design strategy. I have read the paper (paywall-free preprint) which describes it from the point of view of AES. From what I understand, it is a technique to ...
user avatar
  • 12.9k