What does it mean : “Canonical representative of Sbox is 0123468A5BCF79DE”? and How can we calculate this...












2












$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?










share|improve this question











$endgroup$

















    2












    $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?










    share|improve this question











    $endgroup$















      2












      2








      2





      $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?










      share|improve this question











      $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






      share|improve this question















      share|improve this question













      share|improve this question




      share|improve this question








      edited 4 hours ago









      kelalaka

      8,70522351




      8,70522351










      asked 4 hours ago









      Arsalan VahiArsalan Vahi

      917




      917






















          1 Answer
          1






          active

          oldest

          votes


















          1












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






          share|improve this answer









          $endgroup$














            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
            });


            }
            });














            draft saved

            draft discarded


















            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









            1












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






            share|improve this answer









            $endgroup$


















              1












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






              share|improve this answer









              $endgroup$
















                1












                1








                1





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






                share|improve this answer









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







                share|improve this answer












                share|improve this answer



                share|improve this answer










                answered 2 hours ago









                Ilmari KaronenIlmari Karonen

                35.7k373138




                35.7k373138






























                    draft saved

                    draft discarded




















































                    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.




                    draft saved


                    draft discarded














                    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





















































                    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







                    Popular posts from this blog

                    الفوسفات في المغرب

                    Four equal circles intersect: What is the area of the small shaded portion and its height

                    جامعة ليفربول