1
$\begingroup$

Let a plain text message M be DES encrypted with two different keys (K1 and K2) to produce the encrypted messages E1 and E2 (for K1 and K2 respectively).

Lets assume we setup a brute force attack which tests all possible keys K1 and K2 until the decrypted messages M1 and M2 are equal.

Is it mathematically possible to find two different keys K1' and K2' so that the decrypted messages M1 and M2 are same (not necessarily equal to M) and K1' is different from K1 and/or K2' is different from K2?

EDIT:

This question is not a homework actually. It is rather in the context of reverse-engineering. To give more context:

I gathered a few sample data from two sources. Parts of those samples encrypt the same plain text with different keys. I found out that there are 64bits patterns (i.e.: the data is encrypted by blocks of 64bits - date, operation code, etc.). From this I assume a most-likely DES/3DES/Blowfish/XTEA algorithms as they are the most common and most easily implemented on an embedded target.

I was wondering whether it could be worth a try (/practical) to run all possible keys and find the valid one with the condition "M1 is same as M2".

$\endgroup$
11
  • 1
    $\begingroup$ Hint for what could be homework: as a first order approximation, assume that $K\mapsto D_K(E_1)$ and $K\mapsto D_K(E_2)$ (where $D_K$ is decryption with key $K$) behave as two independent random functions. $\endgroup$
    – fgrieu
    Commented Feb 19 at 13:47
  • $\begingroup$ @fgrieu I'm afraid I don't understand .. What would this mean with a more literal language? $\endgroup$
    – Jib
    Commented Feb 19 at 14:04
  • $\begingroup$ Hint, expanded: The properties of a good block cipher are such that it's reasonable to assume that when you fix an E1, the result of decrypting that E1 with any number of distinct keys behaves essentially like as many independent random numbers as there are keys. Same if you fix an E2, with no relationship between the seemingly random results obtained in the two experiments if E2E1. $\endgroup$
    – fgrieu
    Commented Feb 19 at 14:22
  • $\begingroup$ So the answer may be "yes, from a probability point of view, it is possible to have keys K1' and K2' so that M1 and M2 are same and K1' != K1 and/or K2' != K2" .. Do I understand correctly? $\endgroup$
    – Jib
    Commented Feb 19 at 14:26
  • 1
    $\begingroup$ That would likely indicate ECB mode and an 8 byte block cipher. So what you may be looking for are attack vectors against ECB. The chances of blocks "colliding", i.e. having the same value by chance is not that high, so if multiple blocks are the same then the same key is likely used. $\endgroup$
    – Maarten Bodewes
    Commented Feb 19 at 15:52

1 Answer 1

2
$\begingroup$

For the question as originally asked with a single pair of $E_1$ and $E_2\ne E_1$ that have been obtained as $E_1=\operatorname{DES-Enc}_{K_1}(M)$ and $E_2=\operatorname{DES-Enc}_{K_2}(M)$ for unknown $M$, it's likely there are many pairs $(K'_1,K'_2)$ such that $\operatorname{DES-Dec}_{K'_1}(E_1)=\operatorname{DES-Dec}_{K'_2}(E_2)$. So it's very unlikely that the first pair found is the correct $(K_1,K_2)$, and there's no way to tell which pair found is right.

Argument: A good block cipher such as DES is such that for a fixed block $E_1$, the function $K\mapsto\operatorname{DES-Dec}_K(E_1)$ behaves mostly like a pseudo-random function (not permutation). And the other function obtained for $E_2\ne E_1$ is nearly independent, except for the relatively minor detail that $\operatorname{DES-Dec}_K(E_1)\ne\operatorname{DES-Dec}_K(E_2)$. In (simple) DES, the key is 56 effective bits, and a block is 64-bit. If we try $2^{32}$ distinct $K'_1$ (e.g. incremental) and compute $\operatorname{DES-Dec}_{K'_1}(E_1)$, we'll obtain a set of very nearly $2^{32}$ distinct random-like 64-bit values (more than 2 collisions is quite unlikely). If then we try some distinct $K'_2$, compute $\operatorname{DES-Dec}_{K'_2}(E_2)$ and check if it is in the set, that has probability nearly $2^{-32}$. Thus just above $2^{32}$ attempts are expected to find a suitable $K'_2$. But because we have explored only a proportion $2^{-24}$ of the possible $K'_1$, and about $2^{-24}$ of the possible $K'_2$, there's probability about $2^{-48}$ that we hit the right $(K_1,K_2)$.


With two or more distinct pairs of $(E_1,E_2)$, it's quite likely there is a single solution $(K'_1,K'_2)$, and thus that the first one found is the actual $(K_1,K_2)$. However it becomes much more difficult to exhibit that correct pair.

In theory a Meet-in-the-Middle attack needs like $2^{57}$ DES operations (for essentially guaranteed success assuming the block cipher is DES), but requires too much RAM for practice. Variants require manageable RAM and can be efficiently distributed, and require only a few times more work. While $2^{58}$ DES operations with key derivation is feasible (it was in 1998), that's still not an easy task.


For a good 128-bit key cipher (3DES/Blowfish/TEA/XTEA), forget about a practical attack, even if $M$ was also known.

$\endgroup$
1
  • $\begingroup$ Thank you for the detailed explanations. I guess my real-case experiment somehow stops here then .. $\endgroup$
    – Jib
    Commented Feb 19 at 17:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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