Some results on Fruit. (English) Zbl 1421.94046

Summary: At FSE 2015, F. Armknecht and V. Mikhalev [Lect. Notes Comput. Sci. 9054, 451–470 (2015; Zbl 1382.94050)] proposed a new technique to design stream ciphers, which involves repeated use of keybits in each round of the keystream bit generation. This technique showed the possibility to design stream ciphers where the internal state size is significantly lower than twice the key size. They proposed a new cipher based on this idea, named Sprout. But soon Sprout was proved to be insecure. At Crypto 2015 [V. Lallemand and M. Naya-Plasencia, Lect. Notes Comput. Sci. 9215, 663–682 (2015; Zbl 1375.94142)]proposed an attack which was \(2^{10}\) times faster than the exhaustive search. But the new idea used in Sprout showed a new direction in the design of stream cipher, which led to the proposal of several new ciphers with small size of internal state. Fruit is a recently proposed cipher where both the key size and the state size are 80. In this paper, we attack full round Fruit by a divide-and-conquer method. Our attack is equivalent to \(2^{74.95}\) many Fruit encryptions, which is around 16.95 times faster than the average exhaustive key search. Our idea also works for the second version of Fruit.


94A60 Cryptography
Full Text: DOI


[1] Armknecht F., Mikhalev V.: On lightweight stream ciphers with shorter internal states. In: FSE, pp. 451-470. Springer, Berlin (2015). · Zbl 1382.94050
[2] Babbage, S.; Dodd, M.; Robshaw, M. (ed.); Billet, O. (ed.), The MICKEY stream ciphers, 191-209, (2008), Berlin
[3] Banik S.: Some Results on Sprout. In: INDOCRYPT 2015, pp. 124-139. Springer, Cham (2015). · Zbl 1367.94297
[4] Barkan E., Biham E., Shamir A.: Rigorous bounds on cryptanalytic time/memory tradeoffs. In: CRYPTO 2006, pp. 1-21. Springer, Berlin (2006). · Zbl 1161.94384
[5] Biryukov A., Shamir A.: Cryptanalytic time/memory/data tradeoffs for stream ciphers. In: ASIACRYPT 2000, pp. 1-13. Springer, Berlin (2000). · Zbl 0980.94013
[6] Blöcher U., Dichtl M.: Fish: a fast software stream cipher. Fast Software Encryption. http://dblp.uni-trier.de/rec/bib/conf/fse/BlocherD93 (1993).
[7] Bogdanov A., Knudsen L.R., Leander G., Paar C., Poschmann A., Robshaw M., Seurin Y., Vikkelsoe C.: Present: an ultra-lightweight block cipher. In: CHES 2007, pp. 450-466. Springer, Berlin (2007). · Zbl 1142.94334
[8] Cannière, CD; Preneel, B.; Robshaw, M. (ed.); Billet, O. (ed.), Trivium, 244-266, (2008), Berlin · Zbl 1285.94054
[9] Cannière C.D., Dunkelman O., Knezevic M.: KATAN and KTANTAN—a family of small and efficient hardware-oriented block ciphers. In: CHES 2009, pp. 272-288. Springer, Berlin (2009). · Zbl 1290.94060
[10] Dey S., Sarkar S.: Cryptanalysis of full Round Fruit. Workshop on Coding and Cryptography. http://eprint.iacr.org/2017/087 (2017).
[11] Esgin, MF; Kara, O., Practical cryptanalysis of full sprout with TMD tradeoff attacks, SAC, 2015, 67-85, (2015) · Zbl 1396.94074
[12] Ghafari V.A., Hu H., Chen Y.: Fruit: ultra-lightweight stream cipher with shorter internal state. In: IACR. http://eprint.iacr.org/2016/355 (2016).
[13] Gong Z., Nikova S., Law Y.W.: KLEIN: a new family of lightweight block ciphers. In: RFIDSec 2011, pp. 1-18. Springer, Berlin (2011).
[14] Guo J., Peyrin T., Poschmann A., Robshaw M.: The LED block cipher. In: CHES 2011, pp. 326-341. Springer, Berlin (2011). · Zbl 1291.94092
[15] Hamann M., Krause M., Meier W., Zhang B.: On stream ciphers with small state. https://www.cryptolux.org/mediawiki-esc2017/images/c/c2/Smallstate.pdf (2017). · Zbl 1390.94840
[16] Hamann, M.; Krause, M.; Meier, W.; Zhang, B., Design and analysis of small-state grain-like stream ciphers, Cryptogr. Commun., 10, 803-834, (2018) · Zbl 1390.94840
[17] Hamann, M.; Krause, M.; Meier, Willi, LIZARD—a lightweight stream cipher for power-constrained devices, IACR Trans. Symmetric Cryptol., 2017, 45-79, (2017)
[18] Hamann, M.; Krause, M.; Meier, W.; Zhang, B., Time-memory-data tradeoff attacks against small-state stream ciphers, IACR Cryptol. ePrint Arch., 2017, 384, (2017)
[19] Hell M., Johansson T., Meier W.: Grain: a stream cipher for constrained environments. In: IJWMC 2007, pp. 86-93. https://doi.org/10.1504/IJWMC.2007.013798 (2007).
[20] Lallemand V., Plasencia M.N.: Cryptanalysis of full sprout. In: CRYPTO 2015, pp. 663-682. Springer, Berlin (2015). · Zbl 1375.94142
[21] Maitra S., Sarkar S., Baksi A., Dey P.: Key recovery from state information of sprout: application to cryptanalysis and fault attack. In: IACR. http://eprint.iacr.org/2015/236 (2015).
[22] Maitra S., Sinha N., Siddhanti A., Anand R., Gangopadhyay S.: A TMDTO attack against lizard. In: IACR. https://eprint.iacr.org/2017/647 (2017) (Accepted in IEEE Trans. Comput.). · Zbl 1395.94302
[23] Mikhalev V., Armknecht F., Müller C.: On ciphers that continuously access the non-volatile key. Accepted in FSE (2017).
[24] Plasencia M.N.: How to improve rebound attacks. In: CRYPTO 2011, pp. 188-205. Springer, Berlin (2011). · Zbl 1287.94090
[25] Shirai T., Shibutani K., Akishita T., Moriai S., Iwata T.: The 128-bit block- cipher CLEFIA (Extended Abstract). In: FSE 2007, pp. 181-195. Springer, Berlin (2007). · Zbl 1186.94471
[26] Suzaki T., Minematsu K., Morioka S., Kobayashi E.: TWINE: a lightweight block cipher for multiple platforms. In: SAC 2012, pp. 339-354. Springer, Berlin (2012). · Zbl 1327.94075
[27] Wu W., Zhang L.: LBlock: a lightweight block cipher. In: Applied Cryptography and Network Security, ACNS 2011, pp. 327-344. Springer, Berlin (2011). · Zbl 1250.94047
[28] Zhang B., Gong X.: Another tradeoff attack on sprout-like stream ciphers. In: ASIACRYPT 2015, pp. 561-585. Springer, Berlin (2015). · Zbl 1382.94171
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.