Tag: Key

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.

How Humans Beat Computers

Introduction

Number of keys related to the number of bits in the key
Figure 1: Number of keys related to the number of bits in the key

Every code is crackable and the measure of the security of a code is the amount of time it takes a person not addressed in the code to break it. Unless there are weaknesses in the encryption algorithm, the normal way to break cipher text is where a computer tries all the possible keys, until it finds a match. Thus a 1-bit code would only have two keys; a 2-bit code would have four keys; and so on. Figure 1 shows the number of possible keys, as a function of the number of bits in the key. For example it can be seen that a 64-bit code has 18,400,000,000,000,000,000 different keys. Thus if one key is tested every 10 ms then it would take 1.84´1014 seconds (5.11´1010 hours or 2.13´108 days or 5834602 years). So, for example, if it takes 1 million years for a person to crack the code, it can be considered safe. Unfortunately, from the point of security of an encrypted message, the performance of computer systems increases by the year. For example, if a computer takes 1 million years to crack a code, then assuming an increase in computing power of a factor of two per year, it would take 500000 years the next year. Then, Figure 2 shows that after almost 20 years it would take

Time to decrypt a message assuming an increase in computing power
Figure 2: Time to decrypt a message assuming an increase in computing power

only 1 year to decrypt the same message. This is a worrying factor as encryption algorithms which are used in the financial applications, which was one of the first after the military to adopt encryption, are now over 30 years old[1].

The increasing power of computers is one factor in reducing the processing time; another is the increasing usage of parallel processing, as data decryption is well suited to parallel processing as each processor element can be assigned a number of keys to check the encrypted message. Each of them can then work independently of the other[2]. Figure 3 gives example times, assuming a doubling of processing power each year, for processor arrays of 1, 2, 4…4096 elements. It can thus be seen that with an array of 4096 processing elements it takes only seven years before the code is decrypted within two years. Thus an organization which is serious about deciphering messages is likely to have the resources to invest in large arrays of processors, or networked computers. It is also likely that many governments have computer systems which have thousands of processors, operating in parallel.

Time to decrypt a message with increasing power and parallel processing
Figure 3: Time to decrypt a message with increasing power and parallel processing

Real-life example

bob6So let’s take a real-life example. Let’s say that we can process 1billion keys per second. So the key to try a key is 1 nano second (1e-9), and we have a 64-bit key. For this we have:

18,446,744,073,709,551,616 keys

Thus, on average, it will take us to have the key space, so the time to crack is:

T = 1e-9 * 18,446,744,073,709,551,616 / 2 = 9,223,372,036 seconds

which is: 153,722,867 minutes (we divide the seconds value by 60) or 2,562,047 hours (we divide again by 60) or 106,751 days (we again divide by 24) or 292 years (we divide again by 365). If you want to try this I have setup an example:

http://www.asecuritysite.com/Encryption/keys?keys=1000000000

The result is thus:

64 18,446,744,073,709,551,616 keys 292.47 years

This is quite a long time, and a few era, so our message seems to be safe. One thing we have not taken into account is that we can have more than one core on a processor, and we can have more than processors, so if we have an array of 1,024 processors, then the time to crack will be: 0.29 years, which is a much shorter time.

Let’s view the time to crack for:

  • 1 million keys per second. Here. If we assume that we have one day to crack, then the limit will be about 37/38 bits.
  • 10 million keys per second (approximately a standard Intel i7 core). Here. If we assume that we have one day to crack, then the limit will be about 41/42 bits.
  • 100 million keys per second. Here. If we assume that we have one day to crack, then the limit will be about 47/48 bits.
  • 1 billion keys per second. Here. If we assume that we have one day to crack, then the limit will be about 51/52 bits.

So where are we now?

RSA Labs Challenge
Figure 5: RSA Labs Challenge

It can be seen that if we have 1,024 we gain a speed-up of 1,024, but for every doubling of the number of processes we can crack one more bit in the time. So 1,024 is 2 to the power of 10, so we can crack 10 more bits in the same time as one processor. So for our 1 billion keys per second we can crack around 62 bits in a day, which is where the current state-of-the-art it. I’ve taken the table up to 72 bits which is about the limit for massively parallel systems. For 72 bits we have:

4,722,366,482,869,645,213,696 keys

and even if we process at 10 billion keys per second it will take:

7,400 years

