Difference between revisions of "SPARX"
Leo.perrin (talk | contribs) (→Resources) |
(→References) |
||
(19 intermediate revisions by 3 users not shown) | |||
Line 34: | Line 34: | ||
! Instance || Rounds || Attack || Authors | ! Instance || Rounds || Attack || Authors | ||
|- | |- | ||
− | ! rowspan=" | + | ! rowspan="3" | SPARX-64/128 |
− | | rowspan=" | + | | rowspan="3" | 24 |
| 15 rounds (Integral) | | 15 rounds (Integral) | ||
| Designers<ref name=DPUVGB16></ref> | | Designers<ref name=DPUVGB16></ref> | ||
|- | |- | ||
− | ! rowspan=" | + | | 16 rounds (Impossible Differential) |
− | | rowspan=" | + | | Abdelkhalek et al.<ref name=ATY2017></ref> |
+ | |- | ||
+ | | 16 rounds (Truncated Differential, Rectangle, Yoyo) | ||
+ | | Ankele and List<ref name=AL2018></ref> | ||
+ | |- | ||
+ | ! rowspan="2" | SPARX-128/128 | ||
+ | | rowspan="2" | 32 | ||
| 22 rounds (Integral) | | 22 rounds (Integral) | ||
| Designers<ref name=DPUVGB16></ref> | | Designers<ref name=DPUVGB16></ref> | ||
|- | |- | ||
− | ! rowspan=" | + | | 26 rounds (Multidimensional Zero-Correlation) |
− | | rowspan=" | + | | Tolba et al.<ref name=TAY2017></ref> |
+ | |- | ||
+ | ! rowspan="2" | SPARX-128/256 | ||
+ | | rowspan="2" | 40 | ||
| 24 rounds (Integral) | | 24 rounds (Integral) | ||
| Designers<ref name=DPUVGB16></ref> | | Designers<ref name=DPUVGB16></ref> | ||
+ | |- | ||
+ | | 29 rounds (Zero-Correlation) | ||
+ | | Tolba et al.<ref name=TAY2017></ref> | ||
|- | |- | ||
|} | |} | ||
Line 53: | Line 65: | ||
== Resources == | == Resources == | ||
− | * ASIACRYPT'16 paper: | + | * ASIACRYPT'16 paper: [http://link.springer.com/chapter/10.1007/978-3-662-53887-6_18 Springer] |
− | * Eprint full version: | + | * Eprint full version: [https://eprint.iacr.org/2016/984.pdf 2016/984.pdf] |
− | * Bibtex entry: | + | * Bibtex entry: [http://dblp.uni-trier.de/rec/bibtex/conf/asiacrypt/DinuPUVGB16 dblp] |
− | * Presentation slides: NIST | + | * Presentation slides: [https://www.nist.gov/sites/default/files/documents/2016/10/18/perrin-presentation-lwc2016.pdf NIST Lightweight Cryptography Workshop], [https://www.dropbox.com/s/gf7v8ju8s6eotao/sparx.pdf ASIACRYPT] |
* Reference implementation: [[media:Sparx.c|Sparx.c]]. This implementation should only be used to verify the correctness of a better one. For example, no optimizations whatsoever have been made. | * Reference implementation: [[media:Sparx.c|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: [[Media:FELICS.zip|FELICS]]. Check ''block_ciphers/source/ciphers/''. For more details about these implementations and the corresponding results, see [[FELICS|FELICS]]. | * Optimized implementations: [[Media:FELICS.zip|FELICS]]. Check ''block_ciphers/source/ciphers/''. For more details about these implementations and the corresponding results, see [[FELICS|FELICS]]. | ||
+ | * GitHub: [https://github.com/cryptolu/SPARX SPARX] | ||
+ | |||
+ | == Third-party Implementations == | ||
+ | |||
+ | * Implementation in Rust by Frank Denis: [https://github.com/jedisct1/rust-sparx rust-sparx] | ||
== References == | == References == | ||
<references> | <references> | ||
− | <ref name=DPUVGB16>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 ( | + | <ref name=DPUVGB16>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. [http://eprint.iacr.org/2016/984.pdf pdf at eprint.iacr.org] </ref> |
+ | <ref name=ATY2017> 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.</ref> | ||
+ | <ref name=AL2018> Ralph Ankele and Eik List. ''Differential Cryptanalysis of Round-Reduced Sparx-64/128''. In Applied Cryptography and Network Security - ACNS 2018. Springer Berlin Heidelberg. [https://eprint.iacr.org/2018/332.pdf pdf at eprint.iacr.org]</ref> | ||
+ | <ref name=TAY2017> 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. [http://www.site.uottawa.ca/~cadams/papers/prepro/paper_23.pdf pdf at www.site.uottawa.ca]</ref> | ||
+ | |||
</references> | </references> | ||
[[Category:ACRYPT]] | [[Category:ACRYPT]] |
Latest revision as of 17:12, 23 April 2018
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.
Contents
High Level View
- Article: Design Strategies for ARX with Provable Bounds: SPARX and LAX^{[1]}
- 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 2^{16}, 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 2^{k} 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).
Strengths
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.
Cryptanalysis
Here, we list the different cryptanalyses against the SPARX ciphers we are aware of, including those by its designers.
Instance | Rounds | Attack | Authors |
---|---|---|---|
SPARX-64/128 | 24 | 15 rounds (Integral) | Designers^{[1]} |
16 rounds (Impossible Differential) | Abdelkhalek et al.^{[2]} | ||
16 rounds (Truncated Differential, Rectangle, Yoyo) | Ankele and List^{[3]} | ||
SPARX-128/128 | 32 | 22 rounds (Integral) | Designers^{[1]} |
26 rounds (Multidimensional Zero-Correlation) | Tolba et al.^{[4]} | ||
SPARX-128/256 | 40 | 24 rounds (Integral) | Designers^{[1]} |
29 rounds (Zero-Correlation) | Tolba et al.^{[4]} |
Resources
- 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
Third-party Implementations
- Implementation in Rust by Frank Denis: rust-sparx
References
- ↑ ^{1.0} ^{1.1} ^{1.2} ^{1.3} 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
- ↑ ^{4.0} ^{4.1} 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