My First Look at Diffie-Hellman (Merkle) Key Exchange - Part 1

While I have seen references to Diffie-Hellman before, I honestly knew very little about it until this week. After seeing it mentioned on stackoverflow.com, I decided to do some research. Now I am pretty sure this protocol is not available in the standard edition of Adobe ColdFusion, and contrary to popular opinion, I have my doubts about its availability in Enterprise version as well. Though admittedly, I could not find any solid references one way or the other. So I could be wrong. Anyway, since there is a plethora of implementations in the java world, I decided to explore that route.


Disclaimers
First let me say this entry is not intended to be a "how to guide". In the world of encryption, I am most definitely a novice. But I am a curious novice. So in an effort to better understand the Diffie-Hellman (Merkle) exchange, I decided to take one of the simpler java implementations, deconstruct it, and put the results in a CF context.  If you are already familiar with it, this beginner level entry will probably be one big yawn. But any corrections or clarifications are definitely welcome.  Just go easy lest my brain implode.

What is it?
Wikipedia describes Diffie-Hellman as a key exchange protocol

"...that allows two parties that have no prior knowledge of each other to jointly establish a shared secret key over an insecure communications channel. This key can then be used to encrypt subsequent communications using a symmetric key cipher."

My novice interpretation would be that instead of exchanging a key, two parties exchange "other", transitory, pieces of information instead. Then use those "other" pieces of information to derive the key (independently) without actually sending the key itself over an open channel.

What are those "other" pieces of information? In short, they are really, really large numbers. The protocol uses several numbers in a series of simple mathematical formulas to eventually calculate the secret key. I will not go into details about how and why those numbers are selected. The wikipedia entry describes it far better than I ever could. But suffice it to say they are not arbitrary. Each has specific characteristics that directly affect both the results and the security of the exchange. So I would highly recommend you read the article.  But to paraphrase the salient points (without formulas):

1. Two parties (Alice and Bob) agree upon two (2) numbers to be used in their calculations (a prime number and a primitive root) Note: These are public values, known by both Alice and Bob
2. Then Alice and Bob each pick a private number. Note: Alice should not know Bob's value, and Bob should not know Alice's value.
3. Using their private numbers (plus the prime and primitive root) Alice and Bob each calculate a public number. They then exchange public numbers with each other. Note: These are public values, known to both Alice and Bob.
4. After exchanging public values, Alice and Bob now have enough information to calculate the shared secret key (using another formula) Note: They both arrive at the same secret key value, independently, without ever sending that value over an open channel.

Math 101
Now jumping straight into a java example from here felt a bit like sending a student driver onto a five lane highway after receiving only five minutes of instruction. So I decided to test the basic formulas from the wikipedia example first.  It gave me a better understanding of the overall process, and also provided a good basis of comparison for the java results.

Now before someone corrects me, the overview below is conceptual only.  When I finally did run the simple java example, the actual steps were slightly different. But overall the process was the same.

(On a side note, this whole thing felt a bit like something you would read about in a spy novel. But I suppose that cannot be helped...)

Step 1) Preparing for the Meeting
First, a prime number and primitive root are selected. These are considered public values, known to both Alice and Bob.   Now you may notice I am using java objects. That was necessary because the calculations involved produce very large numbers. Even using small test values like 23 and 5 the results exceeded the capacity of a basic CF integer.

<cfset prime = createObject("java", "java.math.BigInteger").init( 23 ) />
<cfset base = createObject("java", "java.math.BigInteger").init( 5 ) />
<strong>Values known to both Alice and Bob</strong>
<cfoutput>
    <p> ie prime  = #prime# AND  base   = #base# </p>
</cfoutput>

Step 2) Secret Code Words
Next, Alice and Bob each select a private number, which they do not share with each other.

<cfset alicesPrivateValue    = createObject("java", "java.math.BigInteger").init( 6 ) />
<cfset bobsPrivateValue        = createObject("java", "java.math.BigInteger").init( 15 ) />

Step 3) The Public Exchange
Alice and Bob then use their private numbers to calculate a public number using the formula: base ^ private MOD prime. They then exchange public numbers. Again, their private numbers are never exchanged.

<cfset alicesPublicValue     = base.modPow( alicesPrivateValue, prime) />
<strong>Alice's values: </strong>
<span class="code">alicesPublicValue = base ^ alicesPrivateValue MOD prime </span>
<cfoutput>
    <p>ie #alicesPublicValue# = #base# ^ #alicesPrivateValue# MOD #prime# </p>
</cfoutput>

<cfset bobsPublicValue     = base.modPow( bobsPrivateValue, prime) />
<strong>Bob's values: </strong>
<div class="code">bobsPublicValue = base ^ bobsPrivateValue MOD prime </div>
<cfoutput>
    <p>ie #bobsPublicValue# = #base# ^ #bobsPrivateValue# MOD #prime#</p>
</cfoutput>

Step 4) Finding the Key
Alice an Bob now have enough information to derive the shared secret value, independently. Alice uses the formula: alicesSharedKey = bobsPublicValue ^ alicesPrivateValue MOD prime .

<strong>Alice uses Bob's value to compute the shared key (B <sup>a</sup> MOD p)</strong>
<div class="code">alicesSharedKey = bobsPublicValue ^ alicesPrivateValue MOD prime </div>
<cfset alicesSharedKey    = bobsPublicValue.modPow(alicesPrivateValue, prime ) />
<cfoutput>
    <p class="result">Alice's shared key is <strong>#alicesSharedKey#</strong></p>
    <p>ie   #alicesSharedKey# = #bobsPublicValue# ^ #alicesPrivateValue# MOD #prime#</p>
</cfoutput>

Whereas Bob uses the formula: bobsSharedKey = alicesPublicValue ^ bobsPrivateValue MOD prime

<strong>Bob uses Alice's value to compute the shared key (A<sup>b</sup> MOD p)</strong><br/>
<div class="code">bobsSharedKey = alicesPublicValue ^ bobsPrivateValue MOD prime </div>
<cfset bobsSharedKey    = alicesPublicValue.modPow( bobsPrivateValue, prime ) />
<cfoutput>
    <p class="result">Bob's shared key: #bobsSharedKey#</p>
    <p>ie   #bobsSharedKey# = #alicesPublicValue# ^ #bobsPrivateValue# MOD #prime#</p>
</cfoutput>

If everything was done correctly, they will both calculate the same value (ie 2). This value can then be used to create a secret key (DES, etcetera) with which to encrypt and decrypt data. 

Next up in Part 2: Working through a java example.