Searching for a differential characteristic (differential cryptanalysis)












1












$begingroup$


Currently I am doing some research on differential cryptanalysis. In general I got a good idea about the attack and how it is done.



I am currently talking about ciphers with multiple rounds. It seems that the success of a attack is depending on a good differential characteristic through the cipher. There are way which have good statistical values and some more which have not. In the paper there is often a good differential characteristic shown which works very well. But there is never a talk about how to find them. For sure I read about some heuristics like "look for differential characteristics with small amount of active sboxes" or something like that.



So my Question: How can I find a good differential or lets say, all? I am looking for a algorithm or a good description which I could implement on my own.










share|improve this question











$endgroup$








  • 1




    $begingroup$
    this might help you : cs.bc.edu/~straubin/crypto2017/heys.pdf
    $endgroup$
    – hardyrama
    8 hours ago
















1












$begingroup$


Currently I am doing some research on differential cryptanalysis. In general I got a good idea about the attack and how it is done.



I am currently talking about ciphers with multiple rounds. It seems that the success of a attack is depending on a good differential characteristic through the cipher. There are way which have good statistical values and some more which have not. In the paper there is often a good differential characteristic shown which works very well. But there is never a talk about how to find them. For sure I read about some heuristics like "look for differential characteristics with small amount of active sboxes" or something like that.



So my Question: How can I find a good differential or lets say, all? I am looking for a algorithm or a good description which I could implement on my own.










share|improve this question











$endgroup$








  • 1




    $begingroup$
    this might help you : cs.bc.edu/~straubin/crypto2017/heys.pdf
    $endgroup$
    – hardyrama
    8 hours ago














1












1








1





$begingroup$


Currently I am doing some research on differential cryptanalysis. In general I got a good idea about the attack and how it is done.



I am currently talking about ciphers with multiple rounds. It seems that the success of a attack is depending on a good differential characteristic through the cipher. There are way which have good statistical values and some more which have not. In the paper there is often a good differential characteristic shown which works very well. But there is never a talk about how to find them. For sure I read about some heuristics like "look for differential characteristics with small amount of active sboxes" or something like that.



So my Question: How can I find a good differential or lets say, all? I am looking for a algorithm or a good description which I could implement on my own.










share|improve this question











$endgroup$




Currently I am doing some research on differential cryptanalysis. In general I got a good idea about the attack and how it is done.



I am currently talking about ciphers with multiple rounds. It seems that the success of a attack is depending on a good differential characteristic through the cipher. There are way which have good statistical values and some more which have not. In the paper there is often a good differential characteristic shown which works very well. But there is never a talk about how to find them. For sure I read about some heuristics like "look for differential characteristics with small amount of active sboxes" or something like that.



So my Question: How can I find a good differential or lets say, all? I am looking for a algorithm or a good description which I could implement on my own.







cryptanalysis differential-analysis






share|improve this question















share|improve this question













share|improve this question




share|improve this question








edited 3 hours ago









hardyrama

8991527




8991527










asked 8 hours ago









chris000rchris000r

13016




13016








  • 1




    $begingroup$
    this might help you : cs.bc.edu/~straubin/crypto2017/heys.pdf
    $endgroup$
    – hardyrama
    8 hours ago














  • 1




    $begingroup$
    this might help you : cs.bc.edu/~straubin/crypto2017/heys.pdf
    $endgroup$
    – hardyrama
    8 hours ago








1




1




$begingroup$
this might help you : cs.bc.edu/~straubin/crypto2017/heys.pdf
$endgroup$
– hardyrama
8 hours ago




$begingroup$
this might help you : cs.bc.edu/~straubin/crypto2017/heys.pdf
$endgroup$
– hardyrama
8 hours ago










2 Answers
2






active

oldest

votes


















2












$begingroup$

Finding differential characteristic means analyzing the structure of the given cipher(substitution and permutation elements). This analyzing means, we should track the input differentials(Δi) through the different elements of the cipher and produce related output differential(Δo).



Δx = X' xor X'' =>



                Δx=[ΔX1,ΔX2,ΔX3,....ΔXn]

=[X'1 xor X''1, X'2 xor X''2, X'3 xor X''3,...,X'n xor X''n]


