Elliptic Curve Diffie Hellman Cryptography

• Download source files - 45.4 KB

Introduction

Elliptic Curve cryptography is the current standard for public key cryptography, and is being promoted by the National Security Agency as the best way to secure private communication between parties. Microsoft has both good news and bad news when it comes to using Elliptic Curve encryption algorithms. The good news is that it is natively supported in the Vista operating system through CNG (Cryptography API Next Generation). The bad news is that a managed library for using EC will not be available until the release of Visual Studio Orcas, which is currently slated for the end of 2007 or the beginning of 2008.

The code in the attached project attempts to fill this gap by providing a wrapper class that will give you access to the underlying Vista Crypto API, as well as offer simple methods for leveraging the Elliptic Curve algorithms. It is intended for educational purposes only, however, and requires much more testing and refactoring before it can be used in any serious way. In other words, please play with it, copy it, and manipulate it in any way you like, but don't use it in its current form to lift any heavy machinery.

Background

Vista's CNG gives tools for using Elliptic Curve mathematics for both encryption as well as digital signing. This project only deals with the former, using EC in combination with the Diffie Hellman protocol (ECDH). However, the underlying P/Invoke signatures should be a good starting point for anyone who wants to try unravelling the ECDSA functions of the Vista Cryptography API.

Asymmetric algorithms involve using a public key and a private key to hide data. In theory, after generating a public and a private key, a user sends the public key to a colleague, who then uses it to encrypt data, which is sent back to the original user. The original user then decrypts the data with his private key. The private key should not be derivable from the public key (or at least it should take a very long time to do so).

In a more common scenario, the public and private keys are used to encrypt and decrypt a third key, which is used for symmetric encryption and decryption. This is done because, unlike symmetric cryptography algorithms, public/private key algorithms are relatively slow, and are better for encrypting small amounts of data.

Diffie Hellman uses a shared secret to accomplish something similar. Users on both ends of communication send a public key, which can be seen by anyone, to his compatriot. The public key is then combined with the private key to create a shared secret which, due to the underlying mathematics, is the same on both sides. This shared secret is then used to hash a new key that can be used by either party for encrypting and decrypting messages.

At first blush, this seems a bit strange (at least it did to me). Alice generates keys A and B, and sends B to Bob. Bob generates keys C and D, sending D to Alice. Somehow, Alice is able to generate a third key based on A and D (a key unrelated to her own key), and generate the same number that Bob does using C and B (a key he has never seen before).

One of the best articles I found explaining how this is possible is written by Keith Palmgren, and can be found here. Without understanding the detailed mathematics, however, a simple example can be given using products. Imagine that on both sides of communication, we have agreed on a common seed number to use, like 2. The public key that Alice sends to Bob can be a product of our seed and the private key. If the private key is 10, then Alice will be sending Bob a public key of 20. If Bob's private key is 12, then he will send Alice 24 as his public key. By multiplying Bob's public key with her own private key, Alice gets a shared secret agreement of 240. On his side, Bob multiplies 12 and 20 to arrive at the same shared secret. These products can then be used to generate a symmetric key for encrypting and decrypting messages back and forth.

Because the numbers are so small, anyone who intercepts the public keys going back and forth can deduce the two private keys fairly easily by simply finding their factors. With very large primes, however, as well as a generation routine involving modulo operations rather than multiplication, this task becomes incrementally more difficult.

The goal of public key encryption algorithms is to make it very difficult to find any connection between the public keys that go back and forth and the private keys that we keep to ourselves. As mathematics progresses, various breakthroughs are made that reveal new ways to generate such primes. Elliptic Curve mathematics is the latest to be plumbed in this regard, and it is generally believed to contain a much more difficult set of problems, and consequently much more robust algorithms for generating public and private keys, than many of the algorithms we have been using over the past decade. Because it is more difficult to crack, using EC in combination with Diffie Hellman is believed to make public key encryption more secure.

It should be pointed out that Diffie Hellman is named after Whitfield Diffie and Martin Hellman, who first proposed the protocol in the 70's. Ralph Merkle is often associated with their work because of his additional efforts in elucidating how public key cryptography should be used.

Using the code

