13
votes
Generate ANF from SBox
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 ...
- 20.1k
13
votes
Why don't table lookups run in constant time?
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 ...
- 140k
12
votes
Accepted
AES s-box representation
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 ...
- 86.1k
12
votes
Accepted
Generate ANF from SBox
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&...
- 148
12
votes
S-box basic question
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 ...
- 14.8k
11
votes
Accepted
Why is the DES s-box non-linear? Why does it make the cracking of the cipher more difficult?
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 ...
- 4,375
11
votes
How does one practically calculate the non-linearity of a multi-output boolean function like the AES s-box?
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),$$
...
- 1,826
11
votes
Accepted
Why do we keep designing new static s boxes?
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 ...
- 4,883
10
votes
Accepted
Is it necessary for the Rijndael polynomial to be primitive?
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 ...
- 140k
10
votes
AES vs DES S-boxes
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 ...
- 101
10
votes
What is this AES SBOX triplet property?
This is rather pretty if you understand finite fields and rather baffling if you don't. All the arithmetic takes place in $GF(256)$, so if you're not used to $1+1=0$, I apologise.
Conversion to pure $...
- 20.2k
9
votes
S-box basic question
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.
- 11.6k
8
votes
Accepted
Rijndael S-boxes: Where do the $\mu$ and $\nu$ polynomial ring elements come from?
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 ...
- 717
8
votes
Accepted
Number of Sbox in a Cipher
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 ...
- 12.9k
8
votes
Accepted
How do the Serpent S-boxes work?
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 ...
- 14.9k
8
votes
Accepted
Why is this function bijective?
It is simply a typo in the paper I believe. It should say:
$$F(x_1, x_2, \ldots, x_n) = (f(x_1, \ldots, x_k), f(x_2, \ldots, x_{k+1}), \ldots, f(x_n, x_1, \ldots, x_{k-1})).$$
(Note the $x_n$ instead ...
- 1,563
7
votes
Accepted
Converting a 5-bit s-box to its bit-sliced format
A recent paper presented at FSE'2016 [1] addresses this exact question. In fact, it even provides a bitsliced implementation for the S-Box you are interested in Section 4.
In summary: you first ...
- 456
7
votes
Accepted
Do key-dependent S-boxes make efficient constant-time software implementations almost impossible?
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) ...
- 134k
7
votes
Accepted
Active S-boxes for AES with 8x8 MDS matrix
It seems that using an 8x8 MDS will have 27 Active Sboxes after 4 Rounds(There may exist a trail shorter than 27). The image below shows the counting of active Sboxes.
The Active and non-Active byte ...
- 2,377
7
votes
Accepted
How constant value 0x63 in affine transformation is chosen or generated while AES Substitution Box is formed?
According to the Rijndael AES proposal (emphasis mine):
We have chosen an affine mapping that has a very simple description per se, but a complicated algebraic expression if combined with the ‘...
- 45.7k
7
votes
Accepted
Construction of S-box in AES
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 ...
- 140k
7
votes
Why do we keep designing new static s boxes?
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 ...
- 19.4k
7
votes
Why don't table lookups run in constant time?
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 ...
- 4,524
7
votes
Accepted
Security of the AES with a Secret S-box
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 ...
- 12.9k
6
votes
Accepted
How to build a difference distribution table?
Those tables are fairly easy to build conceptually but require quite some work to actually carry out.
Note that: The columns show the XOR for the in-going pairs and the rows show the number of pairs ...
- 45.5k
6
votes
BOOLEAN FUNCTIONS: generate a function $f: \{0, 1\}^n \rightarrow \{0, 1\}$ from a $n \times n$ S-Box
Your n x n S-Box can be seen as a set of $ n $ boolean vectors of size $ n $. Actually you have got $ n $ functions, each one is the truth table of one particular vector (or column).
In your example ...
- 219
6
votes
Linear Approximation and Linear Probability of Camellia Sbox
Let $LP$ be the linear probability (also called "correlation potential"), $Cor$ be the correlation coefficient and $\epsilon$ be the bias of a linear approximation. Then
$LP = Cor^2 = (2\times \...
6
votes
S-boxes are not linear
I don't believe you're really asking 'why did they select an SBox with 0 being mapped to something other than 0"; essentially, that's what the designers picked.
Instead, it is "why does $S(0) \ne 0$ ...
- 140k
6
votes
Accepted
How can one construct the weakest S-box ever?
Any affine function will do. Let your Sbox be $$S(x)=Mx\oplus c$$ where $M$ is an $n\times n$ binary matrix and $c$ is an $n-$bit constant vector.
The output difference for this Sbox is, for any ...
- 20.1k
6
votes
Accepted
AES with linear S-Box
does the cipher become entirely affine and hence trivially weak?
Yes; the AES sbox is the only source of nonlinearity (the ShiftRows and MixColumns are linear, and AddRoundKeys for a fixed key is ...
- 140k
Only top scored, non community-wiki answers of a minimum length are eligible