A Deeper Look at Machine Learning-Based Cryptanalysis
At CRYPTO’19, Gohr proposed a new cryptanalysis strategy based on the utilisation of machine learning algorithms. Using deep neural networks, he managed to build a neural based distinguisher that surprisingly surpassed state-of-the-art cryptanalysis efforts on one of the versions of the well studied NSA block cipher SPECK (this distinguisher could in turn be placed in a larger key recovery attack). While this work opens new possibilities for machine learning-aided cryptanalysis, it remains unclear how this distinguisher actually works and what information is the machine learning algorithm deducing. The attacker is left with a black-box that does not tell much about the nature of the possible weaknesses of the algorithm tested, while hope is thin as interpretability of deep neural networks is a well-known difficult task. In this article, we propose a detailed analysis and thorough explanations of the inherent workings of this new neural distinguisher. First, we studied the classified sets and tried to find some patterns that could guide us to better understand Gohr’s results. We show with experiments that the neural distinguisher generally relies on the differential distribution on the ciphertext pairs, but also on the differential distribution in penultimate and antepenultimate rounds. In order to validate our findings, we construct a distinguisher for SPECK cipher based on pure cryptanalysis, without using any neural network, that achieves basically the same accuracy as Gohr’s neural distinguisher and with the same efficiency (therefore improving over previous non-neural based distinguishers). Moreover, as another approach, we provide a machine learning-based distinguisher that strips down Gohr’s deep neural network to a bare minimum. We are able to remain very close to Gohr’s distinguishers’ accuracy using simple standard machine learning tools. In particular, we show that Gohr’s neural distinguisher is in fact inherently building a very good approximation of the Differential Distribution Table (DDT) of the cipher during the learning phase, and using that information to directly classify ciphertext pairs. This result allows a full interpretability of the distinguisher and represents on its own an interesting contribution towards interpretability of deep neural networks. Finally, we propose some method to improve over Gohr’s work and possible new neural distinguishers settings. All our results are confirmed with experiments we have conducted on SPECK block cipher.
On the Usage of Deterministic (Related-Key) Truncated Differentials and Multidimensional Linear Approximations for SPN Ciphers 📺
Among the few works realising the search of truncated differentials (TD) and multidimensional linear approximations (MDLA) holding for sure, the optimality of the distinguisher should be confirmed via an exhaustive search over all possible input differences/masks, which cannot be afforded when the internal state of the primitive has a considerable number of words. The incomplete search is also a long-term problem in the search of optimal impossible differential (ID) and zerocorrelation linear approximation (ZCLA) since all available automatic tools operate under fixed input and output differences/masks, and testing all possible combinations of differences/masks is impracticable for now. In this paper, we start by introducing an automatic approach based on the constraint satisfaction problem for the exploration of deterministic TDs and MDLAs. Since we transform the exhaustive search into an inherent feature of the searching model, the issue of incomplete search is settled. This tool is applied to search for related-key (RK) TDs of AES-192, and a new related-key differential-linear (DL) distinguisher is identified with a TD with certainty. Due to the novel property of the distinguisher, the previous RK DL attack on AES-192 is improved. Also, the new distinguisher is explained from the viewpoint of differentiallinear connectivity table (DLCT) and thus can be regarded as the first application of DLCT in the related-key attack scenario. As the second application of the tool, we propose a method to construct (RK) IDs and ZCLAs automatically. Benefiting from the control of the nonzero fixed differential pattern and the inherent feature of exhaustive search, the new searching scheme can discover longer distinguishers and hence possesses some superiorities over the previous methods. This technique is implemented with several primitives, and the provable security bounds of SKINNY and Midori64 against impossible differential distinguishing attack are generalised.
Analysis of AES, SKINNY, and Others with Constraint Programming
Search for different types of distinguishers are common tasks in symmetrickey cryptanalysis. In this work, we employ the constraint programming (CP) technique to tackle such problems. First, we show that a simple application of the CP approach proposed by Gerault et al. leads to the solution of the open problem of determining the exact lower bound of the number of active S-boxes for 6-round AES-128 in the related-key model. Subsequently, we show that the same approach can be applied in searching for integral distinguishers, impossible differentials, zero-correlation linear approximations, in both the single-key and related-(twea)key model. We implement the method using the open source constraint solver Choco and apply it to the block ciphers PRESENT, SKINNY, and HIGHT (ARX construction). As a result, we find 16 related-tweakey impossible differentials for 12-round SKINNY-64-128 based on which we construct an 18-round attack on SKINNY-64-128 (one target version for the crypto competition https://sites.google.com/site/skinnycipher announced at ASK 2016). Moreover, we show that in some cases, when equipped with proper strategies (ordering heuristic, restart and dynamic branching strategy), the CP approach can be very efficient. Therefore, we suggest that the constraint programming technique should become a convenient tool at hand of the symmetric-key cryptanalysts.