5
$\begingroup$

You can do $2^{30}$ encryptions per second and the key size is 64 bits.

$2^{64}/2^{30}$ should give me the time taken for a brute force attack? What if you double the key size?

How can I calculate the maximum and average time taken for such an attack.

$\endgroup$
  • $\begingroup$ Hints: brute force attack is trying keys, until finding one that matches. We can try them by increasing order. Trying involves one encryption with the key tried, and then a comparison of comparably small cost, and (if there's a match, that is, rarely) some confirmation operation. If a key has $b$ bits, how many possible keys are there? What's the time to try them all at a rate of $r$ keys per second? For the average time, you can compute the average of the exact time over all possible key values, or use a well-known approximation. $\endgroup$ – fgrieu Apr 15 '16 at 5:23
8
$\begingroup$

Well, that's simple: $2^{64}/2^{30}$ is indeed correct. And since $2^{64}/2^{30} = 2^{64 - 30} = 2^{34}$ then that would be the answer. A simple recalculation would give you approximately 545 years. As you can see, 64 bits is pretty much on the border of being cracked by general computers. It is also about the same size as the SHAttered attack; these kind of attacks scale well, so just renting 640 cores for a year in a cloud service would probably do it.

Brute force basically scales linearly with the amount of keys. However, we're doubling the key size here, not the amount of keys. Growing the key size exponentially grows the amount of possible keys. It's a bigger step to go from 10 to 100 as it is to go from 1 to 10, both in decimals as in binary calculations.

545 years would however be the maximum time it would take to find a key by trying all of them. On average you'd need half of that time using a single core as the key may be either on the lower half or higher half of the key space (whichever way you split it in two equal size parts, as each key should be equally likely). Each additional bit in the key size doubles the key space. That means you could subtract a single bit from the key size to find out the average time it costs to brute force the key.

The calculation required to find out the time it takes to brute force a 128 bit key isn't that more complicated: $2^{2 \cdot 64}/2^{30} = 2^{128}/2^{30} = 2^{128 - 30} = 2^{98}$. The outcome of course is rather different though; you'd now need $10^{22}$ years. Or around 700 billion times the current life-time of the universe to try all the keys. Or 350 billion times the life of the universe if you average things out (yeah, right).

Then again, according to WolframAlpha $10^{22}$ years is only 3.3 times the half life of Calcium-76 so there may be some calcium atoms left to witness the end result. Again, you can drastically reduce the time by adding processors. However, you'd need too much processors and energy to bring it back to a value that is possible to crack in a life time. Better not try to brute force a properly randomized 128 bit key then.


Important: it may be that you're not trying to find the value of a single key, but you're trying to find the value of one of a million keys. This, of course, it much easier because the chance of finding one quickly increases. This, and the possible advance of quantum computing, may be enough reason to go for a 256 bit key strength.

$\endgroup$

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.