Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

I am considering attacks on Two-Key Triple-DES Encryption assuming $2^{32}$ known plaintext/ciphertext pairs (that's a mere 32 Giga Bytes of ciphertext) by the method devised by Paul C. van Oorschot and Michael J. Wiener, or another published method not requiring significantly more DES computations.

As a synthetic information for decision makers, I am looking for an independent estimate of how much time this is expected to require, assuming all the RAM ever built by mankind to that day (of April 2012) was put to full use.

Note: I'm purposely not asking when the attack could become feasible using all the RAM ever built by mankind, because estimates on the amount of RAM mankind will build, and when, are less falsifiable.

Update: I am not considering cost; neither of RAM, power, logic including DES engines (as long as the number of DES operations remains within $2^{90}$). I am willing to assume that the amount of RAM used, and its effective speed, are the only factors to account for in determining the expected duration of the attack. This is similar to the hypothesis made by the authors of the linked paper, that their attack is limited by the amount (or cost) of RAM used, with all other factors of secondary importance.

Update: sadly, nobody dared answer the question and the bounty period is over. Thus here is a first order answer to criticize.

share|improve this question
    
Am I correct in assuming that part of the problem is deriving an estimate the total RAM built to date? –  B-Con May 3 '12 at 4:41
    
Is this question really correctly put? If you refer to the Oorshot-Wiener paper originally published in 1990, it seems the memory requirements are fixed by the amount of known plain text, and with $2^32$ known plain text the largest of the two tables requires $2^40$ bits, i.e. just one terabit. Or am I missing something? –  Henrick Hellström May 3 '12 at 5:31
    
Yes, part of the problem is estimating the total amount of RAM built to date, and its usable access rate in the context of the attack. $2^{32}$ blocks is here to match the conditions assumed by the authors. 32 Giga Bytes puts that number in perspective. Yes in the simplest setup the attack needs only $2^{40}$ bits in the biggest table, but runtime is horrific; thus I assume we can put to full use all the RAM built to date, and ask for the runtime. Which is the best way that I could devise to make the result graspable as a single number. –  fgrieu May 3 '12 at 5:57
    
The reason the large table was set to $2^{40}$ bits, was that it is supposed to contain a hash table of the known plain text. AFAICS you have no use for more RAM, unless you also have more known plain text to fill it with. –  Henrick Hellström May 3 '12 at 6:07
1  
Yes, but I reckon you wanted a semi-realistic lower bound of the time required for the attack, and clearly that depends not only on the amount of RAM ever built, but also on engineering questions and a lot of other costs; not only the cost of other hardware, but how many CPU cores and DES engines you might physically wire to a single instance of memory, what it would cost to manufacture such a circuit, and the cost of energy for both running the thing and cooling it? Simply put: Is it really still the amount of memory available that puts a limit to the attack, rather than other factors? –  Henrick Hellström May 4 '12 at 8:07
show 7 more comments

1 Answer

up vote 5 down vote accepted

The original article rightfully neglects the cost of DES computations (there are less than $2^{90}$) and everything except memory accesses to its Table 1 and Table 2. I go one step further: considering that Table 1 is initialized only once and then read-only, it could be in ROM, and I neglect all except the accesses to Table 2. The attack requires an expected $2^{88}$ random writes and as many random reads to Table 2, organized as $2^{25}\cdot 24$-bit words.

The cheap PC that I bought today came with 4 GByte of DDR3 DRAM, as a single 64-bit-wide DIMM with 16 DRAM chips each $2^{28}\cdot 8$-bit, costing about \$1 per chip in volume. Bigger chips exists: my brand new 32-GByte server uses 64 chips each $2^{29}\cdot 8$-bit, and these are becoming increasingly common (though price per bit is still higher than for the mainstream $2^{28}\cdot 8$-bit chips).

Two mainstream $2^{28}\cdot 8$-bit chips hold one instance of Table 2, and one 124-bit word can be accessed as 8 consecutive 8-bit locations in each of the two chips simultaneously (consecutive accesses are like 15 times faster than random accesses). One $2^{29}\cdot 8$-bit chip would be slightly slower.

Assuming DDR3-1066 with 7-cycles latency (resp. DDR3-1333 with 9-cycles latency), 8 consecutive access require at least $(7\cdot 2+7)/1066\approx 0.020$ µs (resp. $(9\cdot 2+7)/1333\approx 0.019$ µs). This is a decimal order of magnitude less than considered in the original article. For each instance of Table 2, that is 0.5 GByte, we can perform at most $365\cdot 86400\cdot 10^6/0.019/2\approx 2^{49.6}$ read+write accesses per year to Table 2 using mainstream DRAM. Thus with $n$ GByte of mainstream DRAM, and unless I err somewhere, the expected duration is $2^{37.4}/n$ years.

Based on press releases of a serious reference, there are less than $2^{31}$ PCs around, and assuming that my cheap PC is representative, that's $2^{33}$ GByte. Another way to look at that is that each 0.25-GByte chip cost about \$$1$; and the DRAM revenues in 2011 is less than \$$2^{35}$, thus enough for $2^{33}$ GByte (but notice that most of the revenue is from chips that are not optimized for cost per bit). I'll guesstimate all the RAM ever built is equivalent to at most $2^{35}$ GByte of mainstream DRAM for the purpose of the attack.

Thus at the end of the day, my answer is: the attack in the original article, updated to use all the RAM chips ever built by mankind to mid 2012 at the maximum of their potential, has an expected duration of at least 5 years; or equivalently has odds at best 20% to succeed in one year.

Update: as noted by the authors of the original article, "the execution time is not particularly sensitive to the number of plaintext/ciphertext pairs $n$ (provided that $n$ is not too small) because as $n$ increases, the number of operations required for the attack ($2^{120-\log_2 n}$) decreases, but memory requirements increase, and the number of machines that can be built with a fixed amount of money decreases". By the same argument, our required amount of RAM is not much changed if we get more known plaintext/ciphertext pairs.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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