Top

Cryptography and Communications

Published in:

08-11-2017

Design and analysis of small-state grain-like stream ciphers

Authors: Matthias Hamann, Matthias Krause, Willi Meier, Bin Zhang

Published in: Cryptography and Communications | Issue 5/2018

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

Time-memory-data (TMD) tradeoff attacks limit the security level of many classical stream ciphers to the birthday bound. Very recently, a new field of research has emerged, which searches for so-called small-state stream ciphers that try to overcome this limitation. In this paper, existing designs and known analysis of small-state stream ciphers are revisited and new insights on distinguishers and key recovery are derived based on TMD tradeoff attacks. A particular result is the transfer of a generic distinguishing attack suggested in 2007 by Englund et al. to this new class of lightweight ciphers. Our analysis shows that the initial hope of achieving full security against TMD tradeoff attacks by continuously using the secret key has failed. In particular, we provide generic distinguishers for Plantlet and Fruit with complexity significantly smaller than that of exhaustive key search. However, by studying the assumptions underlying the applicability of these attacks, we are able to come up with a new design idea for small-state stream ciphers, which might allow to finally achieve full security against TMD tradeoff attacks. Another contribution of this paper is the first key recovery attack against the most recent version of Fruit. We show that there are at least 2⁶⁴ weak keys, each of which does not provide 80-bit security as promised by designers.

previous article Statistical attacks on cookie masking for RC4

next article Success probability of multiple/multidimensional linear cryptanalysis under general key randomisation hypotheses

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Available only for authorised users

Please note that when speaking of a more complicated key schedule, we are referring to the way in which the key bits are used in order to compute the round key bit (e.g., using more than on key bit as input to an elaborate round key function with potentially high algebraic degree).

While, from a theoretical point of view, this looks very elegant, it’s not really clear whether the security of Plantlet does actually benefit from the fact that the LFSR feedback polynomial is also primitive during initialization. After all, due to the additional feedback of the output bit z ^t, the LFSR’s period between t = 0 and t = 319 is unclear anyhow.

A small amount of IV collisions may be tolerable depending on the security claims; see, e.g., Lizard [27], which claims 80-bit security against key recovery and 60-bit security against distinguishing.

Englund, Hell, and Johansson similarly concluded: “If the key size |K| > N/2, then the new distinguishing attack will always succeed with complexity below exhaustive key search”. However, they left out the logarithmic factor, which we chose to include as exhaustive key search has negligible data and memory complexity, whereas in the above distinguishing attack, these complexities are actually each at a factor of \(\tilde {n}\) higher than the time complexity and dominate the overall cost of the attack.

As pointed out in Section 3.1.1, due to the focus on block ciphers in OFB mode, this security margin was not necessary for the attack of Englund, Hell, and Johansson. It would, however, be required in the well-known TMD tradeoff attacks by Babbage [3] and Biryukov and Shamir [10], where, like the additional factor n itself, it is usually not included in the description of the respective attack complexities.

Note that the 112-bit input ((k32∗,…,k63∗), (l130∗,…,l172∗), (n130∗,…,n166∗)) contains all necessary information to compute this keystream prefix, because: the counter at t = 130 before it is overwritten is publicly known, and we suppose the last 16 key bits to be 0, and the first 32 key bits are never needed again for the state update (and the keystream generation) after t = 0.

In fact, e.g., the data complexity would be increased by a factor below 2³ (and possibly even decrease) as now, the keystream blocks can be derived via sliding a 118-bit window over the keystream, just like in the classical TMD tradeoff attack.

A corresponding full paper by two of the authors of this work is currently under submission.

Resulting in Fruit v1 (ePrint version 20170304:073404), for which we now also presented a key recovery attack in Section 3.2.

Also do not forget that, unlike stream ciphers, block ciphers additionally need an appropriate mode of operation (if the problems of electronic codebook mode (ECB) are to be avoided), increasing hardware costs in terms of, e.g., area and power consumption.

More precisely, in the context of cube attacks, the algebraic degree of the Boolean function that maps secret key and IV to the first keystream bit.

In other words, under an arbitrarily fixed key, two IVs will never lead to shifted versions of the same keystream.

Though stream cipher designers seem to hardly talk about this issue in their suggestions and instead leave the problem of IV uniqueness to user.

Armknecht, F., Hamann, M., Mikhalev, V.: Lightweight authentication protocols on ultra-constrained RFIDs - myths and facts. In: Saxena, N., Sadeghi, A.R. (eds.) Radio Frequency Identification: Security and Privacy Issues: 10th International Workshop, RFIDSec 2014, Oxford, UK, July 21-23, 2014, Revised Selected Papers, pp. 1–18. Springer International Publishing, Cham (2014). https://doi.org/10.1007/978-3-319-13066-8_1

Armknecht, F., Mikhalev, V.: On lightweight stream ciphers with shorter internal states. In: Leander, G. (ed.) Fast Software Encryption: 22nd International Workshop, FSE 2015, Istanbul, Turkey, March 8-11, 2015, Revised Selected Papers, pp. 451–470. Springer, Berlin (2015). https://doi.org/10.1007/978-3-662-48116-5_22

Babbage, S.: Improved exhaustive search attacks on stream ciphers. In: 1995 European Convention on Security and Detection, pp. 161–166 (1995). https://doi.org/10.1049/cp:19950490

Babbage, S., Dodd, M.: The stream cipher MICKEY 2.0 eSTREAM: The ECRYPT Stream Cipher Project. http://www.ecrypt.eu.org/stream/p3ciphers/mickey/mickey_p3.pdf (2006)

Banik, S.: Some results on sprout. In: Biryukov, A., Goyal, V. (eds.) Progress in Cryptology – INDOCRYPT 2015: 16th International Conference on Cryptology in India, Bangalore, India, December 6-9, 2015, Proceedings, pp. 124–139. Springer International Publishing, Cham (2015). https://doi.org/10.1007/978-3-319-26617-6_7

Banik, S., Isobe, T.: Some cryptanalytic results on lizard. Cryptology ePrint Archive Report 2017/346. http://eprint.iacr.org/2017/346 (2017)

Barkan, E., Biham, E.: Conditional estimators: An effective attack on A5/1. In: Preneel, B., Tavares, S. (eds.) Selected Areas in Cryptography: 12th International Workshop, SAC 2005, Kingston, ON, Canada, August 11-12, 2005, Revised Selected Papers, pp. 1–19. Springer, Berlin (2006). https://doi.org/10.1007/11693383_1

Biryukov, A.: LEX. eSTREAM: The ECRYPT Stream Cipher Project. http://www.ecrypt.eu.org/stream/lexp3.html (2005)

Biryukov, A., Perrin, L.: State of the Art in Lightweight Symmetric Cryptography. Cryptology ePrint Archive Report 2017/511. http://eprint.iacr.org/2017/511 (2017)

10.

Biryukov, A., Shamir, A.: Cryptanalytic time/memory/data tradeoffs for stream ciphers. In: Okamoto, T. (ed.) Advances in Cryptology — ASIACRYPT 2000: 6th International Conference on the Theory and Application of Cryptology and Information Security Kyoto, Japan, December 3–7, 2000 Proceedings, pp. 1–13. Springer, Berlin (2000). https://doi.org/10.1007/3-540-44448-3_1

11.

Bjørstad, T.E.: Cryptanalysis of Grain using Time/Memory/Date Tradeoffs. eSTREAM, ECRYPT Stream Cipher Project Report 2008/012. http://www.ecrypt.eu.org/stream/papersdir/2008/012.pdf (2008)

12.

Bogdanov, A., Knudsen, L.R., Leander, G., Paar, C., Poschmann, A., Robshaw, M.J.B., Seurin, Y., Vikkelsoe, C.: PRESENT: An ultra-lightweight block cipher. In: Paillier, P., Verbauwhede, I. (eds.) Cryptographic Hardware and Embedded Systems - CHES 2007: 9th International Workshop, Vienna, Austria, September 10-13, 2007. Proceedings, pp. 450–466. Springer, Berlin (2007). https://doi.org/10.1007/978-3-540-74735-2_31

13.

