3
$\begingroup$

As ASICs are specifically designed to generate the hash for a block of a block chain. which is much faster than other GPUs which are used to break 2key-3DES. can we use Array of ASICs to break 2key-3DES in practical time?

$\endgroup$
3
$\begingroup$

First of all, 2DES is

$$\textrm{ciphertext} = E_{K_1}(D_{K_2}(E_{K_1}(\textrm{plaintext})))$$

The below from 19 September 2020 on the Bitcoin mining, Bitcoin mining is based on SHA256d calculations. All in all, ASICs, FPGAs, GPUs, and CPUs.

\begin{array} {|l|c|c|c|c|}\hline & \text{in a second} & \text{in a hour} & \text{in a day} & \text{in an Year} \\ \hline \text{Bitcoin Miners on SHA-256D} & \approx 2^{67.9} & \approx 2^{84} & \approx 2^{84.3} & \approx 2^{92.8} \\ \hline \end{array}

We can adjust the values if we can find 2DES implementation, however, the miners use various sources to mine, however, we can approximate with hashcat on Nvidia RTX 3080.

Hashmode: 14000 - DES (PT = $salt, key = $pass)
Speed.#1.........: 53585.1 MH/s 
Hashmode: 1410 - sha256($pass.$salt) 
Speed.#1.........:  6980.9 MH/s (81.18ms)

The DES is around 8 times faster ( not going into too many details of hash modes ) and 2 times for SHA256d that makes $2^4$-times faster. We call the DES 3 times so the speed is $2^4/3$. Make a little approximation it to $2^3$

\begin{array} {|l|c|c|c|c|}\hline & \text{in a second} & \text{in a hour} & \text{in a day} & \text{in an Year} \\ \hline \text{Bitcoin Miner on 2DES adjusted} & \approx 2^{70.9} & \approx 2^{87} & \approx 2^{87.3} & \approx 2^{95.8} \\ \hline \end{array}

So in a year, they can reach $\approx 2^{95.8}$ 2DES calculations. Therefore they still need $112-86.8 = 20.2$ year that is $\approx 1048576$ years to execute brute force for a single target.

The above is a simple full brute force attack. In a more careful attack design (thanks to Poncho), the attackers can simplify some calculations

for key1 in KeySpace:
   c' = DESDec(k1,m)
   m' = DESEnc(k1,c)

   for key2 in KeySpace:
      assert m' = DECEnc(k2,c') 

Now this totally calls $2^{56}( 2 + 2^{56}) = 2^{57} + 2^{112} $. The outer loop can also benefit from calling the key sechedule once. This can speed the brute-force attack 3 times.

One can go for better options. An interesting case is a multi-target attack. With a multi-target attack, you can find some keys faster. The expected cost of finding a key from $t$ target is $2^{112}/t$. For a billion targets, the cost would be below $2^{84}$ and the time would be below $2^{54}$

$\endgroup$
11
  • 1
    $\begingroup$ Perhaps it should be added that this is for brute force key search, for a single 112-bit key; and a few plaintext/ciphertext pairs (case 1 there). Prospects are much better for the same plaintext enciphered under a number of keys (case 2). Prospects with lots of plaintext/ciphertext pairs uh, that's complicated. $\endgroup$ – fgrieu Nov 16 '20 at 16:49
  • 1
    $\begingroup$ "We call the DES 3 times"; actually, for a brute force search based on a plaintext/ciphertext pair, the attacker can (simplifying a bit) have an outer loop that iterates over the outer DES key (and encrypts the plaintext/decrypts the ciphertext), and then have an inner loop that iterates over the inner DES key (and so effectively does a single DES operation per iteration); using this optimization, your single target estimates can be sped by a factor of 3 (2 actually, because of how you rounded) $\endgroup$ – poncho Nov 16 '20 at 19:57
  • 1
    $\begingroup$ @poncho Very nice. I found that it is almost 3 by $2^{56}( 2 + 2^{56}) = 2^{57} + 2^{112}$ $\endgroup$ – kelalaka Nov 16 '20 at 20:19
  • $\begingroup$ why do we use 2^112 here? if we use Oorschot-Wiener model, we have only 2^80 keys to search and we can get it less than an hour. is it not true? $\endgroup$ – SSA Nov 18 '20 at 5:06
  • $\begingroup$ @SSA What about the memory requirement, known-plaintext? I just wanted to keep the answer as simple as possible and gave links to other solutions as better options. There are other issues that we don't consider here either. The nodes of bitcoin are far from each other compared to a SuperComputer, which will affect the computation time. What about the memories of some nodes? do they enough memory to keep the memory requirements? $\endgroup$ – kelalaka Nov 18 '20 at 7:46

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.