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

After working through the basic formulas in Part 1, I felt I had a decent grasp of the overall process. So I decided to dive into a java example.  From what I have read, there are different implementations. So I looked over a few java examples before choosing what I felt was the simplest: the one from the (Sun) Java Cryptography Extension (JCE) Reference Guide. Make no mistake, there is definitely a lot more involved in establishing secure exchanges than is covered in the example. But as with most things, understanding the concepts and what the code is doing is a good start.


So when I first looked at the java code, I was a bit .. flummoxed. I honestly did not recognize much of anything, other than "DH". I suppose I naively expected I might see objects initialized with secret values, calculations of prime numbers and primitive roots. Ye-ah. Needless to say, I did not find anything like that. At least not in the basic "intro" example.

The more I thought about it, I realized how silly that would be. Remember I mentioned typical exchanges involve really, really big numbers? Well imagine having to calculate really large prime numbers or primitive roots (on your own) in order to use the library? Not fun. After reviewing the code more closely, I realized the SunJCE does indeed provide a class that does the grunt work for you.

First an AlgorithmParameterGenerator is used to generate the initial parameters. In other words the prime number and primitive root agreed upon by Alice and Bob. In this example it is initialized with a key size 512 bits. A real exchange would probably use a larger key like 1024 bits.

As you can imagine, generating the values is an expensive operation and may take a few seconds. But when finished, the generator will return a DHParameterSpec object. It is simply an object containing the settings used for the exchange: prime number (p), primitive root (g) and key size (l). To view the values, use the methods getG(), getP() and getL().

<cfset generator = createObject("java", "java.security.AlgorithmParameterGenerator").getInstance("DH") />
<!--- Intialize the generator to create a 512 bit key pair (Testing only) --->
<!--- This is an expensive operation and may take a while --->
<cfset generator.init( javacast("int", 512) ) />
<cfset params = generator.generateParameters() />
<!--- Convert the parameters to the right type of object --->
<cfset DHParameterSpec = createObject("java", "javax.crypto.spec.DHParameterSpec")/>
<cfset parameterSpec   = params.getParameterSpec(DHParameterSpec.getClass()) />

Next the code passes those parameters into a KeyPairGenerator . The generator returns a KeyPairobject which contains Alice's private and public keys. While so far things may not seem very familiar, the generator is actually doing the same thing we did in Part 1. Except it automatically selects Alice's secret number, and calculates her public number internally using the given parameters (ie prime number and primitive root).

<cfset KeyPairGenerator = createObject("java", "java.security.KeyPairGenerator") />
<cfset alicesKeyPairGenerator = KeyPairGenerator.getInstance("DH") />
<cfset alicesKeyPairGenerator.initialize( parameterSpec ) />
<cfset alicesKeyPair     = alicesKeyPairGenerator.generateKeyPair() /> 

How do you know this? Well if you display Alice's keys, you will see several parameter names followed by a long string of hexadecimal. Those values are just very large numbers, encoded as hex. The "x" represents Alice's private number and the "y" her public number. The "p" and "g" are our prime number and primitive root values. Again, encoded as hex.

Starting to seem familiar now? 

<cfoutput>
<strong>Alice's Values</strong>
<pre>
    Format    = #alicesKeyPair.getPublic().getFormat()#
    Base (g)  = #alicesKeyPair.getPublic().getParams().getG()#
    Prime (p) = #alicesKeyPair.getPublic().getParams().getP()#
</pre>    

<pre>    
#alicesKeyPair.getPrivate()#
</pre>    
<pre>    
#alicesKeyPair.getPublic()#
</pre>
</cfoutput>

Before Alice sends Bob her public number, she creates a KeyAgreement. Basically this object will be used to complete the final step: calculating the shared key. So it is first initialized with Alice's private key. Then Alice sends her public key off to Bob, and waits to receive his in return.

<!--- Alice creates and initializes her DH KeyAgreement object with her Private Key --->
<cfset KeyAgreement = createObject("java", "javax.crypto.KeyAgreement").getInstance("DH") />
<cfset alicesKeyAgreement = KeyAgreement.getInstance("DH") />
<cfset alicesKeyAgreement.init( alicesKeyPair.getPrivate() ) />
<!--- Alice encodes her public key, and sends it over to Bob --->
<cfset alicesPublicKeyBytes = alicesKeyPair.getPublic().getEncoded() />

When Bob receives Alice's public key, it is encoded in x509 format. So it has to be decoded it first. Bob then uses that object to create his own keys. Finally, he encodes his public key and sends it back to Alice.

<!---
    Bob gets the DH parameters associated with Alice's public key. 
    He must use the same parameters when he generates his own key pair.
--->
<cfset dhParamSpec = publicKeyFromAlice.getParams() />

<!--- Bob creates his own DH key pair --->
<cfset KeyPairGenerator = createObject("java", "java.security.KeyPairGenerator") />
<cfset bobsKeyPairGenerator = KeyPairGenerator.getInstance("DH") />
<cfset bobsKeyPairGenerator.initialize( dhParamSpec ) />
<cfset bobsKeyPair = bobsKeyPairGenerator.generateKeyPair() />
<!--- Bob encodes his public key, and sends it over to Alice --->
<cfset bobsPublicKeyBytes = bobsKeyPair.getPublic().getEncoded() />

Just like Alice's values, Bob's keys will be encoded as hex.

<cfoutput>
<strong>Bob's Values</strong>
<pre>
    Base (g)  = #dhParamSpec.getG()#
    Prime (p) = #dhParamSpec.getP()#

