Previously we looked at Public Key encryption, which is also called Asymmetric Encryption because it uses two different keys for the encryption and decryption. This allows us to solve one of the biggest problems in secure encrypted communication, which is key distribution. Because the public key can be freely distributed, you don’t need to maintain security around the process of distributing keys. Symmetric encryption, on the other hand, relies on a shared key that is used for both encryption and decryption. An example of this is the one-time pad, where you printed up a pad of paper that contained various keys, and each one was used only once. As long as no one can get the key, it is unbreakable, but the big weakness was key distribution. How do you get the one-time pad into the hands of your correspondent? And you would need to do this with separate one-time pads for each person you needed to communicate with. These are the kinds of problems that made asymmetric encryption so popular. Finally, symmetric key crypto cannot be used to reliably create a digital signature. The reason should be clear. If I have the same secret key you used to sign a message, I can alter the message, use the shared secret key myself, and claim you sent it.
There is a downside, though, to asymmetric encryption. It requires a good deal more in computational resources to perform asymmetric encryption and decryption. Symmetric crypto, on the other hand, is much more efficient. That is why in practice the two are actually combined. When you use GPG to encrypt a message, you use the public key of the person you are writing to. That much we have already covered. But what are you encrypting? It turns out you are encrypting the symmetric key that was actually used to encrypt the message itself! Yes, a symmetric key is used for the efficiency, but we solve the key distribution problem by using an asymmetric key to encrypt the symmetric key. So when someone sends you a message using your public key, you use your private key to decrypt the symmetric key, then use the symmetric key to decrypt the message itself. This is the best combination of security and efficiency in your communication.
Symmetric Encryption Standards
Data Encryption Standard (DES)
The very first standard popularly used was developed by IBM for the U.S. government and was called the Data Encryption Standard (DES). Without going into a highly technical description. DES employed some techniques that pop up frequently in cryptography, the Block Cipher, and XOR. In simple terms, a block cipher operates on a fixed-length block of bits to transform them in some way. And XOR provides one of the most common transformations. XOR stands for “Exclusive Or” and in logic that means “either A is true or B is true but not both”. If used in circuit design, if either A or B is sending a signal, the signal is output, but if both are sending a signal, nothing is output. When used in cryptography, what XOR does is to use a key that is “XORed” with the message block in such a way that if both the message and the key have a zero in that position, the result is a zero. If the message has a one and the key has a zero, the result is a one. If the message has a zero and the key as a one, the result is a one. And if the message has a one and the key has a one, the result is a zero. One way to think about that is that it is essentially binary addition without the “carry” part. In binary addition, one plus one equals “10”, which is the binary form of “2”, so you write down the zero and “carry the one”. In XOR, you just throw away the carry part altogether.
Understanding how this works begins with the coding. Recall that we distinguished between codes and ciphers earlier in this series. A code is just a one-to-one transform on information from one scheme to another. An example is Morse code. There is nothing secret about it, and the transformation usually is to render information in a way that fits the medium. In computers, everything is ones and zeros, so there is a code that takes our letters and turns them into binary digits. In fact, there are several, but for the purpose of illustration I will use ASCII, which is the American Standard Code for Information Interchange. In ASCII there is a numerical equivalent for every letter. I will do a very simple example, the word “cat”. I can see from the table on the Wikipedia page that c = 1100011, a = 1100001, and t = 1110100. So the word “cat” is represented in binary as 110001111000011110100. The other thing I need is a key. This needs to be a secret in real life, but I’ll tell you that it is “dog”, and by a similar process I can find that dog is represented in binary as 110010011011111100111. When I XOR these two, I get:
| Message | 1 | 1 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 0 | 1 | 0 | 0 |
| Key | 1 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | 1 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 1 | 1 | 1 |
| Result | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 0 | 0 | 0 | 1 | 1 | 1 | 0 | 0 | 0 | 1 | 0 | 0 | 1 | 1 |
And the reason this is useful as an encryption method is that if you XOR the key with the Result you get back the original message. Now, in constructing an encryption algorithm, you take a number of such methods and combine them to get something that is actually secure. In DES, the block size was selected as 64 bits. The key was also 64 bits, except that one bit from each byte was devoted to parity checking, so the effective key length is 56 bits. In creating the DES standard, you would see that processes were repeated for multiple rounds of transformation, which is common. So the final output could be the result of multiple XORs and other such stuff. But the reason is it is symmetric is, like we saw with the XOR process, if you have the key you can reverse all of the steps in the algorithm and get back the original message.
DES really is the beginning of modern cryptogrpahy. Bruce Schneier said about it “”DES did more to galvanize the field of cryptanalysis than anything else. Now there was an algorithm to study.” DES became the standard against which all other algorithms would be compared. But it was not the final word by any means. As we have seen previously, this is an arms race, and methods and technology continually evolve. DES was found to have some weaknesses, particularly in the key length. 56 bits was just too small as computers got better. The NSA had in fact tried to limit it to 48 bits, but resistance from the cryptographic community resulted in this slightly higher length. Nevertheless, in 1999 a DES key was cracked by brute force methods in 22 hours, and the standard has since been removed.
Triple DES
Triple DES attempts to solve the weakness of the 56 bit key in DES by using three independent 56 bit keys which are used in a repeated process. Each block of the message is encrypted three times, once each for the three keys. If done this way, it is generally regarded as secure, and NIST regards it as safe through 2030. On the other hand, there are theoretical attacks which, though not considered feasible with current technology, have lead to a new standard.
Advanced Encryption Standard (AES)
The Advanced Encryption Standard was adopted by NIST in 2001. This is now considered the best available symmetric encryption. It employs a cipher known as Rijndael, which is a play on the names of the two inventors, Vincent Rijman and Joan Daemen. This version of Rijndael used in AES has a block size of 128 bits, and key sizes of 128, 192, or 256 bits, and in general it can be referred to as AES-128, AES-192, or AES-256 depending on the key length, and the most secure would be AES-256. As with the other symmetric ciphers, each block is subjected to repeated rounds of transformation to get the encrypted text.
Asymmetric Encryption Standards
One thing you may have noticed in the above discussion of symmetric encryption is the lack of discussion of entropy in the process. It is not needed there, because the only thing that matters is that the key is agreed, not that it is random. But in asymmetric key encryption entropy is essential. It is the combination of the entropy with the one-way function that makes it work.
One way functions, as you may recall from our earlier discussion, are functions that can easily be computed in one direction, but are computationally infeasible in reverse. Right now there appear to be three types that are known and can be used in cryptography:
- Multiplying large prime numbers
- Discrete logarithm
- Elliptic curve
The mathematics of these approaches are more than I can handle. I suspect you need something like PhD in Math to make sense of this stuff, but maybe that is just me being dense. But here is the basics of each.
Prime number factorization
This is the approach used in RSA encryption. Two large prime numbers are found and multiplied together to get a product. Multiplying them together is simple for a computer, but decomposing the product to the two two primes you started with is computationally infeasible, so far as we know. Of course, since RSA is widely used, it has sparked intense interest in approaches to factorization, so this may get weakened over time. And of course with improvement in computer technology what now appears to be a difficult problem may become much simpler in the future. But for now RSA appears to be secure. The role of entropy in this case lies in finding the prime numbers. Generally they should each be in the neighborhood 1024 digits. And for security, they should not only be random, but not “near” each other.
With the large prime numbers found and multiplied, the product is used to generate other prime numbers which help form the public key and private key. The point here is that these are just two keys such that one key cannot decrypt anything it itself encrypted, but can decrypt anything its complementary key encrypted. So you could in theory use either one as the private key, it is not privileged. In fact, using the public key to decrypt something encrypted with the private key is the principle behind digital signatures, which we will discuss in the following tutorial.
Discrete Logarithm
Discrete logarithm involves finding an integer that solves a logarithmic equation. It is used in Elgamal encryption and Diffie-Hellman key exchange, among many uses. Choosing the particular numbers for the logarithmic equation is where the entropy comes in. Diffie-Hellman Key Exchange is used for perfect forward secrecy, among other uses.
Elliptic Curve
Elliptic Curve cryptography builds on the Discrete Logarithm approach. A curve with the right properties is chosen, then a point on that curve, and the problem becomes finding the discrete logarithm of that point. Generally the curve is chosen from a small number of appropriate curves that have been agreed upon by the crypto community. NIST has recommended 15 curves as suitable. Entropy enters when one chooses the point on the curve that will be used. Elliptic Curve Cryptography is usually faster and more efficient than RSA or general Discrete Logarithm approaches. However, it now appears that at least one of the curves selected was chosen by NSA to have deliberate weaknesses, so that particular curve is now deprecated. The larger question of whether any NIST standard can be trusted given the NSA’s involvement is still open.
So, this wraps up a somewhat more technical discussion of encryption methods which I hope will set us up to look at some other security problems and solutions.
Listen to the audio version of this post on Hacker Public Radio!
