SPARX is a family of lightweight block ciphers allowing small processors to securely encrypt information for a fraction of the cost a standard algorithm would require.
High Level View
- Article: Design Strategies for ARX with Provable Bounds: SPARX and LAX
- Authors: Daniel Dinu, Léo Perrin, Aleksei Udovenko, Vesselin Velichkov, Johann Großschädl and Alex Biryukov
SPARX is a family of ARX-based 64- and 128-bit block ciphers. Only addition modulo 216, 16-bit XOR and 16-bit rotations are needed to implement any version. SPARX-n/k denotes the version encrypting an n-bit block with a k-bit key.
The SPARX ciphers have been designed according to the Long Trail Strategy put forward by its authors in the same paper. It can be seen as a counterpart of the Wide-Trail Strategy suitable for algorithms built using a large and weak S-Box rather than a small strong one. This method allows the designers to bound the differential and linear trial probabilities, unlike for all other ARX-based designs. Non-linearity is provided by SPECKEY, a 32-bit block cipher identical to SPECK-32 except for its key addition. The linear layer is very different from that of, say, the AES as it consists simply in a linear Feistel round for all versions.
The designers claim that no attack using less than 2k operations exists against SPARX-n/k in neither the single-key nor in the related-key setting. They also faithfully declare that they have not hidden any weakness in these ciphers. SPARX is free for use and its source code is available in the public domain (it can be obtained below).
The SPARX ciphers are efficient in terms of memory, code size and time. Due to the use of ARX operations, they are inherently more secure against side-channel attacks than an S-Box-based cipher like the AES. Furthermore, unlike all other ARX-based, which share those advantages, SPARX ciphers are the only ARX-based block ciphers for which bounds on the probability of differential and linear trails can be proved. This means that the security it provides is easier to justify than for other similar cipher, in particular the NSA proposal SPECK. The structure of SPARX also allows functionally equivalent implementations with different properties. For instance, the subkeys can be derived on the fly to reduce the memory footprint or pre-computed to reduce the computation time.
To sum up, SPARX has:
- the lightweightness and side-channel resilience of an ARX-based cipher,
- the security argument of an S-Box-based cipher, and
- a flexible structure easing implementation trade-offs.
Here, we list the different cryptanalyses against the SPARX ciphers we are aware of, including those by its designers.
|SPARX-64/128||24||15 rounds (Integral)||Designers|
|16 rounds (Impossible Differential)||Abdelkhalek et al.|
|16 rounds (Truncated Differential, Rectangle, Yoyo)||Ankele and List|
|SPARX-128/128||32||22 rounds (Integral)||Designers|
|26 rounds (Multidimensional Zero-Correlation)||Tolba et al.|
|SPARX-128/256||40||24 rounds (Integral)||Designers|
|29 rounds (Zero-Correlation)||Tolba et al.|
- ASIACRYPT'16 paper: Springer
- Eprint full version: 2016/984.pdf
- Bibtex entry: dblp
- Presentation slides: NIST Lightweight Cryptography Workshop, ASIACRYPT
- Reference implementation: Sparx.c. This implementation should only be used to verify the correctness of a better one. For example, no optimizations whatsoever have been made.
- Optimized implementations: FELICS. Check block_ciphers/source/ciphers/. For more details about these implementations and the corresponding results, see FELICS.
- GitHub: SPARX
- Implementation in Rust by Frank Denis: rust-sparx
- Dinu, D., Perrin, L., Udovenko, A., Velichkov, V., Großschädl, J. & Biryukov, A. (2016). Design Strategies for ARX with Provable Bounds: SPARX and LAX. In Advances in Cryptology–ASIACRYPT 2016 (pp 484-513). Springer Berlin Heidelberg. pdf at eprint.iacr.org
- Ahmed Abdelkhalek, Mohamed Tolba and Amr M. Youssef. Impossible Differential Attack on Reduced Round SPARX-64/128. In Progress in Cryptology - AFRICACRYPT 2017 (pp 135-146). Springer Berlin Heidelberg.
- Ralph Ankele and Eik List. Differential Cryptanalysis of Round-Reduced Sparx-64/128. In Applied Cryptography and Network Security - ACNS 2018. Springer Berlin Heidelberg. pdf at eprint.iacr.org
- Mohamed Tolba, Ahmed Abdelkhalek and Amr M. Youssef. Multidimensional Zero-Correlation Linear Cryptanalysis of Reduced Round SPARX-128. In Selected Areas in Cryptography - SAC 2017 (pp 423-441). Springer Berlin Heidelberg. pdf at www.site.uottawa.ca