Briceno, M., Goldberg, I., Wagner, D.: A pedagogical implementation of a5/1. http://www.scard.org/gsm/a51.html (1999)

14.

Cannière, C.D., Preneel, B.: Trivium – Specifications eSTREAM: The ECRYPT Stream Cipher Project. http://www.ecrypt.eu.org/stream/p3ciphers/trivium/trivium_p3.pdf (2005)

15.

Cole, P.H., Ranasinghe, D.C.: Networked RFID Systems and Lightweight Cryptography: Raising Barriers to Product Counterfeiting, first edn. Springer, Berlin (2008)CrossRef

16.

De Cannière, C., Dunkelman, O., Knežević, M.: KATAN and KTANTAN — A family of small and efficient hardware-oriented block ciphers. In: Clavier, C., Gaj, K. (eds.) Cryptographic Hardware and Embedded Systems - CHES 2009: 11th International Workshop Lausanne, Switzerland, September 6-9, 2009 Proceedings, pp. 272–288. Springer, Berlin (2009). https://doi.org/10.1007/978-3-642-04138-9_20

17.

Dey, S., Sarkar, S.: Cryptanalysis of full round Fruit. Cryptology ePrint Archive Report 2017/87. http://eprint.iacr.org/2017/87.pdf (2017)

18.

Dierks, T., Rescorla, E.: The Transport Layer Security (TLS) Protocol Version 1.2. RFC 5246 (Proposed Standard). http://www.ietf.org/rfc/rfc5246.txt. Updated by RFCs 5746, 5878, 6176, 7465, 7507, 7568, 7627, 7685, 7905, 7919 (2008)

19.

Dinur, I., Shamir, A.: Cube attacks on tweakable black box polynomials. In: Joux, A. (ed.) Advances in Cryptology - EUROCRYPT 2009: 28th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Cologne, Germany, April 26-30, 2009. Proceedings, pp. 278–299. Springer, Berlin (2009). https://doi.org/10.1007/978-3-642-01001-9_16

20.

ECRYPT – European Network of Excellence for Cryptology: eSTREAM: the ECRYPT stream cipher project. http://www.ecrypt.eu.org/stream/ (2008)

21.

Englund, H., Hell, M., Johansson, T.: A note on distinguishing attacks. In: 2007 IEEE Information Theory Workshop on Information Theory for Wireless Networks, pp. 1–4 (2007). https://doi.org/10.1109/ITWITWN.2007.4318038

22.

Esgin, M.F., Kara, O.: Practical cryptanalysis of full sprout with TMD tradeoff attacks. In: Dunkelman, O., Keliher, L. (eds.) Selected Areas in Cryptography - SAC 2015: 22nd International Conference, Sackville, NB, Canada, August 12-14, 2015, Revised Selected Papers, pp. 67–85. Springer International Publishing, Cham (2016). https://doi.org/10.1007/978-3-319-31301-6_4

23.

Fluhrer, S., Mantin, I., Shamir, A.: Weaknesses in the Key Scheduling Algorithm of RC4. In: Vaudenay, S., Youssef, A.M. (eds.) Selected Areas in Cryptography: 8th Annual International Workshop, SAC 2001 Toronto, Ontario, Canada, August 16–17, 2001 Revised Papers, pp. 1–24. Springer, Berlin (2001). https://doi.org/10.1007/3-540-45537-X_1

24.

Ghafari, V.A., Hu, H., Xie, C.: Fruit: Ultra-lightweight Stream Cipher with Shorter Internal State. Cryptology ePrint Archive Report 2016/355. http://eprint.iacr.org/2016/355 (2016)

25.

Ågren, M., Hell, M., Johansson, T., Meier, W.: Grain-128a: A new version of grain-128 with optional authentication. Int. J. Wireless Mobile Comput. 5(1), 48–59 (2011). https://doi.org/10.1504/IJWMC.2011.044106 CrossRef

26.

Hamann, M., Krause, M.: On Stream Ciphers with Provable Beyond-the-Birthday-Bound Security against Time-Memory-Data Tradeoff Attacks. Cryptology ePrint Archive Report 2015/636. http://eprint.iacr.org/2015/636 (2015)

27.

Hamann, M., Krause, M., Meier, W.: LIZARD – a lightweight stream cipher for power-constrained devices. IACR Trans. Symmetric Cryptology 2017(1), 45–79 (2017). https://doi.org/10.13154/tosc.v2017.i1.45-79

28.

Hamann, M., Krause, M., Meier, W., Zhang, B.: On Stream Ciphers with Small State. Early Symmetric Crypto (ESC), January 2017, Canach, Luxembourg. https://www.cryptolux.org/mediawiki-esc2017/images/c/c2/Smallstate.pdf

29.

Hao, Y.: A Related-key chosen-IV Distinguishing Attack on Full Sprout Stream Cipher. Cryptology ePrint Archive Report 2015/231. http://eprint.iacr.org/2015/231.pdf (2015)

30.

The grain family of stream ciphers. In: Hell, M., Johansson, T., Maximov, A., Meier, W., Robshaw, M., Billet, O. (eds.) New Stream Cipher Designs: The eSTREAM Finalists, pp. 179–190. Springer, Berlin (2008). https://doi.org/10.1007/978-3-540-68351-3_14

31.

Hell, M., Johansson, T., Meier, W.: Grain - A Stream Cipher for Constrained Environments eSTREAM: The ECRYPT Stream Cipher Project. http://www.ecrypt.eu.org/stream/p3ciphers/grain/Grain_p3.pdf (2006)

32.

Hong, J., Sarkar, P.: New Applications of Time Memory Data Tradeoffs, pp 353–372. Springer, Berlin (2005). https://doi.org/10.1007/11593447_19 MATH

33.

Institute of Electrical and Electronics Engineers: IEEE Standard for information technology – telecommunications and information exchange between systems – local and metropolitan area networks – specific requirements – part 11: Wireless LAN medium access control (MAC) and physical layer (PHY) specifications. IEEE Std 802.11-1997 pp. i–445. https://doi.org/10.1109/IEEESTD.1997.85951

34.

Institute of Electrical and Electronics Engineers: IEEE Standard for information technology – telecommunications and information exchange between systems – local and metropolitan area networks – specific requirements – part 11: Wireless LAN medium access control (MAC) and physical layer (PHY) specifications: Amendment 6: Medium access control (MAC) security enhancements. IEEE Std 802.11i-2004 pp. 1–190. https://doi.org/10.1109/IEEESTD.2004.94585 (2004)

35.

Krause, M.: On the Hardness of Trivium and Grain with respect to Generic Time-Memory-Data Tradeoff Attacks. Cryptology ePrint Archive Report 2017/289. http://eprint.iacr.org/2017/289 (2017)

36.

Lallemand, V., Naya-Plasencia, M.: Cryptanalysis of full sprout. In: Gennaro, R., Robshaw, M. (eds.) Advances in Cryptology – CRYPTO 2015: 35th Annual Cryptology Conference, Santa Barbara, CA, USA, August 16-20, 2015, Proceedings, Part I, pp. 663–682. Springer, Berlin. https://doi.org/10.1007/978-3-662-47989-6_32 (2015)

37.

Liu, M.: Degree Evaluation of NFSR-based Cryptosystems. To appear at Crypto 2017 (2017)

38.

Lu, Y., Meier, W., Vaudenay, S.: The conditional correlation attack: A practical attack on bluetooth encryption. In: Shoup, V. (ed.) Advances in Cryptology – CRYPTO 2005: 25th Annual International Cryptology Conference, Santa Barbara, California, USA, August 14-18, 2005. Proceedings, pp. 97–117. Springer, Berlin. https://doi.org/10.1007/11535218_7 (2005)

39.

Maitra, S., Sarkar, S., Baksi, A., Dey, P.: Key Recovery from State Information of Sprout. Cryptology ePrint Archive Report 2015/236. http://eprint.iacr.org/2015/236.pdf (2015)

40.

Méaux, P., Journault, A., Standaert, F.X., Carlet, C.: Towards stream ciphers for efficient FHE with low-noise ciphertexts. In: Fischlin, M., Coron, J.S. (eds.) Advances in Cryptology – EUROCRYPT 2016: 35th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Vienna, Austria, May 8-12, 2016, Proceedings, Part I, pp. 311–343. Springer, Berlin. https://doi.org/10.1007/978-3-662-49890-3_13 (2016)

