A CBC Stream Cipher in C# (With wrappers for two open source AES implementations in C# and C)

• Download source - 99 Kb

Introduction: .NET Cryptography

.NET has very good support for cryptography as part of the System.Security namespace [NETC]. To understand how .NET cryptography implementation works one has to know that most of interfaces and implementation are wrappers to Microsoft Crypto API [CAPI]. The Crypto API design is quite nice but it lacks an important feature: it is not transparent [CGNL]. This means that you have to place a lot of trust into something whose internals you do not know. Another problem with Cryto API is the way its default providers deal with keys. The keys are stored encrypted in a database in the local computer. Again you have no choice but to trust it. For these reasons open source cryptography libraries will always find a way in .NET. The biggest such library comes as part of Mono [MONO] and it is an open source rewrite of .NET System.Security.Cryptography namespace. Despite its availability, non Mono .NET users would have problems to use the library in .NET applications. It is integrated in the Mono corelib.dll and one has to import a lot of unnecessary code in order to use a simple algorithm, not to mention namespace conflicts. So other simpler open source implementations would sell well into .NET world.

When implementing a cryptography provider for .NET the best way to organize it to implement the interfaces of System.Security.Cryptography, so that your provider will work uniformly with any existing code that uses .NET interfaces and users do not have to learn a new API. However this perfect software engineering solution has some security drawbacks. Given that .NET interfaces are well known, it is easier for any third party to intercept calls make to the generic interfaces. Because of the enriched metadata nature of .NET this is even easier to do than with normal binaries. The well known interfaces makes it possible to write generic spy software that works with many products. So despite the cryptography provider quality and transparency you can never be sure that there are no third party programs that can collect the keys in a .NET framework deployment, or in the underlying Crypto API. One partial solution, which is not optimized from the software engineering point of view, is to use custom interfaces. The situation is similar to using Outlook Express for viewing email. Because many people use it, a virus written for Outlook Express will very likely hit a lot of users. If you use a custom email client, no one will bother to write a virus for a program that is used by a small minority of users (unless someone really hates you, of course). In this spirit the CBC stream cipher here uses its own simple interface which does not rely on any of .NET crypto API interfaces and classes. It actually uses only System and System.IO for streams.

The CBC Stream Cipher Library

Everything started when I found an AES [FIPS197] implementation in C# in the MSDN magazine [CSAES]. AES is symmetric block cipher algorithm, which means that the same key is use for encryption and decryption. The C# code of [CSAES] is easy to understand but the implementation is very slow for some reason, even if you replace polynomials multiplication with fixed tables as I did. A faster implementation of AES in C, which is freely available, can be found in [CAES].

To use the AES block cipher implementation for real encryption you have to create a stream cipher. The easiest way is to create an ECB (Electronic Codebook) stream cipher which basically encrypts each block of a stream using the block cipher. The ECB mode is also supported in my implementation because it could be useful for testing purposes. However it is not secure because the correlation patterns found in the plaintext will still be visible in the ciphertext. The CBC (Cipher Block Chaining) mode is safe from this weakness and it is relatively easy to implement. It basically XOR-s each plaintext block with the previous ciphertext block before encrypting it. This way the plaintext patterns are no more visible in the output. The CBC mode makes use of an initialization vector (IV) to XOR the first block. The IV does not need to be secret as it shows nothing about the data (plain or cipher) or about the key. The IV must be selected to be different (it has not to be necessarily random) for each stream (file) we encrypt with a given key. In the CBC implementation given here the IV size must be the same as the size of cipher block, which is always 16 bytes for AES. The CBC mode is the default mode for my stream cipher.

Any block cipher implementation can used with the library as long as there is a wrapper class that implements IBlockCipher interface shown below:

interface IBlockCipher {
    void InitCipher(byte[] key); // key.Length is keysize in bytes

    void Cipher(byte[] inb, byte[] outb);
    void InvCipher(byte[] inb, byte[] outb);
    int[] KeySizesInBytes();
    // iv length will/must be the same as BlockSizeInBytes

    int BlockSizeInBytes();
}

I wrote two wrappers that implement this interface: one for the C# AES implementation [CSAES] and another for the fast C AES DLL implementation [CAES]. This way these two algorithms can be use with my CBC stream cipher. See the ‘aes.CAes.cs’ in the code for an example how a wrapper looks like.

