What does it mean : “Canonical representative of Sbox is 0123468A5BCF79DE”? and How can we calculate this...
$begingroup$
In paper :Cryptographic Analysis of All 4 × 4-Bit S-Boxes Saarinen has classified $4 times 4$ S-Boxes and defined Canonical representative for each class of S-Boxes.
- What does "Canonical representative of S-Box is 0123468A5BCF79DE" mean? And,
- How can I calculate it for an individual S-Box?
symmetric s-boxes differential-analysis linear-cryptanalysis
$endgroup$
add a comment |
$begingroup$
In paper :Cryptographic Analysis of All 4 × 4-Bit S-Boxes Saarinen has classified $4 times 4$ S-Boxes and defined Canonical representative for each class of S-Boxes.
- What does "Canonical representative of S-Box is 0123468A5BCF79DE" mean? And,
- How can I calculate it for an individual S-Box?
symmetric s-boxes differential-analysis linear-cryptanalysis
$endgroup$
add a comment |
$begingroup$
In paper :Cryptographic Analysis of All 4 × 4-Bit S-Boxes Saarinen has classified $4 times 4$ S-Boxes and defined Canonical representative for each class of S-Boxes.
- What does "Canonical representative of S-Box is 0123468A5BCF79DE" mean? And,
- How can I calculate it for an individual S-Box?
symmetric s-boxes differential-analysis linear-cryptanalysis
$endgroup$
In paper :Cryptographic Analysis of All 4 × 4-Bit S-Boxes Saarinen has classified $4 times 4$ S-Boxes and defined Canonical representative for each class of S-Boxes.
- What does "Canonical representative of S-Box is 0123468A5BCF79DE" mean? And,
- How can I calculate it for an individual S-Box?
symmetric s-boxes differential-analysis linear-cryptanalysis
symmetric s-boxes differential-analysis linear-cryptanalysis
edited 19 hours ago
kelalaka
8,74532351
8,74532351
asked 19 hours ago
Arsalan VahiArsalan Vahi
1067
1067
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Let's start with the basics: a bijective 4×4 bit S-box is a permutation of the set ${0,1}^4$ of 4-bit bitstrings. These bitstrings can be viewed as the binary representations of the integers from $0$ to $15$, which in turn are naturally represented by hexadecimal digits. Thus, we can also regard a 4×4 bit S-box as a permutation of the hexadecimal digits 0123456789ABCDEF
.
A common compact way of representing a permutation of a finite naturally ordered set (such as the hex digits listed above) is to list the results of applying the permutation to each element of the set in order. Thus, for example, the string 0123468A5BCF79DE
represents the permutation:
0123456789ABCDEF
↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓
0123468A5BCF79DE
(See e.g. this answer for examples.) While the article you've linked does not seem to actually define this notation, I'm all but certain that this is what they mean.
The story doesn't end here, though. The article you've linked does not discuss individual S-boxes, but equivalence classes of them. One type of equivalence is defined at the beginning of section 3 (formatting original, [editorial notes] mine):
Definition 5. Let $M_i$ and $M_o$ be two [4×4] invertible matrices and $c_i$ and $c_o$ two [4-element] vectors [over $mathbb F_2$]. The S-Box $S'$ defined by two affine transformations $$S'(x) = M_oS(M_i(x ⊕ c_i)) ⊕ c_o$$ belongs to the linear equivalence set of $S$; $S' ∈ mathrm{LE}(S)$.
Later, in definition 7, the author also defines a narrower notion of equivalence of S-boxes, called "permutation equivalence" (PE), which is the same as the linear equivalence defined above, except that the 4×4 binary matrices $M_i$ and $M_o$ are further required to be permutation matrices. (Note that these matrices represent permutations of the four bits in a 4-bit input/output bitstring, not permutations of the entire set of such 4-bit strings!)
The reason for considering these equivalence classes of S-boxes, instead of each S-box individually, is of course that any two S-boxes that only differ by a permutation of their input or output bits (and/or XORing those inputs and outputs with some constant bitstrings) have essentially the same cryptographic strength against attacks that don't care about such details, such as all those considered in the paper.
Anyway, to be able to usefully discuss these equivalence classes of S-boxes, we need to have some way to name them. One obvious way to do that, which the author of the paper indeed uses, is to somehow pick one specific "canonical" S-box out of each equivalence class to represent it. But which one? The author describes their choice in definition 6:
Definition 6. The canonical representative of an equivalence class [of S-boxes] is the member [whose compact representation as a list of hex digits] is first in lexicographic ordering.
For example, the S-boxes 0123468A5BCF79DE
and 5BCF79DE0123468A
are permutation equivalent as defined in the paper, since one can be obtained from the other by XORing the input with the 4-bit vector $1000$ (8
in hex) before applying the S-box. But the string 0123468A5BCF79DE
sorts before 5BCF79DE0123468A
in lexicographic order (since 0
< 5
), and indeed (assuming the author made no silly mistake) also before all other members of its equivalence class, making it the canonical representative of that class.
As for how to calculate the canonical representative of a particular equivalence class of S-boxes, given one member of the class, I believe the simplest (and possibly the only) way to do that is by brute force: just apply all possible input and output bit permutations (or invertible bit matrices, for linear equivalence) $M_i$ and $M_o$ and XOR masks $c_i$ and $c_o$ to the S-box to generate all members of the equivalence class, calculate the hex digit string representation of each of them, and find the one that comes first in lexicographic order.
$endgroup$
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "281"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcrypto.stackexchange.com%2fquestions%2f68584%2fwhat-does-it-mean-canonical-representative-of-sbox-is-0123468a5bcf79de-and%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Let's start with the basics: a bijective 4×4 bit S-box is a permutation of the set ${0,1}^4$ of 4-bit bitstrings. These bitstrings can be viewed as the binary representations of the integers from $0$ to $15$, which in turn are naturally represented by hexadecimal digits. Thus, we can also regard a 4×4 bit S-box as a permutation of the hexadecimal digits 0123456789ABCDEF
.
A common compact way of representing a permutation of a finite naturally ordered set (such as the hex digits listed above) is to list the results of applying the permutation to each element of the set in order. Thus, for example, the string 0123468A5BCF79DE
represents the permutation:
0123456789ABCDEF
↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓
0123468A5BCF79DE
(See e.g. this answer for examples.) While the article you've linked does not seem to actually define this notation, I'm all but certain that this is what they mean.
The story doesn't end here, though. The article you've linked does not discuss individual S-boxes, but equivalence classes of them. One type of equivalence is defined at the beginning of section 3 (formatting original, [editorial notes] mine):
Definition 5. Let $M_i$ and $M_o$ be two [4×4] invertible matrices and $c_i$ and $c_o$ two [4-element] vectors [over $mathbb F_2$]. The S-Box $S'$ defined by two affine transformations $$S'(x) = M_oS(M_i(x ⊕ c_i)) ⊕ c_o$$ belongs to the linear equivalence set of $S$; $S' ∈ mathrm{LE}(S)$.
Later, in definition 7, the author also defines a narrower notion of equivalence of S-boxes, called "permutation equivalence" (PE), which is the same as the linear equivalence defined above, except that the 4×4 binary matrices $M_i$ and $M_o$ are further required to be permutation matrices. (Note that these matrices represent permutations of the four bits in a 4-bit input/output bitstring, not permutations of the entire set of such 4-bit strings!)
The reason for considering these equivalence classes of S-boxes, instead of each S-box individually, is of course that any two S-boxes that only differ by a permutation of their input or output bits (and/or XORing those inputs and outputs with some constant bitstrings) have essentially the same cryptographic strength against attacks that don't care about such details, such as all those considered in the paper.
Anyway, to be able to usefully discuss these equivalence classes of S-boxes, we need to have some way to name them. One obvious way to do that, which the author of the paper indeed uses, is to somehow pick one specific "canonical" S-box out of each equivalence class to represent it. But which one? The author describes their choice in definition 6:
Definition 6. The canonical representative of an equivalence class [of S-boxes] is the member [whose compact representation as a list of hex digits] is first in lexicographic ordering.
For example, the S-boxes 0123468A5BCF79DE
and 5BCF79DE0123468A
are permutation equivalent as defined in the paper, since one can be obtained from the other by XORing the input with the 4-bit vector $1000$ (8
in hex) before applying the S-box. But the string 0123468A5BCF79DE
sorts before 5BCF79DE0123468A
in lexicographic order (since 0
< 5
), and indeed (assuming the author made no silly mistake) also before all other members of its equivalence class, making it the canonical representative of that class.
As for how to calculate the canonical representative of a particular equivalence class of S-boxes, given one member of the class, I believe the simplest (and possibly the only) way to do that is by brute force: just apply all possible input and output bit permutations (or invertible bit matrices, for linear equivalence) $M_i$ and $M_o$ and XOR masks $c_i$ and $c_o$ to the S-box to generate all members of the equivalence class, calculate the hex digit string representation of each of them, and find the one that comes first in lexicographic order.
$endgroup$
add a comment |
$begingroup$
Let's start with the basics: a bijective 4×4 bit S-box is a permutation of the set ${0,1}^4$ of 4-bit bitstrings. These bitstrings can be viewed as the binary representations of the integers from $0$ to $15$, which in turn are naturally represented by hexadecimal digits. Thus, we can also regard a 4×4 bit S-box as a permutation of the hexadecimal digits 0123456789ABCDEF
.
A common compact way of representing a permutation of a finite naturally ordered set (such as the hex digits listed above) is to list the results of applying the permutation to each element of the set in order. Thus, for example, the string 0123468A5BCF79DE
represents the permutation:
0123456789ABCDEF
↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓
0123468A5BCF79DE
(See e.g. this answer for examples.) While the article you've linked does not seem to actually define this notation, I'm all but certain that this is what they mean.
The story doesn't end here, though. The article you've linked does not discuss individual S-boxes, but equivalence classes of them. One type of equivalence is defined at the beginning of section 3 (formatting original, [editorial notes] mine):
Definition 5. Let $M_i$ and $M_o$ be two [4×4] invertible matrices and $c_i$ and $c_o$ two [4-element] vectors [over $mathbb F_2$]. The S-Box $S'$ defined by two affine transformations $$S'(x) = M_oS(M_i(x ⊕ c_i)) ⊕ c_o$$ belongs to the linear equivalence set of $S$; $S' ∈ mathrm{LE}(S)$.
Later, in definition 7, the author also defines a narrower notion of equivalence of S-boxes, called "permutation equivalence" (PE), which is the same as the linear equivalence defined above, except that the 4×4 binary matrices $M_i$ and $M_o$ are further required to be permutation matrices. (Note that these matrices represent permutations of the four bits in a 4-bit input/output bitstring, not permutations of the entire set of such 4-bit strings!)
The reason for considering these equivalence classes of S-boxes, instead of each S-box individually, is of course that any two S-boxes that only differ by a permutation of their input or output bits (and/or XORing those inputs and outputs with some constant bitstrings) have essentially the same cryptographic strength against attacks that don't care about such details, such as all those considered in the paper.
Anyway, to be able to usefully discuss these equivalence classes of S-boxes, we need to have some way to name them. One obvious way to do that, which the author of the paper indeed uses, is to somehow pick one specific "canonical" S-box out of each equivalence class to represent it. But which one? The author describes their choice in definition 6:
Definition 6. The canonical representative of an equivalence class [of S-boxes] is the member [whose compact representation as a list of hex digits] is first in lexicographic ordering.
For example, the S-boxes 0123468A5BCF79DE
and 5BCF79DE0123468A
are permutation equivalent as defined in the paper, since one can be obtained from the other by XORing the input with the 4-bit vector $1000$ (8
in hex) before applying the S-box. But the string 0123468A5BCF79DE
sorts before 5BCF79DE0123468A
in lexicographic order (since 0
< 5
), and indeed (assuming the author made no silly mistake) also before all other members of its equivalence class, making it the canonical representative of that class.
As for how to calculate the canonical representative of a particular equivalence class of S-boxes, given one member of the class, I believe the simplest (and possibly the only) way to do that is by brute force: just apply all possible input and output bit permutations (or invertible bit matrices, for linear equivalence) $M_i$ and $M_o$ and XOR masks $c_i$ and $c_o$ to the S-box to generate all members of the equivalence class, calculate the hex digit string representation of each of them, and find the one that comes first in lexicographic order.
$endgroup$
add a comment |
$begingroup$
Let's start with the basics: a bijective 4×4 bit S-box is a permutation of the set ${0,1}^4$ of 4-bit bitstrings. These bitstrings can be viewed as the binary representations of the integers from $0$ to $15$, which in turn are naturally represented by hexadecimal digits. Thus, we can also regard a 4×4 bit S-box as a permutation of the hexadecimal digits 0123456789ABCDEF
.
A common compact way of representing a permutation of a finite naturally ordered set (such as the hex digits listed above) is to list the results of applying the permutation to each element of the set in order. Thus, for example, the string 0123468A5BCF79DE
represents the permutation:
0123456789ABCDEF
↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓
0123468A5BCF79DE
(See e.g. this answer for examples.) While the article you've linked does not seem to actually define this notation, I'm all but certain that this is what they mean.
The story doesn't end here, though. The article you've linked does not discuss individual S-boxes, but equivalence classes of them. One type of equivalence is defined at the beginning of section 3 (formatting original, [editorial notes] mine):
Definition 5. Let $M_i$ and $M_o$ be two [4×4] invertible matrices and $c_i$ and $c_o$ two [4-element] vectors [over $mathbb F_2$]. The S-Box $S'$ defined by two affine transformations $$S'(x) = M_oS(M_i(x ⊕ c_i)) ⊕ c_o$$ belongs to the linear equivalence set of $S$; $S' ∈ mathrm{LE}(S)$.
Later, in definition 7, the author also defines a narrower notion of equivalence of S-boxes, called "permutation equivalence" (PE), which is the same as the linear equivalence defined above, except that the 4×4 binary matrices $M_i$ and $M_o$ are further required to be permutation matrices. (Note that these matrices represent permutations of the four bits in a 4-bit input/output bitstring, not permutations of the entire set of such 4-bit strings!)
The reason for considering these equivalence classes of S-boxes, instead of each S-box individually, is of course that any two S-boxes that only differ by a permutation of their input or output bits (and/or XORing those inputs and outputs with some constant bitstrings) have essentially the same cryptographic strength against attacks that don't care about such details, such as all those considered in the paper.
Anyway, to be able to usefully discuss these equivalence classes of S-boxes, we need to have some way to name them. One obvious way to do that, which the author of the paper indeed uses, is to somehow pick one specific "canonical" S-box out of each equivalence class to represent it. But which one? The author describes their choice in definition 6:
Definition 6. The canonical representative of an equivalence class [of S-boxes] is the member [whose compact representation as a list of hex digits] is first in lexicographic ordering.
For example, the S-boxes 0123468A5BCF79DE
and 5BCF79DE0123468A
are permutation equivalent as defined in the paper, since one can be obtained from the other by XORing the input with the 4-bit vector $1000$ (8
in hex) before applying the S-box. But the string 0123468A5BCF79DE
sorts before 5BCF79DE0123468A
in lexicographic order (since 0
< 5
), and indeed (assuming the author made no silly mistake) also before all other members of its equivalence class, making it the canonical representative of that class.
As for how to calculate the canonical representative of a particular equivalence class of S-boxes, given one member of the class, I believe the simplest (and possibly the only) way to do that is by brute force: just apply all possible input and output bit permutations (or invertible bit matrices, for linear equivalence) $M_i$ and $M_o$ and XOR masks $c_i$ and $c_o$ to the S-box to generate all members of the equivalence class, calculate the hex digit string representation of each of them, and find the one that comes first in lexicographic order.
$endgroup$
Let's start with the basics: a bijective 4×4 bit S-box is a permutation of the set ${0,1}^4$ of 4-bit bitstrings. These bitstrings can be viewed as the binary representations of the integers from $0$ to $15$, which in turn are naturally represented by hexadecimal digits. Thus, we can also regard a 4×4 bit S-box as a permutation of the hexadecimal digits 0123456789ABCDEF
.
A common compact way of representing a permutation of a finite naturally ordered set (such as the hex digits listed above) is to list the results of applying the permutation to each element of the set in order. Thus, for example, the string 0123468A5BCF79DE
represents the permutation:
0123456789ABCDEF
↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓
0123468A5BCF79DE
(See e.g. this answer for examples.) While the article you've linked does not seem to actually define this notation, I'm all but certain that this is what they mean.
The story doesn't end here, though. The article you've linked does not discuss individual S-boxes, but equivalence classes of them. One type of equivalence is defined at the beginning of section 3 (formatting original, [editorial notes] mine):
Definition 5. Let $M_i$ and $M_o$ be two [4×4] invertible matrices and $c_i$ and $c_o$ two [4-element] vectors [over $mathbb F_2$]. The S-Box $S'$ defined by two affine transformations $$S'(x) = M_oS(M_i(x ⊕ c_i)) ⊕ c_o$$ belongs to the linear equivalence set of $S$; $S' ∈ mathrm{LE}(S)$.
Later, in definition 7, the author also defines a narrower notion of equivalence of S-boxes, called "permutation equivalence" (PE), which is the same as the linear equivalence defined above, except that the 4×4 binary matrices $M_i$ and $M_o$ are further required to be permutation matrices. (Note that these matrices represent permutations of the four bits in a 4-bit input/output bitstring, not permutations of the entire set of such 4-bit strings!)
The reason for considering these equivalence classes of S-boxes, instead of each S-box individually, is of course that any two S-boxes that only differ by a permutation of their input or output bits (and/or XORing those inputs and outputs with some constant bitstrings) have essentially the same cryptographic strength against attacks that don't care about such details, such as all those considered in the paper.
Anyway, to be able to usefully discuss these equivalence classes of S-boxes, we need to have some way to name them. One obvious way to do that, which the author of the paper indeed uses, is to somehow pick one specific "canonical" S-box out of each equivalence class to represent it. But which one? The author describes their choice in definition 6:
Definition 6. The canonical representative of an equivalence class [of S-boxes] is the member [whose compact representation as a list of hex digits] is first in lexicographic ordering.
For example, the S-boxes 0123468A5BCF79DE
and 5BCF79DE0123468A
are permutation equivalent as defined in the paper, since one can be obtained from the other by XORing the input with the 4-bit vector $1000$ (8
in hex) before applying the S-box. But the string 0123468A5BCF79DE
sorts before 5BCF79DE0123468A
in lexicographic order (since 0
< 5
), and indeed (assuming the author made no silly mistake) also before all other members of its equivalence class, making it the canonical representative of that class.
As for how to calculate the canonical representative of a particular equivalence class of S-boxes, given one member of the class, I believe the simplest (and possibly the only) way to do that is by brute force: just apply all possible input and output bit permutations (or invertible bit matrices, for linear equivalence) $M_i$ and $M_o$ and XOR masks $c_i$ and $c_o$ to the S-box to generate all members of the equivalence class, calculate the hex digit string representation of each of them, and find the one that comes first in lexicographic order.
answered 17 hours ago
Ilmari KaronenIlmari Karonen
35.7k373138
35.7k373138
add a comment |
add a comment |
Thanks for contributing an answer to Cryptography Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcrypto.stackexchange.com%2fquestions%2f68584%2fwhat-does-it-mean-canonical-representative-of-sbox-is-0123468a5bcf79de-and%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown