Algoritmos heurísticos para la optimización de Substitution Boxes

Resumen

En pleno siglo XXI, la ciberseguridad es ya una parte importante de la vida cotidiana de muchos ciudadanos. La protección de la información y la defensa contra ataques
cibernéticos es ya algo fundamental y, dentro de este ámbito, el cifrado se ha vuelto una pieza imprescindible en tales tareas. Por ello, el desarrollo de nuevos métodos de cifrado cada vez es más relevante. Por otro lado, la Inteligencia Artificial ha sufrido un auge notorio durante la última década. Sus técnicas ya son cada vez más empleadas en diferentes contextos, entre los que se encuentra la ciberseguridad. Este proyecto aborda la aplicación de técnicas de Inteligencia Artificial para la mejora de diferentes aspectos, relacionados con la criptología, en el ámbito de la ciberseguridad. Una S-Box es un componente importante del cifrado en bloque, cuyo objetivo es transformar una entrada de n bits en una salida diferente de m bits. En la última década varios
investigadores han intentado descubrir nuevas formas de crear S-Boxes. La aplicación de técnicas heurísticas (técnicas pertenecientes al campo de la Inteligencia Artificial) para generar S-Boxes con buenas propiedades criptográficas ha cogido mucha relevancia en relación a métodos más convencionales. El enfoque que se aplica en este proyecto consiste en adaptar el método científico para crear un algoritmo heurístico que optimice algunas
de las propiedades criptográficas (más concretamente la no-linealidad) de estos componentes el cifrado en bloque. Más concretamente, la propuesta de este proyecto consiste
en desarrollar un método constructivo que genera de forma aleatoria una serie de soluciones iniciales sobre las que posteriormente se aplicará una búsqueda local cuyo objetivo es mejorar las soluciones iniciales. Por último se aplica una versión de la metaheurística Variable
Neighborhood Search con la finalidad de evitar los óptimos locales que se producen con la búsqueda y tratar de alcanzar un mejor resultado. Los algoritmos propuestos han
sido validados mediante la realización de pruebas que comparan los tres métodos desarrollados. El tiempo de ejecución de las pruebas aumenta exponencialmente cuanto mayor es la dimensión de la instancia tratada, siendo el tamaño máximo que se ha considerado en este proyecto de 8x8. Los resultados obtenidos con el constructivo aleatorio muestran valores iniciales prometedores. Sin embargo, esto parece indicar que los valores pueden
estar próximos a los óptimos locales, siendo difícil la propuesta de algoritmos de mejora.
Abtract:
Nowadays, cibersecurity is an important part of the daily life of many citizens. Protecting data and defending against attacks have already become fundamental, and within this area, encrypting has become an essential part in such tasks. This is the reason why developing new encryption methods is increasingly important. On the other hand, Artificial Ingelligence has experienced a boom during the last decade. Its techniques are gradually more used in different contexts, among which is cybersecurity.
This project approach the aplication of Artificial Intelligence to improve different aspects related to cryptology, in the context of cibersecurity. An S-Box is an important component of block ciphers, which aim is transform a n bits input into a m bits output. For the last decade, some researchers have tried to find new methods to create S-Boxes. The application of heuristic techniques, which are part of Artificial Intelligence context, to produce S-Boxes with strong cryptological properties has obtained more relevance compared to conventional methods. The approach proposed in this project is to use the scientific method in order to generate an heuristic algorithm to optimize some of those S-Boxes cryptological properties (specifically non linearity). To be more accurate, this project proposes developing a constructive method which create a number of solutions randomly and use a local search in order to improve the initial solutions. Finally, the Variable Neighborhood Search metaheuristic is applied trying to avoid local optima produced by the local search and improve the overall results. The methods proposed have been validated with tests comparing the three methods. The ejecution time of the tests increases exponentially the larger the size of the instance, being 8x8 the maximum size considered in this project. The results obtained with the random consctructive method shows promising initial values. However, this seems to indicate that those values could be near local optima, making the proposal of improvement algorithms harder.