Monte Carlo Tree Search for automatic differential characteristics search: application to SPECK

Emanuele Bellini; David Gerault; Matteo Protopapa; Matteo Rossi

Paper 2024/126

Monte Carlo Tree Search for automatic differential characteristics search: application to SPECK

Emanuele Bellini

, Technology Innovation Institute

David Gerault

, Technology Innovation Institute

Matteo Protopapa, Politecnico di Torino, Torino, Italy

Matteo Rossi, Politecnico di Torino, Torino, Italy

Abstract

The search for differential characteristics on block ciphers is a difficult combinatorial problem. In this paper, we investigate the performances of an AI-originated technique, Single Player Monte-Carlo Tree Search (SP-MCTS), in finding good differential characteristics on ARX ciphers, with an application to the block cipher SPECK. In order to make this approach competitive, we include several heuristics, such as the combination of forward and backward searches, and achieve significantly faster results than state-of-the-art works that are not based on automatic solvers. We reach 9, 11, 13, 13 and 15 rounds for SPECK32, SPECK48, SPECK64, SPECK96 and SPECK128 respectively. In order to build our algorithm, we revisit Lipmaa and Moriai's algorithm for listing all optimal differential transitions through modular addition, and propose a variant to enumerate all transitions with probability close (up to a fixed threshold) to the optimal, while fixing a minor bug in the original algorithm.

Metadata

Available format(s): PDF
Category: Secret-key cryptography
Publication info: Published elsewhere. INDOCRYPT 2022
DOI: 10.1007/978-3-031-22912-1_17
Keywords: Monte Carlo Tree Search Differential Cryptanalysis ARX Block Ciphers SPECK
Contact author(s): emanuele bellini @ tii ae
david gerault @ tii ae
matteoprot @ gmail com
matteo rossi @ polito it
History: 2024-01-30: approved; 2024-01-29: received; See all versions
Short URL: https://ia.cr/2024/126
License: CC BY

BibTeX

@misc{cryptoeprint:2024/126,
      author = {Emanuele Bellini and David Gerault and Matteo Protopapa and Matteo Rossi},
      title = {Monte Carlo Tree Search for automatic differential characteristics search: application to SPECK},
      howpublished = {Cryptology ePrint Archive, Paper 2024/126},
      year = {2024},
      doi = {10.1007/978-3-031-22912-1_17},
      note = {\url{https://eprint.iacr.org/2024/126}},
      url = {https://eprint.iacr.org/2024/126}
}