Using the code

The C# stream cipher library can be used as follows:

IBlockCipher ibc = new CAes(); // new Aes();

byte[] key = ... ;
byte[] iv = ... ;
StreamCtx ctx = StreamCipher.MakeStreamCtx(ibc, key, iv);

The iv array size can be found by calling ibc.BlockSizeInBytes() which returns 16 for AES. The key array size can be found by calling ibc.KeySizesInBytes() which returns {16, 24, 32} for AES, corresponding to 128, 192 and 256 bits. One of these values must be selected. An improvement of IBlockCipher in the future would be to return a key size step as .NET does.

Note that the StreamCtx objects returned by StreamCipher.MakeStreamCtx are read-only and you must always use StreamCipher.MakeStreamCtx to obtain a valid context. Once you have a stream context StreamCtx ctx you can use it with the other static methods of StreamCipher class to encrypt or decrypt streams:

Stream instr = ... ; // open plaintext stream

Stream outstr = ... ; // create a stream for ciphertext output

StreamCipher.Encrypt(ctx, instr, outstr);

It is recommend to buffer streams before passing them to the StreamCipher methods. To encrypt byte arrays you would use:

byte[] indata = ... ;
byte[] outdata = StreamCipher.Encode(ctx, indata, StreamCipher.ENCRYPT);

Decryption is done similarly with respective methods. See ‘aes-example.cs’ for a complete example.

Key Generation

One problem we skipped above it how to get a key. Any byte array with size equal to one of the values returned in IBlockCipher.KeySizesInBytes() array will do for AES. Other algorithms may have sets of weak key values, so a future improvement to IBlockCipher would be to add a method byte[] GenerateKey(), which would be implemented by the block cipher wrapper.

On the other hand, no sane human can remember a 16 or 32 byte key such as 8ea2b7ca516745bfeafc49904b496089 without writing it somewhere. However, most people will find physically storing a secret key somewhere, even when it is encrypted, not a very feasible solution. They would prefer better a form of key which is easy to remember, usually in the form of a string password (or passphrase).

Password based cryptography [PBCS] is weaker that using keys directly, given that the search space of a password is smaller than for a key. For example with a 256 bit key in AES there are 2^256 (read as: 2 in the power of 256) possibilities to search in the worst case. A keyboard contains approximately 2^6 unique keys (letters, capital letters, numbers, special characters) that can be use in a password. This means that for a truly random password of 20 characters long (which we will find too complicated to remember), the brute force search space is only (2^6)^20 = 2^120 in the worst case. This is even lower that the smallest key size for AES which is 2^128. So if you use a password encryption scheme with passwords of 20 characters it makes no sense to use a key bigger than 128 bit for AES. In reality the length of the password is not known which means that for passwords up to 20 characters the search space size can be calculated as follows: sum(for i = 0 to 20) of (2^6)^i, which is again approximately the same as its biggest term value, that is 2^120.

Another problem with passwords is that people tend to reuse them. That is we prefer to (re)use the same password to encrypt different data units (files). This means that we are using the same key to encrypt a large amount of plaintext, resulting in a large amount of ciphertext which in theory can be used to explore patterns and find the cipher key (not the password) and obtain the plaintext. So, it is better to use different keys to encrypt different data units, which seem to contradicts the idea of having a single reusable password.

There are two ways how the situation can be improved without lengthening or changing the password as described in [PBCS]. The first one is to add a few different bytes in the end of the password every time it is used to generated a key, and use different bytes for different data units to be encrypted. These bytes are known as ‘salt’. The salt bytes must be random, or at least different for each stream of data we encrypt. This way we would have a new different key every time, to use for encryption, based on the same root password. A salt between 8 and 16 bytes is usually enough to generate a big possible key space. To decrypt the data we must know the original salt used to encrypt it, apart of the password. The good news is that salt need not to be secret: if you were to keep salt secret then (a) do not use a salt at all, but use a different password/key each time; (b) you would have to remember it, and then you are in no better position that remembering the encryption key itself. Thus, while the salt does not enlarge the password search space, it grows the effective key space that you use for your ciphertext, making it impossible to find the keys by someone which has access to all your ciphertext and all your corresponding salts.

