Hot answers tagged

29

There is a good article from Coppersmith which explains it. Basically, the designers of DES had envisioned differential cryptanalysis (a good 15 years before differential cryptanalysis was rediscovered by Biham and Shamir, and published); they could measure how well DES could resist differential cryptanalysis for a given set of S-boxes. So they generated a ...


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


24

Before it was the standard, the NSA proposed some changes to the S-boxes and didn't explain them. The explanation (which turned out to be correct when differential cryptanalysis was "rediscovered" by the non-spy community) was that if you changed a single bit of the input, every bit of output should have a 50% chance of changing (this is called the "strict ...


22

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.


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


20

Let a "block cipher" be defined with a fixed S-box $S$ (i.e. a permutation of some space) and a key $K$ (same size than a block), such that the encryption of a block $M$ is $C = S[P\oplus K]$. Everybody knows $S$ and can apply and invert it (that's a "S-box", not a "key" -- if the S-box is "key dependent" then the S-box is itself a block cipher in its own ...


17

The following information about the DES S-Box might be useful (taken from here): DES Design Criteria there were 12 criterion used, resulting in about 1000 possible S-Boxes, of which the implementers chose 8 these criteria are CLASSIFIED SECRET however, some of them have become known The following are design criterion: R1: Each row ...


15

The affine transformation works similar to MixColumns, but operates on an array of 8 bits instead of 4 bytes. Confusion in various descriptions of the affine transform in AES comes from where the LSB of the input byte is located. Some show it at the top of the column, others show it at the bottom. I will be using the version shown in the Rijndael paper, with ...


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


12

The security of a block cipher is, based on what we know, invariant to the permutation cycles of the S-box. This is because the values are always transformed (by a fixed function or a keyed function) before going through the S-box again in the next round. Furthermore, many S-boxes are functions not permutations (i.e., output size is different from input size)...


12

Good question and yes, it would appear that data is lost. And technically, something clearly must disappear as 6 don't go into 4. But consider the overall architecture of DES: Trace the flow of the left and right halves of an individual block of data. You'll see that the 2 full 32 bit words flow unimpeded down though the Feistel network. No information is ...


12

It mostly has to do with the real world influence of memory caches. A cache is a small amount of fast memory; when you read from memory, the contents are placed in this fast memory (possibly along with adjacent locations); if you read from the location again, you read it from the fast memory (which, of course, proceeds much faster). Hence, if you read a ...


11

The tricky point is that $\mathbb{F}_2^8$ is not a field; it is a degree-8 vector space. Multiplications are not defined on vector spaces. However, the $A$ transform is defined only on the vector space, not on the field (it is "affine" only when considering its source/destination space as a vector space). The $\phi$ and $\phi^{-1}$ operations are thus "type ...


11

There are simply a long list of properties for S-boxes that are relevant, see for example these questions: Desirable S-box properties S-box design criteria and random sboxes In addition people have been trying to design S-boxes that are fast to implement in hardware or in software or which can be masked efficiently. For example the Midori S-box is designed ...


10

Is it necessary to choose a primitive polynomial for an S-Box? Actually, it is not necessary (and, as the polynomial they actually use in AES, $x^8 + x^4+ x^3 + x + 1$, is not primitive, and so it's a good thing that it's not necessary). The polynomial must be irreducible (if it isn't, the multiplication operation isn't invertible in general, and hence you ...


10

A good source for this kind of questions is the book The Design of Rijndael by Joan Daemen and Vincent Rijmen. On page 35 they write about their choice for the used S-box $S_{RD}$: Design criteria for $S_{RD}$. We have applied the following design criteria for $S_{RD}$, appearing in order of importance: Non-linearity. a) Correlation. The maximum input-...


9

I'm going to ignore the "CBC" part of the question and focus on "What are the strengths and weaknesses of a s-box and xor cipher. I'm going to assume that the s-box size is smaller than the message block size since any cipher that has a block size that is equal to it's s-box size is going to have a block size small enough to be brute forced. Using xor and s-...


9

What are the disadvantages of using random s-boxes? This relates to the "why" behind some of the rules for s-boxes. AES, for example, requires an invertible s-box. A random s-box will not necessarily be invertible. In an s-box we also want non-linearity to thwart linear and differential cryptanalysis. This might not be the case with a random s-box. In ...


9

This is useful to know in general. Given the Sbox map, generate the truth tables for the bits of the map. From the truth tables, obtain the algebraic normal form, via the Mobius transform. So, given an $n-$bit truth table, say $$T=[f(x): x \in \mathbb{F}_2^n]$$ where $$x=(x_1,\ldots,x_n)$$ ranges over the vector space $\mathbb{F}_2^n$ in standard order, ...


8

There are 256! possible 8x8 S-boxes (i.e., bijective functions from $\{0,1\}^8$ to $\{0,1\}^8$). This is an absolutely enormous number. You couldn't possibly enumerate all of them within the lifetime of the universe. So, yes, this is one reason why it is not straightforward to determine whether there exists such a S-box with differential uniformity 2.


8

Desirable Properties For simplicity, I’m skipping some of the details here… but the main criteria of a good s-box are: It should have balanced component functions, The non-linearity of its component functions should be high, The non-zero linear combinations of its component functions should be balanced and highly non-linear, It should satisfy SAC (strict ...


8

The S-boxes in quite many encryption algorithms (for example, in AES) have been already built with math (the AES S-box is an inversion function in $GF(256)$ plus an affine transformation). The lookup tables exist solely to ease the implementation. In fact, modern Intel/AMD CPU are already equipped with AES round function instructions, so the tables are not ...


8

Coincidentally I had the Twofish and Camellia design papers open on my computer when you asked this question. S-boxes in the ciphers Both are Feistel ciphers, and the way the s-boxes are used is quite different when compared to AES. The s-boxes are used almost identically in Twofish and Camellia, but key mixing and post s-box diffusion are quite different. ...


8

Before we start with vectorial Boolean functions, let's recall the definition of the nonlinearity of a Boolean function: $$\mathcal{NL}(f) = \min_{a \in \mathbb{F}_2^n} d_H(f, \ell_a \oplus b),$$ where $\ell_a \oplus b$ represents the affine Boolean function defined by the bitvector $a$: $\ell_a(x) = a \cdot x$ ($\cdot$ is the dot product). The above ...


8

DES uses a Feistel network. The S-box results gets XOR-ed with the other half so no information is lost. It doesn't need to be invertible.


7

The answer is: it depends. It depends on how you plan to use your S-box. Presumably you are going to use your S-box in some block cipher. In that case, you have to look at what properties you need from the S-box, and then generate the S-box accordingly. You can't separate the design of the S-box from the design of the rest of the cipher. There is no ...


7

Ciphers that use S-boxes are typically in the form of a Feistel network. This has the property that inverting the cipher does not involve inverting the round function, but simply applying the rounds in the opposite order. Therefore one doesn't need to invert the S-box to decrypt.


7

The S-Box was generated when Rijndael was designed, not in any step. It's used in every round in the SubBytes step. The S-box is constant. You could see it as a function taking a byte and returning a byte. It is used to reduce algebraic properties of Rijndael. In fact, this is it: | 0 1 2 3 4 5 6 7 8 9 a b c d e f ---|--|--|--|--|--|--|--|...


7

The reason it is taking 4 32-bit integers into the round function is because it IS a bitsliced implementation. It bitsclices 32 4-bit sboxes into 4 32-bit inputs and uses standard logical operations on the words to get the job done. The sbox you posted was not generated by Osvik, but he generated a set of optimized blitsliced sboxes for 32-bit ...


7

Finally I've went to the source and I've mailed the Rijndael's authors. They have answered very fast and very nice. I've understood the other way around. The affine transformation is over the vector space $((GF(2))^8$ and what they've say as simplicity was that, between all the possible affine transformations they select one that can also be described as ...


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