DES with the bitwise complement of a key I was reading upon Biham and Shamir's paper and a fact has been presented over there:
if $ P_1 = \bar P_2$ and I choose a key $K_1 = \bar K_2$ then in that case 
$$T_1 = DES(P_1, K_1)$$
$$T_2 = DES(P_2, K_2)$$

then $T_1 = \bar T_2$ . Does this hold for only that particular combination of S-box or it will be same for any S-box combination. I mean if I change S-boxes randomly then will it still be same?

Also there is one more thing mentioned on the paper, but I am not able to get it. PFB the image. 

Here output $T$ will be $\bar T_2$ only if I $P_2$ was inserted with $\bar K$. And clearly I am entering $P_1$ (which is $\bar P_2$) hence the output can never be $T_2$. Please correct.
This is known as the complementation property of $DES$; I had thought that it actually predated Biham and Shamir's work.

In any case, your questions:


  Does this hold for only that particular combination of $S$-Box or it will be same for any $S$-Box combination?


It'd remain even if you change the $S$-Boxes arbitrarily. The reason for this is that it is not actually caused by the $S$-Boxes. $DES$ generates the inputs to the $S$-Boxes by $XOR$ing $R_i$ with $k_i$. The reason this property holds is if you complement $R_i$ with $k_i$, the result of the $XOR$ won't change, and so the input the to $S$-Box is exactly the same (and hence the output of the $S$-Box is exactly the same).


  Also there is one more thing mentioned on the paper, but I am not able to get it.


Actually, that's a fairly straight-forward exploit of this property. I'll see if I can state it more explicitly.

Suppose you knew the ciphertexts for two plaintexts, and these plaintexts happened to be the complement of each other. That is, we know the value $T_1 = E_k(P_1)$ and we also know the value $T_2 = E_k(P_2)$, where $P_1$ and $P_2$ are complements of each other (that is, wherever $P_1$ has a $0$ bit, $P_2$ has a $1$ bit, or in other words, $\overline{P_1} = P_2$

Consider further that we don't know the key $k$; and we'd like to find it.

One thing we can try is pick a random key $k'$, and do a trial encryption of $P_1$ with it.  If our $k'$ just happened to be the value $k$, then $E_{k'}(P_1)$ would be $T_1$, and so we know know that $k'$ is likely to be the correct value.

However, consider if our $k'$ is the complement of $k$ (that is, we got every bit wrong).  In that case, the key complementation property would hold, and we would have $E_{k'}(P_1) = \overline{E_{\overline{k'}}(\overline{P_1})} = \overline{E_k(P_2)} = \overline{T_2}$, that is, we would see the bitwise complement of $T_2$.  So, if we see that value, that also tells us what the key is likely to be.

Hence, by doing a single $DES$ encryption, we can actually test two keys -- that's what Biham and Shamir are pointing out.