# 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.

94 questions
Filter by
Sorted by
Tagged with
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
1k views

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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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, ...
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 ...
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.
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 ...
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 ...
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 ...
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 ...
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 ...
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}$$ ...
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 ...
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´...
70 views

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$ ...
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 ...
144 views

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

How does he end up with this result in his article ?
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)$ ...
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 ...
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; ...
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 ...