27

They are both linear, but in different algebraic Groups. Which is to say, xor is linear in any finite field of characteristic 2, while 'ordinary' addition is linear in the infinite field of the Real numbers. Addition modulo $n$ (which is more cryptologically significant than addition over the Reals) is also a linear operation, but in the ring of integers $\...


21

What is the definition of linearity? Linearity is defined for maps between vector spaces. If you have a field $F$ and two vector spaces $U$ and $V$ over the field $F$, a map $$T:U\rightarrow V$$ is said to be linear if $$T(\gamma_1\odot u_1\oplus\gamma_2\odot u_2)=\gamma_1 \odot T(u_1)\oplus\gamma_2\odot T(u_2)$$ whenever $\gamma_1,\gamma_2\in F$ and $u_1,...


14

Differential cryptanalysis works on differences. Linear cryptanalysis works on linearity. Neat, isn't it ? Instead of speaking of how they differ, it is easier to list their common features. Both kinds of attacks: Use a lot of known pairs plaintext/ciphertext (many input messages encrypted with the same key, and, for each of them, the attacker knows both ...


14

Given the importance of the wide-trail strategy in modern symmetric-key cryptography, this question really deserves an answer (and a much better score). Since nobody else has tried, I'll give a brief summary and some context. Hopefully this will help you understand the paper by Daemen and Rijmen (paywal-free preprint) better. Since the (public) discovery of ...


12

The Berlekamp-Massey algorithm is an iterative method for finding the shortest LFSR that can generate a given sequence of bits. The given sequence might or might not be generated by an LFSR: the Berlekamp-Massey algorithm does not care. It just finds the shortest LFSR that can generate the given sequence, and if the sequence has been generated by an LFSR of ...


11

If there was no non-linearity, then every bit of keystream output would be a (known) linear function of the unknown key bits. Consequently, in a known-plaintext attack scenario, each bit of known keystream output would allow us to write a linear equation on the unknown key bits. If we have a 128-bit key, there are 128 boolean unknowns (variables), so once ...


10

It is of course possible to write DES or any block cipher as a system of non-linear equations involving the plaintext bits, the ciphertext bits, and the key bits, which hold with probability 1. In principle, cracking the cipher would then merely involve collecting enough linearly independent equations (e.g. from a couple different known plaintexts) and then ...


9

Leaving besides that the designers (NSA) of Simon and Speck did not provide an initial design rational for their ciphers/parameter choices, they added some notes later after pressure from the cryptographic community/ISO. There they mention that they selected the round constants to be ... optimal with respect to resistance against 8-round differential and ...


8

Linear functions when expressed as polynomials only have terms of degree 1 or 0. Non-linear functions have at least one term of degree 2 or higher. For example, here is a linear boolean function: $y = ax + bz + c$, where $y$ is the output bit, $x$ and $z$ are input variables, and $a$, $b$, and $c$ are constants. Notice that none of the variables are ...


7

The most well known example of a cipher practically broken with linear attacks is by no doubt DES, a cipher with 56-bit key and 64-bit block. Equipped with a cluster of PCs in the year 1994, Mitsuru Matsui has experimentally found a secret key after 10 days of the analysis (the data generation took additional 40 days on the same machine set). By that time ...


7

Does hashing require non-linear components as well? Yes How would a hash built from a linear psuedo-random permutation be vulnerable to collision/preimage search? You could find a preimage by solving for the preimage with linear equations; that is, for a linear function, each output bit is a linear function of the input bits. We would express the ...


6

I would say a distinguishing attack should count as a break. Especially so if it is practical. The reason for this is that if you can distinguish the key-stream from random, you invariably leak details about the plain-text. For example, suppose somebody turned up a few terabyte disks encrypted with VMPC under the same key. It says in the paper that after ...


5

For this cipher, I suggest finding all possible linear approximations by simply enumerating them. If $S$ is the S-box, the bias of the linear approximation $\alpha \cdot x = \beta \cdot S(x)$ is given by $$b(\alpha,\beta) = |2 \Pr[\alpha \cdot x = \beta \cdot S(x)] - 1|.$$ Notice that you can compute $b(\alpha,\beta)$ for a single value of $\alpha,\beta$ ...


5

The ability to recover $x$ in the latter case is a direct consequence of RSA's homomorphic property and the ability to recover $x$ in the former case. Suppose you are given the equations (with $c_i,a_i,b_i$ known): $$c_i=(a_i\cdot x+b_i)^e\bmod N$$ $$\iff c_i=(a_i\cdot x+a_i\cdot b_i\cdot a_i^{-1})^e\bmod N$$ $$\iff c_i=a^e_i(x+b_i\cdot a_i^{-1})^e\bmod N$$...


5

