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.

3
votes
1answer
68 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
101 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
56 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
62 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
45 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
80 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
85 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
58 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
298 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
119 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
135 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
114 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
310 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
129 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
179 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 ...
7
votes
1answer
382 views

Understanding the wide trail design strategy

I am trying to understand the wide trail design strategy. I have read the paper which describes it from the point of view of AES. From what I understand, it is a technique to increase diffusion in a ...
4
votes
1answer
140 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
111 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
465 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
81 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
63 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
100 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
170 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
179 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
50 views

Understanding linear cipher dencryption process

I am new to cryptography but having hard time understanding the concept. I understand all part except why 4 power -1 has become to 7. Can anyone explain why this is? Thank you
2
votes
1answer
338 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
125 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
476 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
157 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
191 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
562 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
209 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
63 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
134 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
342 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
449 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
82 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
256 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
222 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
132 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
159 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
285 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
213 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
110 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 ...
3
votes
2answers
160 views

Linear cryptanalysis complete key guessing

In linear crypt analysis, partial sub keys are guessed and verified for its correctness with the help of plaintext and ciphertext. From the partial sub key, how it is possible to guess the complete ...
1
vote
0answers
151 views

How to apply linear cryptanalysis to PRESENT?

Can someone help me implement linear cryptanalysis of the PRESENT block cipher? How should I start with 64 bits of plaintext and 80 bits of key?
-1
votes
1answer
726 views

How does non-linearity (S-box) add security to AES?

I'm trying to understand how AES guarentees security. One of the named points on the web is that AES uses a non-linear step (the SubBytes step). But how exactly does the Rijndael key schedule add ...