Courtois, N;
Mourouzis, T;
Song, G;
Sepehrdad, P;
Susil, P;
(2014)
Combined Algebraic and Truncated Differential Cryptanalysis on Reduced-round Simon.
In: Obaidat, MS and Holzinger, A and Samarati, P, (eds.)
Proceedings of the 11th International Conference on Security and Cryptography (ICETE 2014).
(pp. pp. 399-404).
Science and Technology Publications: Vienna, Austria.
![[thumbnail of simonac2col.pdf]](https://discovery.ucl.ac.uk/style/images/fileicons/text.png) Preview |
Text
simonac2col.pdf Download (102kB) |
Abstract
Recently, two families of ultra-lightweight block ciphers were proposed, SIMON and SPECK, which come in a variety of block and key sizes (Beaulieu et al., 2013). They are designed to offer excellent performance for hardware and software implementations (Beaulieu et al., 2013; Aysu et al., 2014). In this paper, we study the resistance of SIMON-64/128 with respect to algebraic attacks. Its round function has very low Multiplicative Complexity (MC) (Boyar et al., 2000; Boyar and Peralta, 2010) and very low non-linearity (Boyar et al., 2013; Courtois et al., 2011) since the only non-linear component is the bitwise multiplication operation. Such ciphers are expected to be very good candidates to be broken by algebraic attacks and combinations with truncated differentials (additional work by the same authors). We algebraically encode the cipher and then using guess-then-determine techniques, we try to solve the underlying system using either a SAT solver (Bard et al., 2007) or by ElimLin al gorithm (Courtois et al., 2012b). We consider several settings where P-C pairs that satisfy certain properties are available, such as low Hamming distance or follow a strong truncated differential property (Knudsen, 1995). We manage to break faster than brute force up to 10(/44) rounds for most cases we have tried. Surprisingly, no key guessing is required if pairs which satisfy a strong truncated differential property are available. This reflects the power of combining truncated differentials with algebraic attacks in ciphers of low non-linearity and shows that such ciphers require a large number of rounds to be secure.
| Type: | Proceedings paper |
|---|---|
| Title: | Combined Algebraic and Truncated Differential Cryptanalysis on Reduced-round Simon |
| Event: | 11th International Conference on Security and Cryptography |
| ISBN-13: | 9789897580451 |
| Open access status: | An open access version is available from UCL Discovery |
| DOI: | 10.5220/0005064903990404 |
| Publisher version: | https://doi.org/10.5220/0005064903990404 |
| Language: | English |
| Additional information: | © The Author(s), 2014. This is an open access article distributed under the terms of the Creative Commons Attribution-Non Commercial-No Derivatives License 4.0 (CC-BY-NC-ND), where it is permissible to download and share the work provided it is properly cited. The work cannot be changed in any way or used commercially without permission from the journal. http://creativecommons.org/licenses/by-nc-nd/4.0/ |
| Keywords: | Lightweight Cryptography, Block Cipher, Feistel, SIMON, Differential Cryptanalysis, Algebraic Cryptanalysis, Truncated Differentials, SAT Solver, Elimlin, Non-linearity, Multiplicative Complexity, Guess-then-determine |
| UCL classification: | UCL UCL > Provost and Vice Provost Offices UCL > Provost and Vice Provost Offices > UCL BEAMS UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science > Dept of Computer Science |
| URI: | https://discovery.ucl.ac.uk/id/eprint/1469754 |
Archive Staff Only
 |
View Item |
