Hot answers tagged

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


16

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


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

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

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


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

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

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

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

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

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


7

The point in the question makes senses, especially if one restricts to portable software implementations. But: Small or moderately large constant-time RAM tables are reasonable, efficient, and (thus) common hardware building blocks. They are often used in DPA-protected DES and AES hardware coprocessors. Thus we can't dismiss key-dependent S-tables in ...


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

In the field $GF(2^8)$, $x^{254} = x^{-1}$ (except for $x=0$, as $0^{-1}$ doesn't exist; for AES, that's treated as 0), and so it's two ways of describing the same thing. When we talk about AES, we typically use the $x^{-1}$ nomenclature; for whatever reason, your class decided to go with the $x^{254}$ one.


7

Why? There are many factors besides basic linear/differential properties. For example, as mentioned by Elias, there are other considerations such as "How does the mapping facilitate masking countermeasures?". Arguably the most important factor, besides optimal linear/differential properties, is the implementation cost. Could we not just devote an hour ...


7

Are the S-boxes they are considering just random permutations of bytes that fit into an 8×8 table? How might they have chosen all the entries to get the S-box? Yes, they chose a random s-box. Are they choosing a random S-box and then leaving it unchanged thereafter Yes, it was unchanged. In Section 3.1 they state differential cryptanalysis will not ...


7

Serpent uses 8 different 4-bit S-boxes (i.e. each S-box contains 16 elements) a total of 32 times. There are no "rows" or "columns" as it is a one-dimensional array containing a derangement of 16 elements. For each S-box, a 4-bit integer from 0 to 15 is mapped to another 4-bit integer from 0 to 15. When implementing the S-box as an array, ...


6

If you are looking specifically for $3 \times 3$ S-boxes, you might want to take a look at the printCipher specification since it uses one. You can trust the people who chose it to have picked the best one. If you still want to go for the generation, keep in mind that many S-boxes have identical cryptographic properties (differential uniformity/spectrum, ...


6

You should think of Rijndael's S-box as a function that maps bytes to bytes, where a byte (octet) is considered to be a member of a finite field of size $2^8$ (with xor as addition). It's not seen as a 16x16 octet array, really. The substitution is then just done byte-wise: every octet in the 4x4 block is replaced by its function value under the S-box ...


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