41.

Meier, W., Staffelbach, O.: Fast correlation attacks on stream ciphers. In: Barstow, D., Brauer, W., Brinch Hansen, P., Gries, D., Luckham, D., Moler, C., Pnueli, A., Seegmüller, G., Stoer, J., Wirth, N., Günther, C.G. (eds.) Advances in Cryptology — EUROCRYPT ’88: Workshop on the Theory and Application of Cryptographic Techniques Davos, Switzerland, May 25–27, 1988 Proceedings, pp. 301–314. Springer, Berlin. https://doi.org/10.1007/3-540-45961-8_28 (1988)

42.

Mikhalev, V., Armknecht, F., Müller, C.: On ciphers that continuously access the non-volatile key. IACR Trans. Symmetric Cryptology 2016(2), 52–79 (2017). https://doi.org/10.13154/tosc.v2016.i2.52-79. http://tosc.iacr.org/index.php/ToSC/article/view/565

43.

Popov, A.: Prohibiting RC4 cipher suites RFC 7465 (proposed standard). http://www.ietf.org/rfc/rfc7465.txt (2015)

44.

Poschmann, A.: Lightweight Cryptography - Cryptographic Engineering for a Pervasive World. Cryptology ePrint Archive Report 2009/516. http://eprint.iacr.org/2009/516 (2009)

45.

Schneier, B.: Applied Cryptography (2nd Ed.): Protocols, Algorithms, and Source Code in C. Wiley, New York (1995)MATH

46.

SIG, B.: Bluetooth Core Specification 4.2. https://www.bluetooth.org/DocMan/handlers/DownloadDoc.ashx?doc_id=286439 (2014)

47.

Subhamoy Maitra, A.S.: A differential fault attack on plantlet. Cryptology ePrint Archive Report 2017/088. http://eprint.iacr.org/2017/088 (2017)

48.

Todo, Y.: Structural evaluation by generalized integral property. In: Oswald, E., Fischlin, M. (eds.) Advances in Cryptology – EUROCRYPT 2015: 34th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Sofia, Bulgaria, April 26-30, 2015, Proceedings, Part I, pp. 287–314. Springer, Berlin. https://doi.org/10.1007/978-3-662-46800-5_12 (2015)

49.

Todo, Y., Isobe, T., Hao, Y., Meier, W.: Cube Attacks on Non-Blackbox Polynomials Based on Division Property. Cryptology ePrint Archive, Report 2017/306 (to appear at Crypto 2017). http://eprint.iacr.org/2017/306 (2017)

50.

Wu, H.: Acorn v3 Submission to CAESAR competition (2016)

51.

Zhang, B., Gong, X.: Another tradeoff attack on sprout-like stream ciphers. In: Iwata, T., Cheon, H.J. (eds.) Advances in Cryptology – ASIACRYPT 2015: 21st International Conference on the Theory and Application of Cryptology and Information Security, Auckland, New Zealand, November 29 – December 3, 2015, Proceedings, Part II, pp. 561–585. Springer, Berlin. https://doi.org/10.1007/978-3-662-48800-3_23 (2015)

Title: Design and analysis of small-state grain-like stream ciphers
Authors: Matthias Hamann
Matthias Krause
Willi Meier
Bin Zhang
Publication date: 08-11-2017
Publisher: Springer US
Published in: Cryptography and Communications / Issue 5/2018
Print ISSN: 1936-2447
Electronic ISSN: 1936-2455
DOI: https://doi.org/10.1007/s12095-017-0261-6

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Other articles of this Issue 5/2018

On rate-1 and beyond-the-birthday bound secure online ciphers using tweakable block ciphers

Statistical properties of side-channel and fault injection attacks using coding theory

A note on the chi-square method: A tool for proving cryptographic security

Statistical integral distinguisher with multi-structure and its application on AES-like ciphers

Success probability of multiple/multidimensional linear cryptanalysis under general key randomisation hypotheses

Guest editorial

Premium Partner