Using the ECDiffieHellmanMerkle wrapper which I wrote to access the CNG API is very straightforward. The following code simulates a common scenario. Two users, A and B, create their ECDiffieHellmanMerkle instances, also passing an enumeration value indicating the strength of the ECDH. Each sends his public key to the other, who then uses it to generate a secret key. The code below performs a final test to show that the secret keys are identical. The secret key can then be used to encrypt and decrypt messages between the two parties. Without access to either of the private keys, it would be prohibitively difficult for any third party to derive the secret key.

ECDiffieHellmanMerkle A = new ECDiffieHellmanMerkle(ECDHAlgorithm.ECDH_256);
ECDiffieHellmanMerkle B = new ECDiffieHellmanMerkle(ECDHAlgorithm.ECDH_256);
byte[] SecretA = A.RetrieveSecretKey(B.PublicKey);
byte[] SecretB = B.RetrieveSecretKey(A.PublicKey);
string strSecretA = Encoding.ASCII.GetString(SecretA);
string strSecretB = Encoding.ASCII.GetString(SecretB);
MessageBox.Show((strSecretA.Equals(strSecretB)).ToString());

By default, ECDH hashes the secret key using SHA1, which only produces a 160 bit key. If we wanted to use an AES compliant algorithm such as the Rijndael managed class provided in the System.Security.Cryptography namespace in .NET, we would need at least a 256 bit hash.

To this end, I added an enum to my helper class that allows the developer to determine the SHA hash that should be used, allowing larger keys to be generated. To use the ECDH functions in order to generate a useful key for Rijndael encryption, we would want to use the SHA256 hash. The full code looks like this:

byte[] SecretA=null;
byte[] SecretB=null;
try
{
    ECDiffieHellmanMerkle A = new ECDiffieHellmanMerkle(ECDHAlgorithm.ECDH_384);
    ECDiffieHellmanMerkle B = new ECDiffieHellmanMerkle(ECDHAlgorithm.ECDH_384);
    A.KeyDerivationFunction = ECDHKeyDerivationFunction.HASH;
    B.KeyDerivationFunction = ECDHKeyDerivationFunction.HASH;
    A.HashAlgorithm = DerivedKeyHashAlgorithm.SHA256_ALGORITHM;
    B.HashAlgorithm = DerivedKeyHashAlgorithm.SHA256_ALGORITHM;
    SecretA = A.RetrieveSecretKey(B.PublicKey);
    SecretB = B.RetrieveSecretKey(A.PublicKey);
}
catch(Exception ex)
{
    MessageBox.Show(ex.Message,"Win32 Error Message");
}

The shared secret key (SecretA and SecretB), derived independently by the two parties involved in secret communication, can now be used with the standard .NET 2.0 cryptography classes to encrypt and decrypt their messages.

//A encrypts the message with her secret key
string SecretMessage = "The owl of Minerva only flies at dusk.";
byte[] SecretMessageByteArray = Encoding.Unicode.GetBytes(SecretMessage);
string IVString = "initialV";
byte[] IVByteArray = Encoding.Unicode.GetBytes(IVString);
RijndaelManaged rijndael = new RijndaelManaged();
ICryptoTransform encryptor = rijndael.CreateEncryptor(SecretA, IVByteArray);
MemoryStream memoryStream = new MemoryStream();
CryptoStream cryptoStream =
        new CryptoStream(memoryStream, encryptor, CryptoStreamMode.Write);
cryptoStream.Write(SecretMessageByteArray, 0, SecretMessageByteArray.Length);
cryptoStream.FlushFinalBlock();
byte[] cipherText = memoryStream.ToArray();
memoryStream.Close();
cryptoStream.Close();

//B decrypts the message with his secret key
ICryptoTransform decryptor = rijndael.CreateDecryptor(SecretB, IVByteArray);
memoryStream = new MemoryStream(cipherText);
cryptoStream =
        new CryptoStream(memoryStream, decryptor, CryptoStreamMode.Read);
byte[] clearText = new byte[cipherText.Length];
int clearTextByteSize = cryptoStream.Read(clearText, 0, clearText.Length);
memoryStream.Close();
cryptoStream.Close();
this.textBox1.Text =
        Encoding.Unicode.GetString(clearText, 0, clearTextByteSize);

Some Nitty-Gritty

