This page uses content from Wikipedia and is licensed under CC BY-SA.
A time/memory/data tradeoff attack is a type of cryptographic attack where an attacker tries to achieve a situation similar to the space–time tradeoff but with one more parameter data: amount of data available to the attacker at real time. An attacker balances or reduces one or two of those parameters in favor of the other one or two. This type of attack is very hard and most of the ciphers and encryption schemes were not designed to resist such type of attack. This attack is a special type of the general cryptanalytic time/memory tradeoff attack.
Tradeoff attacks on symmetric cryptosystems dates back to 1980 when Hellman suggested a time/memory tradeoff method to break block ciphers with possible keys in time and memory related by the tradeoff curve where .^{[1]} Later, Babbage and Golic devised a different tradeoff attack for stream ciphers with a new bound such that for and is the output data available to the cryptanalyst at real time.^{[2]}^{[3]}
This attack is a special type of the general cryptanalytic time/memory tradeoff attack. A general time/memory tradeoff attack has two main phases:
Any time/memory/data tradeoff attack has the following parameters:
For block ciphers, is the total number of possible keys and also assume the number of possible plaintexts and ciphertexts to be . Also let the given data be a single ciphertext block of a specific plaintext counterpart. If we consider the mapping from the key to the ciphertext as a random permutation function over an point space, and if this function is invertible; we need to find the inverse of this function . Hellman's technique to invert this function:
According to Hellman, if the block cipher at hand has the property that the mapping from its key to cipher text is a random permutation function over an point space, and if this is invertible, the tradeoff relationship becomes ways better: .
For stream ciphers, is specified by the number of internal states of the bit generator - probably different from the number of keys. is the count of the first pseudorandom bits produced from the generator. Finally, the attacker goal is to find one of the actual internal states of the bit generator to be able to run the generator from this point on to generate the rest of the key. Associate each of the possible internal states of the bit generator with the corresponding string that consists of the first bits obtained by running the generator from that state by the mapping from states to output prefixes . This previous mapping is considered a random function over the points common space. To invert this function, an attacker establishes the following.
This result from the Birthday attack gives the condition with attack time and preprocessing time which is just a particular point on the tradeoff curve . We can generalize this relation if we ignore some of the available data at real time and we are able to reduce from to and the general tradeoff curve eventually becomes with and .
This novel idea introduced in 2000 combines both techniques: Hellman tradeoff^{[1]} and Babbage-and-Golic tradeoff^{[2]}^{[3]} attacks to achieve a new tradeoff curve with better bounds for stream ciphers cryptoanalysis. You can apply Hellman's block cipher technique to stream cipher by using the same idea of covering the points space through matrices obtained from multiple variants of the function which is the mapping of internal states to output prefixes. Recall that this tradeoff attack on stream cipher is successful if any of the given output prefixes is found in any of the matrices covering . Therefore, we can cut the number of covered points by the matrices from to points. This is done by reducing the number of matrices from to while keeping as large as possible (but this requires to have at least one table). For this new attack, we have because we reduced the number of matrices to and the same for the preprocessing time . The realtime required for the attack is which is the product of the number of matrices, length of each iteration and number of available data points at attack time.
Eventually, we again use the matrix stopping rule to obtain the tradeoff curve for (because ).
This attack was invented by Biryukov, Shamir, Wagner. The idea relies on the following feature of various stream ciphers: the bit generator undergoes only few changes in its internal state before producing the next output bit. Therefore, we can enumerate those special states that generate zero bits for small values of at low cost. But when forcing large number of output bits to take specific values, this enumeration process become very expensive and difficult. Now, we can define the sampling resistance of a stream cipher to be with the maximum value which makes such enumeration feasible.
Let the stream cipher be of states each has a full name of bits and a corresponding output name which is the first bits in the output sequence of bits. If this stream cipher has sampling resistance , then an efficient enumeration can use a short name of bits to define the special states of the generator. Each special state with short name has a corresponding short output name of bits which is the output sequence of the special state after removing the first leading bits. Now, we are able to define a new mapping over a reduced space of points and this mapping is equivalent to the original mapping. If we let , the realtime data available to the attacker is guaranteed to have at least one output of those special states. Otherwise, we relax the definition of special states to include more points. If we substitute for by and by in the new time/memory/data tradeoff attack by Shamir and Biryukov, we obtain the same tradeoff curve but with . This is actually an improvement since we could relax the lower bound on since can be small up to which means that our attack can be made faster. Another advantage of this technique is that we reduced the number of expensive disk access operations from to since we will be accessing only the special points. And this also can greatly make our attack faster because of the reduced number of expensive disk operations.