Crash course on cryptography: Secret key cryptography

Secret key cryptography uses a single key which both parties (usually named Alice and Bob) both must know. They must keep this key a secret (hence the name) from an eavesdropper (named Eve), otherwise Eve will be able to decrypt any messages encrypted using that key.

Alice uses a secret key encryption scheme (or cryptographic algorithm) to transform a message into something resembling random noise. The scheme may be publicly known. The security of the system comes from the secret key that Alice uses. The transformation can only be undone by Bob and Alice herself, since only they know the secret key.

The basic principle

Encryption and decryption using a secret key

To secretly communicate with Bob, Alice encrypts her messages before sending them. There are many techniques (cryptographic algorithms) that she can use. All these algorithms have in common that they can transform a message using a key into something that resembles random noise. This is called encrypting the message. Only the persons who know the key can transform the random noise back into the original message, or in other words, decrypt the message. This means that those persons must keep this key a secret, hence the name secret key cryptography.

How to get the key to the recipient

A fundamental problem with secret key encryption is that somehow the secret key has to be delivered to the recipient of the message in a secure way. Once that key has been securely delivered, other keys can be delivered by simply encrypting them with that first key. One way to solve this problem is to have Alice and Bob meet in person so they can agree on a key. They must make sure that Eve is not listening in on them, otherwise Eve also learns the key. This applies especially if Alice and Bob agree on a key via telephone or e-mail. Of course Bob must also be able to distinguish Alice and Eve if they meet for the first time (for Alice it shouldn't be a problem to tell Bob from Eve).

If Alice and Bob can not meet in private to agree on the key, it is very difficult for them to use secret key cryptography. If they simply agree on a key by e-mail for example, Eve could be listening in on their e-mail conversation and thus also learn what the key is. If Alice and Bob had a secure channel that Eve could not tap, they could use that channel to agree on a secret key. However, then they could also use the secure channel to simply transmit their messages.

This problem is solved by using public key cryptography, which is discussed in the next chapter.

How secret key cryptography works

Secret key cryptography transforms (scrambles) a message into something resembling random noise. The precise transformation is determined by the key. Mathematically seen, a cryptographic algorithm is a function that maps a message onto a ciphertext (an encrypted message). By using keys, it is possible to encrypt many different messages using one particular cryptographic algorithm in different ways. And keeping the key a secret is much easier than keeping a complete algorithm a secret.

Some cryptographic algorithms operate on single characters of the message. These are called stream ciphers. Others operate on entire blocks, and therefore are called block ciphers. Stream ciphers are easier to implement in hardware than block ciphers, and they are also generally faster. Block ciphers tend to be harder to crack.

Popular cryptographic algorithms are DES, 3-DES, IDEA, Blowfish and recently also the Advanced Encryption Standard (AES).

An example of a secret key cryptographic system

A very simple technique to encrypt messages is to replace every letter of the message with one that is a certain number of positions further in the alphabet. The key then is the number of positions. For example, the message "This is an example" can be encrypted using the key "1 position" into the encrypted message "Uijt jt bo fybnqmf". Taking the letter that is 1 position previous in the alphabet results in the original message again.

This system is of course not very secure. There are only twenty-six possible keys. Eve can simply try out all the keys to see which one results in a readable message. Furthermore, it is a well-known fact that certain letters occur more often in messages than others. The letter "e" is the most frequently used letter in the English language, for example. Using this fact Eve can simply count which letter occurs the most often in the encrypted message and replace that one with the letter "e". She then knows how many positions she has to rotate to get from "e" to the encrypted version of "e" and thus she immediately knows the key.

One-time pads

In principle, all cryptographic systems can be broken. At the very least, Eve can try out all different keys until she finds one that successfully decrypts the message. Eve might also be able to break one of the mathematical principles behind the cryptographic algorithm that Alice and Bob use. For example, some cryptographic systems assume that it is very difficult to divide a number into its prime factors. Eve might find a quick way to do this. This then enables Eve to read Alice and Bob's messages or to recover their keys.

There is one cryptographic algorithm that cannot be broken. This algorithm is called the one-time pad (OTP). According to this algorithm, Alice generates a very large sequence of random numbers. The numbers in the sequence serve as the key. The sequence is called the "pad". Alice communicates the sequence to Bob in a secure way, so that Eve cannot obtain a copy of the key.

Every character in the message that Alice wants to send to Bob is encrypted with a different number in the sequence. In practice this means that the first character of the message will be encrypted with the first number in the sequence, the second character with the second number, and so on. When Bob receives the encrypted message, he takes out his copy of the sequence and simply decrypts the first character with the first number in the sequence, the second character with the second number, and so on.

Because every character of the message is encrypted with a different key, there is nothing Eve can do to guess the key. Even if she knew that the first words of the message were "Dear Bob", she could not use this information to recover the key of other words in the message. Every number is chosen randomly, so Eve has no way to know which number is the right one, even if Eve knew how to decrypt all other characters.

It is absolutely essential that every number in the sequence is chosen randomly and is only used once. If Eve can recover some of the numbers in the sequence and use those to predict other numbers, she can eventually reconstruct the entire sequence and thereby decrypt the message. For this reason it is not a good idea to use a random number generator implemented in software. Those generators are unable to generate really random numbers. They use a mathematical function that generates a set of numbers that appears to be random. But if you know the mathematical function and the number that it last generated, you can immediately compute the next "random" number.

To achieve this unbreakability, Alice and Bob must have very large sequences that contain only really random numbers. This makes an OTP very difficult to manage. It is said to have been used for the "hotline" between Washington and Moscow during the Cold War. In a case like that, it is practical to send couriers carrying suitcases chained to their arms to securely transmit the pad.

Applications of secret key cryptography

Secret key encryption is most often used to encrypt data to be stored on a particular location. If the encrypted data has to be transmitted, there always is the problem of how to get the secret key to the recipient in a safe way. Usually the key is encrypted using public key encryption so it can be transmitted safely.

Hiding spoilers

Even though it is not secure, the simple alphabet shifting system is still in use on the Internet. It is used to hide "spoilers" (revealing plot twists in movies or books) and potentially offensive messages from unsuspecting readers. Such messages are encrypted using the key "13 positions". Anyone can thus decrypt the message by simply taking the letter that is 13 positions previous in the alphabet. However, this requires some active step by the reader, and so he should then not be surprised or upset if the decrypted message reveals something about the plot of a movie he wanted to see. This system is commonly known as "ROT-13".

Encrypting the contents of hard disks

Using secret key encryption Alice can encrypt her entire hard disk so the data on it is safe if the disk (or laptop containing it) is ever stolen. Disk encryption programs exist that can encrypt and decrypt data as it is being written and read to and from the hard disk. This way Alice does not notice that her data is stored encrypted, except for the fact that disk access might be a bit slower. Once she turns off her computer, it is not possible anymore for Eve to read the data.

Protecting pay TV transmissions

Secret key encryption and smart cards are used for example in pay TV applications. Sometimes this is referred to as "conditional access" television. Television programs (usually premium movies, football or soccer matches and adult content) are encrypted using a secret key. To make it difficult for Eve to obtain this key, the secret key is changed every few minutes or sometimes even every few seconds. This way, even if Eve can successfully use a brute force attack to guess the key, she only has a very small portion of the television program. Alice has a set-top box and a smart card that allows her to decrypt the television programs. The set-top box passes the decrypted television program on to the television. Originally these boxes were designed to be placed on top of the television set, hence the name.

Special messages, called Entitlement Control Messages (ECMs), are sent along with the program. These messages contain the secret keys. Of course the ECMs themselves are also encrypted, this time using a key stored on the smart card. Alice's set-top box receives the ECMs and passes them on to the smart card. The smart card decrypts the ECMs and extracts the secret keys contained therein. This allows the set-top box to decrypt the television program.

The keys needed to decrypt the ECMs can be programmed on the smart card in advance. By regularly changing these keys, Alice is forced to purchase a new smart card every month or so. If Eve manages to make a copy of the smart card, or to extract the keys from it, she will only be able to watch the programs for the rest of that particular month.

Another option is to regularly send out so-called Entitlement Management Messages (EMMs) that contain the keys needed to decrypt the ECMs. The EMMs themselves are then encrypted with keys stored on the smart card. The service provider then every month simply sends out a new EMM. This provides much greater flexibility, and Alice does not have to go to the store every month. Every smart card can now have a different key. The service provider sends out different EMMs for all the smart cards in the system. Every EMM thus is readable only by one smart card. If the service provider thinks a particular smart card has been copied illegally, he simply does not send out a new EMM for that particular smart card.

All parts