Atime/memory/data tradeoff attack is a type ofcryptographic attack where an attacker tries to achieve a situation similar to thespace–time tradeoff but with the additional parameter ofdata, representing the amount of data available to the attacker. 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 difficult, so most of the ciphers and encryption schemes in use were not designed to resist it.^{[citation needed]}

Tradeoff attacks onsymmetric cryptosystems date back to 1980, whenMartin Hellman suggested a time/memory tradeoff method to breakblock ciphers with${\displaystyle N}$ possible keys in time${\displaystyle T}$ and memory${\displaystyle M}$ related by the tradeoff curve${\displaystyle T{M}^2=N^2}$ where${\displaystyle 1\le T\le N}$.^[1] Later, in 1995, Babbage and Golic devised a different tradeoff attack forstream ciphers with a new bound such that${\displaystyle TM=N}$ for${\displaystyle 1\le T\le D}$ where${\displaystyle D}$ is the output data available to the cryptanalyst at real time.^[2][3]

This attack is a special version of the general cryptanalytic time/memory tradeoff attack, which has two main phases:

1. Preprocessing:
   During this phase, the attacker explores the structure of the cryptosystem and is allowed to record their findings in large tables. This can take a long time.
2. Realtime:
   In this phase, the cryptanalyst is granted real data obtained from a specific unknown key. They then try to use this data with the precomputed table from thepreprocessing phase to find the particular key in as little time as possible.

Any time/memory/data tradeoff attack has the following parameters:

${\displaystyle N}$ search space size

${\displaystyle P}$ time required for thepreprocessing phase

${\displaystyle T}$ time required for therealtime phase

${\displaystyle M}$ amount of memory available to the attacker

${\displaystyle D}$ amount of realtime data available to the attacker

For block ciphers, let${\displaystyle N}$ be the total number of possible keys and also assume the number of possible plaintexts and ciphertexts to be${\displaystyle N}$. Also let the given data be a single ciphertext block of a specific plaintext counterpart. If we consider the mapping from the key${\displaystyle x}$ to the ciphertext${\displaystyle y}$ as a random permutation function${\displaystyle f}$ over an${\displaystyle N}$ point space, and if this function${\displaystyle f}$ is invertible; we need to find the inverse of this function${\displaystyle f^{-1}(y)=x}$.Hellman's technique to invert this function:

During the preprocessing stage

Try to cover the${\displaystyle N}$ point space by an${\displaystyle m\times t}$ rectangular matrix that is constructed by iterating the function${\displaystyle f}$ on${\displaystyle m}$ random starting points in${\displaystyle N}$ for${\displaystyle t}$ times. The start points are the leftmost column in the matrix and the end points are the rightmost column. Then store the pairs of start and end points in increasing order of end points values.

Now, only one matrix will not be able to cover the whole${\displaystyle N}$ space. But if we add more rows to the matrix, we will end up with a huge matrix that includes recovered points more than once. So, we find the critical value of${\displaystyle m}$ at which the matrix contains exactly${\displaystyle m}$ different points. Consider the first${\displaystyle m}$ paths from start points to end points are all disjoint with${\displaystyle mt}$ points, such that the next path which has at least one common point with one of those previous paths and includes exactly${\displaystyle t}$ points. Those two sets of${\displaystyle mt}$ and${\displaystyle t}$ points are disjoint by thebirthday paradox if we make sure that${\displaystyle t\cdot mt\le N}$. We achieve this by enforcing thematrix stopping rule:${\displaystyle m{t}^2=N}$.

Nevertheless, an${\displaystyle m\times t}$ matrix with${\displaystyle m{t}^2=N}$ covers a portion${\displaystyle mt/N=1/t}$ of the whole space. To generate${\displaystyle t}$ to cover the whole space, we use a variant of${\displaystyle f}$ defined:${\displaystyle f_i(x)=h_i(f(x))}$ and${\displaystyle h_i}$ is simple out manipulation such as reordering of bits of${\displaystyle f(x)}$^[1] (refer to the original paper for more details). And one can see that the total preprocessing time is${\displaystyle P\approx N}$. Also${\displaystyle M=mt}$ since we only need to store the pairs of start and end points and we have${\displaystyle t}$ matrices each of${\displaystyle m}$ pairs.

During the real time phase

The total computation required to find${\displaystyle f^{-1}(y)}$ is${\displaystyle T=t^2}$ because we need to do${\displaystyle t}$ inversion attempts as it is likely to be covered by one matrix and each of the attempts takes${\displaystyle t}$ evaluations of some${\displaystyle f_i}$. The optimum tradeoff curve is obtained by using the matrix stopping rule${\displaystyle m{t}^2=N}$ and we get${\displaystyle T{M}^2=N^2,P=N,D=1}$ and choice of${\displaystyle T}$ and${\displaystyle M}$ depends on the cost of each resource.

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${\displaystyle f}$ over an${\displaystyle N}$ point space, and if this${\displaystyle f}$ is invertible, the tradeoff relationship becomes much better:${\displaystyle TM=N}$.

