Hot answers tagged

27

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


21

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


20

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


11

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


11

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


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

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


7

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


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

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


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


5

The difference distribution table for the AES s-box contains mostly probability 2/256 differentials. However, there is a single probability 4/256 for each input/output difference. I uploaded a dump of the table here so that you can see. The code used to produce this table can be found here. Disclaimer: This is my personal github. If by "uniform", you mean ...


5

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


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

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

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

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


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

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