# Tag Info

## Hot answers tagged s-boxes

26

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

20

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

18

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 $\... 16 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. 16 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 ... 10 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 ... 9 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,...

9

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

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

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

8

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

7

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

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

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

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.

6

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

5

This is only a partial answer to the question, but still: The S-boxes where chosen to maximize confusion and to create an avalanche of change. For example, there were specific properties chosen to make the S-boxes resistant against differential cryptanalysis, by making sure that small differences between different inputs lead to larger differences in the ...

5

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.

5

Is it valid to call this table an S-Box? Not really; at least, not with the meaning we usually give to "S-box". The "S" in "S-box" stands for Substitution; we take the data, and replace it with a value from the S-box (using the data as an index into the S-box). The classical (if not the original) example is the S-boxes within AES; at certain points ...

4

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

4

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

4

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

4

Your code is an attempt to implement the function $f$ which is a polynomial representation of the $\text{GF}(2)$ affine part of the S-box of the AES (usually referred to as $A$). Function $f$ is described on page 7 of the paper and your coefficients seems to be OK. Your code is mapping $\text a$ to $\text q$ such that $\text q=f(\text a)$. You're however ...

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

The XOR state is irreversible without the proper key which is what I understand, so whats the point of all of the other operations that happen on the key? Suppose all we had was secret keys and the XOR operation. Well, actually, it is possible to build a secure cipher out of that, called the one time pad. One time pads offer perfect secrecy, but suffer ...

3

DES is based on a Feistel construction - while the one-way function used is.. well.. one-way, you don't need to reverse it at all to "decrypt" (otherwise you are correct we would have a problem). Look at this diagram, specifically the decryption one: As you can see, even though one half of the ciphertext is passed through the one-way function, there's ...

3

The answer is: it depends upon the cipher. You cannot design a S-box in isolation; the S-box properties need to be crafted together with the design of the block cipher, to make sure they work well together. See also Desirable S-box properties. Don't forget to use "search" before asking questions. The 3-Way cipher also uses 3x3 S-boxes.

3

As I already said in my comment, what you have here is not what one usually calls a block cipher. A (standard) block cipher is a pair of functions $$E : K \times M \to M \text{ and } D : K \times M \to M$$ This means $E$ takes an element of $K$ and an element of $M$ as input, and gives an element of $M$ as output – same for $D$. (where $K$ is called the key ...

3

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

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