5
$\begingroup$

Out of interest, what would be the largest size lookup table which would be feasible to implement to attack a cipher (possibly under a fixed key) or in a TMTO setting, for an organisation with a large but not arbitrary budget, say a global multinational.

Is $2^{64}$ within reach?

Edit: Mainly intetested in block ciphers. Let's consider, for concreteness sake, blocklength $n=64$ and a TMTO attack.

Edit 2: There were comments, before the question was put on hold, to the effect that an exabyte is probably not possible but a petabyte ($2^{50}$) is. Assuming this, I'd say that it would be possible to build a $2^{50}/8 = 2^{47}$ size lookup table.

The TMTO scenario is probably more interesting, so any answers/comments directed to that case, assuming a petabyte is feasible, will be interesting.

$\endgroup$
2
  • $\begingroup$ This will depend on some factors - (1) is it a block cipher, if so what are the block sizes? (2) what mode are we encrypting in (if any), e.g. do we need to store nonces / IVs as well? $\endgroup$ – puzzlepalace Feb 28 '18 at 21:49
  • $\begingroup$ Don't immediately have any references, but I would say: order of $2^{60}$ (exbibyte) is probably out of reach, order of $2^{50}$ (pebibyte) is feasible. One obvious problem is the access speed. $\endgroup$ – Aleph Feb 28 '18 at 21:54
3
$\begingroup$

The answer depends a lot on the latency you may tolerate.

In 2011, Oracle/Sun/StorageTek announced a new storage system with exabyte capability (roughly $2^{60}$ bytes, but that's assuming a 2x compression rate; for crypto purposes, this is closer to $2^{59}$ bytes). Note that this was already seven years ago. Latency for random accesses could be up to a few minutes: the system uses a robotic arm that shuffles through thousands of magnetic tapes in a silo.

In a TMTO with the use of distinguished points (in particular Oechslin's "rainbow tables"), there is a "compression factor"; let's call it $t$. Costs for a rainbow table that cover $N$ preimages for a given function will be the following:

  • Building the table: about $1.7\times N$ evaluations of the function, and a sorting step (mostly $O((N/t)\log N)$ operations, but details vary a lot; merge sort variants are normally used because they can work with high-bandwidth sequential access).

  • Storage cost: about $(N/t)\log N$ bits.

  • For each lookup, about $t^2$ evaluations of the function, and $t$ accesses to the stored data (the original TMTO from Hellman would have needed $t^2$ accesses to storage, but the use of "distinguished points" fixes that).

The different variants of rainbow tables all follow these lines, sometimes with a factor somewhere, but always between 0.5 and 2.

For instance, if you have the half-exabyte storage system described previously, and want to find preimages for a 64-bit problem (e.g. an encryption system with a 64-bit key), then you will need $(N/t)\log N = 2^{59}$, hence $t = 2^{11}$. This means that each attack would require a few days (about three days, assuming an access latency of 2 minutes). This can probably be optimized: the $t$ lookups don't really depend on each other, so they could be collected and sorted so as to be performed in a better order that maximizes the robotic arm efficiency.

Some important notes:

  • The one-time cost of building the table is larger than the cost of exhaustive search. In fact, average cost for brute force is $N/2$ evaluations of the function. The table is worth the effort only if it will be used for at least four attacks.

  • The attacked function must be known in advance, completely. In the context of attacking a block cipher used in CBC mode with a random IV, then encryption is applied on plaintexts that are, by definition, randomized (that's the point of CBC mode). Thus, a known plaintext/ciphertext pair is not sufficient in that case.

  • On the other hand, the attacked system may help. For instance, the attacked system may provide enough "known plaintext" that the attacker can afford to wait for a favourable situation. This is the gist of the Biryukov-Shamir-Wagner attack on A5/1, where attackers wait for the algorithm to reach a "special state".

And with hard disks? Instead of using the tape-driven system, which can store a lot of data but with a high latency, you could try to use mechanical hard disks, which store less data for a given cost, but with a much lower access latency. Suppose that you have a budget of a mere million of dollars, that you may spend on "normal hard disks". You can get 4 TB for \$100; thus, we are here speaking about 40 petabytes. Let's round that down to $2^{55}$ bytes. Now you need $t$ to rise up to $t = 2^{25}$ for a 64-bit problem ($N = 2^{64}$). But you have ten thousands of disks, each able to perform about 100 lookups per second, and the lookups will be spread quite uniformly, so they can be made in parallel to a great extent. You can hope for a million lookups per second in total, and the $2^{25}$ will be done in half a minute... On the other hand, the computation cost of $t^2$ evaluations of the function has risen to $2^{50}$, which is prohibitive.

If the storage budget rises to ten millions of dollars, then you can divide $t$ by 10, which divides $t^2$ by 100, making it totally in range of a small cluster of beefy PC. Take care that we are then talking about a hundred thousands of hard disks, which is bound to have some non-negligible operational costs (if only for heat management and replacing failed units). Still, this would fit in a medium-sized server farm.

To sum up, a 64-bit symmetric problem which is amenable to precomputed tables is certainly in range of big organizations; in fact, it can even be done discreetly by medium-sized enterprises, and even spy agencies. On the other hand, such hardware budget would yield much more money by mining bitcoins.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.