arantius
11-04-2002, 03:43 PM
It seems to me that a lot of people do not understand how/why PKI encryption works, and why SEQ is really broken. Consider this my contribution to the project :)
Note: The reason I know any of this is because when PoP came out, I went to the library and got some books and read them. Especially if you do not understand what follows, I suggest you do the same.
Other Note: I am not infallible, and there could be mistakes here, feel free to correct me but please do so constructively.
Ok, so let's get started. There are multiple kinds of encryption. We need not go into any history now, but explain the two kinds of encryption that are prevalent on computers. These are symmetric key and public/private key, or public key for short. Here already we have introduced terminology we must explain. First, we must understand the concept of a key. It is very similar to a physical lock and key. There can be many different keys, but only one particular key will open the lock I have secured, for example, my briefcase with.
The symmetric key encryption is again very similar to a physical lock that holds a box closed. When you put the lock onto the box, you do it with the key, and use that same key to open the lock at a later time.
In encryption, that means there is one magic number that will do both things, encrypt and decrypt. So to examplify symmetric key encryption, imagine that our key is three, and our message is feed.
Plaintext: 6 5 5 4
Encryption: 6+3 5+3 5+3 4+3
Ciphertext: 9 8 8 7
What we have done is turn the word feed into the word ihhg. Though this is a trivial encryption, we can see that the message has been basically changed. We use the same key, 3, but a slightly different operation to decrypt the message.
Ciphertext: 9 8 8 7
Decryption: 6-3 5-3 5-3 4-3
Plaintext: 6 5 5 4
So that is how symmetric key processing works. Note that addition/subtraction is the simplest example and is the reason it was chosen to make the example. Multiplication/division would work as well. The two operations must simply be inverses of each other. Inverse functions perform opposite transformations. Multiplcation by two doubles a number, while division by two halves it. Take any number, multiply by two and then divide by two and the final result is the same, yet there is a third intermediary form which is different. This is the heart of encryption, take plain text, make it something different (ciphertext), and be able to turn it back into the plain text.
Symmetric key encryption is no longer secure in today's world of computers. DES was once the de facto standard for encryption, and is a symmetric key system. Although DES uses 56 bits, making 2^56 combinations or approximately 72,000,000,000,000,000 different unique keys, with high powered computers DES can be broken in under a day.
It may be worth noting here that the bulk of EQ traffic is encrypted with a symmetric key algorithm. To break a symmetric key algorithm a cryptanalyst needs know only two things. The decryption algorithm, and the secret key. You likely know that EQ makes a different key each time you zone. The server and your computer must both know this key to be able to encrypt and decrypt the information and have it make sense. Distribution of secret keys for symmetric algorithms is a challenge. This is where public key encryption comes in.
Public key encryption is at the basis the same, but much harder to understand because it is more complicated. It is still based on the idea of inverse functions, but in this case instead of using opposite functions with the same key, it uses two seperate keys, one to encrypt with and one to decrypt with.
How can this be you say? If I add one and then subtract two, I am not left with the same number! Well, the answer is that neither addition nor multiplication are used. The primary work of public key encryption is done with modular inverses.
So, what is a modular inverse? Think about division. If I ask you, what's eight divided by four, you would quickly reply two. But what if I ask what is nine divided by four? Umm.. uhh.. two point something? Think back to fourth grade! It is two with a remainder of one! The remainder is an often overlooked feature of division that is the heart of public key encryption.
Now for an example. Let's take our original secret message, feed or 6 5 5 4, and encrypt it with a public key system. Remember, a public key system uses two keys. It is such named because one key is public, or safe to distribute, and one key is private, which must be kept secret. The public key encodes, and the private key decodes. This way, anyone can encode a message with the public key you can freely give them, and only your private key will turn it back into a sensible message.
We will take this example one letter at a time, because the steps are much more complicated than just adding three. First thing though, we must select keys. I have purposely selected my word to use low letters, whose numbers are single digits. This way I can choose simple keys. Selection of keys is a complicated process. Let us just say that prime numbers are the best (go get a book to understand this part, it will explain it much better than me). Also, it must satisfy a particular forumla, notably:
(p * a * b) mod c = p
Or, the plain text p times a times b is some number, then mod (modulus, or the remainder of division) that number by c, and the final result will be the original plaintext p. Example, the first letter of our message:
(6 * 3 * 7) = 126
126 mod 10 = 6
So what does this mean? This means that if our keys are 3 and 7, we can use these two numbers to change our plaintext into something else. Continued example:
Plaintext: 6 5 5 4
Encryption: (6*3 mod 10) (5*3 mod 10) (5*3 mod 10) (4*3 mod 10)
Ciphertext: 8 5 5 2
We have used 3 as our public key. We can use the same function with our private key, 7, to turn the message back:
Ciphertext: 8 5 5 2
Encryption: (8*7 mod 10) (5*7 mod 10) (5*7 mod 10) (2*7 mod 10)
Plaintext: 6 5 5 4
Do you see? Eight times seven is 56, mod 10 is 6, our original number.
Suffice to say that working in single digits to make an easily understood example is far from a secure method. This is why real encryption uses huge numbers, up to as many as 1024 bits which, suffice to say, is a really big number. These bigger numbers make the transformations much more complex. Here is another example.
Public key: 23 mod 101
Plaintext: Bomb at five AM, or 2 15 16 2 1 20 6 9 22 5 1 16
Ciphertext: 46 42 65 46 23 56 37 5 1 14 23 65
Here is an exersize for you. What is the private key that will decode this message? You know the public key ends in mod 101, so the number has to be less than 101, but that is 100 different numbers to try. You can try multiplying each number and then taking mod 101, and then replacing numbers with letters to see if it makes sense, 100 times. But this will be very time consuming. Now imagine if there were not 100 possible keys, but a million, or billion, or quadrillion! Here's the secret: the private key is 22. Take each number in the ciphertext, multiply by 22, and then take the remainder when you divide by 101. Don't be surprised if you are left with the plaintext!
This is the secret behind public key encryption. I can tell anyone in the world to turn their messages into numbers, A starting at 1, then take each number and multiply by 23, then divide by 101 and take the remainder as the ciphertext for that letter. Now, I can do the same but with 22 instead of 23, and have the secret message quickly. Everyone else must try 100 different combinations though. Again, using larger keys the challenge becomes obvious. The secret as it applies to EQ is even though the secret of public key encryption is making a problem that is easy to solve for the intended recipient, and difficult to solve for anyone else, it is still slow. So, EQ uses slow public encryption with a very large key to safely transmit the symmetric key that encrypts the bulk of the data. Your computer generates a symmetric key, and then encodes it with the server's public key. It transmits this encrypted version, and the server now knows the same key as your computer, to use efficient symmetric key encryption with, since this is faster. The trick is sharing the key between server and client, which is done with public keys. As shown, this public key encryption is not something as simple as "know the decrypt function" Though we may know, take message times x then mod 101, we don't know what x is, and the only way is to steal it from the EQ client's memory, since it must know the key.
I hope this has helped someone understand a little more about encryption. I'll try to watch comments to this thread, and update this post if someone points out mistakes or something I deem worth adding :)
Note: The reason I know any of this is because when PoP came out, I went to the library and got some books and read them. Especially if you do not understand what follows, I suggest you do the same.
Other Note: I am not infallible, and there could be mistakes here, feel free to correct me but please do so constructively.
Ok, so let's get started. There are multiple kinds of encryption. We need not go into any history now, but explain the two kinds of encryption that are prevalent on computers. These are symmetric key and public/private key, or public key for short. Here already we have introduced terminology we must explain. First, we must understand the concept of a key. It is very similar to a physical lock and key. There can be many different keys, but only one particular key will open the lock I have secured, for example, my briefcase with.
The symmetric key encryption is again very similar to a physical lock that holds a box closed. When you put the lock onto the box, you do it with the key, and use that same key to open the lock at a later time.
In encryption, that means there is one magic number that will do both things, encrypt and decrypt. So to examplify symmetric key encryption, imagine that our key is three, and our message is feed.
Plaintext: 6 5 5 4
Encryption: 6+3 5+3 5+3 4+3
Ciphertext: 9 8 8 7
What we have done is turn the word feed into the word ihhg. Though this is a trivial encryption, we can see that the message has been basically changed. We use the same key, 3, but a slightly different operation to decrypt the message.
Ciphertext: 9 8 8 7
Decryption: 6-3 5-3 5-3 4-3
Plaintext: 6 5 5 4
So that is how symmetric key processing works. Note that addition/subtraction is the simplest example and is the reason it was chosen to make the example. Multiplication/division would work as well. The two operations must simply be inverses of each other. Inverse functions perform opposite transformations. Multiplcation by two doubles a number, while division by two halves it. Take any number, multiply by two and then divide by two and the final result is the same, yet there is a third intermediary form which is different. This is the heart of encryption, take plain text, make it something different (ciphertext), and be able to turn it back into the plain text.
Symmetric key encryption is no longer secure in today's world of computers. DES was once the de facto standard for encryption, and is a symmetric key system. Although DES uses 56 bits, making 2^56 combinations or approximately 72,000,000,000,000,000 different unique keys, with high powered computers DES can be broken in under a day.
It may be worth noting here that the bulk of EQ traffic is encrypted with a symmetric key algorithm. To break a symmetric key algorithm a cryptanalyst needs know only two things. The decryption algorithm, and the secret key. You likely know that EQ makes a different key each time you zone. The server and your computer must both know this key to be able to encrypt and decrypt the information and have it make sense. Distribution of secret keys for symmetric algorithms is a challenge. This is where public key encryption comes in.
Public key encryption is at the basis the same, but much harder to understand because it is more complicated. It is still based on the idea of inverse functions, but in this case instead of using opposite functions with the same key, it uses two seperate keys, one to encrypt with and one to decrypt with.
How can this be you say? If I add one and then subtract two, I am not left with the same number! Well, the answer is that neither addition nor multiplication are used. The primary work of public key encryption is done with modular inverses.
So, what is a modular inverse? Think about division. If I ask you, what's eight divided by four, you would quickly reply two. But what if I ask what is nine divided by four? Umm.. uhh.. two point something? Think back to fourth grade! It is two with a remainder of one! The remainder is an often overlooked feature of division that is the heart of public key encryption.
Now for an example. Let's take our original secret message, feed or 6 5 5 4, and encrypt it with a public key system. Remember, a public key system uses two keys. It is such named because one key is public, or safe to distribute, and one key is private, which must be kept secret. The public key encodes, and the private key decodes. This way, anyone can encode a message with the public key you can freely give them, and only your private key will turn it back into a sensible message.
We will take this example one letter at a time, because the steps are much more complicated than just adding three. First thing though, we must select keys. I have purposely selected my word to use low letters, whose numbers are single digits. This way I can choose simple keys. Selection of keys is a complicated process. Let us just say that prime numbers are the best (go get a book to understand this part, it will explain it much better than me). Also, it must satisfy a particular forumla, notably:
(p * a * b) mod c = p
Or, the plain text p times a times b is some number, then mod (modulus, or the remainder of division) that number by c, and the final result will be the original plaintext p. Example, the first letter of our message:
(6 * 3 * 7) = 126
126 mod 10 = 6
So what does this mean? This means that if our keys are 3 and 7, we can use these two numbers to change our plaintext into something else. Continued example:
Plaintext: 6 5 5 4
Encryption: (6*3 mod 10) (5*3 mod 10) (5*3 mod 10) (4*3 mod 10)
Ciphertext: 8 5 5 2
We have used 3 as our public key. We can use the same function with our private key, 7, to turn the message back:
Ciphertext: 8 5 5 2
Encryption: (8*7 mod 10) (5*7 mod 10) (5*7 mod 10) (2*7 mod 10)
Plaintext: 6 5 5 4
Do you see? Eight times seven is 56, mod 10 is 6, our original number.
Suffice to say that working in single digits to make an easily understood example is far from a secure method. This is why real encryption uses huge numbers, up to as many as 1024 bits which, suffice to say, is a really big number. These bigger numbers make the transformations much more complex. Here is another example.
Public key: 23 mod 101
Plaintext: Bomb at five AM, or 2 15 16 2 1 20 6 9 22 5 1 16
Ciphertext: 46 42 65 46 23 56 37 5 1 14 23 65
Here is an exersize for you. What is the private key that will decode this message? You know the public key ends in mod 101, so the number has to be less than 101, but that is 100 different numbers to try. You can try multiplying each number and then taking mod 101, and then replacing numbers with letters to see if it makes sense, 100 times. But this will be very time consuming. Now imagine if there were not 100 possible keys, but a million, or billion, or quadrillion! Here's the secret: the private key is 22. Take each number in the ciphertext, multiply by 22, and then take the remainder when you divide by 101. Don't be surprised if you are left with the plaintext!
This is the secret behind public key encryption. I can tell anyone in the world to turn their messages into numbers, A starting at 1, then take each number and multiply by 23, then divide by 101 and take the remainder as the ciphertext for that letter. Now, I can do the same but with 22 instead of 23, and have the secret message quickly. Everyone else must try 100 different combinations though. Again, using larger keys the challenge becomes obvious. The secret as it applies to EQ is even though the secret of public key encryption is making a problem that is easy to solve for the intended recipient, and difficult to solve for anyone else, it is still slow. So, EQ uses slow public encryption with a very large key to safely transmit the symmetric key that encrypts the bulk of the data. Your computer generates a symmetric key, and then encodes it with the server's public key. It transmits this encrypted version, and the server now knows the same key as your computer, to use efficient symmetric key encryption with, since this is faster. The trick is sharing the key between server and client, which is done with public keys. As shown, this public key encryption is not something as simple as "know the decrypt function" Though we may know, take message times x then mod 101, we don't know what x is, and the only way is to steal it from the EQ client's memory, since it must know the key.
I hope this has helped someone understand a little more about encryption. I'll try to watch comments to this thread, and update this post if someone points out mistakes or something I deem worth adding :)