We’re rewarding the question askers & reputations are being recalculated! Read more.

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
0answers
63 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 ...
0
votes
0answers
38 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 ...
1
vote
2answers
111 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 ...
3
votes
1answer
81 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 ...
6
votes
1answer
117 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 ...
3
votes
0answers
54 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 ...
3
votes
1answer
67 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 $...
1
vote
1answer
63 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 ...
1
vote
2answers
48 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)$ ...
3
votes
1answer
100 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 ...
3
votes
2answers
101 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; ...
1
vote
1answer
74 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 ...
15
votes
1answer
330 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$ ...
2
votes
2answers
186 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 ...
-1
votes
1answer
148 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 ...
3
votes
1answer
138 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 ...
1
vote
1answer
431 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 ...
3
votes
1answer
154 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? ...
4
votes
1answer
184 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 ...
9
votes
1answer
543 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 ...
4
votes
1answer
169 views

Non Linearity of huge Sbox

Sboxes provide confusion in cipher. Non Linearity measures the strength of sbox layer. In order to measure non linearity of sbox, a table is computed to measure distances with its affine functions. If ...
3
votes
1answer
123 views

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

How does he end up with this result in his article ?
2
votes
1answer
536 views

Key recovery after AES-ECB encryption of two blocks with some known plaintext/ciphertext

I am analysing a small, bespoke end-to-end encryption service's source code, in particular their user registration process. I am finding some interesting things going on and I am wondering if there's ...
3
votes
1answer
1k views

Non-Linearity of an Sbox

Non-Linearity of an Sbox affects its resistance towards Linear Cryptanalysis. What happens, if an Sbox has low non-linearity (specially with respect to Linear Cryptanalysis)?
1
vote
0answers
86 views

Known Plaintext Attack A5/2

I am trying to understand the non-optimized known plaintext attack on A5/2 from Barkan, Bikan and Keller. I don't understand the construction of the equation system: $$S_{R4_1} * S_1 = k$$ Where $S$ ...
0
votes
0answers
70 views

Security of an S-box based on modular multplicative inverse

The construction of Rijndael's S-box starts with the multiplicative inverses of each number over a finite field. It seems like this is the main source of its non-linearity. I figured that modular ...
2
votes
0answers
115 views

How can I identify the linear equations for a block cipher with 4 different s-boxes?

For a block cipher with 4 different s-boxes (each used in an individual round) how can I identify the linear equations? Normally, for ciphers like AES with a single s-box, linear cryptanalysis can be ...
2
votes
0answers
188 views

If we use another irreducible polynomial for AES how can we show it is still resistant to DCA and LCA?

AES has been rigorously tested against all known attacks. However, I believe there are 30 suitable irreducible polynomials that could be used for AES. If we were to change the current irreducible poly ...
1
vote
1answer
188 views

Can McEliece cryptosystem be used as an additively homomorphic encryption scheme?

Since McElice cryptosystem is linear, if matrix G is kept constant for different plaintexts, it can be used for linearly combining the corresponding ciphertexts. In that case, what are the advantages ...
0
votes
1answer
71 views

Understanding the linear cipher decryption process

Being new to Cryptography, I'm having a hard time understanding the basic concepts. I understand all parts except why 4 power -1 has become to 7. Can anyone explain why this is?
2
votes
1answer
387 views

What is an advantage of MDS matrices in block ciphers?

I saw the several articles about MDS matrices. They said that, one goal of MDS matrices is to protect the block ciphers against linear and differential attacks. My question is: For example in the ...
1
vote
1answer
137 views

