We have a problem in modern society … how can we be sure that someone really is who they say they are? On the Internet we normally trusted third party that both parties trust. In many cases when we discuss secret communications we have Bob and Alice, so let’s call our pair Bob and Alice, and we will define their trusted person as Trent, who is the only person in the world that both Bob and Alice trust. Unfortunately Trent’s fees are high, so they want to minimise the things that he has to do, and must thus use Trent to set-up a secret channel for them to communicate. For this Trent will create a secret box, which can be passed between Bob and Alice, who will have secret keys for it. If they loose them, hopefully Trent will have a copy of the key, just in case.
Bob and Alice and going through a difficult time, and now they only communicate through their lawyer, who they both trust, but want a way to identify each other and communicate in a secret way (so that Trent doesn’t actually see them messages). Unfortunately they cannot afford any expensive lawyer fees for their communications, so how do they use Trent to create a secret box for their communications? Well they can use a proposal known as Kerberos.
Trent Gets a Box and a Key
So Alice goes to Trent and says that she has to prove her identity to Bob, and vice-versa. For this Trent will make a special key for a box, and will make a copy for Bob and Alice (he might also keep a copy for himself, just in case they lose them – this technique is know as key escrow). Trent will then take a photograph of Alice, and write down the date and time on it, and the amount of time he can verify Alice for. He will then put it into the box, and gives the box to Alice, along with the key. Along with this he will give her a sealed letter for the attention Bob which has his stamp on it. Inside will be a photograph of Alice that he took, and the secret key, along with the date/time that he created the key. With key escrow, Trent will keep a copy of the key, just in case that Bob and Alice loose their keys, but if even Bob and Alice do not want this, then Trust must prove that he does not have any other keys. In this way Trent will not be blamed for any leakage of the information in the box.
Alice Sends the Box
Alice then goes home, and then puts her photograph in the box, and locks it with the secret key. She then passes the box, without the key, along with the sealed letter to Bob. Bob opens the sealed letter, which has a key inside to open up the box, and which has the photograph that Trent took of Alice. Bob then opens the box with the secret key provided by Trent, and takes out the photograph that Alice has provided. If it is the same as the one that Trent put in the sealed letter, Bob thus verifies Alice’s identity.
Now we have a Secret Box … and no lawyer
Bob and Alice now have the same key to open and close the secret box, and can now use it to send secret messages to each other. No-one else will have that unique key, thus any messages in there must have been provided by Bob and Alice. Now they can both define the terms of the divorce without being billed for more solicitor fees for their messages.
The Encryption Protocol
If you are interested, here is the actual encryption proposal based on this example:
As we become more dependent on the Web, we can never be 100% sure that everything is correct and as it should be. This might relate to receiving an email from someone who says that they know you, but how can you tell if the person is genuine? The email address looks fine, but the email content does not have the same writing style as the person who normally writes from that email address. Unfortunately there is very little that we can do, at present, to determine if this is genuine, but things are changing, and it is trust that is becoming the key element of how we interact with the Web.
Bruce Schneier highlights this, in that we are entering a new phase, and defines that:
Trust and cooperation are the first problems we had to solve before we could
become a social species. In the 21st century, they have become the most important
problems we need to solve—again.Our global society has become so large and complex that
our traditional trust mechanisms no longer work.
Kerberos (The Three-headed Beast)
Users must thus ask themselves who they trust on the Internet? We can use hash signatures to determine if information has been changed, but how can we be sure that the person who created the data, and signed it, is actually the person who they say they are. So the only way we can properly identify two users to each other is to use a trusted partner who both parties trust, and thus we introduce the concept of Trent, who is trusted by both Bob and Alice. In a legal system, Trent is a lawyer, who is trusted enough to see-through a house sale, and to take the money from Bob’s account, and then place it in Alice’s account, and where Trent has to places the funds in his own account as part of the transfer. Bob and Alice trust Trent enough that he will not deposit the money in his account, and then run-off with the money. Trust is thus a key part of our lives and as citizens we have developed strong trust relationships, such as with the legal systems, the police, and with our banks. We thus trust our banks to be able to look after our money, and not to go and use it to invest in doggy deals, and use the money to pay high salaries to their executives — or do we? If not, then are trust has reduced, as banks at one time were seen to be a safe place to deposit money, and then be able to take it out again.
So we now have three parties involved: Bob, Alice and Trent. So where does Kerberos come in? Well Kerberos (or Cerberus) was defined in Greek and Roman mythology as, typically, a three-headed dog. It is often known as the hellhound that guards the gates of the Underworld, in order to stop those who have crossed the river Styx from escaping. As we’ll find both the description of the three headed beast fits the three way communication, and also that the protocol is a bit of a beast.
The Detail of the Encryption
One of the best protocols for implementing this trust infrastructure is Kerberos. It is fairly complex in its implement, but it supports both the security of the transmitted data between Bob and Alice, and also proves the identity of both Bob and Alice. So with the Kerberos protocol, Alice and Bob first deposit their secret keys, and will define their unique identifies (such as their email addresses). Trent will then be trusted to store these keys. What we need now is to generate a session key between Bob and Alice that they can use, and also to be able for Trent to prove Alice’s identity to Bob, and also Bobs identity to Alice. An example is here:
Step 1: First Alice sends her identity, and Bob’s to Trent, who will then find the keys where relate to them.
Step 2: Next Trent creates a random key to be used for the session key, and create a Timestamp (T), a Lifetime (L), which define the starting time for the trust relationship, and how long it will be valid for. He will then create two parts to send back to Alice:
EA(T,L,K,B) and EB(T,L,K,A)
where is the first part is encrypted with Alice’s secret key, and the other part is encrypted with Bob’s secret key.
Step 3: Next Alice will decrypt the first part, and can thus determine T (the timestamp), L (the lifetime), K (the session key) and B (Bob’s Identity). Alice now knows the session key (K), and now uses it to encrypt the Timestamp (T) and Alice’s Identity (A) to Bob, along with the second part of the message from Trent [EB(T,L,K,A)]:
EK(T,A) and EB(T,L,K,A)
Step 4: Bob will then decrypt the second part, and determines the session key (K), which can be used to decrypt the first part. He will then check Alice’s identity is the same as the one that Trent sent.
Step 5: Bob takes the timetable and add one onto it, and sends back to Alice:
Step 6: Alice then decrypts with the session key, and checks the timestamp. If it checks with the expected value, then Bob has proven his identity. Bob and Alice and now communicate using the session key, and be secure, as only Trent will know the session key.
So Bob and Alice trust Trent! The key fundamental element of this, is that Bob neverhas to communicate withTrent, as he knows that the only person who has his key is Trent, so he is the only one able to encrypt the information contained within the information sent by Alice. Alice then cannot change her identity, as Bob will be able to determine this by checking what Trent has said is Alice’s identity is, with the identity that Alice produces, using the session key.
So let’s relate this to real life. Bob and Alice trust Trent, but want a way to identify each other and communicate in a secret way. So Alice goes to Trent and says that she has to prove her identity to Bob, and vice-versa. For this Trent will make a special key for a box, and will make a copy for Bob and Alice (he might also keep a copy for himself, just in case they lose them). Trent will then take a photograph of Alice, and write down the date and time on it, and the amount of time he can verify Alice for. He will then put it into the box, and gives the box to Alice, along with the key. Along with this he will give her a sealed letter for the attention Bob which has his stamp on it. Inside will be a photograph of Alice that he took, and the secret key, along with the date/time that he created the key.
Alice goes home, and then puts her photograph in the box, and locks it with the secret key. She then passes the box, without the key, along with the sealed letter to Bob. Bob opens the sealed letter, which has a key inside to open up the box, and which has the photograph that Trent took of Alice. Bob then opens the box with the secret key provided by Trent, and takes out the photograph that Alice has provided. If it is the same as the one that Trent put in the sealed letter, Bob thus verifies Alice’s identity.
Bob and Alice now have the same key to open and close the secret box, and can now use it to send secret messages to each other. No-one else will have that unique key, thus any messages in there must have been provided by Bob and Alice.
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 …
Like 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:
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.
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.
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:
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:
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:
different keys, so if you do the calculation you get:
which is a LONG TIME!
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?
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
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.
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. 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.
So 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:
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:
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?
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:
and even if we process at 10 billion keys per second it will take:
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
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
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:
which is a largely large number.
 DES is the standard encryption algorithm used in financial transactions and was first published in 1977.
 This differs from many applications in parallel processing which suffer from interprocess(or) communication
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.
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):
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:
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:
but when I try it again I get:
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:
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….
Computer Security is subject a great subject to study, especially that the area is ever changing, and basically involves the understanding of virtually everything to do with computing … including networks, software, embedded systems, people, crime, and so much more. The thing I love most is cryptography, especially that it is the continual battle between man and computer. A computers get more powerful by the day, and the cloud can distribute both the storage of information and also the processing, it gets more challenging for humans to keep anything secret from them. They thus can determine where we have been, what we have been watching, what we like to have for lunch, and what type of coffee we like, so it’s nice to know that we can still be them at cryptography. Well, we don’t actually beat them, we just make it so difficult, that eventually the humans controlling them will give up. In past times, as you can see from Figure 1, we could code our messages in a way that only Bob and Alice knew the secret code. Unfortunately there was no way of knowing that Eve had actually discovered the code. So humans have had to derive task which are so simple when you know a secret, but extremely difficult if you do not know it.
Big Numbers and Primes
When I first started in computing computers could only deal with 8 bits at a time – known as the 8-bit processors, such as the Intel 8008. Microprocessor technology then evolved through 16-bit processors (such as with the Intel 8086) and onto 32-bit ones (Intel 80386), and finally to 64-bit processors. Our current hardware architecture for most PCs and mobile devices runs on a 64-bit processor, even though much of the software still runs in a 32-bit mode. Thus most computers are optimized to run with values that are 64-bits long. So one of the ways to make life difficult for computers is to force them to deal with numbers that are much longer than this, such as for 256 bits (for private-key encryption) or 1,024 bit (for public-key encryption). These sizes of numbers make even the addition of two numbers a challenge task, taking many ticks of the clock. For a normal add operation the computer could, with two 64-bit numbers, do it in a fraction of a nano-second, whereas with 1,024 bits it becomes a major task to split the numbers up into chunks, and then perform the addition on the chunks, and with associated carry-over taken into account.
So we end up with the concept of Big Integers in cryptography. These are whole numbers who can be any size we want, and we can undertake some basic operations such as raising to a power, taking the modulus, adding, and so on.
So what does a Big Integer look like? Well for 512-bits we get numbers such as [Example]:
This might not seem a difficult task, as surely computers know all the prime numbers possible? Well the answer is no, it takes a great deal of computing power to determine if a number if prime, and we haven’t found them all yet. So normally what we do when we are selecting one is we pick a number, and test if it is prime, if not, take one away, and re-test, and so on, and eventually we will find one. For 1 to 100, here’s the list of primes:
A sample page to determine the prime numbers is here, and to test is here.
Lots of Keys
In standard key-based encryption, we can have a single key, which is secret between Bob and Alice, and then Bob will use it to encrypt his plaintext, and then Alice will use the same key to decrypt. If Bob and Alice know the key, it will be easy for them to encrypt and decrypt, but will be difficult for Eve, and she would have to search for all the possible keys. Thus the other thing we can do to defeat computers is to have lots of different keys – the more the better. Just like when you come home, and you’ve got lots of keys on your key ring, it can take a while to find the right key, the same happens for brute force cracking of encryption. For this the more bits that we have in a key, the more keys that will be possible. So it we had a four bit key, we could have 16 (2 to the power of 4) different keys: 0000, 0001, … 1110 and 1111). In this way we can calculate the key space, and where the average number of keys tried will be half the key space size (as you may be lucky at get it first time, or you may have to search to the end, but, on average, it will take half the key space size).
So we have a lot of keys, but we know that computers are actually very powerful in doing repetitive tasks, so lets determine how long it would take a standard computer to crack some codes which has a certain key size. Let’s start with 32 bits, which gives 4,294,967,296 keys. If we assume that it will take 1 nano seconds to try each key it will take:
T = 4,294,967,296 x 1 x 10^-9 /2 = 2.15 seconds
So it only takes 2 seconds to crack. Let’s try 56 bits (which is the basis of the DES encryption method). Now we have 72,057,594,037,927,936 keys and it will take 1.14 years to crack, on average. For 64-bits we have 18,446,744,073,709,551,616 keys and it will now take 292.47 years, on average, which should be enough to keep more messages secret.
But what about parallel processing and improving computing power? Check back for the next part of this discussion for more details on this.
If you are interested?
If you are interested in anything related to this subject, I’ve created a new presentation at: