Tag: Brute-force attack

So how can a 1.8 million billion billion billion billion billion billion years become a few minutes?

Introduction

I always find it amusing when someone loses a laptop or a USB stick with some sensitive information, and they say “It’s okay, it was encrypted” … which unfortunately, is far from the truth, as the encryption can be easily broken in most cases. But in a previous blog I outlined how it takes 1.8 million billion billion billion billion billion billion years to find a 256 bit encryption key. So how come we can still crack even the strong encryption? Well it tends to be quite easy, as if you have find out where the key is, you can normally open it up, as humans tend to use weak passwords to save their keys. So if prompted to save your newly created password, which would you choose … “$p7GiLl1%69” or “password”? If the answer to this is “password”, then read on … If it isn’t then you are super-human, and easily a match for any intruder.

You’ve got to store it somewhere …

bob10Like it or not, you’ve got to store your encryption key somewhere, as you’ll need it to decrypt your encrypted content. If you loose your key, you’ll not be able to recover your encrypted data. This can become a particular problem when you encrypt your whole disk drive, as you’ll not be able to even start your computer. So how to you keep it secure? Well we could put it in a secret place, but an intruder could search for this. The method that is normally used, it to protect it with a password. So here is the flaw, it takes a 1.8 million billion billion billion billion billion billion years to find the encryption key, but it can take just a few minutes to find out someones password, as the passwords we use are normally memorable, and are thus found with a standard dictionary. So if an intruder pops-off the key with its protection, they can then run it against a standard dictionary, and crack the key. So protecting keys with a simple password, it a bit like having a high quality security systems, and leaving the key to it under the plant pot.

It’s on a certificate

The place to find encryption keys is normally the certificate store, and the important one to find is the digital certificate which contains the private key. Thus even if we use top quality encryption, the certificate itself can be cracked with a dictionary attack. In this video I show how we can break a certificate with a password:

If you want to try my certificate cracker, it is here:

http://buchananweb.co.uk/clienttoolkit.zip

and I’ve created an example of reading a digital certificate with a password:

http://www.asecuritysite.com/Encryption/digitalcert2

where the first certificate has a password of apples and the second as battery. Both are easy to guess from a standard dictionary. With the advent of cloud-based systems, the concept of distributing the cracking over a range of processors becomes so much easier. So to crack an encryption key with purely brute force … almost impossible! … to determine it from a container which is protected by a password … simple … to determine the a source which is based on a phase phrase … just as simple! I often to surveys of audience at conferences, and you would be amazed how many people say they use the name of their pet, or their favorite football team, or the name of someone in their family, all of which are normally easy to guess.

Conclusions

Well we’ve just seen that it’s passwords that’s the problem. Is your password secure from a dictionary attack? Well most people use a fairly simple password, so that they can remember it. So forget about the size of your keys, and the methods used, it is likely that it is the certificate that causes the problems. In fact, it may be the Windows password that will compromise the whole system.

What takes 1.8 million billion billion billion billion billion billion years to find?

Question

4-bit key
4-bit key

So what takes 1.8 million billion billion billion billion billion billion years, on average, to find, and is only 256 things long? Well it is the time it would take you, or to be more precise, your high-powered computer, to find the key used in a 256-bit encryption process. This calculation takes into account that you would be using one of the best computers around, which would be able to process at 1,000,000,000 keys per second, which is much faster most normal desktop computer. The following tables shows you how long it would take for different key sizes:

http://www.asecuritysite.com/encryption/keys

So you can’t understand why it would take so long? Well the number of keys that we have relates to the number of bits that we have in the key. So a 4-bit key would have 8 different keys from 0000 to 1111. An 8-bit key has 256 keys, a 20-bit key has over 1 million keys, and so on. Mostly we start with something like a 56-bit key, which gives us:

72,057,594,037,927,936

different keys. So if we use a computer which checks 1 billion keys per second, then the time to check one key will be 1ns, so the time to find, on average, the key will be:

T = 72,057,594,037,927,936 * 1×10^-9 / 2

which is 36,028,797 seconds, or 600,479 minutes, or 10,007 hours or 416 days, or 1.14 years. But why do we go from just over a year to billions of years? Well for ever bit that we add, we double the key space. So 57 bits takes 2.28 years, 58 bits takes 4.56 years, and so on. Thus it doesn’t take too long to get to a point where it takes billions of years. So for 256-bits, we get:

115,792,089,237,316,195,423,570,985,008,687,907,853,269,984,665,640,564,039,457,584,007,913,129,639,936

different keys, so if you do the calculation you get:

1,835,871,531,540,400,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000 years

which is a LONG TIME!

Conclusion

For a completely random key, 256-bits is completely uncrackable with today’s, tomorrow’s computers. If we were to do it, we would need a quantum computer, which could parallelise the computation, and perform them at the speed of light. But the thing we must ask is … are the keys actually random? If not, then it’s a whole different calculation?