Detail publikace

On the Application of Symbolic Regression and Genetic Programming for Cryptanalysis of Symmetric Encryption Algorithm

Originální název

On the Application of Symbolic Regression and Genetic Programming for Cryptanalysis of Symmetric Encryption Algorithm

Anglický název

On the Application of Symbolic Regression and Genetic Programming for Cryptanalysis of Symmetric Encryption Algorithm

Jazyk

en

Originální abstrakt

The aim of the paper is to show different point of view on the problem of cryptanalysis of symmetric encryption algorithms. Our dissimilar approach, compared to the existing methods, lies in the use of the power of evolutionary principles which are in our cryptanalytic system utilized with utilization of the genetic programming (GP) in order to perform known plain-text attack (KPA). Our expected result is to find a program (i.e. function) that models the behavior of a symmetric encryption algorithm DES instantiated by specific key. If such a program would exist, then it could be possible to decipher new messages that have been encrypted by unknown secret key.The GP is employed as the basis of this work. GP is an evolutionary algorithm-based methodology inspired by biological evolution which is capable of creating computer programs solving a corresponding problem. The symbolic regression (SR) method is employed as the application of GP in practical problem. The SR method builds functions from predefined set of terminal blocks in the process of the GP evolution; and these functions approximate a list of input values pairs. The evolution of GP is controlled by a fitness function which evaluates the goal of a corresponding problem. The Hamming distance, a difference between a current individual value and a reference one, is chosen as the fitness function for our cryptanalysis problem.The functionality of our GP solution is verified by validation tests composed of polynomials of various degrees. Control statements IF and FOR are verified by computation of factorial function.The set of preconditions is determined in the experimenting stage: estimation of the worst fitness value; finding the most suitable GP parameters; transformation of KPA with elimination of an initial and final permutations; evolution of the best individual; influence of the number of encryption rounds; the cardinality of a training set; and the model generalization.The results of the experiment did not approve the most of initial assumptions. The number of encryption rounds did not influence the quality of the best individual, however, its quality was influenced by the cardinality of a training set. The elimination of the initial and final permutations had no influence on the quality of the results in the process of evolution. These results showed that our KPA GP solution is not capable of revealing internal structure of the DES algorithm's behavior. The symbolic regression method proved itself to be successful only within the convergence of the best solution where it reveals up to the 70% of secret information (45 bits), however, sub-optimal solutions do not need to be similar to optimal one.The complexity of the DES algorithm encountered with the scalability of GP. The DES algorithm takes as input a key containing 56 bits implying extensive state space explosion of generated functions, in which the discovery of the best model is highly improbable with contemporary technical capabilities.

Anglický abstrakt

The aim of the paper is to show different point of view on the problem of cryptanalysis of symmetric encryption algorithms. Our dissimilar approach, compared to the existing methods, lies in the use of the power of evolutionary principles which are in our cryptanalytic system utilized with utilization of the genetic programming (GP) in order to perform known plain-text attack (KPA). Our expected result is to find a program (i.e. function) that models the behavior of a symmetric encryption algorithm DES instantiated by specific key. If such a program would exist, then it could be possible to decipher new messages that have been encrypted by unknown secret key.The GP is employed as the basis of this work. GP is an evolutionary algorithm-based methodology inspired by biological evolution which is capable of creating computer programs solving a corresponding problem. The symbolic regression (SR) method is employed as the application of GP in practical problem. The SR method builds functions from predefined set of terminal blocks in the process of the GP evolution; and these functions approximate a list of input values pairs. The evolution of GP is controlled by a fitness function which evaluates the goal of a corresponding problem. The Hamming distance, a difference between a current individual value and a reference one, is chosen as the fitness function for our cryptanalysis problem.The functionality of our GP solution is verified by validation tests composed of polynomials of various degrees. Control statements IF and FOR are verified by computation of factorial function.The set of preconditions is determined in the experimenting stage: estimation of the worst fitness value; finding the most suitable GP parameters; transformation of KPA with elimination of an initial and final permutations; evolution of the best individual; influence of the number of encryption rounds; the cardinality of a training set; and the model generalization.The results of the experiment did not approve the most of initial assumptions. The number of encryption rounds did not influence the quality of the best individual, however, its quality was influenced by the cardinality of a training set. The elimination of the initial and final permutations had no influence on the quality of the results in the process of evolution. These results showed that our KPA GP solution is not capable of revealing internal structure of the DES algorithm's behavior. The symbolic regression method proved itself to be successful only within the convergence of the best solution where it reveals up to the 70% of secret information (45 bits), however, sub-optimal solutions do not need to be similar to optimal one.The complexity of the DES algorithm encountered with the scalability of GP. The DES algorithm takes as input a key containing 56 bits implying extensive state space explosion of generated functions, in which the discovery of the best model is highly improbable with contemporary technical capabilities.

BibTex


@inproceedings{BUT134046,
  author="Tomáš {Smetka} and Ivan {Homoliak} and Petr {Hanáček}",
  title="On the Application of Symbolic Regression and Genetic Programming for Cryptanalysis of Symmetric Encryption Algorithm",
  annote="The aim of the paper is to show different point of view on the problem of
cryptanalysis of symmetric encryption algorithms. Our dissimilar approach,
compared to the existing methods, lies in the use of the power of evolutionary
principles which are in our cryptanalytic system utilized with utilization of the
genetic programming (GP) in order to perform known plain-text attack (KPA). Our
expected result is to find a program (i.e. function) that models the behavior of
a symmetric encryption algorithm DES instantiated by specific key. If such
a program would exist, then it could be possible to decipher new messages that
have been encrypted by unknown secret key.The GP is employed as the basis of this
work. GP is an evolutionary algorithm-based methodology inspired by biological
evolution which is capable of creating computer programs solving a corresponding
problem. The symbolic regression (SR) method is employed as the application of GP
in practical problem. The SR method builds functions from predefined set of
terminal blocks in the process of the GP evolution; and these functions
approximate a list of input values pairs. The evolution of GP is controlled by
a fitness function which evaluates the goal of a corresponding problem. The
Hamming distance, a difference between a current individual value and a reference
one, is chosen as the fitness function for our cryptanalysis problem.The
functionality of our GP solution is verified by validation tests composed of
polynomials of various degrees. Control statements IF and FOR are verified by
computation of factorial function.The set of preconditions is determined in the
experimenting stage: estimation of the worst fitness value; finding the most
suitable GP parameters; transformation of KPA with elimination of an initial and
final permutations; evolution of the best individual; influence of the number of
encryption rounds; the cardinality of a training set; and the model
generalization.The results of the experiment did not approve the most of initial
assumptions. The number of encryption rounds did not influence the quality of the
best individual, however, its quality was influenced by the cardinality of
a training set. The elimination of the initial and final permutations had no
influence on the quality of the results in the process of evolution. These
results showed that our KPA GP solution is not capable of revealing internal
structure of the DES algorithm's behavior. The symbolic regression method proved
itself to be successful only within the convergence of the best solution where it
reveals up to the 70% of secret information (45 bits), however, sub-optimal
solutions do not need to be similar to optimal one.The complexity of the DES
algorithm encountered with the scalability of GP. The DES algorithm takes as
input a key containing 56 bits implying extensive state space explosion of
generated functions, in which the discovery of the best model is highly
improbable with contemporary technical capabilities.",
  address="Institute of Electrical and Electronics Engineers",
  booktitle="Proceedings of 2016 IEEE International Carnahan Conference on Security Technology",
  chapter="134046",
  doi="10.1109/CCST.2016.7815720",
  edition="NEUVEDEN",
  howpublished="online",
  institution="Institute of Electrical and Electronics Engineers",
  year="2016",
  month="july",
  pages="305--312",
  publisher="Institute of Electrical and Electronics Engineers",
  type="conference paper"
}