Automatic differential cryptanalysis of the SPECK block cipher with Monte Carlo Tree Search

Nowadays, cryptography is one of the main building blocks in computer science, as it contributes to digital data security in the broadest sense, both when stored and when exchanged. Block ciphers play an important role in this scenario, as they represent some of the functions used to achieve cryptographic security. Differential cryptanalysis is a powerful tool to assess the security and robustness of ciphers and hash functions. This technique, which usually takes the form of a chosen plaintext attack, aims to analyse the multiple rounds in a block cipher. In practice, its purpose is to find sequences of perturbations, called differences, from the input of the cipher and up to the largest possible number of rounds so that the total propagation probability is as high as possible. When a good sequence (also called differential characteristic) is found, the attack is considered successful, and in some cases it can allow a key recovery attack, in which the secret key used with the cipher is discovered. The work described in this Thesis regards the automation of the search for differential characteristics in block ciphers. The case study focuses on the SPECK family of ciphers. The objective is to ease the security assessment of block ciphers by developing a tool capable of finding good sequences of differences in an automated way, with a very small knowledge of the target cipher and with no human interaction. The tool is based on a variant of the Monte-Carlo Tree Search (MCTS) called Single Player MCTS. Monte-Carlo Tree Search is a well-known algorithm in the context of board games such as Chess of Go because of its strength when the number of solutions is so high that a complete search is unfeasible, as is the case in cryptanalysis, but it is almost unexplored in this field. The research started from a survey of the works present in literature, which led to the discovery of precious heuristics that improve the performance of the MCTS algorithm. Then, the implementation phase has taken place, from the code for the precomputation of data needed to the algorithm, to the algorithm itself, the collection of statistics and the validation of the outcome. During this phase, several heuristics collected from previous works were gradually added to face the limitations that arose, and each addition contributed positively to the global performance of the algorithm. At last, a comparison between the new tool and the existing ones is performed: although graph-based searches are the natural competitor of the Monte-Carlo Tree Search, due to their internal behaviour, also solver-based ones are taken into account. The results are promising as the search is significantly faster than the state-of-the-art works for the smallest versions of SPECK, while non-optimal but still good results are obtained for the bigger version. Moreover, additional optimizations can be introduced, leaving room to further improvements in the already good results.