Published: 18 Jul 2007
By: Derek Smyth

This article describes the internal workings of symmetric encryption; also known as secret key encryption. Concentrating mostly on the older DES encryption method this article doesn't contain any code examples and intends to cover the internals in a manner that isn't technology specific.

Algorithms in newer secret key encryption methods, such as Rijndael, differ from DES. However, there are some similarities. Hopefully reading this article will give you a better understanding of a symmetrical encryption process and help you to make better decisions when using it.

Introduction

There really is no need to know the internals of an encryption technology as the various classes provided by the Windows Crypto Service Provider - and, more recently, the managed cryptography classes of the .NET framework - hide most of the mathematical complexities involved with encryption, allowing developers to concentrate more on the important issue of protecting the key.

So you might be wondering, with a lack of code examples, why you'd need to read this article. Taking a car as an example, then knowing how to drive will get you from A to B but having some knowledge of how the engine consumes fuel, for example, helps you to save fuel, money, and perhaps large repair bills from wear and tear.

Knowing how to use a technology is one thing. Having a bit more knowledge on how the technology works assists in making decisions that improve performance and - with encryption - security.

What is encryption?

The concept behind encryption is simple: To protect data so that only certain people can unprotect it. The simplest way to do this with computers - where data is represented in bits of 1's and 0's - is to shuffle the bits around, and that's all encryption really is. At its lowest denominator, it's just a bit shuffler.

Now, that's an extremely over simplistic view of encryption and doesn't give the highly intelligent mathematicians that create - and try to crack - these 'shufflers' any justice at all.

However, it is worthwhile keeping the 'shuffler' point of view in mind. No matter how complex the process is, at the end of the day it's just moving bits around. Actually, encryption also replaces bits as well according to preset substitution tables. This isn't covered in this article, as doing so would make it extremely long and a bit dull.

Data Encryption Standard (DES)

DES is one of the oldest computer based encryption methods. Designed by IBM in 1977, DES is considered breakable due to its fairly small key size of 56 bits. Although the algorithm was broken in 1998, it took a dedicated machine costing 250 thousand dollars and 3 days to crack it.

"On Tuesday, January 19, 1999, Distributed.Net, a worldwide coalition of computer enthusiasts, worked with EFF's DES Cracker and a worldwide network of nearly 100,000 PCs on the Internet, to win RSA Data Security's DES Challenge III in a record-breaking 22 hours and 15 minutes. The worldwide computing team deciphered a secret message encrypted with the United States government's Data Encryption Standard (DES) algorithm using commonly available technology. From the floor of the RSA Data Security Conference & Expo, a major data security and cryptography conference being held in San Jose, Calif., EFF's DES Cracker and the Distributed.Net computers were testing 245 billion keys per second when the key was found."

To put things into perspective, DES is breakable but it took a series of dedicated custom built DES cracking CPUs some effort to do so. Maybe less effort would be needed now; however, DES is a fairly tough nut to crack and still has its uses depending on your security needs and the sensitivity of the data.

A simplified overview of the DES Encryption Algorithm.

It's very difficult to discuss how encryption works without getting drawn into mathematical terms. Hopefully this won't happen and although this overview is not a complete picture, I've tried to keep the description fairly complete; yet not to the level that it becomes obscure and difficult to understand.

Regardless of how complex the algorithm looks, keep in mind that encryption is, at its lowest denominator, just bit shuffling. Here are the steps to DES encryption.

1. Take the plain text input and break it into blocks of 64 bits. For this reason, DES is a block based encryption method. This blocking is fairly important, as you will see later.

2. Derive - from the 56 bit encryption key - 16 sub keys of length 48 bits. This is again based on bit shuffling. The process is fairly straightforward. For generating each sub key, the previous sub key is halved and the bits of each half are moved one bit to the left. The first bits are wrapped around to the end. The two new halves are rejoined to make a new key. The 56 bit key that you provide to the encryption method is only used to generate the first sub key, and isn't directly used to encrypt the data.

3. Once the plain text has been broken up into a series of 64 bit blocks, it is shuffled (a process also called permutation) based on a known 'shuffle' table that specifies how the bit are shuffled. That is, bit 1 is placed in bit 40, bit 2 is placed in bit 23 and so on. This doesn't actually help making the encryption any more secure. In fact, it makes the process more difficult to achieve using a software based algorithm.

4. Once this shuffle has been done, the bits then are passed through 16 steps, or rounds, using one of the generated 16 sub keys.

