Published: 01 Aug 2007
By: Derek Smyth
Download Sample Code

The Diffie-Hellman Key Agreement Standard describes an algorithm which allows two individual parties to separately generate the same secret key but by only sharing non sensitive data. This article discusses the Diffie-Hellman Key Agreement algorithm, providing an implementation in .NET, before discussing areas not covered by the algorithm.

Introduction

One problem with symmetric encryption is the fact that it is extremely difficult to share the encryption key. For example, imagine Bob and Alice wanted to send a secret message to each other. In order to do this, Bob and Alice both need to have the same encryption key. How do they share the key securely? How can Bob give Alice the encryption key that he used to encrypt the data in such way that the key is kept safe?

There are a couple of methods of doing this. The Diffie-Hellman Key Agreement Standard, which from now we'll call the algorithm, describes a method that gives two individual parties the ability to generate the same secret encryption key using sharable non sensitive data.

Password Derived Keys Vs Diffie-Hellman Key Generation

The best way to protect a key is not to store it anywhere; but instead derive it for some other information. There are a couple of ways to achieve this and everyone who reads this article will be familiar with one of those ways: Passwords.

Generating a key from a password is a very common practice and is very useful. Unfortunately the effectiveness of this approach depends on the user picking a strong password and not writing that password down; say, on a yellow post-it note stuck on the side of the monitor.

The Diffie-Hellman Key Algorithm derives a key from a collection of randomly generated numbers using some very clever mathematics. Instead of having to pass the key between themselves, the two parties share the results of the computations and these form the information from which the key is derived.

Although the two approaches (password and Diffie-Hellman) produce an encryption key, they differ in one major respect. The password approach requires a user. The Diffie-Hellman approach, although it can require a user, doesn't depend on one.

The Diffie-Hellman approach is really used when sending a batch of data to another computer-or a message to a person-during a finite communication session. Ideally, the generated key is not saved between each session. Instead, a new key is generated. The Diffie-Hellman approach is not ideal in storing encrypted data for long periods of time; the password approach would be better suited for this. 

The Diffie-Hellman Key Algorithm

The algorithm itself is very simple to understand but describing it can get a little complicated. In order to keep it simple we'll work through an example using our good friends Bob, Alice, and newcomer Mandy. The following example will brush over the mathematics of the algorithm.

Bob wants to tell Alice a secret message but he doesn't want Mandy to be able to read that secret message. Unfortunately Mandy knows something secret is going to being passed between Bob and Alice and she wants to know what it is. In this example Mandy is performing a man in the middle attack. Here is what happens.

Bob generates three random numbers [a, b, c] and performs a calculation using all three, which produces another number (a + b + c = ~d). Bob now has four numbers [a, b, c, ~d]. Bob must keep one of these numbers secret ([c]) but he sends the other three to Alice ([a, b, ~d]).

When Alice receives these numbers, she generates her own secret number [x] and performs the same calculation as Bob. Now she uses her own secret number (a + b + x = ~z). She then sends the result [~z] back to Bob.

Bob now has [a, b, c, ~d, ~z].

Alice now has [a, b, x, ~d, ~z].

Mandy-who has been listing in the whole time-has gathered [a, b, ~d, ~z].

Bob then takes his secret number [c] and performs a calculation on the result of Alice's calculation [~z], which produces a value [~k]. Alice takes her secret number [x] and performs a calculation on the result of Bob's calculation [~d]. She produces a value that, amazingly, turns out to be [~k]. Bob and Alice have arrived at the same value and that value becomes the encryption key.

Mandy has neither Bob's or Alice's secret values and so she is unable to perform the last calculation step. She is therefore never able to calculate the encryption key. Here is a diagram that visualizes the process.

Figure 1: Diagram of the process

DiffieHellmanSmall.gif

There are a couple of conditions needed to be imposed in order for the algorithm to work. First of all, the shared non sensitive data [a, b] used by both Bob and Alice need to be whole number integers. One of them needs to be a prime number. The other number must be smaller than the prime and larger than 0.