The second technique effectively grows the search space for passwords without growing up the password size. It takes into consideration not only the size of the search space but also the time it takes to make a try. When we said that the search space for random 20-character long passwords is around 2^120, which is smaller than 2^128, the space of the smallest AES key size, we assumed that testing for a password takes the same time as testing a key. We can make the situation better by growing the time it makes to generate a key from a password. Of course this cannot be done by adding delays in code, but by growing the amount of calculations needed. In [PBCS] this is controlled by what is called an iteration count. An iteration count of 2^10 will make the effective time grow up around 2^120 * 2^10 = 2^130 time units compared with an iteration count of 1. Bigger values are of course better but make the key generation two slow in practice with the current computation power. So if you know the password you compute the key in around 2^10 time units. If you do not know the password, the worst case to try all passwords up to 20 characters would require around 2^130 time units.

These two improvements make using passwords (even when you do not change them) comparable in security with using different keys. The class KeyGen in my library implements the first method described in [PBCS] (which is easier to implement and also relatively secure). A key can be generated from a string password as follows:

int keySize = 32;
byte[] salt = ...;
byte[] key = KeyGen.DeriveKey(password, keySize, salt); //iteration count 1024

DeriveKey uses a free C# implementation of SHA256 to hash the data. It can generate keys up to 32 bytes (256 bits) long.

The stream cipher library I implemented does not offer a way to create a salt or an IV, given that different applications may use different ways to generate and distribute them. A simple way to get an IV and salt byte array of a given length is to use a pseudo-random byte generator.

Before I close up, I will explain what time means in the calculations above. A number such as 2^120 means that if a computer makes 100 guesses per second, it will take approximately 421495432453359929256661295 years to finish (in the worst case). However if you ever had 421495432453359929256661295 computers, it would take you only one second. And if you use a hidden camera or a keylogger to steal the password from someone as s/he types it in (etc, etc), you do not need such many computers at all.

History

• 01-Jul-2004
  • Several spelling errors in the article corrected :).
  • Changed StreamCipher.cs to make padding compatible with (CryptoAPI) .NET’s SymmetricAlgorithm implementation. Now data encrypted with .NET Rijndael can be decrypted with my library (using the AES wrappers) and vice-versa.
    Note: The KeyGen.DeriveKey is also compatible with .NET PasswordDeriveBytes. This call:

    string password = ...;
    int keyLength = 16; // up to 32
    
    byte[] salt = ...;
    int iterationCount = ...;
    
    byte[] key = KeyGen.DeriveKey(password, 
      keyLength, salt, iterationCount);
    

    produces the same key from a password as the following System.Security.Cryptography code:

    PasswordDeriveBytes pdb = new PasswordDeriveBytes(
      password, salt, "SHA256", iterationCount);
    byte[] key = pdb.GetBytes(keyLength);
    

• 02-Jul-2004
  • Modified Decrypt to fail silently if errors.
  • Removed some AES specific constants that I had forgotten from the code.

Acknowledgements

Ulrike Meyer explained to me why the IV-s need not to be secret. My understanding of salt and iteration count also followed a nice discussion with her of [PBCS]. James McCaffrey' comments on the first ECB version of my stream cipher encouraged me to finish the standart-compatible CBC version.

References

• [CAPI] V. Smyslov, RFC 2628 - Simple Cryptographic Program Interface (Crypto API), 1999, http://www.faqs.org/rfcs/rfc2628.html
• [FIPS197] AES: Federal Information Processing Standards Pub 197, http://csrc.nist.gov/publications/fips/fips197/fips-197.pdf
• [CSAES] James McCaffrey, Keep Your Data Secure with the New Advanced Encryption Standard, MSDN Magazine, 2003. http://msdn.microsoft.com/msdnmag/issues/03/11/AES/default.aspx
• [CAES] Brian Gladman, C AES Implemention, http://fp.gladman.plus.com/AES/index.htm
• [PBCS] B. Kaliski, RFC 2898 - PKCS #5: Password-Based Cryptography Specification Version 2.0, 2000, http://www.faqs.org/rfcs/rfc2898.html
• [CGNL] Bruce Schneier, Crypto-Gram Newsletter, September 15, 1999, http://www.schneier.com/crypto-gram-9909.html
• [MONO] Mono Crypto, http://www.go-mono.com/crypto.html
• [NETC] MSDN System.Security.Cryptography Namespace, 2004 http://msdn.microsoft.com/library/default.asp?url=/library/en-us/cpref/html/frlrfsystemsecuritycryptography.asp

