Total votes:
3
Views:
16,197
Comments:
4
Category:
Security
Print:
Print Article
Please login to rate or to leave a comment.
Published: 01 Aug 2007
By: Derek Smyth
Download Sample Code
The DiffieHellman 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 DiffieHellman 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 DiffieHellman 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 DiffieHellman 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 postit note stuck on the side of the monitor.
The DiffieHellman 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 DiffieHellman) produce an encryption key, they differ in one major
respect. The password approach requires a user. The DiffieHellman approach, although it can require a user,
doesn't depend on one.
The DiffieHellman approach is really used when sending a batch of data to another computeror a message to a
personduring a finite communication session. Ideally, the generated key is not saved between each session.
Instead, a new key is generated. The DiffieHellman approach is not ideal in storing encrypted data for long
periods of time; the password approach would be better suited for this.
The DiffieHellman 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
].
Mandywho has been listing in the whole timehas 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
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 perspectiveit'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 codeone 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 runningusing either Bob's or
Alice's applicationclick 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
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 reencrypt
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 DiffieHellman 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
About Derek Smyth

Sorry, no bio is available
This author has published 6 articles on DotNetSlackers. View other articles or the complete profile here.

Please login to rate or to leave a comment.