Regex... Love it or Leave Programming

I love regular expressions, but I may be one of the few developers who doesn't have a hate/hate relationship with them.  Some guy once said,

Some people, when confronted with a problem, think “I know, I’ll use regular expressions.” Now they have two problems.

Personally, I think that guy is...  Well, just look at his homepage and you'll figure it out. 

My answer to people who hold this opinion (whether they are joking or super-cereal) is that regex is the language of parsing text.  There are other ways to parse text, but they suck in comparison.  Stop being lazy and learn it. 

Still not in agreement?  Let me put it another way,

Some people, when confronted with relational data, think "I know, I'll use SQL."  Now they have two problems.

If you have the requirement to deal with relational data in your application, you'd better know SQL.  SQL is the language of parsing relational data.  Yes, there are other ways to parse and handle relational data.  There is nothing to say that you can't scan through data tables in a sequential manner using procedural code, but it would suck in comparison. 

That's not to say Regex or SQL is easy.  But good things rarely are easy, and powerful things never are.  With the right tools you can make them easier. 

More...

(You can find the previous parts here:  part 1 (background), part 2 (hashes), and part 3 (Symmetric encryption))

Background

This last part in this primer series covers asymmetric encryption, also known as public/private key encryption.  A "public" key, freely distributed, is paired with a "private" key, which is kept secret.  The public key is used to encrypt messages that, without massive computational power, only the paired private key can decrypt.  This is only secure one way--from public key to private key--so two-way encrypted communications usually involve both sender and receiver exchanging public keys in order to encrypt transmissions both ways.

Shared secret (symmetric) encryption is vulnerable to eavesdroppers, decompilers and those with sufficient computational power, each of whom have a relatively simple path to discovering what that secret is.  If that shared secret is sniffed as it is transmitted over the network, or recovered from source code, or cracked using a rainbow table, your data is now open to everyone.  Asymmetric cryptography allows for the easy storage and transmission of the public key without fear of it falling into the wrong hands, as determining the private key is practically impossible.  I'm no expert, but I believe if you started to brute-force crack a 4096 bit key today, you'd finish roughly five seconds after the universe collapses back into a singularity.

Another common use for asymmetric algorithms is to generate signatures.  This is useful for ensuring that data transmitted in cleartext isn't tampered with.  For a given message, you can use your private key to generate a signature.  This is transmitted in cleartext along with the message.  On the receiving end, you can use the public key to verify that the signature was generated by the private key and that it matches the set of bytes.  This ensures that the message is from a trusted source (the owner of the private key) and that the message hasn't been tampered with in a "man in the middle" style attack. 

Implementations

There are two different types of asymmetric algorithms available to .NET coders.  They are RSA and DSA (Digital Signature Algorithm).  Without going into details, the algorithms are essentially the same.  The difference is that DSA can only be used to generate signatures and is legal to export, whereas RSA can be used to perform encryption as well and cannot be legally exported to some countries.  Of course, that is a huge over-generalization; if you're interested in learning more you can always Google it.  For my examples, I'll be using RSA as it can do both and is more commonly used.

Like other cryptographic algorithms in the .NET framework, the RSA implementation is implemented as a provider, the RSACryptoServiceProvider, which extends an abstract base class for all algorithms of this type:  System.Security.Cryptography.RSA.  By using the static Create() method on this base class, you can get the default or a specifically named implementation of the provider.  In my examples I'll be new-ing up instances, as the constructor for the RSACryptoServiceProvider takes a CspParameters object that can be used to configure the provider.  For more information on the different types of RSA CSPs available for Microsoft developers and how to specify which to use, go here.

A word or two thousand about Key Containers

The security of asymmetric algorithms depends on the private key remaining private.  Imagine a software product that uses RSA signatures for a license key.  You compile the public key into the software and use it to verify licenses.  The company generates these a license by taking the "Licensed to" information from a user and generating a signature.  If the private key is stolen or lost, every boxed copy of the software is now trash.  The source code has to be recompiled with a new public key.  And the next software update will require users to re-register their copies of the software.  This is commonly known as "a nightmare."