</pre>
<pre>
#bobsKeyPair.getPrivate()#
</pre>

<pre>
#bobsKeyPair.getPublic()#
</pre>
</cfoutput>

Bob is now ready to calculate the shared key. So he too creates a KeyAgreement, and initializes it with his private key. Finally he plugs in Alice's public key and calculates the shared value. Now internally this class is using the same formulas as we did in Part 1. But it is all done for you auto-magically.

<!--- Bob creates his DH KeyAgreement and initializes it with his private key --->
<cfset bobsKeyAgreement = createObject("java", "javax.crypto.KeyAgreement").getInstance("DH") />
<cfset bobsKeyAgreement.init( bobsKeyPair.getPrivate() ) />
<cfset bobsKeyAgreement.doPhase(publicKeyFromAlice, true) />
<cfset bobsSharedSecret = bobsKeyAgreement.generateSecret() />
<cfset bobsSharedSecretAsHex = binaryEncode(bobsSharedSecret, "hex") />

Once Alice receives Bob's public key, she decodes it and plugs the value into her KeyAgreement object. Then calculates the shared value.

<cfset alicesKeyFactory = createObject("java", "java.security.KeyFactory").getInstance("DH") />
<cfset X509EncodedKeySpec = createObject("java", "java.security.spec.X509EncodedKeySpec") />
<cfset x509KeySpec = X509EncodedKeySpec.init( bobsPublicKeyBytes ) />
<cfset publicKeyFromBob = alicesKeyFactory.generatePublic(x509KeySpec) />
<cfset alicesKeyAgreement.doPhase( publicKeyFromBob, true ) />
<cfset alicesSharedSecret = alicesKeyAgreement.generateSecret() />
<cfset alicesSharedSecretAsHex = binaryEncode(alicesSharedSecret, "hex") />

Thanks to the wonders of mathematics, Alice and Bob both arrive at the same shared value.

<cfset areSecretsTheSame = alicesSharedSecretAsHex eq bobsSharedSecretAsHex />
<cfoutput>
<strong>Are Alice and Bob's secrets the same?</strong> #areSecretsTheSame#

<p class="result">alicesSharedSecretAsHex</p>
<p>#alicesSharedSecretAsHex#</p>

<p class="result">bobsSharedSecretAsHex</p>
<p>#bobsSharedSecretAsHex#</p>
</cfoutput>

By itself, the shared value cannot be used for encryption. However Alice and Bob can use the shared value to generate a secret key which can be used for encryption.

The java documentation includes a simple example using DES. Obviously outdated, but it does demonstrate that Alice and Bob can successfully can encrypt/decrypt each other's values, starting only with the shared key.

Bob Encrypts

<!--- 
     The previous call to bobsKeyAgreement.generateSecret resets the key
     agreement object, so we call doPhase again prior to another generateSecret call
--->
<cfset bobsKeyAgreement.doPhase(publicKeyFromAlice, true) />
<cfset bobsDESKey         = bobsKeyAgreement.generateSecret("DES") />

<!--- Encrypt the text with a simple encryption --->
<cfset Cipher               = createObject("java", "javax.crypto.Cipher") />
<cfset bobsCipher          = Cipher.getInstance("DES/ECB/NoPadding") />
<cfset bobsCipher.init( Cipher.ENCRYPT_MODE, bobsDESKey ) />
<cfset textToEncrypt      = "StandAndDeliver!" />
<cfset bytesToEncrypt       = CharsetDecode(textToEncrypt, "utf8") />
<cfset encryptedBytes       = bobsCipher.doFinal(bytesToEncrypt) />
<cfset encryptedText     = BinaryEncode(encryptedBytes, "hex")  />

<!--- results --->
<strong>Bob's Values:</strong>
<cfoutput>
<p><strong>DES Key</strong>  : #BinaryEncode(bobsDESKey.getEncoded(), "hex")# </p>
<p><strong>Encrypted Text</strong>  : #encryptedText# </p>
</cfoutput>

Alice Decrypts

<!--- 
     The previous call to bobsKeyAgreement.generateSecret resets the key
     agreement object, so we call doPhase again prior to another generateSecret call
--->
<cfset alicesKeyAgreement.doPhase(publicKeyFromBob, true) />
<cfset alicesDESKey = alicesKeyAgreement.generateSecret("DES") />
<cfset Cipher               = createObject("java", "javax.crypto.Cipher") />
<cfset alicesCipher         = Cipher.getInstance("DES/ECB/NoPadding") />
<cfset alicesCipher.init( Cipher.DECRYPT_MODE, alicesDESKey ) />
<cfset bytesToDecrypt     = BinaryDecode(encryptedText, "hex") />
<cfset unencryptedBytes  = alicesCipher.doFinal( bytesToDecrypt ) />

<!--- results --->
<strong>Alice's Values:</strong>
<cfoutput>
<p><strong>DES Key</strong>  : #BinaryEncode(alicesDESKey.getEncoded(), "hex")# </p>
<p><strong>Unencrypted text</strong>  : #CharsetEncode(unencryptedBytes, "utf8")# </p>
</cfoutput>            

Obviously there is a lot more to consider before entering into this type of exchange. Guarding against man-in-the-middle attacks is definitely one issue. So you will want to do a lot more reading first. But hopefully this entry helped de-mystify Diffie-Hellman key exchanges ... a little.

As always, any comments or corrections are welcome!