# Tag Info

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

13

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

13

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

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

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

From TRUTH TABLE to ANF First write [6, 4, 7, 8, 0, 5, 2, 10, 14, 3, 13, 1, 12, 15, 9, 11] in that way: the columns of matrix are those numbers in $\mathbb{F_2^4}$. $$\begin{bmatrix} 0&0&1&0&0&1&0&0&0&1&1&1&0&1&1&1\\ 1&0&1&0&0&0&1&1&1&1&0&0&0&1&... 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 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 ... 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 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 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. 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 ... 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 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 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 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 I just wanted to extend poncho's answer as aspects of this question keep coming up. Generally speaking, you can write constant-time portions of software if you have privileged OS access, but it's not very practical. I also think it's impossible from userspace. Here's the crux of the problem: Everyone wants their computer to be "faster"; however, it doesn'... 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 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 ... 6 I understand the question as you have a single 4-bit S-box, which you first apply rowwise, and then columnwise. As already mentioned, this is equivalent to a large S-box \mathcal{S}$$ c = \mathcal{S}(m\oplus k_1)\oplus k_2.  This is a well-known Even-Mansour cipher, and it can be broken with complexity $2^{n/2}$, which is $2^8$ for your $n=16$. The ...

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

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