Unlike shared secret keys (aka passwords), public/private key pairs are complex structures that cannot be memorized.  Because of this, Microsoft stores these keys in what is called a "Key Container".  This is implemented as a file on the hard drive and is secured by ACLs.  Key Containers can be scoped to the machine (look in Documents and Settings\All Users\Application Data\Microsoft\Crypto\RSA\ MachineKeys) or to the user (Documents and Settings\[USER ACCOUNT]\Application Data\Microsoft\Crypto\RSA).  Machine level keys are accessible by the system and those with configured access rights (by default the principal that created them).  User-scoped containers are, oddly enough, accessible by the system, the user that created them, AND administrators.  Because of this, they can optionally be encrypted with a password.  Another important aspect about user-scoped key containers is that they are stored within the user's profile, which means they are lost when the user account is deleted.  You can have more than one key container of either type, each being identified by its name.

User-scoped Key Containers

User scoped key containers, by default, are only available to the system, admins, and the user that created them.  You can also configure the provider to allow users to apply a password to the container to make them more secure.  I'll be using the machine store for simplicity later, but to scope the container to the user is simple:

// create a configuration object for the provider

CspParameters parms = new CspParameters();

// set the flag to use a user protected key

parms.Flags = CspProviderFlags.UseUserProtectedKey;

// name the key container 

parms.KeyContainerName = "foo";

// Instantiate the provider

RSACryptoServiceProvider rsa 

    = new RSACryptoServiceProvider(parms);

The provider creates a new public/private key pair for you the first time you try to do something that requires it (encrypt, sign, export).  When a new key is created, a dialog is presented to the user that allows the user to set the security level of the key container to high and apply a password to it.  The user can set the security level to High to password protect the key pair.

From this point on, any operation that attempts to access this key will result in a dialog being shown requesting the user's password:

I'll refrain from the obvious statement of how this could easily be spoofed by a malicious application on the user's system.  If you are thinking about using this as an additional security layer, I'd suggest looking into using the KeyPassword property of the CspParameters object to set this password from within your application's UI.

Creating the RSA Provider

This method shows how to create the default implementation of the RSA crypto provider that uses the machine key store.  If containerName is new, a new key pair is created prior to using or accessing it.  Every example from here on will use this method to create the provider.

private RSACryptoServiceProvider CreateRSA(

    string containerName)

{

    CspParameters parms = new CspParameters();

    parms.KeyContainerName = containerName;

    RSACryptoServiceProvider rsa = 

        new RSACryptoServiceProvider(parms);

    return rsa;

}

Deleting a key from a Key Container

Deleting a key from a key container is a little tricky, as the actual deletion takes place in the set method of the PersistKeyInCsp property, which isn't intuitive.

private void DeleteKeyInContainer

    (string containerName)

{

    // get a provider configured to the container

    RSACryptoServiceProvider rcsp = 

        CreateRSA(containerName);

    // Deletes the key entry from the container

    rcsp.PersistKeyInCsp = false;

    // clears the key from the provider

    rcsp.Clear();

}

Importing and exporting keys

Key pairs can be imported and exported from a key container.  A key pair is actually a complex structure containing the different components the algorithm needs.  This can be exported as a blob (compatible with unmanaged implementations), as an XML string, and as a strut (RSAParameters):

private void ExportImportKeys(string containerName)

{

    // get a provider configured to the container

    RSACryptoServiceProvider rcsp = 

        CreateRSA(containerName);

    // export the key pair 3 different ways

    byte[] keyBlob = rcsp.ExportCspBlob(true);

    string keyXml = rcsp.ToXmlString(true);

    RSAParameters keyParms = 

        rcsp.ExportParameters(true);

    // and import them back in

    rcsp.ImportCspBlob(keyBlob);

    rcsp.FromXmlString(keyXml);

    rcsp.ImportParameters(keyParms);

}