5. The shuffled 64 bits created in step 3 are passed to a round, where it is split into two blocks of 32 bits each and processed against the corresponding key for that round. The process conducted in the round is covered later.

6. Step 4 is repeated 16 times, once for each sub key. The output of each round is fed into the following round.

7. Once the 16th round is complete, the resulting two 32 bit halves are switched and then rejoined back into a 64 bit block.

8. Finally, the 64 bit block is then reshuffled (permutated) using the inverse shuffle that was applied in step 3. Again, this doesn't make any great difference to the effectiveness of the encryption method.

All the blocks of the plain text go through this process. Once all the blocks have been processed they are combined; and that's the encrypted cipher text.

Figure 1: DES Symmetric Encryption

DES1.jpg

The above diagram shows the process. As you can see, it's pretty thorough. However, the diagram only shows the big picture. Most of the complexity occurs within each of the rounds.

An overview of a DES round.

There are 16 rounds to the DES encryption algorithm and the 64 bit outcome from one round becomes the input of the next round. Each round also has an associated 48 bit key that was derived from the master 56 bit key. Within each round the following process occurs.

?h4> Figure 2: DES Round Process

DES2.jpg

The 64 bit block is halved. The right hand half is copied down and makes up the left hand side of the output block. The right hand half also goes through a mangler function before being exclusively OR'd with the left hand half to make up the right hand half of the output block.

The mangler function is a substitution algorithm, which is another full process in itself. The substitution involves rather a large number of look up substitution tables that are not particularly interesting.

Basically, the right hand 32 bits are expanded to 48 bits before being broken down into 8 chunks of 6 bits. The rounds key, which is 48 bits, is also broken down into 8 chucks of 6 bits. The chunks of the data is exclusively OR'd with the chucks of the key.

The resulting 48 bits are then passed through the substitution method - also known as an s-box - which produces a 32 bit block of data. It's this data block that is exclusively OR'd with the left hand half of the block passed into the round, as shown in the graphic above.

Hopefully the above description of DES encryption, which is by no means a simple algorithm, was reasonably comprehensible and fairly complete.

Review of the DES encryption algorithm

Prior to modern CPUs, DES encryption wasn't a particularly fast process. Coupled with some unnecessary data shuffles, the only way DES was achievable was using custom built CPUs.

That has changed thanks to modern CPUs. Since DES uses an unusual and small key size, it's fast as most of the bit shuffling is performed using exclusive Ors, which are extremely fast.

What I find amazing about the process is that the DES algorithm is completely reversible. With all the shuffles and substitutions performed throughout the algorithm, the whole encryption process can be reversed.

Another interesting fact about the algorithm is: If any of the 16 rounds where performed in a different order - say round 3 was performed before round 1 - the effectiveness of the algorithm would have reduced by a number of factors, making the algorithm much easier to crack.

Block based encryption

DES, as well as many other encryption algorithms, works by breaking the data into blocks. With DES, this block size can only be 64 bits. In some other encryptions, you can change the block size. It is very unlikely that the data being encrypted will be a multiple of 64 bits, which results in the last block not being large enough for the process. Usually, the last block is padded so that it fills the required size.

Breaking the data into blocks creates a problem. If two 64 bit blocks happen to contain the same data, then the cipher text of each block will also be the same and this leaks information to a potential attacker.

An attacker can also easily copy a cipher block and use it anywhere in the cipher to replace another cipher block. When the cipher is decoded, no error will occur and an attacker has essentially altered the original data.

To solve this problem, there are a couple of approaches that can be used. Each of the approaches has certain advantages and disadvantages. Which approach you choose depends on various factors. These approaches are called modes of operation.

This approach should be avoided. It doesn't change the behaviour of the encryption. Identical blocks produce identical cipher text resulting in the above problem. It does have one advantage, though. Only the key needs to be known in order to decrypt the message. In other modes of operation, an initialization vector (iv) is required, which means two pieces of information - the key and iv - need to be known to encrypt and decrypt.

Cipher Block Chaining (CBC)

This is the most common mode of operation. In this approach, ?n initialization vector (iv) is used along with the key to encrypt the initial block. The produced cipher block is then used as an iv for encrypting subsequent blocks. The previous cipher block effects the encryption of the current block, which effects the encryption of the next block.

The advantage of this approach is that it removes the problem of duplicate cipher blocks. Another advantage is the iv. By changing the iv, the same message can be encrypted to a complete different cipher. So if you're in the habit of sending the same data over and over, it won't be apparent to a potential attacker.

Some disadvantages: You cannot decrypt the cipher unless you have all the cipher blocks. Also, if there are any damaged bits in one of the block, it results in garbled output in the subsequent block.

