Abstract
Tradeoff attacks on symmetric ciphers can be considered as the generalization of the exhaustive search. Their main objective is reducing the time complexity by exploiting the memory after preparing very large tables at a cost of exhaustively searching all the space during the precomputation phase. It is possible to utilize data (plaintext/ciphertext pairs) in some cases like the internal state recovery attacks for stream ciphers to speed up further both online and offline phases. However, how to take advantage of data in a tradeoff attack against block ciphers for single key recovery cases is still unknown. We briefly assess the state of art of tradeoff attacks on symmetric ciphers, introduce some open problems and discuss the security criterion on state sizes. We discuss the strict lower bound for the internal state size of keystream generators and propose more practical and fair bound along with our reasoning. The adoption of our new criterion can break a fresh ground in boosting the security analysis of small keystream generators and in designing ultra-lightweight stream ciphers with short internal states for their usage in specially low source devices such as IoT devices, wireless sensors or RFID tags.
Keywords
- symmetric cipher
- block cipher
- stream cipher
- tradeoff attack
- keystream
- keystream generator
- Hellman table
- rainbow table
- one-way function
- preimage
1. Introduction
In general, bulk encryption is performed through symmetric ciphers; that is, block ciphers or stream ciphers. Hash functions, message authentication codes and authenticated encryption schemes are also based on the quite similar design and security principles. All these cryptographic primitives are examples of one-way functions for which it must be computationally infeasible to find a preimage. Indeed, the only generic method to invert a given output is exhaustively searching for one of its inputs.1 This may be embodied as brute force attacks on block ciphers and stream ciphers, internal state recovery attacks on keystream generators, preimage attacks on hash functions or constructing valid messages to given tag values for message authentication codes.
The brute force attacks can be expedited significantly by utilizing very large tables that have been already prepared during the offline phase. This phase is called the precomputation phase also and is usually equivalent to exhaustive search. Nevertheless, once it is executed, the prepared tables can be used several times.
It may be possible to further improve a tradeoff attack by exploiting large amount of data (plaintext/ciphertext pairs). Biryukov-Shamir attack on keystream generators can be considered as a typical example of a tradeoff among time, memory and data [1]. One of the internal states of a long keystream sequence is recovered. However, it is still unknown how to use data to improve the tradeoff attacks on block ciphers.
The state sizes of block ciphers are not of security concern against tradeoff attacks, enabling to design ultra-lightweight block ciphers. In fact, we encounter several such block cipher designs in the literature during the last decades [2, 3, 4, 5, 6, 7, 8, 9]. However, it seems to be almost impossible to design ultra-lightweight stream ciphers due to their strict security criterion on the lower bound of their internal state sizes to resist tradeoff attacks.
The tradeoff attacks can be quite effective against some real world cryptographic primitives. The tradeoff tables can be used in practical applications to break real life ciphers such as A5/1 for the GSM encryption [10, 11, 12] or to crack passwords by finding preimages to hash functions [13, 14, 15, 16, 17]. In this chapter, we introduce briefly how to use tradeoff tables to invert small sized one-way functions. Moreover, we evaluate the state of art of the applications, raise some open problems and come up with a discussion on the countermeasures against tradeoff attacks on keystream generators.
We argue that it is possible to loosen the lower bound for the state size without sacrificing the security against tradeoff attacks and this can enable designing ultra-lightweight stream ciphers. We claim that the lower bound for the internal state size can be diminished to
It is straightforward that resistance against tradeoff attacks is not sufficient for security. Unfortunately, the security of small stream ciphers has not been studied sufficiently so far. We still do not know how to design secure and small stream ciphers. This is due to fact that almost all the stream ciphers in the literature have internal state sizes at least twice as large as their key sizes. Hence, there is almost no example in the literature to analyze. The recent small keystream generators such as Sprout [18] or Plantlet [19] are analyzed intensively in a short while and several weaknesses are discovered [20, 21, 22, 23, 24, 25, 26].
The tradeoff attacks on block ciphers so far are limited to the tradeoff between only time and memory. It is an open problem how to construct a tradeoff curve between memory and data or among memory, data and time for a single key recovery attack. We phrase the problem of
The outline of the chapter is as follows. We briefly overview the tradeoff attacks on symmetric ciphers, give some recent applications of these attacks and evaluate them in Section 2. Then, we assess the tradeoff attacks on stream ciphers and keystream generators in Section 3. We also introduce the tradeoff attacks on block ciphers, discuss the differences from those on stream ciphers and state some open problems in Section 4. We assess the internal state recovery tradeoff attacks and make an argument about the internal state sizes of keystream generators in Section 5. Finally, we introduce our concluding remarks in Section 6.
2. Inverting a one-way function through tradeoff
Let
The phrase” computationally infeasible” is not a formal or a precise statement. Indeed, we mean that the fastest algorithm of finding a preimage
The time complexity may be substituted by the memory complexity if we compute all the
In general, we can regard the tradeoff attacks as the attacks searching for a preimage of a one-way function by utilizing a significant memory prepared in the precomputation phase to reduce the time complexity from
It is possible to ease the problem of inverting a one-way function
We can define the problem of
It is possible to address the problem of inverting one-way function with data in stream ciphers and mount some tradeoff attacks for single key setting. We introduce these attacks in Section 3. However, it is not known in the literature yet how to associate a single key recovery attack for a block cipher as a problem of inverting one-way function with data (see Section 4 for details of the tradeoff attacks in the case of block ciphers).
2.1 Hellman and rainbow tables
One very well known way of inverting a one-way function is using Hellman tables [27]. Initially, Hellman introduced the tables only for recovering the DES keys in his original work in [27] but it can be used to invert any one-way function.
Let us assume that the input and the output sizes of a one-way function,
If a given value
Therefore, it is highly probable that
Choosing
The most significant disadvantage of Hellman tables is the high propagation of the collisions throughout the rows. If
The time complexity is
Oechslin introduces another kind of tables to invert one-way functions, which he calls rainbow tables [29]. He proposes to use a different function for the computation of each column and hence each row is constituted as
instead of
Rainbow tables have a significant advantage over Hellman tables: The collisions in different columns do not propagate in rainbow tables. So, it is possible to use only one rainbow table for covering majority of the space
Both the Hellman tables and the rainbow tables have the same tradeoff curve. But, the time complexity is
Barkan
3. Tradeoff attacks on stream ciphers
The main building blocks of (synchronous) stream ciphers are keystream generators. The most general design principle of keystream generators make use of a state update function
The objective of the attacks on stream ciphers is twofold in general. They aim at either recovering the key or an internal state. The same approach is adopted for tradeoff attacks. The state recovery attacks are conventional examples of the problem of inverting one-way function with data in a single key attack scenario. Indeed, it is enough to recover one of the internal states occurred during the encryption process.
Babbage [32] and Golić [33] independently introduce a natural way of recovering one of the internal states by using data. They define a one-way function by extending the output function which produces enough number of output bits by calling
Another tradeoff attack on keystream generators using data is introduced by Biryukov and Shamir [1]. They propose to use Hellman tables to recover one of the internal states which produce
Both the Babbage-Golić attack and the Biryukov-Shamir attack aim at recovering one of the internal states. The online phases of these attacks are compared with the exhaustive search rather than the default tradeoff attacks. The attacks use multiple data since the one-way function they would like to invert has several outputs available. On the other hand, it is possible to define the one-way function as the function taking the
Armknecht and Mikhalev examine the keyed update functions and show that the keystream generators with keyed state update functions are secure against conventional tradeoff attacks no matter how small the internal state sizes are [18]. They also introduce an example cipher they call Sprout [18]. A keyed state update function takes the main key as the second parameter of the input to produce the next internal state from the current internal state.
The cipher Sprout is analyzed intensively in a short while and some weaknesses are discovered [20, 22]. More interestingly, special tradeoff attacks are mounted [21, 23]. Then, Armknecht and Mikhalev present another keystream generator with keyed state update. They call it Plantlet [19]. This cipher also attains significant interests of cyrptanalysts and several results are published including correlation attacks [24, 25, 26, 37, 38], some of them are even faster than exhaustive search [25]. It seems that it is indeed a challenging task for the crypto community to design keystream generators of small state sizes even if the tradeoff attacks are ignored in their security assessments.
4. Tradeoff attacks on block ciphers
Let
It is possible to invert
There is no known method of using multiple data to improve the tradeoff curve
and
Choosing
The problem may further be generalized as inverting only one of the
be given for
The problem of mutual inverting multiple one-way functions can be applied to stream ciphers also. Several one-way functions may be defined by choosing several
where
It may be still possible to use any number of
It seems that inverting only one specific one-way function once is not easier than the other two problems. One can use the algorithm of inverting a one-way function to invert one of
It is not known yet if these three problems are of equal difficulty. It is an open problem if the mutual inverting problem is strictly easier than the problem of inverting one of the several one-way functions. It is also an open problem that inverting one of the several one-way functions is strictly easier than inverting only one one-way function. If there is an algorithm solving problem of mutual inverting problem but not solving the problem of inverting one-way function then the security levels and the key lengths for both block ciphers and stream ciphers must be assessed again. Because, the algorithms solving mutual inverting problems efficiently can be very powerful and serious attacks on symmetric ciphers.
5. Assessment of security criterion on state size
The online complexities of both the Babbage-Golić and the Biryukov-Shamir attacks are compared to the complexity of the exhaustive search and the security criterion on the state size of a stream cipher is imposed thereof. However, there is still a faster tradeoff attack even though the internal state size is larger than twice of the key size. It is possible to define a one-way function from a main key to its keystream piece of a stream cipher by choosing and fixing an
Any tradeoff attack on symmetric ciphers should be compared with the default tradeoff attack with its complexity
Recall that we have the tradeoff curve
Similarly, the optimum point of the tradeoff curve for the Biryukov-Shamir attack is
As a result, the tradeoff attacks aiming at the internal state recovery should be compared to the default tradeoff key recovery attack. Then, it is possible to loosen the restriction on the state size from
6. Conclusions
We briefly introduce the tradeoff attacks on symmetric ciphers and initiate hopefully a fruitful discussion about how to assess the degree of precautions or countermeasure to be taken against these attacks.
The tradeoff attacks targeting at recovering one of the internal states producing a given keystream sequence are compared to the exhaustive search attack on the corresponding key used. However, a stream cipher key can be recovered much faster thorough the default tradeoff attack. Therefore, the internal state recovery tradeoff attacks should be compared to the default key recovery tradeoff attack. In this case, it is possible to loosen the bound for the countermeasure taken against state recovery tradeoff attacks.
The internal state size is supposed to be at least twice as large as the key size if the security threshold for tradeoff attacks is taken as the complexity of the exhaustive search. This is indeed a well known and worldwide adopted security criterion. We argue that it is indeed not necessary to allocate such large internal state just for the resistance against tradeoff attacks. The internal state size is enough to be at least
We believe that it is a challenging task to design small stream ciphers and the industry requires such ciphers to use in lightweight applications such as IoT devices, wireless sensors or RFID tags.
Acknowledgments
We would like to thank Mehmet Sabır Kiraz, Ali Aydın Selçuk and Sırrı Erdem Ulusoy for their helpful comments. We also would like to thank IntechOpen LIMITED for the grant.
References
- 1.
A. Biryukov and A. Shamir, “Cryptanalytic time/memory/data tradeoffs for stream ciphers,” in Advances in Cryptology - ASIACRYPT 2000 , vol. 1976 ofLNCS , pp. 1–13, Springer, 2000 - 2.
B. Aboushosha, R. A. Ramadan, A. D. Dwivedi, A. El-Sayed, and M. M. Dessouky, “SLIM: A lightweight block cipher for internet of health things,” IEEE Access , vol. 8, pp. 203747–203757, 2020 - 3.
K. Shibutani, T. Isobe, H. Hiwatari, A. Mitsuda, T. Akishita, and T. Shirai, “Piccolo: An ultra-lightweight blockcipher,” in Cryptographic Hardware and Embedded Systems - CHES 2011 - 13th International Workshop, Nara, Japan, September 28–October 1, 2011. Proceedings (B. Preneel and T. Takagi, eds.), vol. 6917 ofLecture Notes in Computer Science , pp. 342–357, Springer, 2011 - 4.
L. Li, B. Liu, and H. Wang, “QTL: A new ultra-lightweight block cipher,” Microprocess. Microsystems , vol. 45, pp. 45–55, 2016 - 5.
Z. Gong, S. Nikova, and Y. W. Law, “KLEIN: A new family of lightweight block ciphers,” in RFID. Security and Privacy - 7th International Workshop, RFIDSec 2011, Amherst, USA, June 26–28, 2011, Revised Selected Papers (A. Juels and C. Paar, eds.), vol. 7055 ofLecture Notes in Computer Science , pp. 1–18, Springer, 2011 - 6.
H. AlKhzaimi and M. M. Lauridsen, “Cryptanalysis of the SIMON family of block ciphers,” IACR Cryptol. ePrint Arch. , vol. 2013, p. 543, 2013 - 7.
W. Wu and L. Zhang, “Lblock: A lightweight block cipher,” in Applied Cryptography and Network Security - 9th International Conference, ACNS 2011, Nerja, Spain, June 7–10, 2011. Proceedings (J. López and G. Tsudik, eds.), vol. 6715 ofLecture Notes in Computer Science , pp. 327–344, 2011 - 8.
J. Guo, T. Peyrin, A. Poschmann, and M. J. B. Robshaw, “The LED block cipher,” in Cryptographic Hardware and Embedded Systems - CHES 2011 - 13th International Workshop, Nara, Japan, September 28–October 1, 2011. Proceedings (B. Preneel and T. Takagi, eds.), vol. 6917 ofLecture Notes in Computer Science , pp. 326–341, Springer, 2011 - 9.
C. D. Cannière, O. Dunkelman, and M. Knezevic, “KATAN and KTANTAN - A family of small and efficient hardware-oriented block ciphers,” in Cryptographic Hardware and Embedded Systems - CHES 2009, 11th International Workshop, Lausanne, Switzerland, September 6–9, 2009, Proceedings (C. Clavier and K. Gaj, eds.), vol. 5747 ofLecture Notes in Computer Science , pp. 272–288, Springer, 2009 - 10.
M. Kalenderi, D. N. Pnevmatikatos, I. Papaefstathiou, and C. Manifavas, “Breaking the GSM A5/1 cryptography algorithm with rainbow tables and high-end FPGAS,” in 22nd International Conference on Field Programmable Logic and Applications (FPL), Oslo, Norway, August 29–31, 2012 (D. Koch, S. Singh, and J. Tørresen, eds.), pp. 747–753, IEEE, 2012 - 11.
P. Papantonakis, D. N. Pnevmatikatos, I. Papaefstathiou, and C. Manifavas, “Fast, fpga-based rainbow table creation for attacking encrypted mobile communications,” in 23rd International Conference on Field programmable Logic and Applications, FPL 2013, Porto, Portugal, September 2–4, 2013 , pp. 1–6, IEEE, 2013 - 12.
Z. Li, “Optimization of rainbow tables for practically cracking GSM A5/1 based on validated success rate modeling,” in Topics in Cryptology - CT-RSA 2016 - The Cryptographers’ Track at the RSA Conference 2016, San Francisco, CA, USA, February 29–March 4, 2016, Proceedings (K. Sako, ed.), vol. 9610 ofLecture Notes in Computer Science , pp. 359–377, Springer, 2016 - 13.
J. Bieniasz, K. Skowron, M. Trzepinski, M. Rawski, P. Sapiecha, and P. Tomaszewicz, “Hardware implementation of rainbow tables generation for hash function cryptanalysis,” in Information Systems Architecture and Technology: Proceedings of 36th International Conference on Information Systems Architecture and Technology - ISAT 2015 - Part II, Karpacz, Poland, September 20–22, 2015 (A. Grzech, L. Borzemski, J. Swiatek, and Z. Wilimowska, eds.), vol. 430 ofAdvances in Intelligent Systems and Computing , pp. 189–200, Springer, 2015 - 14.
G. Avoine, A. Bourgeois, and X. Carpent, “Analysis of rainbow tables with fingerprints,” in Information Security and Privacy - 20th Australasian Conference, ACISP 2015, Brisbane, QLD, Australia, June 29–July 1, 2015, Proceedings (E. Foo and D. Stebila, eds.), vol. 9144 ofLecture Notes in Computer Science , pp. 356–374, Springer, 2015 - 15.
J. Horalek, F. Holík, O. Horák, L. Petr, and V. Sobeslav, “Analysis of the use of rainbow tables to break hash,” J. Intell. Fuzzy Syst. , vol. 32, no. 2, pp. 1523–1534, 2017 - 16.
H. Ying and N. Kunihiro, “Decryption of frequent password hashes in rainbow tables,” in Fourth International Symposium on Computing and Networking, CANDAR 2016, Hiroshima, Japan, November 22–25, 2016 , pp. 655–661, IEEE Computer Society, 2016 - 17.
G. Avoine, X. Carpent, and C. Lauradoux, “Interleaving cryptanalytic time-memory trade-offs on non-uniform distributions,” in Computer Security - ESORICS 2015 - 20th European Symposium on Research in Computer Security, Vienna, Austria, September 21–25, 2015, Proceedings, Part I (G. Pernul, P. Y. A. Ryan, and E. R. Weippl, eds.), vol. 9326 ofLecture Notes in Computer Science , pp. 165–184, Springer, 2015 - 18.
F. Armknecht and V. Mikhalev, “On lightweight stream ciphers with shorter internal states,” in Fast Software Encryption - 22nd International Workshop, FSE 2015, Istanbul, Turkey, March 8–11, 2015, Revised Selected Papers (G. Leander, ed.), vol. 9054 ofLecture Notes in Computer Science , pp. 451–470, Springer, 2015 - 19.
V. Mikhalev, F. Armknecht, and C. Müller, “On ciphers that continuously access the non-volatile key,” IACR Trans. Symmetric Cryptol. , vol. 2016, no. 2, pp. 52–79, 2016 - 20.
V. Lallemand and M. Naya-Plasencia, “Cryptanalysis of full sprout,” in Advances in Cryptology - CRYPTO 2015 - 35th Annual Cryptology Conference, Santa Barbara, CA, USA, August 16–20, 2015, Proceedings, Part I (R. Gennaro and M. Robshaw, eds.), vol. 9215 ofLecture Notes in Computer Science , pp. 663–682, Springer, 2015 - 21.
B. Zhang and X. Gong, “Another tradeoff attack on sprout-like stream ciphers,” in 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 (T. Iwata and J. H. Cheon, eds.), vol. 9453 ofLecture Notes in Computer Science , pp. 561–585, Springer, 2015 - 22.
S. Maitra, S. Sarkar, A. Baksi, and P. Dey, “Key recovery from state information of sprout: Application to cryptanalysis and fault attack,” IACR Cryptol. ePrint Arch. , vol. 2015, p. 236, 2015 - 23.
M. F. Esgin and O. Kara, “Practical cryptanalysis of full sprout with TMD tradeoff attacks,” in Selected Areas in Cryptography - SAC 2015 - 22nd International Conference, Sackville, NB, Canada, August 12–14, 2015, Revised Selected Papers (O. Dunkelman and L. Keliher, eds.), vol. 9566 ofLecture Notes in Computer Science , pp. 67–85, Springer, 2015 - 24.
O. Kara and M. F. Esgin, “On analysis of lightweight stream ciphers with keyed update,” IEEE Trans. Computers , vol. 68, no. 1, pp. 99–110, 2019 - 25.
S. Banik, K. Barooti, and T. Isobe, “Cryptanalysis of plantlet,” IACR Trans. Symmetric Cryptol. , vol. 2019, no. 3, pp. 103–120, 2019 - 26.
Y. Todo, W. Meier, and K. Aoki, “On the data limitation of small-state stream ciphers: Correlation attacks on fruit-80 and plantlet,” in Selected Areas in Cryptography - SAC 2019 - 26th International Conference, Waterloo, ON, Canada, August 12–16, 2019, Revised Selected Papers (K. G. Paterson and D. Stebila, eds.), vol. 11959 ofLecture Notes in Computer Science , pp. 365–392, Springer, 2019 - 27.
M. E. Hellman, “A cryptanalytic time-memory trade-off,” IEEE Transactions on Information Theory , vol. 26, no. 4, pp. 401–406, 1980 - 28.
G. Avoine, P. Junod, and P. Oechslin, “Characterization and improvement of time-memory trade-off based on perfect tables,” ACM Trans. Inf. Syst. Secur. , vol. 11, no. 4, pp. 17:1–17:22, 2008 - 29.
P. Oechslin, “Making a faster cryptanalytic time-memory trade-off,” in Advances in Cryptology - CRYPTO 2003, 23rd Annual International Cryptology Conference, Santa Barbara, California, USA, August 17–21, 2003, Proceedings (D. Boneh, ed.), vol. 2729 ofLecture Notes in Computer Science , pp. 617–630, Springer, 2003 - 30.
E. Barkan, E. Biham, and A. Shamir, “Rigorous bounds on cryptanalytic time/memory tradeoffs,” in Advances in Cryptology - CRYPTO 2006, 26th Annual International Cryptology Conference, Santa Barbara, California, USA, August 20–24, 2006, Proceedings (C. Dwork, ed.), vol. 4117 ofLecture Notes in Computer Science , pp. 1–21, Springer, 2006 - 31.
A. Biryukov, S. Mukhopadhyay, and P. Sarkar, “Improved time-memory trade-offs with multiple data,” in Selected Areas in Cryptography, 12th International Workshop, SAC 2005, Kingston, ON, Canada, August 11–12, 2005, Revised Selected Papers (B. Preneel and S. E. Tavares, eds.), vol. 3897 ofLecture Notes in Computer Science , pp. 110–127, Springer, 2005 - 32.
S. Babbage, “Improved exhaustive search attacks on stream ciphers.” Security and Detection 1995, European Convention IET, 1995 - 33.
J. D. Golić, “Cryptanalysis of alleged A5 stream cipher,” in EUROCRYPT ‘97 , vol. 1233 ofLNCS , pp. 239–255, Springer, 1997 - 34.
B. Preneel, NESSIE Project , pp. 408–413. Boston, MA: Springer US, 2005 - 35.
M. Robshaw, “The estream project,” in New Stream Cipher Designs - The eSTREAM Finalists (M. J. B. Robshaw and O. Billet, eds.), vol. 4986 ofLecture Notes in Computer Science , pp. 1–6, Springer, 2008 - 36.
V. Rijmen, “Stream ciphers and the estream project,” ISC Int. J. Inf. Secur. , vol. 2, no. 1, pp. 3–11, 2010 - 37.
J. Copeland and L. Simpson, “Finding slid pairs for the plantlet stream cipher,” in Proceedings of the Australasian Computer Science Week, ACSW 2020, Melbourne, VIC, Australia, February 3–7, 2020 (P. P. Jayaraman, D. Georgakopoulos, T. K. Sellis, and A. Forkan, eds.), pp. 7:1–7:7, ACM, 2020 - 38.
S. Wang, M. Liu, D. Lin, and L. Ma, “Fast correlation attacks on grain-like small state stream ciphers and cryptanalysis of plantlet, fruit-v2 and fruit-80,” IACR Cryptol. ePrint Arch. , vol. 2019, p. 763, 2019 - 39.
M. J. Mihaljević, S. Gangopadhyay, G. Paul, and H. Imai, “Generic cryptographic weakness of k -normal boolean functions in certain stream ciphers and cryptanalysis of Grain-128,”Periodica Mathematica Hungarica , vol. 65, no. 2, pp. 205–227, 2012
Notes
- Permutations as one-way functions are out of scope of this chapter.