In these export methods, you must pass in a boolean that indicates whether you wish to export the private key as well as the public key (true to export both).  Note that when you bring a private key out of the Key Container you are greatly reducing the security of your application.  If you intend to distribute the public key, you will have to call one of these methods passing in false.  You do not have to use a different import method when importing a public key. 

Encryption and decryption

Remember, you must encrypt with the public key, and decrypt with the private key.  This seems a little backwards, but it is how the algorithm works.  The following code creates an encryptor and decryptor pointing to different key containers (I use a randomly generated Guid for the name).  The public key is extracted from the decryptor and loaded into the encryptor, and a byte array is encrypted and decrypted.  The code after the CollectionAssert demonstrates that a public key cannot be used to decrypt.

// create an encryptor and decryptor

RSACryptoServiceProvider decryptor = 

    CreateRSA(Guid.NewGuid().ToString());

RSACryptoServiceProvider encryptor = 

    CreateRSA(Guid.NewGuid().ToString());

// Export the public key from the decryptor

string key = decryptor.ToXmlString(false);

// Load the public key into the encryptor

encryptor.FromXmlString(key);

byte[] expected = new byte[] { 1, 2, 3 };

// encrypt with the public key

byte[] encrypted = encryptor.Encrypt(

    expected, true);

// decrypt with the private key

byte[] decrypted = decryptor.Decrypt(

    encrypted, true);

CollectionAssert.AreEqual(expected,decrypted);

// the following will fail

encryptor.Decrypt(encrypted, true);

Creating and Verifying Signatures

A signature is a cryptographic hash created by a private key that can be verified by its public key.  The public key can be compiled into code and be used to verify signatures that are generated by, say, a trusted employee at your company.  The following code demonstrates generating a signature and verifying it.  The private key is used to generate the signature and the public key is used to verify it.  The last line demonstrates that the public key cannot be used to generate a new license for the tampered data.

RSACryptoServiceProvider signer = 

    CreateRSA(Guid.NewGuid().ToString());

RSACryptoServiceProvider verifier = 

    CreateRSA(Guid.NewGuid().ToString());

// Export the public key from the signer

string publicKey = signer.ToXmlString(false);

// Load the public key into the verifier

verifier.FromXmlString(publicKey);

byte[] rawData = new byte[] { 1, 2, 3 };

// encrypt with the public key

byte[] signature = signer.SignData(

    rawData, "SHA1");

bool untampered = verifier.VerifyData(

    rawData, "SHA1", signature);

// Tamper!

rawData[2] = 4;

bool tampered = verifier.VerifyData(

    rawData, "SHA1", signature);

Assert.IsTrue(untampered);

Assert.IsFalse(tampered);

// the following will fail

signature = verifier.SignData(

    rawData, "SHA1");

Summary

Asymmetric cryptography is used to encrypt and sign data without having to rely on an insecure shared secret.  Key pairs are stored in a Key Container (a file on the hard drive) that can be scoped to the machine or to a specific user.  User-scoped containers can be secured using a password.  The public key is used to encrypt data and verify signatures.  The private key is used to decrypt data and generate signatures. 

Whew!  That was a long one.  I've learned a bunch writing these four parts, including how much more I don't know about the process.  I would have liked to go into more details about some of the aspects of cryptography on the .NET platform, but the more I say the more I risk being wrong. 

Most likely, if you're reading this, you care about security.  Don't just stop here; if you need cryptography in your program, you need to keep learning.  If you use it and you don't thoroughly understand it, you're probably doing it wrong.  And this is one area where you have to do it right.

