Questions tagged [s-boxes]
(or substitution boxes), components in many block ciphers used to substitute parts of the data in a non-linear way. While often fixed by the algorithm (like in DES and AES), sometimes they are key-dependent (like in Blowfish).
55
questions
23
votes
5
answers
9k
views
Desirable S-box properties
What desirable properties should an S-box have?
My current standard selection process is to just pick them at random and verify that they fit the following criteria:
The probability that any random ...
- 3,527
7
votes
3
answers
3k
views
Why don't table lookups run in constant time?
The Wikipedia article on big O notation says that performing a lookup is a constant time operation. So why are lookup tables susceptible to timing attacks?
- 3,655
17
votes
1
answer
48k
views
How are the AES S-Boxes calculated?
I'm trying to understand how the AES S-Boxes are calculated. I understand how the multiplicative inverse is calculated over $GF(2^8)$, but I'm confused by the description of the affine transformation. ...
- 413
15
votes
4
answers
3k
views
Generate ANF from SBox
Given an SBox, how can I generate its component equations (in ANF)?
For example, let's say I have this SBox:
6, 4, 7, 8, 0, 5, 2, 10, 14, 3, 13, 1, 12, 15, 9, 11
Then, the equations are:
$y_0 = x_1 ...
- 603
33
votes
2
answers
12k
views
Reason why “XOR” is a linear operation, but ordinary “addition” isn’t?
I'm new in cryptography and try to read some articles in this field.
Many of these articles talk about non-linear S-boxes, and nothing more on what they mean by their non-linearity.
I have a simple ...
- 495
21
votes
3
answers
2k
views
Choice of multiplication polynomial in Rijndael s-box affine mapping
The Rijndael specification details the design choices for the s-box in section 7.2. They describe the choice of affine mapping as follows:
We have chosen an affine mapping that has a very simple ...
- 13.1k
28
votes
2
answers
11k
views
How were the DES S-box values determined?
It seems like the S-boxes in DES have essentially random values.
How were these chosen?
- 3,236
17
votes
1
answer
5k
views
S-box design criteria and random sboxes
What are the disadvantages of using random s-boxes?
In AES, the s-boxes had to obey certain mathematical rules, which? And why?
What security does using hidden s-boxes (GOST) or generating them from ...
- 193
16
votes
1
answer
2k
views
Replacing the Rijndael S-Box?
The Rijndael S-Box design generates a permutation cycle of type $2+27+59+81+87$. What effect would replacing that permutation with a cycle of type $256$ have on the security of AES?
- 525
6
votes
1
answer
5k
views
How can I calculate the Rijndael SBox?
I would like to implement the Rijndael subBytes() operation using calculation instead of tables, because I like to play with this on different wordsizes, as an ...
- 737
26
votes
3
answers
11k
views
Why do block ciphers need a non-linear component (like an S-box)?
Why is there a requirement of "Non-Linear functions" as a component of many popular block ciphers (e.g. the S-box in DES or 3DES)?
How does it make the cipher more secure?
The only intuition I have ...
- 443
9
votes
2
answers
8k
views
How to build a difference distribution table?
i am studying about differential cryptanalysis, and found one metric to measure the resistance of a sbox to it, but to use it, it is necessary to build a difference distribution table, like the one in ...
- 281
8
votes
1
answer
1k
views
How does one practically calculate the non-linearity of a multi-output boolean function like the AES s-box?
I am working on multi-output boolean function i.e. a function that takes an $n$-bit input and gives an $m$-bit output for all possible inputs (i.e. $2^n$ inputs).
To be more exact: I am trying to do ...
- 284
7
votes
1
answer
1k
views
How constant value 0x63 in affine transformation is chosen or generated while AES Substitution Box is formed?
Me and one of my friends are working on AES algorithm. We have understood how multiplicative inverse table is generated. Rijndael AES algorithm shows us how S-Box is generated through the affine ...
- 151
3
votes
2
answers
2k
views
Polynomial representation of the affine part of the AES S-box
I have been reading up on the polynomial representation of the AES Sbox (PDF: “Essential Algebraic Structure Within the AES” by Murphy and Robshaw) and I can't get it to produce the correct output.
...
- 353
2
votes
1
answer
1k
views
How can one construct the weakest S-box ever?
Is it possible to come up with an NxN S-box which would have a difference distribution table with N entries of 100% probability?
I am studying the properties of S-boxes and I don't quite understand ...
- 81
11
votes
2
answers
1k
views
Evaluating Algebraic Complexity of a S-box
While studying the design and the desirable properties of an AES S-box , I came to know that Algebraic Complexity is also an important property of an S-box which is usually considered while evaluating ...
- 111
7
votes
1
answer
719
views
Increases in the AES S-box
AES uses one S-box to substitute all 16 bytes in one round. Will using 16 different S-boxes (with cryptographic properties similar to the AES S-box (i.e., non-linearity of 112, differential ...
- 2,427
7
votes
1
answer
2k
views
Is it necessary for the Rijndael polynomial to be primitive?
I am working on selecting a S-box for my Cipher (Similar to AES). I found out there are 30 irreducible polynomials and over 16 primitive polynomials of degree 8. Is it necessary to choose a primitive ...
user38956
6
votes
2
answers
1k
views
Security of the AES with a Secret S-box
In this paper they change the $AES$ S-box to a uniformly random one and answer the questions:
How does the security of AES change when the S-box is changed by a secret S-box?
Would it be safe to ...
- 1,025
6
votes
1
answer
49k
views
How does DES decryption work? Is it the same as encryption or the reverse? [duplicate]
If DES decryption is the same as encryption done in reverse order, then how can the reversed S-Box convert 4 bits into 6 bits?
- 711
6
votes
2
answers
1k
views
Number of Sbox in a Cipher
Camellia has 4 SBOX and so does the TwoFish(key dependent 4 Sboxes). Where as AES uses only one. Would it have made AES more secure if AES had 4 or more SBOX too? Does using more Sbox with similar ...
- 2,427
5
votes
1
answer
3k
views
AES s-box – How do I calculate the inverse of this field equation?
I want to implement AES algorithm,instead of LUT based S-box, but I’m stuck at point creating "Inverse of equation" during implementation.
In creation of S-box I am using the following steps:
($...
- 153
4
votes
1
answer
8k
views
How are the AES inverse S-Boxes calculated?
I would like to know, how to calculate the inverse S-box.
I followed this
link (with affine transformation first, then multiplicative inverse), but the result is wrong. For example, if I use the value ...
- 147
4
votes
1
answer
2k
views
How to calculate inverse affine transform in AES from forward affine transform?
In AES the forward affine tranformation matrix is defined as:
$$
\begin{bmatrix}
1& 0& 0& 0& 1& 1& 1& 1 \\
1& 1& 0& 0& 0& 1& 1& 1 \\
1& 1&...
- 41
3
votes
1
answer
808
views
Linear Approximation and Linear Probability of Camellia Sbox
In this article,Analysis of Camellia (para 2. Differential and linear cryptanalysis, page 3), it says
The maximum bias of a linear approximation through one S-box is $2^{-4}$
, which gives a ...
- 2,427
3
votes
2
answers
2k
views
AES: How to create the S-box with Sage
The $Sage$ code for the AES $S-box$ is below and a link is here: Polynomial representation of the affine part of the AES S-box. An online version of $Sage$ to test this is here.
I understand most of ...
- 1,025
3
votes
1
answer
450
views
Why Camellia has 4 Sbox
I asked a question about using 16 different Sboxes in AES each for one state byte instead of using same One Sbox for substituting 16 state bytes (See the Question Increase in AES SBox). The answers i ...
- 2,427
3
votes
1
answer
522
views
AES-CTR security if S-boxes substituion is omitted?
I understand why s-boxes are needed in general especially when ECB mode is used(because of using the same key for encryption of other blocks)but I wonder if it's ...
- 403
1
vote
1
answer
874
views
How does this code calculating AES S-Box work?
How does this code calculating the AES S-Box work? I don't understand the overall calculation procedure. Code is attached below:
...
- 13
0
votes
1
answer
2k
views
S-Box and it's linearity
I am trying to figure out why it is necessary S-box's to be nonlinear. I have been searching for some materials but was not able to find out clear proof why it means that if we use S-box in DES, it ...
- 23
20
votes
2
answers
5k
views
S-box basic question
I'm trying to understand DES and a bunch of other cryptographic systems using S-Boxes.
I have now a quite basic question about how Sboxes work in general. For DES, Sboxes are substituting a 6-bits ...
- 201
15
votes
3
answers
5k
views
Security of simple xor and s-box cipher?
What weaknesses (or strengths) do block ciphers based on only key xor and s-box have when operating in CBC mode?
A cipher's internal primitive might be a simple as this:
$C = S[M \oplus k]$, where $...
- 3,527
11
votes
2
answers
9k
views
How can an S-Box be reversed?
So, as an exercise to greater understand some things about cryptography, I decided to try and implement GOST 28147-89, which uses eight 4x4 S-Boxes. I can grasp the concept of putting 4 bits through ...
- 213
9
votes
2
answers
415
views
How to implement arbitrary s-box in a side-channel-free way in C?
This could be a question for CodeReview.SE, but I thought it might require non-trivial cryptographic knowledge to merit it on-topic here.
The C language is chosen as it's a common language for ...
- 9,217
7
votes
2
answers
4k
views
Why is the DES s-box non-linear? Why does it make the cracking of the cipher more difficult?
I know that if we have a cipher that makes only linear transformations (let's say a bunch of $XOR$s), we break it simply by writing a system of equations with $\oplus$ operation starting from the ...
- 357
7
votes
2
answers
961
views
S-box with differential uniformity = 2
I read that we do not know if there exists an 8x8 sbox with differential uniformity = 2.
I suppose we cannot compute every possible sbox because there are $64!$ possible s-boxes. Am I right?
- 324
6
votes
1
answer
444
views
Rijndael S-boxes: Where do the $\mu$ and $\nu$ polynomial ring elements come from?
I've asked some other questions before about Rijndael's S-boxes, and step by step I'm coming to an understanding; but those steps often guide me to new questions.
I did some lines of code to ...
- 737
6
votes
1
answer
340
views
Does a masked look-up table prevent cache timing attacks?
When applying the boolean masking countermeasure to a cipher which uses an S-box $S$, a way to handle this nonlinear operation is to recompute a new S-box $S'$ such that $S'(x \oplus r_{in}) = S(x) \...
- 2,836
6
votes
1
answer
661
views
S-box Cryptanalytic Resistance
In DES, different S-boxes were tested for cryptanalytic resistance and the most secure one was chosen for the algorithm itself.
How do different S-boxes offer different levels of security against ...
- 63
5
votes
3
answers
2k
views
AES column mixing and S-Box confusion
I am trying to understand the AES encryption algorithm. I know that we process 128 bits at a time for a 128 bit key in a 4x4 octet form, but am confused by the following:
How does the substitution ...
- 53
4
votes
3
answers
1k
views
Calculate the Number of active s boxes
I really want to learn how to calculate the number of active s _boxes for block cipher cryptographic algorithms.
I want to do that manually after running each round of an algorithm such as LED ...
- 101
4
votes
1
answer
384
views
Last Sbox of a block cipher for Linear Cryptanalysis
I figured I should try to learn about linear cryptanalysis with a super simple cipher with only one Sbox. The problem is that with that approach the last subkey bits seem to be involved in the linear ...
- 1,535
3
votes
1
answer
2k
views
How do the Serpent S-boxes work?
Warning: The link in the answer explain the S-Box well, but there is an error in the pseudocode.
$K_i = K_{i-8} \oplus K_{i-5} \oplus K_{i-3} \oplus K_{i-1} \oplus 0x9e3779b9 \oplus i$;
Instead, it ...
- 163
3
votes
2
answers
705
views
Math to replace s-boxes - Good or bad idea?
The following was going through my brain for the past week. If my thoughts are generally known to the cryptographic community would someone provide a link or two. Even if I’m making a classic newbie ...
- 59
2
votes
2
answers
369
views
What rule(s) for a good S-box is this one violating and how does it relate to non-linearity etc.?
I generated this single-cycle substitution box and I want to post it as an example for understanding what a good S-box would be like. I get the feeling that this particular one is weak. Here it is (...
- 3,655
2
votes
2
answers
1k
views
BOOLEAN FUNCTIONS: generate a function $f: \{0, 1\}^n \rightarrow \{0, 1\}$ from a $n \times n$ S-Box
I want to calculate the hamming weight of a S-Box using this formula:
$\text{hw}(f) = \sum_{x=0}^{2^n-1} f(x)$.
Where $f: \{0, 1\}^n \rightarrow \{0, 1\}$
My problem is that I don't know how to get ...
- 23
2
votes
3
answers
1k
views
What is the time complexity of the basic components of a symmetric cipher?
I have a very basic knowledge on time complexity and even less on programming, so please bear with me. I am interested to know the time complexity in big-O notation of some of the basic operations in ...
- 1,025
1
vote
0
answers
959
views
how to compute Bit Independent Criteria on a 4-bit S-box?
The idea of Bit Independence Criterion (BIC ) was introduced by Webster and Tavares . For a given set of avalanche vectors generated by complementing a single plaintext bit, all avalanche variables ...
- 75
1
vote
1
answer
1k
views
how to compute the correlation between two binary vectors?
We find different equations to compute the correlation or correlation coefficient:
$\begin{align*}
corr &= \frac{a+d}{a+b+c+d}\\
&= \frac{(a+d) - (b+d)}{a+b+c+d}\\
&= \frac{(a+...
- 75