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
-1
votes
1answer
46 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 ...
4
votes
2answers
640 views

Differential and Linear Cryptanalysis

I have been reading about differential and linear cryptanalysis. They were mainly introduced by Adi Shamir and Biham to show the weakness of DES. However, many articles state that differential and ...
1
vote
0answers
65 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 ...
0
votes
0answers
33 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 ...
2
votes
1answer
56 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 ...
3
votes
1answer
116 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 ...
1
vote
1answer
166 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 ...
2
votes
2answers
1k views

Generate random number which should depend on key

i want to generate random number for example from [1..100]. The algorithm which would generates random number should work similarly like a "Linear congruential generator", like this: $X_{n+1}≡(aX_n +...
0
votes
1answer
106 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 ...
2
votes
1answer
54 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 $\...
6
votes
2answers
3k views

Why is the DES s-box non-linear? Why does it make the cracking of the cipher more difficult?

I know that if we have a cipher that makes only linear transformations (let's say a bunch of $XOR$s), we break it simply by writing a system of equations with $\oplus$ operation starting from the ...
2
votes
1answer
42 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 ...
1
vote
1answer
248 views

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

Since the McEliece 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 ...
0
votes
2answers
145 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 ...
0
votes
0answers
24 views

calculating the branch number/ active bundles of a cipher

I have read the papers Wide Trail Strategy and Wide Trail Design Strategy for Binary MixColumns. These papers describe the need for a good linear transformation in a cipher, a provable mechanism to ...
3
votes
2answers
151 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 ...
2
votes
1answer
106 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 ...
0
votes
0answers
25 views

How do I invert the final round S Boxes during linear cryptanalysis

I'm using Howard Hey's tutorial on linear cryptanalysis, however I don't understand the final stages. I understand using exhaustive partial subkeys to turn the ciphertext into the final round output, ...
22
votes
3answers
10k views

Why do block ciphers need a non-linear component (like an S-box)?

Why is there a requirement of "Non-Linear functions" as a component of many popular block ciphers (e.g. the S-box in DES or 3DES)? How does it make the cipher more secure? The only intuition I have ...
0
votes
1answer
43 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.
2
votes
0answers
39 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 ...
3
votes
0answers
218 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$ and ...
3
votes
1answer
584 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 ...
3
votes
1answer
78 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 ...
0
votes
2answers
124 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 ...
2
votes
2answers
258 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} $$ ...
3
votes
0answers
161 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 ...
2
votes
0answers
43 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
0answers
70 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^{\...
3
votes
0answers
116 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 ...
14
votes
1answer
1k 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 ...
0
votes
1answer
102 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
0answers
89 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 ...
11
votes
2answers
3k views

Combining LFSRs for Stream Ciphers: Why do we need high non-linearity?

Linear Feedback Shift Registers (LFSRs) can be excellent (efficient, fast, and with good statistial properties) pseudo-random generators. Many stream ciphers are based on LFSRs and one of the possible ...
1
vote
2answers
410 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
189 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 ...
4
votes
1answer
239 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?
3
votes
1answer
143 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
145 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
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 ...
3
votes
1answer
94 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 $...
16
votes
1answer
474 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$ ...
1
vote
1answer
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 ...
3
votes
1answer
144 views
1
vote
2answers
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)$ ...
3
votes
1answer
144 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
165 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; ...
4
votes
1answer
215 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 ...
1
vote
1answer
120 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 ...
2
votes
2answers
912 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 ...