to crack the encryption, on average, which is a long time. Over the past few years RSA labs have had an encryption challenge, where in 1997, distributed.net cracked a 56-bit code (by search almost 47% of the key space) and it took them 250 days. With the distributed.net system, an agent is installed on a machine, and when the screen saver comes on, the agent will download a number of keys and try then. Eventually one of the agents will find the correct key. In this way we have a massively parallel processing system. So for encryption methods such as AES, 3DES, Blowfish, and so on, it seems the limit of cracking a code in a resonable time is 72-bits, so if you are using 128-bit

Parallel processing
Figure 6: Parallel processing

So, in conclusion:

Humans 1 Computers 0

… oh … I’ll tell you about how computers are fighting back in another blog … and the score will be:

Humans 1 Computers 1

Postscript

If you look at the code I’ve used for the table of encryption keys, you’ll find I use BigIntegers. This is because whole numbers in computer only go up to:

4,294,967,296 (32-bit) or 18,446,744,073,709,551,616 (64-bit)

So if we need to operate on 72-bits, for example, we need a new type of variable, and that is where BigIntegers come in. So we can calculate 2 to the power of 72 as:

4,722,366,482,869,645,213,696

which is a largely large number.


[1] DES is the standard encryption algorithm used in financial transactions and was first published in 1977.

[2] This differs from many applications in parallel processing which suffer from interprocess(or) communication

The strength is in the keys

Introduction

The main objective of cryptography is to provide a mechanism for two (or more) entities to communicate without any other entity being able to read or change the message. Along with this it can provide other services, such as:

  • Integrity check. This  makes sure that the message has not been tampered with by non-legitimate sources.
  • Providing authentication. This verifies the sender identity. Unfortunately most of the current Internet infrastructure has been build on a fairly open system, where users and devices can be easily spoofed, thus authentication is now a major factor in verifying users and devices.
Key-based encryption
Figure 1: Key-based encryption

One of the main problems with using a secret algorithm for encryption is that it is difficult to determine if Eve has found-out the algorithm used, thus most encryption methods use a key-based approach where an electronic key is applied to a well-known algorithm. Another problem with using different algorithms for the encryption is that it is often difficult to keep devising new algorithms and also to tell the receiving party that the text is being encrypted with the new algorithm. Thus, using electronic keys, there are no problems with everyone having the encryption/decryption algorithm, because without the key it should be computationally difficult to decrypt the message (Figure 1).

The three main methods of encryption are (Figure 2):

  • Encryption methods
    Figure 2: Encryption methods

    Symmetric key-based encryption. This involves the same key being applied to the encrypted data, in order that the original data is recovered. Typical methods are DES, 3DES, RC2, RC4, AES, and so on.

  • Asymmetric key-based encryption. This involves using a different key to decrypt the encrypted data, in order that the original data is recovered. A typical method is RSA, DSA and El Gamal.
  • One-way hash functions. With this it is not possible to recover the original source information, but the mapping between the value and the hashed value is known. The one-way hash function is typically used in authentication applications, such as generating a hash value for a message. The two main methods are MD5 and SHA-1, and it is also used in password hashing applications, where a password is hashed with a one-way function, and the result is stored. This is the case in Windows and UNIX login, where the password is stored as a hash value. Unfortunately, if the password is not a strong one, the hash value is often prone to a dictionary-type attack, where an intruder tries many different passwords and hashes them, and then compares it with the stored one.

Generate your own keys

In order for you to see what keys look like, I’ve created a Web page where you can generate your own keys:

http://asecuritysite.com/Encryption/keygen

For example, we I use “fred” as the pass phrase and for aes-128-cbc (128-bit AES with CBC – Chained Block Cipher), I get:

salt=187938EEE4E87FDA
key=39E2095E5789CAD5CD1995219B48FFE6
iv =6D55F343E0D60985564D2D51D44C40D0

but when I try it again I get:

salt=BEAF690035812A3D
key=610C6519F47ECDDC370B88AECC0A4BDC
iv =247BF2166C1672CA935829B75F814EA4

In this way the salt, the key and the IV value all change, so that they cannot be easily guessed. The salt value allows us to create a difficult to crack hash value, and the IV value allows for the ciphertext to change with the same message. The trick is to add randomness into the generation, so that Eve cannot guess what the generated values are.

Obviously the size of the key will vary with the number of bits in the key, so if we use AES-256 CBC we get:

salt=3142A388014686CA
key=B4E2195C7F2BF04EB67722DF7FB8D5E6B4FE62E9CA9C896760D4435175A4EBA7
iv =8CE70C8998BB237997BFA9ED4B75A587

which shows that the encryption key is twice as long (but the salt and the IV values stay the same).

I’ll cover computational difficulty in the next article….