Software Engineer A Primer On Symmetric-Key Encryption
For those who don't know me, I write open-source applications in my free time, one of which uses symmetric-key encryption. I am by no means an expert, but I have spent so much time researching encryption for my hobbies that I feel qualified enough and compelled to write about it.
When I started my application, I knew next to nothing about encryption. All I wanted was to find some magical library that had an "EncryptString()" function and a "DecryptString()" function, and I didn't care how it worked or how secure it was as long as the crypt-text was obscure enough that a human couldn't read it. Online searches led me to the Crypto++ library, from which examples I was able to find the encryption functions I needed. As it turned out the encryption I chose was very weak; it used an outdated and now broken block-cipher, it used the default cipher mode, which I can only assume is too generic for my needs, and I had no strategy for key derivation (all concepts to be discussed in this post). Now that the initial version of my password application has been out almost 5 years, I'm working on a brand-spanking new version and I decided I wanted to really understand the encryption side of things and do it right. I wanted to write an application that even decades from now is still secure, and I wanted to be able to explain to someone why it is secure.
So that started my crusade to understand this stuff. I spent weeks poring over white papers and online articles about encryption to find out what my options were and how it all works, and now I'm going to neatly summarize it for you in this post. The intended audience is someone who wants to learn about symmetric-key encryption at a high level without getting into details about the specific block ciphers and cipher modes. Maybe you're going to write your own application that uses an encryption library and you don't know where to start, or maybe you're just a layman interested in the topic of encryption and data security in general. Whatever your situation, I hope you get a lot of useful information from this article and share it with your geek friends.
When I started my application, I knew next to nothing about encryption. All I wanted was to find some magical library that had an "EncryptString()" function and a "DecryptString()" function, and I didn't care how it worked or how secure it was as long as the crypt-text was obscure enough that a human couldn't read it. Online searches led me to the Crypto++ library, from which examples I was able to find the encryption functions I needed. As it turned out the encryption I chose was very weak; it used an outdated and now broken block-cipher, it used the default cipher mode, which I can only assume is too generic for my needs, and I had no strategy for key derivation (all concepts to be discussed in this post). Now that the initial version of my password application has been out almost 5 years, I'm working on a brand-spanking new version and I decided I wanted to really understand the encryption side of things and do it right. I wanted to write an application that even decades from now is still secure, and I wanted to be able to explain to someone why it is secure.
So that started my crusade to understand this stuff. I spent weeks poring over white papers and online articles about encryption to find out what my options were and how it all works, and now I'm going to neatly summarize it for you in this post. The intended audience is someone who wants to learn about symmetric-key encryption at a high level without getting into details about the specific block ciphers and cipher modes. Maybe you're going to write your own application that uses an encryption library and you don't know where to start, or maybe you're just a layman interested in the topic of encryption and data security in general. Whatever your situation, I hope you get a lot of useful information from this article and share it with your geek friends.
What is Symmetric-Key Encryption?
There are a myriad of types of encryption, and symmetric-key (aka shared-key) encryption is the type where the same key that is used to encrypt the message is also used to decrypt it. This form of encryption is used, for example, in my password application because the user's master password is used to encrypt the data and also to decrypt it. This is different than the encryption websites use (https), because the website has its own keys which are different than your keys (called public-key encryption). However, in this post I will only be talking about symmetric-key encryption.
There are two basic things that you might want from an encryption algorithm. First and foremost you want confidentiality, meaning that the message you send should be completely obscured to all parties except those who know the secret key. In practice, the message ciphertext should look indistinguishable from random data, and there can be no way to generate the plaintext again without possessing the original key. The second thing you might want is a guarantee of authenticity. In other words a guarantee that the message you're reading is the exact same message that was sent, without any corruption, malicious or otherwise. I will dissect both of these concepts and show how they can be achieved.
To help make this less abstract, let's talk concretely about a cipher mode called CBC (Cipher-Block Chaining). Below is a diagram I stole from Wikipedia that shows how CBC works. Basically it takes the entire plaintext message and divides it into block-sized chunks so they will each fit into the block cipher. Before feeding the first block into the cipher, you must create an Initialization Vector (IV) to initialize the encryption. The IV is usually generated randomly or incremented like a counter to guarantee uniqueness (it's also called a "nonce" for that reason, meaning that it should only be used once), and as long as the IV is unique the generated ciphertext is guaranteed to be completely different each time you encrypt a message. That means even if you encrypt the same message multiple times with the same key, you will always get a completely different ciphertext each time. This is an important aspect of confidentiality, because even though they can't read the ciphertext, you still don't want a man in the middle to see if you're sending the same message twice, because maybe he can send it a third time and see what happens.
The reason you need to know about cipher modes is because different modes have different properties. For example, CBC as discussed above, does not implement an authenticity check on the message. That means that you have no idea if what you decrypt is valid or not, unless you implement your own checks (maybe tag it with a known string or use a checksum). Different modes also may have different rules governing the Initialization Vector. Some of them expect a specific sized IV, others let you choose within a range of sizes, thus allowing you to tune other properties of the cipher mode. For example CCM (Counter with CBC + MAC, discussed below) lets you choose in a range of 7-13 byte nonces, which determine A.) The maximum payload size for encryption, and B.) How many times you can use the key before it becomes stale. To understand the former, you need to do some homework and read the NIST paper on CCM (hint: That's where I learned about all of this!) The latter seems intuitive to me though: since you can never reuse a nonce, the longer size you pick the more nonces you can go through before reusing one.
CCM lets you generate nonces randomly or deterministically as with a counter. If you use a counter then you know exactly how many times you can use the key before it becomes stale (until the counter rolls over), but if you generate nonces randomly you have to take probability into account. The rule is that you should consider your key stale after the probability of nonce collision is greater than 2^-32 (which is the same odds as guessing a random 32-bit integer in one try). So it's incredibly low but that just emphasizes how bad it is to reuse a nonce. It breaks the encryption for that key.
Yet another cool thing with CCM is that it can also validate a payload of plaintext "authenticated data" alongside, or instead of, the encrypted payload. So let's say you want to send a message and you don't care who reads it (perhaps the contents will be made public anyways), but you want to make damn sure that the receiver knows that it was you who sent it. Then you can use CCM to create a MAC for your plaintext, and if the receiver has the same key as you he will generate the same MAC and know with certainty that the entire message is authentic and it came only from you. Admittedly the encryption part is much more useful, but there are use cases for the plaintext authenticated data, and anyways I think it's pretty cool.
There are two basic things that you might want from an encryption algorithm. First and foremost you want confidentiality, meaning that the message you send should be completely obscured to all parties except those who know the secret key. In practice, the message ciphertext should look indistinguishable from random data, and there can be no way to generate the plaintext again without possessing the original key. The second thing you might want is a guarantee of authenticity. In other words a guarantee that the message you're reading is the exact same message that was sent, without any corruption, malicious or otherwise. I will dissect both of these concepts and show how they can be achieved.
Obscuring the Message
Encrypting data requires feeding it through something called a block cipher. The best block cipher is currently AES (Advanced Encryption Standard). A block cipher behaves like this: it takes a block of data of fixed size and generates a block of ciphertext with the same size as the input block. It uses a secret key of a fixed size to encrypt and decrypt the data. Using a block cipher by itself, you can only encrypt/decrypt data that is less than or equal to the size of the block. So how do you encrypt messages that are larger than a single block size? That is where the cipher mode comes in. The cipher mode does the job of "gluing" several blocks together into an arbitrarily long message. So the block cipher encrypts single blocks of data, and the cipher mode determines how to glue the blocks together so they form a coherent ciphertext that can be decrypted using the same block cipher and mode.To help make this less abstract, let's talk concretely about a cipher mode called CBC (Cipher-Block Chaining). Below is a diagram I stole from Wikipedia that shows how CBC works. Basically it takes the entire plaintext message and divides it into block-sized chunks so they will each fit into the block cipher. Before feeding the first block into the cipher, you must create an Initialization Vector (IV) to initialize the encryption. The IV is usually generated randomly or incremented like a counter to guarantee uniqueness (it's also called a "nonce" for that reason, meaning that it should only be used once), and as long as the IV is unique the generated ciphertext is guaranteed to be completely different each time you encrypt a message. That means even if you encrypt the same message multiple times with the same key, you will always get a completely different ciphertext each time. This is an important aspect of confidentiality, because even though they can't read the ciphertext, you still don't want a man in the middle to see if you're sending the same message twice, because maybe he can send it a third time and see what happens.
CCM lets you generate nonces randomly or deterministically as with a counter. If you use a counter then you know exactly how many times you can use the key before it becomes stale (until the counter rolls over), but if you generate nonces randomly you have to take probability into account. The rule is that you should consider your key stale after the probability of nonce collision is greater than 2^-32 (which is the same odds as guessing a random 32-bit integer in one try). So it's incredibly low but that just emphasizes how bad it is to reuse a nonce. It breaks the encryption for that key.
Authenticating the Message
I will talk about authentication using the CCM mode, because it has the ability to authenticate messages, but there are also lots of other ways of doing it. Counter with CBC+MAC means that it is a combination of the Counter mode, Cipher Block Chaining mode and a Message Authentication Code, the last of which is used to validate authenticity. It uses a special hash function which takes the entire payload as input and produces a MAC with which you tag the message. Then when the receiver decrypts it, they compute the hash again and expect the same MAC. If the MAC is different than the purported MAC sent with the message, then the message is junk. That could happen if the key was wrong, or if any part of the message was tampered with or corrupted.Yet another cool thing with CCM is that it can also validate a payload of plaintext "authenticated data" alongside, or instead of, the encrypted payload. So let's say you want to send a message and you don't care who reads it (perhaps the contents will be made public anyways), but you want to make damn sure that the receiver knows that it was you who sent it. Then you can use CCM to create a MAC for your plaintext, and if the receiver has the same key as you he will generate the same MAC and know with certainty that the entire message is authentic and it came only from you. Admittedly the encryption part is much more useful, but there are use cases for the plaintext authenticated data, and anyways I think it's pretty cool.
Generating Keys
The last major thing you need to know about is key generation. Your block cipher will determine the key sizes allowed, but basically you have to make a Key Derivation Function (KDF) which derives some fixed size byte sequence from the user's password and/or keyfile. Since the password/keyfile can be any size, you have to pass them through a hash function like SHA-256 and use the fixed-size output as a key.
I already mentioned that when your key becomes stale you have to generate a new one, but how can you do that if the key was generated from a password? Do you have to force the user to use a new password? Thankfully you don't, as long as you design it that way. Since you're using a hash function in the KDF, you can "salt" the hash with some random data that you'll need to keep as long as the key is in use. This salt guarantees that every encryption key is unique, even though the user's password may be the same.
There is another very important thing you need to consider before implementing a simple key derivation function like the one I described above. What is to prevent someone from intercepting a message and guessing the key? If they know the key was made from a password they can do a simple dictionary attack and eventually break your key. To mitigate this risk, besides obviously using a strong password, you want to make it very costly for them to do a dictionary attack. If you're using salt in your KDF, then the attacker must generate a new dictionary of keys using that salt. And if it's really expensive to generate a key, then they may as well give up because they'll spend the remaining life of the universe generating keys for their dictionary. At least that's the idea. To make your KDF expensive I read that it's encouraged to re-hash the result of every previous hash many, many times and use the last result as the key. The paper I read suggested re-hashing 65 thousand times, and increasing this over time as hardware becomes faster. This doesn't affect the user who knows the password, because generating a single key still happens fast enough that it's not inconvenient, but if you want to generate millions or billions of keys, you will spend a very long time hashing.
Where to Go From Here?
If you find this kind of stuff interesting, hopefully this gave you some guidance that points you to the things you need to know about. You can read any of the NIST papers, like the ones about the cipher modes GCM and CCM Coming soon I will make another post about how I implemented the encryption in my Gryptonite application, and I will discuss how I addressed all of the topics above. If you're a programmer I encourage you to try out Crypto++. I learned a ton just by playing around with it and reading the online documentation for the different cipher modes. Plus it's open-source so if you're geeky enough you can really dive in and see how all of this is implemented.
