Paper 2024/126
Monte Carlo Tree Search for automatic differential characteristics search: application to SPECK
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 SearchDifferential CryptanalysisARXBlock CiphersSPECK
- 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},
url = {https://eprint.iacr.org/2024/126}
}