Time/memory/data tradeoff attack

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 the additional parameter of data, 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]

History

edit

Tradeoff attacks on symmetric cryptosystems date back to 1980, when Martin 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, in 1995, Babbage and Golic devised a different tradeoff attack for stream ciphers with a new bound such that   for   where   is the output data available to the cryptanalyst at real time.[2][3]

Attack mechanics

edit

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 the preprocessing phase to find the particular key in as little time as possible.

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

  search space size
  time required for the preprocessing phase
  time required for the realtime phase
  amount of memory available to the attacker
  amount of realtime data available to the attacker

Hellman's attack on block ciphers

edit

For block ciphers, let   be 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:

During the preprocessing stage
Try to cover the   point space by an   rectangular matrix that is constructed by iterating the function   on   random starting points in   for   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.
 
Hellman's Matrix
Now, only one matrix will not be able to cover the whole   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   at which the matrix contains exactly   different points. Consider the first   paths from start points to end points are all disjoint with   points, such that the next path which has at least one common point with one of those previous paths and includes exactly   points. Those two sets of   and   points are disjoint by the birthday paradox if we make sure that  . We achieve this by enforcing the matrix stopping rule:  .
Nevertheless, an   matrix with   covers a portion   of the whole space. To generate   to cover the whole space, we use a variant of   defined:   and   is simple out manipulation such as reordering of bits of   [1] (refer to the original paper for more details). And one can see that the total preprocessing time is  . Also   since we only need to store the pairs of start and end points and we have   matrices each of   pairs.
During the real time phase
The total computation required to find   is   because we need to do   inversion attempts as it is likely to be covered by one matrix and each of the attempts takes   evaluations of some  . The optimum tradeoff curve is obtained by using the matrix stopping rule   and we get   and choice of   and   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   over an   point space, and if this   is invertible, the tradeoff relationship becomes much better:  .

Babbage-and-Golic attack on stream ciphers

edit

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'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 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.

  1. During the preprocessing phase, pick   random   states and compute their corresponding   output prefixes.
  2. Store the pairs   in increasing order of   in a large table.
  3. During the realtime phase, you have   generated bits. Calculate from them all   possible combinations of   of consecutive bits with length  .
  4. Search for each   in the generated table which takes log time.
  5. If you have a hit, this   corresponds to an internal state   of the bit generator from which you can forward run the generator to obtain the rest of the key.
  6. By the Birthday Paradox, you are guaranteed that two subsets of a space with   points have an intersection if the product of their sizes is greater than  .

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  .

Shamir and Biryukov's attack on stream ciphers

edit

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   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  . This cuts 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  ).

Attacks on stream ciphers with low sampling resistance

edit

This attack, invented by Biryukov, Shamir, and Wagner, 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   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. This technique reduces the number of expensive disk access operations from   to   since we will be accessing only the special   points, and makes the attack faster because of the reduced number of expensive disk operations.

References

edit
  1. ^ a b Hellman, M.E., "A cryptanalytic time-memory trade-off", IEEE Transactions on Information Theory, vol.26, no.4, pp. 401, 406, Jul 1980
  2. ^ Babbage, S. H., "Improved “exhaustive search” attacks on stream ciphers", European Convention on Security and Detection, 1995, vol., no., pp.161-166, 16–18 May 1995
  3. ^ Golic, J., "Cryptanalysis of Alleged A5 Stream Cipher" Lecture Notes in Computer Science, Advances in Cryptology – EUROCRYPT ’97, LNCS 1233, pp.239-255, Springer-Verlag 1997
  4. ^ Biryukov A., Shamir A., "Cryptanalytic Time/Memory/Data Tradeoffs for Stream Ciphers" Lecture Notes in Computer Science, Advances in Cryptology – ASIACRYPT 2000, LNCS 1976, pp.1-13, Springer-Verlag Berlin Heidelberg 2000
  5. ^ Biryukov A., Shamir A., Wagner D., "Real Time Cryptanalysis of A5/1 on a PC" Fast Software Encryption 2000, pp.1-18, Springer-Verlag 2000