## 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 * inverting one-way function with data*, the problem of

*and the problem of*mutual inverting of multiple one-way functions

*. Moreover, we address these problems with block ciphers and raise a question about the hierarchical relationships between any pair of them.*inverting only one of the several independent one-way functions

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 * inverting one-way function with data*as follows. Let

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 * et al.*introduce an efficient way of ruling out the false alarms, particularly in the perfect tables [28].

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 * et al.*compares these two methods and combine them in a general model based on stateful random graphs [30]. They also improve the time complexity of the rainbow tables [30]. Lu

*use the unified rainbow tables to break GSM A5/1 algorithm and recover an A5/1 key in 9 s with a success rate of 81% by using general purpose GPUs with 3 NVIDIA GeForce GTX690 cards [12]. There are also FPGA implementation versions of tracing through the rainbow tables of the A5/1 states [10, 11]. The success rates of the rainbow tables for A5/1 are improved in [12]. Rainbow tables are commonly used to invert hash functions and crack passwords [13, 14, 15, 16, 17]. Even though rainbow tables are ubiquitously used in the real world applications, Biryukov*et al.

*show that Hellman tables are superior to rainbow tables in multiple data scenario [31].*et al.

## 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 * mutual inverting of multiple one-way functions*where

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.

## Conflict of interest

The authors declare no conflict of interest.

## Notes

- Permutations as one-way functions are out of scope of this chapter.