Output Feedback Mode (OFM)

In this mode of operation the encryption process is altered slightly. Instead of the message being directly encrypted, the initialization vector (iv) is encrypted. If the original message is 256 bits long (4 blocks of 64 bits) then the iv is encrypted 4 times to produce a similar size piece of information, called the one-time pad. The original message is then exclusively OR'd with this one-time pad to produce the cipher text. The encryption process remains the same but the iv is encrypted rather than the data.

Similar to CBC approach, the previous iv encryption block influences the current iv blocks encryption. However, only a certain number of bits are used. In CBC, the whole block is used to alter the encryption of the next block. In ORM, only a certain number of bits are used.

Advantages are: The one-time pad can be created at any time, meaning that only a portion of the cipher can be decrypted at a time. In other words, you do not need the whole cipher to be able to decrypt.

The disadvantage is: If an attacker has a copy of the original data and a copy of the cipher, then they can work out the one-time pad, meaning they can replace the original data with whatever replacement data they want.

Cipher Feedback Mode (CFM)

This mode is similar to OFM and CBC. As with OFM, the initialisation vector is encrypted and the plain text message is exclusively OR'd with the result to produce the cipher. However, as with CBC, it's the resulting cipher that is used to alter the next iv blocks encryption.

In other words, the iv is encrypted and exclusively OR'd with n-bits of the plain text, which produces a cipher. Part of this cipher is then used to alter the next iv encryption process. That result is then exclusively OR'd with the next n-bits of the plain text, and so on.

Conclusion

There are two important considerations you need to consider with symmetric encryption. The first one, and the most important, is the key. The second is the mode of operation and how cipher blocks are used to alter subsequent cipher blocks.

With the key, it's a choice between key size, performance, and the nature of the data. A larger key size means better security but at a cost of reduced performance.

DES with the smallest key is the fastest encryption method but the 56 bit key size means it isn't necessarily the most secure. Consider the nature of the data. If the data you're protecting only has a 'shelf-life' of a couple of hours and contains reasonably insensitive data, then DES is still a valid choice. If the data has a longer 'shelf life', is fairly sensitive and doesn't belong to you (for example, your customer's credit card details) then it's best to sacrifice performance in favour for a larger key.

With the blocks, it's a choice between functionality and performance. Using ECB is the fastest mode of operation but is a bad idea if your data uses more than 64 bits of information (more than one block). If you're sending a one off value less than 64 bits, then use ECB.

CBC is the most common process. For the most part is generally suitable, ?ut it's slightly slower than the CFM method, especially in larger data sets. If your data set is of a reasonable size then either CBC or OFM mode is the better choice. If you need to decrypt the cipher before receiving all the cipher text, then OFM should be used; otherwise, use CFM.

References

  • Cracking DES
  • Network Security – Private communication in a public world. Second edition. Charlie Kaufman, Radia Perlman, Mike Speciner
  • <<  Previous Article Continue reading and see our next or previous articles Next Article >>

    About Derek Smyth

    Sorry, no bio is available

    This author has published 6 articles on DotNetSlackers. View other articles or the complete profile here.

    Other articles in this category


    The Diffie-Hellman Key Agreement Standard
    The Diffie-Hellman Key Agreement Standard describes an algorithm which allows two individual parties...
    Microsoft’s CardSpace: Part 3 – Using a Card
    This article is the final part in a series of articles designed to get you up and running with Micro...
    Microsoft's CardSpace: Part 2 - Creating and using your first identity card
    This article is part two in a series of articles designed to get you up and running with Microsoft's...
    Protect Code with Skater .NET Obfuscator
    Application vulnerabilities, Intellectual Property theft and revenue loss are among the most serious...
    Book Review: Understanding Windows CardSpace
    Review of the book “Understanding Windows CardSpace”.

    You might also be interested in the following related blog posts


    Lookbehind in Regex searches read more
    Create NHibernate classes using T4 read more
    Finding malware in your Web Site using IIS SEO Toolkit read more
    Stopping the panic: how to improve HtmlHelper.RenderPartial performances. Don’t run in debug mode read more
    Implementing a WCF service firewall part II of N read more
    Soft-deletes are bad, m'kay? read more
    Multi-Value Key for a Dictionary read more
    Tutorial: Create a Silverlight 2 User Control from a Popup Control read more
    There are still great GSoC opportunities left! read more
    Visual Studio 2008 Plug Ins read more
    Top
     
     
     

    Please login to rate or to leave a comment.