3-round DES: what bit do we find? (Regarding matsui's Paper on Linear Cryptanalysis of DES)

In Matsui's paper, Section 5 ‘Linear Approximation of DES Cipher’, Matsui gives two similar equations: Eq. (6) for the first round and Eq. (7) for the third round. The two equations give an ...
4
votes
1answer
575 views

Linear Related Message Attack on RSA

I have a question about this attack: Oded Yacobi and Yacov Yacobi, A New Related Message Attack on RSA (in proceedings of PKCS2005). Given $e$ linear related messages encrypted with RSA: $c_i = ({x_i}...
4
votes
1answer
170 views

linear cryptanalysis of hash function

I have studied linear cryptanalysis for block ciphers, but i did not understand how it works on hash functions. Can you give me an explanation of this attack on hash functions?
6
votes
1answer
201 views

Linear Cryptanalysis of hash function

I've studied linear cryptanalysis, but i don't think I have it very clear. I've the following doubt: I've constructed a "cryptographic" hash function for an exercise, and now i want to show summarily ...
5
votes
2answers
630 views

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

I was reading this paper which has a lot of references to the terms MEDP and MELP. Even though i think i got the general meaning, I could not verify that it is indeed correct. For the MEDP, I would ...
5
votes
1answer
264 views

Does hashing require non-linearity?

I know that for encryption we require non-linearity because it impedes the ability to attack the cipher by solving for the key with linear equations. Does hashing require non-linear components as ...
1
vote
0answers
64 views

Are there methods for finding not optimal but good linear approximations for functions?

I'm interested in finding the best, or maybe just a good linear approximation of the function $F^{(19)}: V_{56}\to V_8$, where $$ \begin{array}{l} F^{(1)}(x_1,x_2,\ldots, x_7) = P(x_2+x_6); \\ F^{(...
-1
votes
2answers
138 views

Hill-Chiffre - How can I find the Matrix $X$

This is a problem of classical cryptography: Hill-Chiffre Where the matrix $A$ is the clear message and the matrix $C$ the coded message. How can I find the Matrix $X$? Which method I can use? $$\...
5
votes
1answer
392 views

FEAL-4 Linear Cryptanalysis - Prevention

currently, I prepare for an exam about cryptanalysis. In class, we talked about linear cryptanalysis for FEAL-4. We constructed four linear equations, extended them to equations for three rounds and ...
5
votes
2answers
2k views

Why DES s-box non-linear? Why it makes the cracking of the cypher more difficult?

I know that if we have a cypher which makes only linear transformations (let's say a bunch of $XOR$'s), we break it simply writing a system of equations with $\oplus$ operation starting from the ...
0
votes
1answer
469 views

A5/2: Ciphertext Only Attack

A5/2 could be attacked with cipher-text only, using the Error Correction Code, in order to retrieve the session key. For the purpose of simplicity suppose that the error correction code copy the ...
2
votes
1answer
85 views

linear cryptanalysis: how are the subkey bits removed from the linear approximation?

I'm currently reading the tutorial on linear/differential crypta here: https://www.engr.mun.ca/~howard/PAPERS/ldc_tutorial.pdf End of page 14/Beginning of page 15: all the bits from the subkeys are ...
3
votes
1answer
285 views

Last Sbox of a block cipher for Linear Cryptanalysis

I figured I should try to learn about linear cryptanalysis with a super simple cipher with only one Sbox. The problem is that with that approach the last subkey bits seem to be involved in the linear ...
3
votes
1answer
235 views

Differential & linear characteristics for integer multiplication

What are the probabilities of differential & linear characteristics for the function that XORs the high and low bits from a $n \times n \rightarrow 2n$ bit multiplication? I remember reading ...
3
votes
0answers
142 views

Breaking linear blockcipher - expanding recursive formula

I am trying to break a block cipher that can be defined as follows: We have 12 rounds and at each round we perform the following operation. We split 64 bit data into 2 parts each 32-bits, $\ x_r$ ...
3
votes
1answer
168 views

Differential bound of the S-Box in GOST R34.11-2012

In Russian GOST R34.11-2012 LPS-transformation is used. LPS gets all of its non-linearity from the 8-bit S-box S, which apparently has been designed to offer resistance against classical methods of ...
2
votes
1answer
315 views

Why is not there any ideal S-Box?

i read about linear cryptanalysis and about S-Box that there is not any ideal S-Box (ideal S-Box is a random S-Box in another words S-Box that bias of input and output bits is zero) then i read about ...
2
votes
1answer
265 views

Extracting key bits from linear cryptanalysis equation for SDES

From the linear cryptanalysis of SDES, we get a linear equation consisting the K[1, 3] of the round key 1 and 2. From this how will I retrieve the key bit? How do we solve the linear equation we get ...
3
votes
1answer
119 views

The sign of the correlation in linear approximation

${\text{Let }}g:{\{ 0,1\} ^n} \to {\{ 0,1\} ^n}$ be a round function of an $n$-bit iterated block cipher and let $K \in {\{ 0,1\} ^n}$ be a fixed round-key, and denote ${g_K}(x) = g(x \oplus K).$ Show ...