Hot answers tagged

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 ...
kodlu's user avatar
  • 21.9k
13 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&...
pico's user avatar
  • 158
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 ...
poncho's user avatar
  • 146k
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 ...
Thomas Pornin's user avatar
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 ...
Paul Uszak's user avatar
  • 15.3k
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),$$ ...
Aleph's user avatar
  • 1,856
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 ...
J.D.'s user avatar
  • 4,415
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 ...
Elias's user avatar
  • 4,903
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 ...
poncho's user avatar
  • 146k
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 ...
itsme's user avatar
  • 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 $...
Daniel S's user avatar
  • 22.8k
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.
Meir Maor's user avatar
  • 11.8k
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 ...
Richie Frame's user avatar
  • 13.1k
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 ...
forest's user avatar
  • 15.2k
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 ...
meshcollider's user avatar
  • 1,573
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 ...
picarresursix's user avatar
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) ...
fgrieu's user avatar
  • 140k
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 ...
crypt's user avatar
  • 2,397
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 ‘...
Ilmari Karonen's user avatar
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 ...
poncho's user avatar
  • 146k
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 ...
Ella Rose's user avatar
  • 19.6k
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 ...
b degnan's user avatar
  • 4,722
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 ...
Richie Frame's user avatar
  • 13.1k
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 ...
Fraktal's user avatar
  • 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 \...
FreeDisciplina's user avatar
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$ ...
poncho's user avatar
  • 146k
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 ...
kodlu's user avatar
  • 21.9k
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 ...
poncho's user avatar
  • 146k
6 votes

What's happens if we use the weakest S-BOX for AES?

See: How can one construct the weakest S-box ever? and How do I choose the best 3*3 s-boxes? I believe that user Hend's question is not "how to design the worst possible S-box" but about "having ...
Rob's user avatar
  • 280
6 votes
Accepted

$\alpha^{2^{m} + 1}$ is a generator of $\operatorname{GF}(2^m)$?

Since you haven't heard of splitting fields, here is an argument based on more elementary group theory. Let $G$ denote a cyclic group. Then, it is easy to show (or you might already know it) that if $...
Dilip Sarwate's user avatar

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