(Illness and work has been kicking my ass for the past couple weeks; I'm posting a quick how-to so my parents don't worry.  I'll be finishing up the crypto series next week, I swear!)

I've been doing lots of work in WPF over the last few weeks, getting familiar with xaml for a major project at work (xaml templating and XPS documents, cool stuff).  Getting to re-know standard windows forms controls in their new WPF flavors has been interesting.  Every once in awhile you come on an issue that takes a while to figure out.

One of those I just encountered was getting the WPF version of the TextBox to scroll a particular chunk of text into view.  Here's the scenario:

• Text is pasted into a multiline TextBox without wrapping that overflows the available visual space
• Both horizontal and vertical scrollbars appear
• In code, a word is selected.  That word happens to be outside the visible area of the TextBox.

In this situation, the question becomes how to scroll this selected text into view via code so the user can see the selected text.

The standard methods don't work.  The obvious methods for scrolling (I'll skip them for brevity's sake) only scroll the TextBox vertically, or take a value that cannot easily and reliably be determined from the available information. 

The solution is to use the BringIntoView method.  The problem is that this method is designed to communicate to an owning ScrollView in order to tell it to scroll.  If you call this on the TextBox and the TextBox is using an internal ScrollView, the method fails to work.

You must turn off your TextBox' scrolling and place the TextBox into a ScrollView.  Here's the xaml:

<Border

  DockPanel.Dock="Top"

  BorderBrush="Gray"

  BorderThickness="1">

  <ScrollViewer

   VerticalScrollBarVisibility="Auto"

   HorizontalScrollBarVisibility="Auto">

    <TextBox

     BorderThickness="0"

     Name="_inputString"

     AcceptsReturn="True"

     TextWrapping="NoWrap"

     GotMouseCapture="TextBox_GotFocus"

     Text="{Binding Path=InputString, 

        UpdateSourceTrigger=PropertyChanged}">

    </TextBox>

  </ScrollViewer>

</Border>

Notice the Border; the ScrollView doesn't display a border, so you have to create one and turn off the TextBox' so it doesn't look weird.  Here's the codebehind:

_inputString.Select(m.Index, m.Length);

Rect start = _inputString

  .GetRectFromCharacterIndex(m.Index, true);

Rect end = _inputString

  .GetRectFromCharacterIndex

    (m.Index + m.Length, true);

_inputString.BringIntoView(Rect.Union(start, end));

_inputString.Focus();

The m object in this case is actually a Regex Match object and _inputString is the TextBox; the code is from a databound wpf regex tool I'm working on.  I can select text using the start index of the text and the length of the selection.

The BringIntoView method takes a Rect struct.  The GetRectFromCharacterIndex method returns a Rect that covers an individual character of the text; we want to bring the whole selection into view so we need the union of the Rect from the first and last characters of the selection.

Its a little sloppy.  I haven't done much testing on this; guaranteed that if the first character Rect is on line 278 and the last is on line 279 something odd might happen, but it does work.

Update

Adding this to the scrolling code allows you to scroll to the first half of the text if the selection contains a newline:

if (_inputString.SelectedText.Contains(Environment.NewLine))

{

    string selected = _inputString.SelectedText;

    int length = selected.IndexOf(Environment.NewLine);

    end = _inputString.GetRectFromCharacterIndex

        (m.Index + length, true);

}

else

{

    end = _inputString.GetRectFromCharacterIndex

        (m.Index + m.Length, true);

}

Monster Cable, a company whose reputation of suck is well documented on the internets, recently tried to bully a small competitor with a Cease and Desist.

A small company that is run by a former trial attorney.  With balls of steel.  Who eats raw meat for breakfast.

I know where I'll be buying my cables from now on.

Part one covered the background, part two went into detail about cryptographic hashes.  Part three covers the most easily understood type of encryption, though you wouldn't know it by its name:  symmetric encryption.

Symmetric Cryptographic Algorithms

Sometimes referred to as "shared secret" cryptography, Symmetric cryptographic algorithms encrypt and decrypt data using a trivial key.  Its name comes from the fact that encryption and decryption both rely upon the same key. 