For more information on these conditions and the mathematics involved (which are fairly simple) see the PKCS #3 standard in the references section at the end of this article.

Implementing the Algorithm

The example provided with the article does not completely follow the algorithms standard. This was done to make things easier to understand. For example, it's recommended that a central authority is used to issue the shared data. 

There are also limitations on some of the random number generators in the example applications. The mathematics of the algorithm produces some extremely large numbers and the .NET primitive data types aren't sufficient to store these numbers. This will change as Orcas is introducing a very large integer data type, mainly for cryptography mathematics.

Prime numbers are used by the algorithm. The standard recommends that a random 10 digit prime number is used. In order to prevent the algorithm from taking several universe lifetime to find a prime number of that magnitude, a limitation was placed on the size of the prime. This makes this implementation not as secure as it should be; but lets put things into perspective-it's ok for a chat application.

The above limitations meant that the secret value calculated by both parties at the end of the algorithm was not an adequate key length. So what the example does is treating the value as a password and using it to derive the encryption key. Since both parties have the same secret value they will derive the same encryption key.

There are two application in the example code-one for Bob and one for Alice. You need to run both. If you have a firewall running, unblock the ports when prompted. Once both applications are running-using either Bob's or Alice's application-click the "Establish Secret Key" button. This will create the key used by both applications. After that, you can use the Messaging tab to sent messages. Behind the scenes, the message is encrypted before being sent; and is decrypted on arrival. 

Figure 2: Sample applications

Sample 

applications

Important problem with the algorithm

The algorithm is cool but there is a flaw: No authentication. In the example involving Bob, Alice and Mandy, there is nothing stopping Mandy from fooling Bob into thinking she is Alice and nothing to stop Mandy from fooling Alice into thinking she's Bob.

Essentially, when Bob sent the message he's used a key he agreed with Mandy. When Bob sends he thinks he's sending it to Alice but really the message goes to Mandy. Mandy could then decrypt it, change it, then re-encrypt with the key she agreed on with Alice, and then forward the message to Alice. Alice believes the message came from Bob.

To get around this, it's advisable to include HMACs and Digital Signatures into the process to verify the message source. See the reference section for my article on how to implement these in .NET.

Summary

The Diffie-Hellman Key Generation Standard is a wonderful piece of mathematics. It's simple and very effective. There are a number of ways in which the algorithm could be applied. Its best use is for data communication; or where the encryption key and/or data has a finite shelf life. It is not ideally suited for producing a key that will be used to encrypt data that will be stored; but it is ideal for creating a key for encrypting data that you want to transport. Unfortunately there is no authentication so using it without introducing digital signatures or challenge response technologies is a security risk.

References

<<  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


An inside look at Symmetric Encryption
This article describes the internal workings of symmetric encryption; also known as secret key encry...
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...
Protect Code with Skater .NET Obfuscator
Application vulnerabilities, Intellectual Property theft and revenue loss are among the most serious...
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...
Book Review: Understanding Windows CardSpace
Review of the book “Understanding Windows CardSpace”.

You might also be interested in the following related blog posts


Are you mouse-bored? read more
XAML By FARR: Animations, Resources Vs. Code Behind read more
Microsoft and the Apache Stonehenge Project read more
Automated Attendant with the OCSDK Wrapper and WPF read more
Work on your Vocabulary. The word for today is "CodableValue" read more
NavigationWindow, WinFormsHost and TextBoxes: backspace bug read more
Did You Know... There are 3 Versions of Keyframe Animation? read more
WPF NavigationWindow, WinFormsHost and TextBoxes: backspace bug read more
Creating and Managing a Connection String with Oracle ODP.NET read more
Pressing keys simulation in Selenium, RadInput on fire read more
Top
 
 
 

Discussion


Subject Author Date
placeholder Bad example! Rogier 21 5/2/2011 6:00 PM
Asymetric encryption Karl Seguin 8/1/2007 8:01 AM
placeholder RE: Asymetric encryption Derek Smyth 8/1/2007 1:26 PM
Asymetric encryption Kazi Manzur Rashid 8/6/2007 3:56 AM

Please login to rate or to leave a comment.