For stream ciphers,N is specified by the number of internal states of the bit generator—probably different from the number of keys.D is the count of the first pseudorandom bits produced from the generator. Finally, the attacker's 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 possibleN internal states of the bit generator with the corresponding string that consists of the first${\displaystyle \log (N)}$ bits obtained by running the generator from that state by the mapping${\displaystyle f(x)=y}$ from statesx to output prefixesy. This previous mapping is considered a random function over theN points common space. To invert this function, an attacker establishes the following.

1. During the preprocessing phase, pickM random${\displaystyle x_i}$ states and compute their corresponding${\displaystyle y_i}$ output prefixes.
2. Store the pairs${\displaystyle (x_i,y_i)}$ in increasing order of${\displaystyle y_i}$ in a large table.
3. During the realtime phase, you have${\displaystyle D+\log (N)-1}$ generated bits. Calculate from them allD possible combinations of${\displaystyle y_1,y_2,...,y_D,}$ of consecutive bits with length${\displaystyle \log (N)}$.
4. Search for each${\displaystyle y_i}$ in the generated table which takes log time.
5. If you have a hit, this${\displaystyle y_i}$ corresponds to an internal state${\displaystyle x_i}$ of the bit generator from which you can forward run the generator to obtain the rest of the key.
6. By theBirthday Paradox, you are guaranteed that two subsets of a space withN points have an intersection if the product of their sizes is greater thanN.

This result from the Birthday attack gives the condition${\displaystyle DM=N}$ with attack time${\displaystyle T=D}$ and preprocessing time${\displaystyle P=M}$ which is just a particular point on the tradeoff curve${\displaystyle TM=N}$. We can generalize this relation if we ignore some of the available data at real time and we are able to reduceT fromT=D to1 and the general tradeoff curve eventually becomes${\displaystyle TM=N}$ with${\displaystyle 1\le T\le D}$ and${\displaystyle P=M}$.

This novel idea introduced in 2000 combines the Hellman and Babbage-and-Golic tradeoff attacks to achieve a new tradeoff curve with better bounds for stream cipher cryptoanalysis.^[4] Hellman's block cipher technique can be applied to a stream cipher by using the same idea of covering the${\displaystyle N}$ points space through matrices obtained from multiple variants${\displaystyle f_i}$ of the function${\displaystyle f}$ 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${\displaystyle D}$ output prefixes is found in any of the matrices covering${\displaystyle N}$. This cuts the number of covered points by the matrices from${\displaystyle N}$ to${\displaystyle N/D}$ points. This is done by reducing the number of matrices from${\displaystyle t}$ to${\displaystyle t/D}$ while keeping${\displaystyle m}$ as large as possible (but this requires${\displaystyle t\ge D}$ to have at least one table).For this new attack, we have${\displaystyle M=mt/D}$ because we reduced the number of matrices to${\displaystyle t/D}$ and the same for the preprocessing time${\displaystyle P=N/D}$. The realtime required for the attack is${\displaystyle T=(t/D)\cdot t\cdot D=t^2}$ 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${\displaystyle T{M}^2{D}^2=t^2\cdot (m^2{t}^2/D^2)\cdot D^2=m^2{t}^4=N^2}$ for${\displaystyle D^2\le T\le N}$ (because${\displaystyle t\ge D}$).

This attack, invented byBiryukov,Shamir, andWagner, relies on a specific feature of some stream ciphers: that the bit generator undergoes only few changes in its internal state before producing the next output bit.^[5]Therefore, we can enumerate those special states that generate${\displaystyle k}$ zero bits for small values of${\displaystyle k}$ 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 thesampling resistance of a stream cipher to be${\displaystyle R=2^{-k}}$ with${\displaystyle k}$ the maximum value which makes such enumeration feasible.

Let the stream cipher be of${\displaystyle N=2^n}$ states each has afull name of${\displaystyle n}$ bits and a correspondingoutput name which is the first${\displaystyle n}$ bits in the output sequence of bits. If this stream cipher has sampling resistance${\displaystyle R=2^{-k}}$, then an efficient enumeration can use ashort name of${\displaystyle n-k}$ bits to define the special states of the generator. Each special state with${\displaystyle n-k}$short name has a correspondingshort output name of${\displaystyle n-k}$ bits which is the output sequence of the special state after removing the first${\displaystyle k}$ leading bits. Now, we are able to define a new mapping over a reduced space of${\displaystyle NR=2^{n-k}}$ points and this mapping is equivalent to the original mapping. If we let${\displaystyle DR\ge 1}$, 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${\displaystyle D}$ by${\displaystyle DR}$ and${\displaystyle N}$ by${\displaystyle NR}$ in the new time/memory/data tradeoff attack by Shamir and Biryukov, we obtain the same tradeoff curve${\displaystyle T{M}^2{D}^2=N^2}$ but with${\displaystyle (DR{)}^2\le T\le NR}$. This is actually an improvement since we could relax the lower bound on${\displaystyle T}$ since${\displaystyle (DR{)}^2}$ can be small up to${\displaystyle 1}$ which means that our attack can be made faster. This technique reduces the number of expensive disk access operations from${\displaystyle t}$ to${\displaystyle tR}$ since we will be accessing only the special${\displaystyle DR}$ points, and makes the attack faster because of the reduced number of expensive disk operations.

• Cryptographic attacks

• Articles with short description
• Short description matches Wikidata
• All articles with unsourced statements
• Articles with unsourced statements from December 2020