4
$\begingroup$

Random keys are often produced using high-quality random generators. Assuming a key produced for a symmetrical cipher, this means that the number of zeros and ones in the key will, on average, concentrate on about half of the key's length.

Having this in mind, is it anywhere more profitable to start a brute-force attack from bit patterns with similar population counts (that is, with similar counts of ones and zeros)? Will this increase the probability of success?

$\endgroup$
6
$\begingroup$

No, you can't get any advantage by using a special algorithm to determine with which keys to start your brute-force attempt if the key was chosen by a truly random key generator.

You are right, the amount of bits set to 1 of such a truly random key will be (statistically) equal / close to $\frac{x}{2}$ with $x$ defined as the length of the key in bits. It's also true that it is more likely that the key will have $\frac{x}{2}$ bits set to 1 than only 1 bit set to 1 (at least for bigger $x$). The problem is that the amount of possible keys will rise the same as the number of bits set to 1 until it reaches $\frac{x}{2}$ and then drop again. For $x = 4$ there are $2^4 = 16$ possible values of your key. The amount of keys with $\frac 4 2 = 2$ bits set to 1 are $\frac{4!}{2!(4-2)!} = 6$ elements. (See Binomial coefficient for an explanation of this formula) That are $\frac 6 {16} = 37.5\%$ of the whole keyspace, and that's also the chance that the randomly chosen key will be in this space.
In contrast to that there's only exactly 1 element of the space of possible keys that has exactly 0 bits set to 1 - a key containing only 0. With a key length of 4 that one has a chance of $\frac 1 {16} = 6.25\%$, but there's also only 1 key you have to check. The chance is smaller, but you are also much faster through that list.

When you now start your search with half of the bits set to 1, you will have the same chance to find the key as when you start with all bits set to 0.

$\endgroup$
  • 1
    $\begingroup$ Although the answer was obvious at sight (since otherwise one would be deriving information from pure randomness), I was curious to see the calculations. Thanks for sharing this. $\endgroup$ – alecov Apr 24 '17 at 0:02
15
$\begingroup$

No, it doesn't help. It doesn't hurt either; as long as you don't repeat keys, the probability of success is always the same. That is, if there are $2^n$ possible keys, and you test $\lambda$ of them, the probability you hit the right one is always $\lambda / 2^{n}$.

A key generated by a high quality random number generator (or a good key derivation function) is equidistributed; every possible value has an equal probability of being the correct one. Yes, most keys will have approximately the same number of 0's and 1's; but that's because most possible values will have approximately the same number of 0's and 1's.

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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