You must Sign In to use this message board.

FAQ  Noise Tolerance Very HighHighMediumLowVery Low  Search Messages    Layout Expand All MessagesThread ViewNo Javascript (slow)No Javascript Preview    Per page 102550

Msgs 1 to 8 of 8 (Total in Forum: 8) (Refresh) FirstPrevNext

Subject   Author  Date  Free AES Encryption tool and Updated article Vasian Cepa 9:21 11 Sep '06   An updated version of this article can be found at: http://madebits.com/articles/aes/index.php A free AES encryption tool, Cr!ptAES, with an easy to use graphical interface that is based on this code can be found at: http://madebits.com/criptaes/index.php Sign In·View Thread·PermaLink Encryption & compression in general Herre Kuijpers 5:55 15 Aug '06   I have a general question, not specifically related to your software, but i'd like your opinion on this. I'm working on a small tool that is to store sensitive user data in an XML file. because the XML file can become large I want to compress it. But because it contains sensitive data I also want to encrypt it with a password. What would be the best way to do it? first encrypt then compress? or first compress and then encrypt? Because XML can be compressed at a very high compression ratio I would think that first compressing and then encrypting would be preferable, resulting in a smaller file, however will it be less secure then? also what would be the most effective/efficient encryption algorithm to use? And how do you suggest I could best link the password to the file? I'd appreciate any comments. Tnx Herre Sign In·View Thread·PermaLink Re: Encryption & compression in general Jonathan C Dickinson 1:17 2 Jun '08   Hi, Both encryption and compression have the same fundamental goals. Take data and make it more random (called a high entropy). Compression can only work on low-entropy data, such as your XML. Making the data more random is a side-effect of trying to reduce common occurences and patterns. Encryption can work on any kind of data, such as your XML or compressed data. It works by trying to obscure the data so that it can only be retrieved if a secret is known. Most algorithms (in fact, the ones that are taken seriously) have near identical size to the original (most have identical). Given that both encryption and compression emit high-entropy data you would do well to compress the data first, because the compression won't work on high-entropy data (in fact, in some instances, it can make the data bigger). If you choose an encryption algorithm that increases the size of the data significantly you *may* find that compression decreases it's size, so apply it and see if it does. So in the end you will: Compress -> Encrypt (for near-identical output size encryption) Compress -> Encrypt -> Optionally Compress (for expanding excryption) But using expanding encryption algorithms is not recommended for your purposes. And I wouldn't think Steganography would work if your XML is large. HTH Sign In·View Thread·PermaLink Good Stuff Abbasi Qasim Waqar 21:28 27 Apr '06   Cute Bird is Here Sign In·View Thread·PermaLink not working v.jayakrishnan 5:07 16 Feb '06   missing the project file.. doesn't working the project.. Sign In·View Thread·PermaLink Re: not working Vasian Cepa 6:28 16 Feb '06   Try to grow up! Do not cry and yield for help at the first sight when you do not find a project file. There has never been a project file for this code. Compile it from the command-line (csc remember?). And think a bit more before you post a message despite it is so easy to post one. After more than 24,000 views of this article, the probability that you find something real to complain about it, that no one else has thought of, is very low. Sign In·View Thread·PermaLink Good stuff Hugo Hallman 16:30 5 Jul '04   Well, this was a good read. Here's my stupid question of the day: -Is the IV allways public? Per definition? (Can't find it in msdn and want to be shure Out of curiosity, how's the performance of this library? And is it possible to make it as fast as a decent C version? Then I mean a C version used from an unmanaged environment without marshalling. Sign In·View Thread·PermaLink Re: Good stuff Vasian Cepa 4:45 7 Jul '04   Q: IV public? A: Yes. MSDN .NET doc is not a cryto tutorial thought Q: Performance? A: C# version of AES is slow, the C version quite fast. I tried to optimize C# version (not shown here), removed multimplications and byte XOR-s with word XOR-s in unsafe code wrappers. Still it was slow. So .NET developers were not lazy not to implement it in C#. It is just too CPU intensive for C#. Sign In·View Thread·PermaLink 3.50/5 (2 votes)

Last Visit: Friday, October 10, 2008 10:24 AM     Last Update:Friday, October 10, 2008 10:24 AM