In order to access the CNG API, I was forced down the road of using P/Invoke to make my calls. I still have sores from the experience, but nevertheless found it a fascinating adventure that helped me to understand some of the complexity of the underlying API, as well as provided me more experience with using P/Invoke calls than I ever imagined was possible. For instance, just implementing the code to retrieve the secret key from the public and private keys required the following code, which I will attempt to explain. It actually only uses three P/Invoke calls, BCryptImportKeyPair, BCryptSecretAgreement, and BCryptDeriveKey. The devil, of course, is in the details.

The initial code for this function simply evaluates some enumeration values in the wrapper class and determines how to turn these into the appropriate string values required by the P/Invoke signatures. In cases such as KDF_USE_SECRET_AS_HMAC_KEY_FLAG, which is actually a uint value, I used a constant defined elsewhere in the wrapper.

public byte[] RetrieveSecretKey(byte[] externalPublicKey)
{
    string keyDerivationFunction;
    uint keyDerivationFlagValue;
    switch(KDF)
    {
        case ECDHKeyDerivationFunction.HMAC:
            keyDerivationFunction = "HMAC";
            keyDerivationFlagValue = KDF_USE_SECRET_AS_HMAC_KEY_FLAG;
            break;
        default:
            keyDerivationFunction = "HASH";
            keyDerivationFlagValue = 0;
            break;
    }

    byte[] _secretKey = new Byte[0];
    uint derivedSecretByteSize;
    string KDFHash;
    switch (HASH)
    {
        case DerivedKeyHashAlgorithm.SHA1_ALGORITHM:
            KDFHash = "SHA1";
            break;
        case DerivedKeyHashAlgorithm.SHA256_ALGORITHM:
            KDFHash = "SHA256";
            break;
        case DerivedKeyHashAlgorithm.SHA384_ALGORITHM:
            KDFHash = "SHA384";
            break;
        case DerivedKeyHashAlgorithm.SHA512_ALGORITHM:
            KDFHash = "SHA512";
            break;
        default:
            KDFHash = "SHA1";
            break;
    }
    uint status=0;

BCryptImportKeyPair simply allows us to take the public key provided by the person we wish to have secret communications with, and create a handle for it that we can use in the BCryptSecretAgreement method. I use the Marshal.AlocHGlobal method in order to allocate enough memory for the IntPtr value I want to use as my handle, and then pass it to the BCryptImportKeyPair P/Invoke method in order to fill the memory my handle points to with the actual public key.

try
{
    //discover public key size
    uint publicKeyByteSize = (uint)externalPublicKey.Length;
    //get pointer to public key
    IntPtr publicKeyHandle = Marshal.AllocHGlobal((int)publicKeyByteSize);
    status = CryptoPrimitives.BCryptImportKeyPair(_hAlgorithmProvider,
        IntPtr.Zero, PUBLIC_BLOB, ref publicKeyHandle, externalPublicKey, 
        publicKeyByteSize, 0);
    if (!CryptoPrimitives.SUCCESS_STATUS(status))
        throw new Exception();

BCryptSecretAgreement takes my private key, the public key provided by my partner, and returns a handle to the secret agreement generated from these using ECDH.

//create pointer to secret agreement from private key and external public key
status = CryptoPrimitives.BCryptSecretAgreement
        (_hPrivateKey, publicKeyHandle, ref _hSecretAgreement, 0);
if (!CryptoPrimitives.SUCCESS_STATUS(status))
    throw new Exception();

A difficult call to figure out how to make is BCryptDeriveKey. BCryptDeriveKey has to be called twice, the first time in order to find out how much memory needs to be allocated for the secret key, which is a byte array, and the second time in order to actually give it a value.

The trickiest thing about this was figuring out how to pass it the parameter value, which is a struct that contains another struct within it. The parameter value is necessary in order to instruct the method which kind of hash to use in order to generate the secret key. The difficulty involved the fact that the string value which specifies the hash to use is marked as a PVOID type in the struct BCryptBuffer. IntPtr was the most likely data type to use, in this case, but then I had to find a way to create a pointer to my string value and pass this to a new IntPtr. To do this, I used Marshal.AllocHGlobal once again to set aside a memory location to which IntPtr would point. I then had to cast my string as a char array and copy it to the memory location I had set aside using Marshal.Copy. Having created the BCryptBuffer value in this way, I then had to perform a similar procedure to create an IntPtr to my BCryptBuffer struct, using Marshal.StructureToPtr this time, and pass that to a BCryptBufferDesc struct. Finally, I spent half a day before I realized that I didn't need to pass the BCryptBufferDesc by ref, even though the documentation seemed to say that I did. This sort of gerrymandering is actually fairly rare in P/Invoke scenarios, and I only found two other instances of it on http://www.pinvoke.net/. Hopefully, having already gone through this on your behalf, none of you will have to go through the same travails, but can simply reuse this solution.

//create parameters for hash type
CryptoPrimitives.BCryptBuffer bcBuffer = new CryptoPrimitives.BCryptBuffer();
bcBuffer.BufferType = KDF_HASH_ALGORITHM;
bcBuffer.cbBuffer = (uint)((KDFHash.Length * 2) + 2);
IntPtr pvBuffer = Marshal.AllocHGlobal(KDFHash.Length * 2);
Marshal.Copy(KDFHash.ToCharArray(), 0, pvBuffer, KDFHash.Length);
bcBuffer.pvBuffer = pvBuffer;
CryptoPrimitives.BCryptBufferDesc parameters = 
        new CryptoPrimitives.BCryptBufferDesc();
parameters.cBuffers = 1;
parameters.ulVersion = BCRYPTBUFFER_VERSION;
parameters.pBuffers = Marshal.AllocHGlobal(Marshal.SizeOf(bcBuffer));
Marshal.StructureToPtr(bcBuffer, parameters.pBuffers, false);

//call BCryptDeriveKey with null parameter to find size of secret key
if (KDFHash == "SHA1")
    status = CryptoPrimitives.BCryptDeriveKey(_hAlgorithmProvider,
    keyDerivationFunction, null, null, 0, out derivedSecretByteSize, 
    keyDerivationFlagValue);
else
    status = CryptoPrimitives.BCryptDeriveKey(_hSecretAgreement,
    keyDerivationFunction, parameters, null, 0, 
    out derivedSecretByteSize, keyDerivationFlagValue);
if (!CryptoPrimitives.SUCCESS_STATUS(status))
    throw new Exception();
//set aside memory for secret key
_secretKey = new byte[derivedSecretByteSize];
//create a secret key as byte array from secret agreement
if (KDFHash == "SHA1")
    status = CryptoPrimitives.BCryptDeriveKey(_hSecretAgreement,
            keyDerivationFunction, null, _secretKey, 
            derivedSecretByteSize, out derivedSecretByteSize,
            keyDerivationFlagValue);
else
    status = CryptoPrimitives.BCryptDeriveKey(_hSecretAgreement,
    keyDerivationFunction, parameters, _secretKey, derivedSecretByteSize,
    out derivedSecretByteSize, keyDerivationFlagValue);
if (!CryptoPrimitives.SUCCESS_STATUS(status))
    throw new Exception();
}

A word should also be mentioned about exception handling, which is unfortunately often ignored in P/Invoke implementations. Each call to the CNG API returns a uint value. The best solution I found was to evaluate each uint returned to determine whether the call was successful or not. I used a set of values I found in the bcrypt.h header file. If the call fails, I throw an exception that is handled in a catch block. The catch block then throws a Win32 error, which is the last error on the error stack, by making this simple call: new Win32Exception(). This in turn required that every P/Invoke signature in my CryptoPrimitives class (named this because it contains many of the functions that Microsoft calls "primitive" or low-level cryptography functions) be decorated with the following attribute-value pair to make sure all errors are retained rather than ignored: SetLastError = true.

catch
{
    throw new Win32Exception();
}
finally
{
    CryptoPrimitives.BCryptCloseAlgorithmProvider(_hAlgorithmProvider, 0);
    CryptoPrimitives.BCryptDestroyKey(_hPrivateKey);
    CryptoPrimitives.BCryptDestroySecret(_hSecretAgreement);
}
return _secretKey;
}

