Sage Journals: Discover world-class research

Abstract

As a fully homomorphic encryption friendly symmetric-key primitive, DASTA was invented by Hebborn at Fast Software Encryption 2020. A new fixed linear layer design concept is introduced in the DASTA stream cipher so that its AND depth and the number of ANDs per encrypted bit are quite small. Currently, the security of the DASTA stream cipher has received extensive attention. Note that the best-known attack (i.e., algebraic attack) on DASTA still has a very high data complexity. It appears to be an important task to reduce the data complexity of the attack on DASTA. In this article, a new algebraic attack on DASTA is proposed. More specifically, the key feed-forward operation, the properties of the nonlinear layer and the invariance from the linear layer are successfully utilized in the attack. In particular, the nonlinear relation of internal states in DASTA is linearized effectively. In this case, more secret key bit equations with low algebraic degrees are collected by fixing the bit. It is illustrated that four $(r - 1)$ -round instances of the DASTA cipher family are theoretically broken by the attack, where r is the iterative number of round operations. Compared with the results of previous algebraic attacks, our approach achieves more favorable data complexity.

Keywords

DASTA algebraic attack linearize

Get full access to this article

View all access options for this article.

References

M.R.

Albrecht,

Grassi,

Rechberger et al., Mimc: Efficient encryption and cryptographic hashing with minimal multiplicative complexity, in: ASIACRYPT 2016, Springer, 2016, pp. 191–219. doi:10.1007/978-3-662-53887-6_7.

M.R.

Albrecht,

Rechberger,

Schneider et al., Ciphers for MPC and FHE, in: EUROCRYPT 2015, Springer, 2015, pp. 46–48.

Armknecht, A linearization attack on the bluetooth key stream generator, 13 December 2002, http://eprint.iacr.org/2002/191/.

Biryukov,

Bouillaguet and

Khovratovich, Cryptographic schemes based on the ASASA structure: Black-box, white-box, and public-key (extended abstract), in: ASIACRYPT 2014, Springer, 2014, pp. 63–84.

Canteaut,

Carpov,

Fontaine et al., Stream ciphers: A practical solution for efficient homomorphic-ciphertext compression, in: The 23rd International Conference on Fast Software Encryption, Springer, 2016, pp. 313–333. doi:10.1007/978-3-662-52993-5_16.

N.T.

Courtois,

Klimov,

Patarin et al., Efficient algorithms for solving overdefined systems of multivariate polynomial equations, in: EUROCRYPT 2000, Springer, 2000, pp. 14–18.

N.T.

Courtois and

Meier, Algebraic attacks on stream ciphers with linear feedback, in: EUROCRYPT 2003, Springer Press, Warsaw, 2003, pp. 345–359.

Dobraunig,

Eichlseder,

Grassi et al., RASTA: A cipher with low ANDdepth and few ANDs per bit, in: CRYPTO 2018, Springer, 2018, pp. 662–692. doi:10.1007/978-3-319-96884-1_22.

Dobraunig,

Grassi,

Guinet et al., Ciminion: Symmetric encryption based on Toffoli-gates over large finite fields, in: EUROCRYPT 2021, Springer, 2021, pp. 3–34. doi:10.1007/978-3-030-77886-6_1.

10.

J.C.

Faugere, A new efficient algorithm for computing Gröbner bases (F4), Journal of Pure and Applied Algebra 139 (1999), 61–88. doi:10.1016/S0022-4049(99)00005-5.

11.

J.C.

Faugere, A new efficient algorithm for computing Gröbner bases without reduction to zero F5, in: International Symposium on Symbolic and Algebraic Computation Symposium – ISSAC 2002, ACM, 2002, pp. 75–83. doi:10.1145/780506.780516.

12.

Grassi,

Lüftenegger,

Rechberger et al., On a generalization of substitution-permutation networks: The HADES design strategy, in: EUROCRYPT 2020, Springer, 2020, pp. 674–704. doi:10.1007/978-3-030-45724-2_23.

13.

Guo,

G.H.

Liao,

G.Z.

Liu et al., Practical collision attacks against round-reduced SHA-3, Journal of Cryptology 33 (2019), 228–270. doi:10.1007/s00145-019-09313-3.

14.

Hebborn and

Leander, DASTA – Alternative linear layer for RASTA, IACR Transactions on Symmetric Cryptology 3 (2020), 46–86. doi:10.13154/tosc.v2020.is.46-86.

15.

F.K.

Liu,

Isobe and

Meier, Algebraic attacks on RASTA and DASTA using low-degree equations, in: ASIACRYPT 2021, Springer, 2021, pp. 214–240. doi:10.1007/978-3-030-92062-3_8.

16.

Meaux,

Journault,

Standaert et al., Towards stream ciphers for efficient FHE with low-noise ciphertexts, in: EUROCRYPT 2016, Springer, 2016, pp. 311–343. doi:10.1007/978-3-662-49890-3_13.

17.

Mittal and

K.R.

Ramkumar, Research perspectives on fully homomorphic encryption models for cloud sector, Journal of Computer Security 29 (2021), 135–160. doi:10.3233/JCS-219001.

18.

Pasalic, On guess and determine cryptanalysis of LFSR-based stream ciphers, IEEE Transactions on Information Theory 55 (2009), 3398–3406. doi:10.1109/TIT.2009.2021316.

19.

M.S.

Rajasree, Cryptanalysis of round-reduced KECCAK using non-linear structures, in: INDOCRYPT 2019, Springer, 2019, pp. 175–192. doi:10.1007/978-3-030-35423-7_9.

20.

SHA-3 standard: Permutation-based hash and extendable-output functions, (NIST FIPS)-202, 2014.

A new algebraic attack on DASTA

Abstract

Keywords

Get full access to this article

References