We repeat this to round - 1. Each of these paths are called "Differential characteristic" and each of them has its own happening chance(probability).



As mentioned, in the paces of tracking Δi to Δo, we should consider that cipher structure is made of different confusion and diffusion elements which these elements effect the path in each round and leads to activating some SBoxes(called Active SBoxes). But the most important factor is finding the probability of each differential path(differential characteristic) and choosing the highest one(or ones) among them. The rout with the highest probability is the objection of the analyzer.



In order to find these differential characteristics we can use one of these three methods( It is general recommendation but not exact!!!):




  • choose each differential characteristic in the cipher structure visually and calculate probability for them. However we should mention that this method is not applicable for the most variety of ciphers in that the number of input to the cipher is big( at least 16 bit) and if we want to have a precise estimation of differential status of the cipher,nearly we should test 2^16 input differentials and calculate the probability for each round. In the most situations this way is impossible.



  • ** Use Sage S-box MILP toolkit ** which is developed and intended to calculate the differential characteristics for well-known block ciphers which have Substitution and permutation structure in them. This toolkit can be found in: http://www.swmath.org/?term=differential%20cryptanalysis and in this paper: https://www.esat.kuleuven.be/cosic/publications/article-2080.pdf the way of using them is explained.(I should remark that in the given toolkit, you should make some modifications in order to use them like changing the "coin solver"). This method is a very good way to finding the number of active SBoxes and calculating the differential characteristic of the cipher.



    -Implementation on our own code in order to find the differential characteristics with the highest probability among all input differentials. It is not hard and possible. We firstly should define all input differentials (states) and then calculate the probability of each state by considering these two factors:



              -Each SBox has differential property and should  affect in 
    each round in the differential characteristic when it is
    activated.

    -Multiply calculated probabilities by the prior probability in
    order to finding rounds differential characteristics.


    A good reference: https://www.engr.mun.ca/~howard/PAPERS/ldc_tutorial.pdf






But I should mention that finding differential characteristic for Feistel structures have a different story and a good reference is in:
http://www.cs.haifa.ac.il/~orrd/BlockCipherSeminar/Lecture2-Differential.pdf






share|improve this answer