Vista Platform Invoke Signatures: A Reference

The hardest part of working with P/Invoke in order to access a C API is figuring out how best to declare the P/Invoke signatures. I'd like to say this is more of an art than a science, but it is actually more mind-numbing trial and error than it is either art or science. I think I got most of them right, and that you will be saved time and trouble by referring to the ones I wrote. On the other hand, since it is more than likely that I got a few wrong, I would greatly appreciate any corrections you might find the time to offer. I would like to get the whole CNG API worked out eventually, and, with help, may even succeed in doing this before Microsoft eventually releases Visual Studio Orcas and the new managed cryptography classes. In any case, here are some of the P/Invoke signatures I have been working with. Microsoft has a tendency not to publish P/Invoke signatures, despite various requests that they do so, so finding other people's implementations is always a great leg-up. I hope these will be of use to you, as other developers' published P/Invoke signatures have always been to me.

[DllImport("Bcrypt.dll",
            CharSet = CharSet.Auto, SetLastError = true)]
public static extern uint BCryptOpenAlgorithmProvider(
ref IntPtr hAlgorithm,
string AlgId,
string Implementation,
uint Flags
);

[DllImport("Bcrypt.dll", SetLastError = true)]
public static extern uint BCryptGenerateKeyPair(
IntPtr hObject,
ref IntPtr hKey,
uint length,
uint Flags
);

