I am currently thinking about the complexity of a brute-force attack on a cipher. Let the key length of the cipher be 64 bit. Then there are $2^{64}$ different keys in the keyspace. If you do a brute-force search, in the middle you will have to search through $2^{63}$ keys for success. So my question is now, what is the complexity of the attack? Is it $2^{64}$ or $2^{63}$? I am not sure about it.
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
3
It is exactly $2^{64}$. You need to look for all possible keys for a successful brute-force. One cannot guarantee that the key will be in the half, $2^{63}$, that you are going to search. In, CS there is an adversary argument, that the adversary can always force you to the worst case. Tell him how you the search, he will produce a case that you are not going to find in $2^{63}$ key-space.
Actually, $2^{63}$ is the average case that you will find your keys during the brute-force.
If you have multiple known-plaintext with encrypted different keys then with a multi-target attack you can find some keys faster. The expected cost of finding a key from $t$ target is $2^{64}/t$.
answered Nov 2, 2019 at 19:41
-
$\begingroup$ could you explain the value of average case? $\endgroup$ Commented Nov 14, 2022 at 12:58
-
1$\begingroup$ One needs to write some formulas to see that exactly. See the average case of linear search where each element has the same probability. $\endgroup$– kelalakaCommented Nov 14, 2022 at 13:16
-
$\begingroup$ thank you I'm going to try to find that $\endgroup$ Commented Nov 14, 2022 at 13:56