A common example of symmetric cryptography in action is the common zip file.  You have the option to add a password to the zip file when creating it.  You must, in turn, provide the same password when the file is decrypted.  In order for your secret stash to stay hidden from your mom's eyes, you have to keep the key secret.  For example, you shouldn't write it on a post-it note pasted to your monitor.

Types of Symmetric Algorithms

There are five different types of symmetric algorithms available in System.Security.Cryptography.  They are DES (Data Encryption Standard), TripleDES, RC2, and Rijndael/AES (Advanced Encryption Standard). 

DES and TripleDES

DES is an older standard, originating from government requirements back in the 70's.  Since it was designed for the computing power available at that time, it is considered very weak today.  It can be brute-force cracked in under a day's worth of computation at today's power.  DES has been superceded by both TripleDES, which runs data through the DES encryption algorithm three times (why not QuadDES?  I dunno.), and Rijndael/AES.

RC2

RC2 was a follow-up to DES developed for Lotus Notes with the goal of being more secure but legal for export overseas.  There are also more secure versions with longer keys, but they are all called RC2 in .NET; only the key length is changed (this isn't exactly true; research it if you want more info).  RC2 is most famous for being the encryption used by WEP (with a 40 bit key).  If you're running your wireless access point with WEP, somebody is right now connected to your network chatting up 13 year olds on MySpace.  You should go home immediately, rip out your router by the power cord, and slam it into the wall.  RC2 in its default form is NOT considered secure and should not be used when better alternatives are available.  WEP2, by the way, uses AES for encryption.

Rijndael/AES

Rijndael is considered the most secure of the crop of symmetric algorithms available to .NET programs.  I'm not sure what the differences between them are, but supposedly AES is the official, NSA approved version of Rijndael.  They are both different enough to be implemented separately.  If you have a choice among all symmetric algorithms, you should always use one or the other as they are the most secure and are projected to be secure for another 20 or so years. 

Initialization Vectors and You

Symmetric algorithms introduce a new requirement that must be understood:  The Initialization Vector, or IV.  Very simply, the symmetric algorithm must start somewhere, and that is the job of the IV.  Symmetric algorithms usually use "block chaining" to add an additional layer of randomness to the cypher.  This is done by logically XOR-ing the current block with the previously processed block.  This process is reversible, so it works well and is fast.  However, to fully encrypt the first block of text you need a previous block to XOR it with.  That is the purpose of the IV, to be the starting point of this process.  Because it does impact the rest of the cypher, the same IV must be used to decrypt as was used to encrypt.  Usually, in order to avoid having to memorize a random series of bytes along with your password, the IV is generated from the password itself.

CODE ALREADY!

The pseudocode for encrypting is:

1. Convert the string to encrypt into a byte array
2. Generate our IV from our password
3. Create our encryption provider (Rijndael in this example)
4. Get an encryptor using our password and initialization vector
5. Encrypt our string to encrypt
6. Return the encrypted data as an encoded string

The pseudocode for decrypting is:

1. Decode our encrypted data into a byte array
2. Create our provider with the same configuration
3. Generate an IV from the given password
4. Get a decryptor using our password and IV
5. Decrypt the encrypted bytes
6. Convert the byte array into a string

A Word About IV Generation

The current, cryptographically secure, deterministic and non obsolete way to generate our IV from our password is to use the class Rfc2898DeriveBytes.  This is a replacement for the PasswordDeriveBytes class that you'll see in most examples on the net.  This class takes a password and a salt and provides a method called GetBytes which provides an easy way to get your key and IV for use by your symmetric algorithm provider.  If you use the same password and same salt, you are guaranteed to get the same bytes, and these bytes are generated in a secure manner. 

Generally, you don't want to require users to remember a random salt along with their password, so its best to base it off of your password.  In this example, I use the following method, which will generate a salt that's different for each password, but is always the same for the same password:

private byte[] GenerateSalt(string password)

{

    return Encoding.Default.GetBytes(

        "A salt must always be the same"

        + "for Rfc2898DeriveBytes to give you"

        + "the same password bytes and IV for"

        + "each password, or in this case: "

        + password);

}

Encrypting

The encryption method demonstrates how to use the Rfc2898DeriveBytes class to generate a key and IV from your password and salt:

private string Encrypt(string password, 

                       string toEncrypt)

{

    Rijndael rinedal = null;

    byte[] toEncBytes = null;

    try

    {

        toEncBytes = Encoding.Default

                             .GetBytes(toEncrypt);

        Rfc2898DeriveBytes pdb = new 

            Rfc2898DeriveBytes(

            password,

            GenerateSalt(password));

        rinedal = Rijndael.Create();

        rinedal.Padding = PaddingMode.ISO10126;

        ICryptoTransform tx = rinedal

            .CreateEncryptor(

            pdb.GetBytes(32), // our key

            pdb.GetBytes(16)); // our IV

        byte[] encrypted = 

            tx.TransformFinalBlock(

            toEncBytes, 

                0, 

                toEncBytes.Length);

        return Convert.ToBase64String(encrypted);

    }

    finally

    {

        // this clears out any secret data

        if (rinedal != null)

            rinedal.Clear();

        // zeroes out our array

        if (toEncBytes != null)

            for (int i = 0; i < toEncBytes.Length; 

                i++)

                toEncBytes[i] = 0;

    }

}

We use the default system encoding to convert the text to a byte array.  Next, we use our GenerateSalt method, along with the given password, to instantiate our Rfc2898blahblah object.  We get the implementation of the Rijndael algorithm configured on the system next, and specify what type of padding mode to use. 

Symmetric algorithms work on fixed sizes of data, or blocks, so when data doesn't fill up a block the remaining space must be padded somehow.  Default padding modes may differ between systems, so being specific here is better than not.

Next, we get our encryptor from the provider, passing in bytes for our key and initialization vector.  Key and IV lengths must be certain lengths, depending on the flavor of algorithm you are using.  For instance, Rijndael allows for a maximum key length of 256 bits, or 32 bytes.  Consult the docs for your algorithm to find out what sizes are acceptable.

Once encrypted, we convert the encrypted byte array into a string that can be easily stored and retrieved.  And in our finally block we do a little house cleaning, sweeping up all our secret data (or as much as we can do easily). 

Decrypting

The decryption method is just the reverse of the previous:

private string Decrypt(string password, string toDecrypt)

{

    Rijndael rinedal = null;

    byte[] toDecBytes = Convert

                        .FromBase64String(toDecrypt);

    try

    {

        Rfc2898DeriveBytes pdb = new 

            Rfc2898DeriveBytes(

                password, 

                GenerateSalt(password));

        rinedal = Rijndael.Create();

        rinedal.Padding = PaddingMode.ISO10126;

        ICryptoTransform tx = rinedal

            .CreateDecryptor(

                pdb.GetBytes(32),

                pdb.GetBytes(16));

        byte[] decrypted = tx.TransformFinalBlock(

            toDecBytes, 0, toDecBytes.Length);

        return Encoding.Default.GetString(decrypted);

    }

    finally

    {

        if (rinedal != null)

            rinedal.Clear();

    }

}

Summary

Symmetric cryptographic algorithms use a key, commonly referred to as a password, to encrypt and decrypt data.  There are lots of different versions available, but Rijndael and AES are the current industry standards.  You'll need to generate an initialization vector (IV) using the Rfc2898DeriveBytes object.  The bytes you use as the key and IV must be the correct length for the algorithm you use. 

Part Four Preview

In part four we go over (or maybe just start to go over; its pretty complex) asymmetric cryptographic algorithms.  These use public/private key pairs to perform one-way encrypting and data signing, and is some pretty heavy and useful stuff.  Could somebody else write that one for me, please?  This stuff is getting complex!