$endgroup$





















    1












    $begingroup$

    The details depend on the exact cipher design. However what you need to optimize (maximize) is the probability
    $$
    prod_{S_i ~mathrm{active~in~differential~trail}}
    P(Delta_{in},Delta_{out},S_i),
    $$

    where the deltas are the input and output differences to Sbox $S_i,$ and the differential trail is usually chosen to cover $r-1$ rounds for an $r$ round cipher.



    In the case of SPN networks with wire crossing permutation layer, as in the Heys tutorial in the comment, you should look for an output differential with low Hamming weight to minimize the number of active Sboxes in the next round.






    share|improve this answer









    $endgroup$














      Your Answer








      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%2f68755%2fsearching-for-a-differential-characteristic-differential-cryptanalysis%23new-answer', 'question_page');
      }
      );

      Post as a guest















      Required, but never shown

























      2 Answers
      2






      active

      oldest

      votes








      2 Answers
      2






      active

      oldest

      votes









      active

      oldest

      votes






      active

      oldest

      votes









      2












      $begingroup$

      Finding differential characteristic means analyzing the structure of the given cipher(substitution and permutation elements). This analyzing means, we should track the input differentials(Δi) through the different elements of the cipher and produce related output differential(Δo).



      Δx = X' xor X'' =>



                      Δx=[ΔX1,ΔX2,ΔX3,....ΔXn]

      =[X'1 xor X''1, X'2 xor X''2, X'3 xor X''3,...,X'n xor X''n]


      We repeat this to round - 1. Each of these paths are called "Differential characteristic" and each of them has its own happening chance(probability).



      As mentioned, in the paces of tracking Δi to Δo, we should consider that cipher structure is made of different confusion and diffusion elements which these elements effect the path in each round and leads to activating some SBoxes(called Active SBoxes). But the most important factor is finding the probability of each differential path(differential characteristic) and choosing the highest one(or ones) among them. The rout with the highest probability is the objection of the analyzer.



      In order to find these differential characteristics we can use one of these three methods( It is general recommendation but not exact!!!):




      • choose each differential characteristic in the cipher structure visually and calculate probability for them. However we should mention that this method is not applicable for the most variety of ciphers in that the number of input to the cipher is big( at least 16 bit) and if we want to have a precise estimation of differential status of the cipher,nearly we should test 2^16 input differentials and calculate the probability for each round. In the most situations this way is impossible.



      • ** Use Sage S-box MILP toolkit ** which is developed and intended to calculate the differential characteristics for well-known block ciphers which have Substitution and permutation structure in them. This toolkit can be found in: http://www.swmath.org/?term=differential%20cryptanalysis and in this paper: https://www.esat.kuleuven.be/cosic/publications/article-2080.pdf the way of using them is explained.(I should remark that in the given toolkit, you should make some modifications in order to use them like changing the "coin solver"). This method is a very good way to finding the number of active SBoxes and calculating the differential characteristic of the cipher.



        -Implementation on our own code in order to find the differential characteristics with the highest probability among all input differentials. It is not hard and possible. We firstly should define all input differentials (states) and then calculate the probability of each state by considering these two factors:



                  -Each SBox has differential property and should  affect in 
        each round in the differential characteristic when it is
        activated.

        -Multiply calculated probabilities by the prior probability in
        order to finding rounds differential characteristics.


        A good reference: https://www.engr.mun.ca/~howard/PAPERS/ldc_tutorial.pdf






      But I should mention that finding differential characteristic for Feistel structures have a different story and a good reference is in:
      http://www.cs.haifa.ac.il/~orrd/BlockCipherSeminar/Lecture2-Differential.pdf






      share|improve this answer











      $endgroup$


















        2












        $begingroup$

        Finding differential characteristic means analyzing the structure of the given cipher(substitution and permutation elements). This analyzing means, we should track the input differentials(Δi) through the different elements of the cipher and produce related output differential(Δo).



        Δx = X' xor X'' =>



                        Δx=[ΔX1,ΔX2,ΔX3,....ΔXn]

        =[X'1 xor X''1, X'2 xor X''2, X'3 xor X''3,...,X'n xor X''n]


        We repeat this to round - 1. Each of these paths are called "Differential characteristic" and each of them has its own happening chance(probability).



        As mentioned, in the paces of tracking Δi to Δo, we should consider that cipher structure is made of different confusion and diffusion elements which these elements effect the path in each round and leads to activating some SBoxes(called Active SBoxes). But the most important factor is finding the probability of each differential path(differential characteristic) and choosing the highest one(or ones) among them. The rout with the highest probability is the objection of the analyzer.



        In order to find these differential characteristics we can use one of these three methods( It is general recommendation but not exact!!!):




        • choose each differential characteristic in the cipher structure visually and calculate probability for them. However we should mention that this method is not applicable for the most variety of ciphers in that the number of input to the cipher is big( at least 16 bit) and if we want to have a precise estimation of differential status of the cipher,nearly we should test 2^16 input differentials and calculate the probability for each round. In the most situations this way is impossible.



        • ** Use Sage S-box MILP toolkit ** which is developed and intended to calculate the differential characteristics for well-known block ciphers which have Substitution and permutation structure in them. This toolkit can be found in: http://www.swmath.org/?term=differential%20cryptanalysis and in this paper: https://www.esat.kuleuven.be/cosic/publications/article-2080.pdf the way of using them is explained.(I should remark that in the given toolkit, you should make some modifications in order to use them like changing the "coin solver"). This method is a very good way to finding the number of active SBoxes and calculating the differential characteristic of the cipher.



          -Implementation on our own code in order to find the differential characteristics with the highest probability among all input differentials. It is not hard and possible. We firstly should define all input differentials (states) and then calculate the probability of each state by considering these two factors:



                    -Each SBox has differential property and should  affect in 
          each round in the differential characteristic when it is
          activated.

          -Multiply calculated probabilities by the prior probability in
          order to finding rounds differential characteristics.


          A good reference: https://www.engr.mun.ca/~howard/PAPERS/ldc_tutorial.pdf






        But I should mention that finding differential characteristic for Feistel structures have a different story and a good reference is in:
        http://www.cs.haifa.ac.il/~orrd/BlockCipherSeminar/Lecture2-Differential.pdf






        share|improve this answer











        $endgroup$
















          2












          2








          2





          $begingroup$

          Finding differential characteristic means analyzing the structure of the given cipher(substitution and permutation elements). This analyzing means, we should track the input differentials(Δi) through the different elements of the cipher and produce related output differential(Δo).



          Δx = X' xor X'' =>



                          Δx=[ΔX1,ΔX2,ΔX3,....ΔXn]

          =[X'1 xor X''1, X'2 xor X''2, X'3 xor X''3,...,X'n xor X''n]


          We repeat this to round - 1. Each of these paths are called "Differential characteristic" and each of them has its own happening chance(probability).



          As mentioned, in the paces of tracking Δi to Δo, we should consider that cipher structure is made of different confusion and diffusion elements which these elements effect the path in each round and leads to activating some SBoxes(called Active SBoxes). But the most important factor is finding the probability of each differential path(differential characteristic) and choosing the highest one(or ones) among them. The rout with the highest probability is the objection of the analyzer.



          In order to find these differential characteristics we can use one of these three methods( It is general recommendation but not exact!!!):




          • choose each differential characteristic in the cipher structure visually and calculate probability for them. However we should mention that this method is not applicable for the most variety of ciphers in that the number of input to the cipher is big( at least 16 bit) and if we want to have a precise estimation of differential status of the cipher,nearly we should test 2^16 input differentials and calculate the probability for each round. In the most situations this way is impossible.



          • ** Use Sage S-box MILP toolkit ** which is developed and intended to calculate the differential characteristics for well-known block ciphers which have Substitution and permutation structure in them. This toolkit can be found in: http://www.swmath.org/?term=differential%20cryptanalysis and in this paper: https://www.esat.kuleuven.be/cosic/publications/article-2080.pdf the way of using them is explained.(I should remark that in the given toolkit, you should make some modifications in order to use them like changing the "coin solver"). This method is a very good way to finding the number of active SBoxes and calculating the differential characteristic of the cipher.



            -Implementation on our own code in order to find the differential characteristics with the highest probability among all input differentials. It is not hard and possible. We firstly should define all input differentials (states) and then calculate the probability of each state by considering these two factors:



                      -Each SBox has differential property and should  affect in 
            each round in the differential characteristic when it is
            activated.

            -Multiply calculated probabilities by the prior probability in
            order to finding rounds differential characteristics.


            A good reference: https://www.engr.mun.ca/~howard/PAPERS/ldc_tutorial.pdf






          But I should mention that finding differential characteristic for Feistel structures have a different story and a good reference is in:
          http://www.cs.haifa.ac.il/~orrd/BlockCipherSeminar/Lecture2-Differential.pdf






          share|improve this answer











          $endgroup$



          Finding differential characteristic means analyzing the structure of the given cipher(substitution and permutation elements). This analyzing means, we should track the input differentials(Δi) through the different elements of the cipher and produce related output differential(Δo).



          Δx = X' xor X'' =>



                          Δx=[ΔX1,ΔX2,ΔX3,....ΔXn]

          =[X'1 xor X''1, X'2 xor X''2, X'3 xor X''3,...,X'n xor X''n]


          We repeat this to round - 1. Each of these paths are called "Differential characteristic" and each of them has its own happening chance(probability).



          As mentioned, in the paces of tracking Δi to Δo, we should consider that cipher structure is made of different confusion and diffusion elements which these elements effect the path in each round and leads to activating some SBoxes(called Active SBoxes). But the most important factor is finding the probability of each differential path(differential characteristic) and choosing the highest one(or ones) among them. The rout with the highest probability is the objection of the analyzer.



          In order to find these differential characteristics we can use one of these three methods( It is general recommendation but not exact!!!):




          • choose each differential characteristic in the cipher structure visually and calculate probability for them. However we should mention that this method is not applicable for the most variety of ciphers in that the number of input to the cipher is big( at least 16 bit) and if we want to have a precise estimation of differential status of the cipher,nearly we should test 2^16 input differentials and calculate the probability for each round. In the most situations this way is impossible.



          • ** Use Sage S-box MILP toolkit ** which is developed and intended to calculate the differential characteristics for well-known block ciphers which have Substitution and permutation structure in them. This toolkit can be found in: http://www.swmath.org/?term=differential%20cryptanalysis and in this paper: https://www.esat.kuleuven.be/cosic/publications/article-2080.pdf the way of using them is explained.(I should remark that in the given toolkit, you should make some modifications in order to use them like changing the "coin solver"). This method is a very good way to finding the number of active SBoxes and calculating the differential characteristic of the cipher.



            -Implementation on our own code in order to find the differential characteristics with the highest probability among all input differentials. It is not hard and possible. We firstly should define all input differentials (states) and then calculate the probability of each state by considering these two factors:



                      -Each SBox has differential property and should  affect in 
            each round in the differential characteristic when it is
            activated.

            -Multiply calculated probabilities by the prior probability in
            order to finding rounds differential characteristics.


            A good reference: https://www.engr.mun.ca/~howard/PAPERS/ldc_tutorial.pdf






          But I should mention that finding differential characteristic for Feistel structures have a different story and a good reference is in:
          http://www.cs.haifa.ac.il/~orrd/BlockCipherSeminar/Lecture2-Differential.pdf







          share|improve this answer














          share|improve this answer



          share|improve this answer








          edited 3 hours ago

























          answered 3 hours ago









          Arsalan VahiArsalan Vahi

          15610




          15610























              1












              $begingroup$

              The details depend on the exact cipher design. However what you need to optimize (maximize) is the probability
              $$
              prod_{S_i ~mathrm{active~in~differential~trail}}
              P(Delta_{in},Delta_{out},S_i),
              $$

              where the deltas are the input and output differences to Sbox $S_i,$ and the differential trail is usually chosen to cover $r-1$ rounds for an $r$ round cipher.



              In the case of SPN networks with wire crossing permutation layer, as in the Heys tutorial in the comment, you should look for an output differential with low Hamming weight to minimize the number of active Sboxes in the next round.






              share|improve this answer









              $endgroup$


















                1












                $begingroup$

                The details depend on the exact cipher design. However what you need to optimize (maximize) is the probability
                $$
                prod_{S_i ~mathrm{active~in~differential~trail}}
                P(Delta_{in},Delta_{out},S_i),
                $$

                where the deltas are the input and output differences to Sbox $S_i,$ and the differential trail is usually chosen to cover $r-1$ rounds for an $r$ round cipher.



                In the case of SPN networks with wire crossing permutation layer, as in the Heys tutorial in the comment, you should look for an output differential with low Hamming weight to minimize the number of active Sboxes in the next round.






                share|improve this answer









                $endgroup$
















                  1












                  1








                  1





                  $begingroup$

                  The details depend on the exact cipher design. However what you need to optimize (maximize) is the probability
                  $$
                  prod_{S_i ~mathrm{active~in~differential~trail}}
                  P(Delta_{in},Delta_{out},S_i),
                  $$

                  where the deltas are the input and output differences to Sbox $S_i,$ and the differential trail is usually chosen to cover $r-1$ rounds for an $r$ round cipher.



                  In the case of SPN networks with wire crossing permutation layer, as in the Heys tutorial in the comment, you should look for an output differential with low Hamming weight to minimize the number of active Sboxes in the next round.






                  share|improve this answer









                  $endgroup$



                  The details depend on the exact cipher design. However what you need to optimize (maximize) is the probability
                  $$
                  prod_{S_i ~mathrm{active~in~differential~trail}}
                  P(Delta_{in},Delta_{out},S_i),
                  $$

                  where the deltas are the input and output differences to Sbox $S_i,$ and the differential trail is usually chosen to cover $r-1$ rounds for an $r$ round cipher.



                  In the case of SPN networks with wire crossing permutation layer, as in the Heys tutorial in the comment, you should look for an output differential with low Hamming weight to minimize the number of active Sboxes in the next round.







                  share|improve this answer












                  share|improve this answer



                  share|improve this answer










                  answered 4 hours ago









                  kodlukodlu

                  9,37311331




                  9,37311331






























                      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%2f68755%2fsearching-for-a-differential-characteristic-differential-cryptanalysis%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

                      Сан-Квентин

                      Алькесар

                      Josef Freinademetz