Yes, your table is perfectly linear: The output is the sum of the inner four bits plus left outer bit*0101 plus right outer bit*1010.


4

We need to get back to Matsui's notations. X is represented as X[31].... X[0] K is represented as K[47]......K[0] In X[15] ⨁ F5(X,K)[7,18,24,29] = K[22] X[15] is actually the round input before expansion E and is therefore the 4th bit of SBOX 5 with input bits of S5 being x[5]x[4]x[3]x[2]x[1]x[0]. X[15] = x[4] in practise and the key bit is the 23rd ...


4

Yes, linear cryptanalysis may still be possible, depending upon the distribution on the plaintexts and the specifics of the block cipher. For instance, suppose we know that the plaintext is English encoded in ASCII. Then we know that the high bit of each 8-bit byte is zero. We may also know some additional linear approximations that hold on the plaintext ...


4

If you include a key addition layer ($K_1$) at the output as well the key addition layer ($K_0$) at the input of the Sbox then you can perform linear cryptanalysis on this simple cipher. You shall have access to $P,C$ pairs but no keys, of course, and the $P/C$ relationship is $$C=K_1\oplus(S(P\oplus K_0))$$ and so your linear bias equations become something ...


4

The S-Boxes are lossy. They map 6-bit inputs to 4-bit outputs, so for a given 4-bit output there are several possible inputs. Considering that there are 8 S-boxes, that's 16 bits of information lost per round, or 256 bits for all 16 rounds. It's much easier to exhaustively search the 56-bit keyspace than try to work backwards against that kind of information ...


4

The paper you link to gives precise definitions for the MEDP and MELP. I will attempt to explain the definitions more expansively & clearly. First, the differential probability (DP) function with respect to a given block cipher takes an input difference $\Delta x$, an output difference $\Delta y$, and a key $k$ as inputs and generates a probability as ...


4

They said that, one goal of MDS matrices is to protect the block ciphers against linear and differential attacks. That would probably depend on the cipher, but in generally, pretty accurate. is constructing the bias table of MDS matrices behavior impossible? Actually, it's trivial; MDS matrices are completely linear, and so they have probability 1 ...


4

This is a type of "Gaussian approximation", assuming the wrong key randomization hypothesis, and given the bias $|p-1/2|$, the success probability depends on the order statistics of the "sample bias" of the various subkey bit guesses. Let $T_i$ be the number of times the linear approximation is satisfied by subkey guess $k_i,$ and $$Y_i=|(T_i/N)-1/2|,$$ is ...


4

This is due to the duality between linear and differential trails. Let $L$ be an invertible linear map on $\mathbb{F}_2^n$, think of it as a matrix for convenience. In general, a nonzero differential $\Delta_1 \to \Delta_2$ over $L$ must satisfy $$\Delta_2 = L\,\Delta_1.$$ A nonzero linear approximation $u_1 \to u_2$, however, must satisfy $$u_2 = L^{-\...


4

Let $N(\alpha,\beta)$ be the number of times the equation $$ \alpha\cdot x \oplus \beta \cdot y=0 \tag{0} \label{0} $$ holds. Then the LAT matrix entry is $$ L(\alpha\cdot x \oplus \beta \cdot y )= N(\alpha\cdot x \oplus \beta \cdot y)-2^{n-1} $$ and since the second term is even (can prove $n=1$ case directly) we need to show that $N(\alpha\cdot x \oplus \...


4

In this formulation you need to convert your function's output range to $\{-1,+1\}$ via $$f`(x)=(-1)^{f(x)}$$ and apply the Walsh Hadamard to the new function $f`(x)$. Using the zero one formulation means you are off by a constant depending on the number of variables since $$ (-1)^u=1-2u $$ for $u\in \{0,1\}.$ See my answer below on Boolean functions and ...


4

What I don’t get is why the complexity became quadratic in linear case? Well, in linear cryptanalysis, for each input, we get a bit with a bias of $0.5 \pm \epsilon$, and we need to determine if that bias is $0.5 + \epsilon$ or whether it is $0.5 - \epsilon$ If we were to query a random bit (that is, one with no bias) $n$ times and sum the results, we're ...


3

By convention: LC = Linear Cryptanalysis DC = Differential Cryptanalysis There are multiple ways to increase the security of a block cipher. The first one (and usually applied) is to increase the number of rounds. In the case of FEAL, they switched from 4 to 8 rounds and then to X rounds. Therefore you would have to extend the equations for 7+ rounds ...


3

It is important to understand that although a very large random function will only have linear biases with very low probability, this is simply not true of small random functions. If you choose a small random function, then it is unlikely that you will get one that is suitable for block cipher constructions. In addition, it is not enough to construct an S-...


Only top voted, non community-wiki answers of a minimum length are eligible