[DllImport("Bcrypt.dll", SetLastError = true)]
public static extern uint BCryptFinalizeKeyPair(
IntPtr hKey,
uint Flags
);

[DllImport("Bcrypt.dll",
            CharSet = CharSet.Auto, SetLastError = true)]
public static extern uint BCryptExportKey(
IntPtr hKey,
IntPtr hExportKey,
string BlobType,
byte[] pbOutput,
uint OutputByteLength,
out uint Result,
uint Flags
);

[DllImport("Bcrypt.dll", SetLastError = true)]
public static extern uint BCryptDestroyKey(
IntPtr hKey
);

[DllImport("Bcrypt.dll", SetLastError = true)]
public static extern uint BCryptCloseAlgorithmProvider(
IntPtr hAlgorithm,
uint Flags
);

[DllImport("Bcrypt.dll", SetLastError = true)]
public static extern uint BCryptDestroySecret(
IntPtr hSecretAgreement
);

[DllImport("Bcrypt.dll", CharSet =
            CharSet.Auto, SetLastError = true)]
public static extern uint BCryptImportKeyPair(
IntPtr hAlgorithm,
IntPtr hImportKey,
string BlobType,
ref IntPtr hPublicKey,
byte[] Input,
uint InputByteLength,
uint Flags
);

[DllImport("Bcrypt.dll",
            CharSet = CharSet.Auto, SetLastError = true)]
public static extern uint BCryptSecretAgreement(
IntPtr hPrivKey,
IntPtr hPublicKey,
ref IntPtr phSecret,
uint Flags
);

[StructLayout(LayoutKind.Sequential, CharSet=CharSet.Auto)]
public class BCryptBufferDesc
{
public uint ulVersion;
public uint cBuffers;
public IntPtr pBuffers;
}

[StructLayout(LayoutKind.Sequential, CharSet = CharSet.Auto)]
public class BCryptBuffer
{
public uint cbBuffer;
public uint BufferType;
public IntPtr pvBuffer;
}

[StructLayout(LayoutKind.Sequential)]
public class BCRYPT_ECCKEY_BLOB
{
uint Magic;
uint cbKey;
}

[DllImport("Bcrypt.dll",
            CharSet = CharSet.Auto, SetLastError = true)]
public static extern uint BCryptDeriveKey(
IntPtr hSharedSecret,
string KDF,
BCryptBufferDesc ParameterList,
byte[] DerivedKey,
uint DerivedKeyByteSize,
out uint Result,
uint Flags
);

Resources

For those who are just starting out with P/Invoke, here are some articles I found extremely helpful in explaining the technology and how to use it. All of these articles are good, but the two MSDN Magazine articles are especially so.

• Using Platform Invoke by NetPointerIN (CodeProject)
• Essential Pinvoke by Cohen Shwartz Oren (CodeProject)
• MSDN Platform Invoke Tutorial
  Using P/Invoke to Call Unmanaged APIs from Your Managed Classes
• MSDN Magazine - Calling Win32 DLLs in C# with P/Invoke
• MSDN Magazine - P/Invoke Revisited

History

• 5/1/2007 - Read the very nice cryptography article by Quartz and realized I needed to work a little on the details in order to make this article presentable. Sometimes, just saying "there's the code, go to it" really doesn't work.
• 5/2/2007 - Added some P/Invoke resources, per Quartz's suggestion.
• 5/3/2007 - Again per Quartz recommendation, I added some graphics, broke up the long code fragments into smaller chunks, and wrote a more interesting article description. It is pandering, admittedly, but it also seems to make the article read much better. I'm better pleased with it, in any case. Thanks again, Q-man. Presentation really does make a big difference.