26

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


21

If a block cipher is linear with respect to some field, then, given a few known plaintext-ciphertext pairs, it is possible to recover the key using a simple Gaussian elimination. This clearly contradicts the security properties one expects from a secure block cipher.


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

Here's the cryptography theory perspective. We want block ciphers to resemble pseudo-random permutations (PRPs). PRPs are a desirable modeling goal because a block cipher under a given key is a permutation on the input, and a PRP is simply a random collection of permutations. The block cipher's key can never be better at creating permutations than an actual ...


11

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


10

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


9

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 better. Since the (public) discovery of 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 ...


8

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


7

Any Pseudo Random Number Generator using a Linear Congruential Generator, and no cryptography, is going to be unsafe, or at the very least unsatisfactory, per the criteria in our FAQ. Likely, a skilled adversary would be able to predict future output from some amount of past output with moderate work; at best, that won't happen, but there will be no sound ...


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

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


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

@Sarwate gave a clear answer. I'm just following with an example to demonstrate his answer for the potential benefit of other readers: Consider the sequence with minimal polynomial $\Lambda(z)=z^6+z^5+z^4+z+1$. With initial state $100111$ this starts as $1001110110000011\dots$ and repeats every $63$ bits ($63$ is its period). So here $L=6$. If we try ...


5

The Berlekamp-Massey algorithm find the shortest LFSR that can produce the given sequence. Formally, if the sequence has $n$ elements $S_0, S_1, \ldots, S_{n-1}$, then the algorithm finds $\lambda_1, \lambda_2, \ldots, \lambda_t$ such that for $i = t, t+1, \ldots, {n-1}$, the following equation holds: $$ S_{i} +S_{i-1}\lambda_{1} + S_{i-2}\lambda_2 + \...


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

Not to my knowledge. Here is a possible explanation: non-trivial differential attacks are rather difficult to find in a fully automated way, and most of the time, one requires some (human) insight from a cryptanalyst before beginning to write some software. Another explanation could be the following: cutting-edge differential attacks (like against SHA-3 ...


4

They are generally relevant only to symmetric-key cryptography (e.g., block ciphers, hash functions, message authentication codes). There's no deep reason why -- it's just that differential and linear cryptanalysis tend to be effective against the sort of structure that are commonly used in block ciphers, but not very effective against the sort of designs ...


4

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


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

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

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^{-\...


3

To apply this kind if cryptoanalysis you need to have at least few pair of plaintext-ciphertext. Without knowing plaintext you could not build correct linear expression, because you will not know where to start. Quote from Tutorial on Linear and Differential Cryptanalysis: Linear cryptanalysis tries to take advantage of high probability occurrences of ...


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