Guarding your Keys – Understanding Diffie Hellman | Nihal Pasham

 

 

 

Image

 

The internet or the web by itself doesn’t really offer much when it comes to confidentiality. It employs a set of encryptions standards (like SSL/TLS) to provide secure channels for communication. The general idea of these encryption standards allows a user who wants to send a message to another to feed an encryption function/algorithm with the message (i.e plaintext) to be encrypted along with a ‘secret key’ to produce what’s called cipher-text (essentially gibberish) and the recipient on the other end retrieves the encrypted message by running it through a corresponding decryption function which uses the same ‘secret key’.

However, this raises the question – How do I send my ‘secret key’ to an intended recipient without it being comprised while in transit?  Indeed, the most challenging part of any cryptosystem is key management or more specifically key distribution. Well, traditional key-distribution methods such as sending your key in an email or the use of secure physical transport services (like a man handcuffed to a briefcase containing your keys) are neither scalable in terms of practicality nor reliable when dealing with volume (billions) of transactions across the internet on a daily basis.

The Diffie Hellman key-exchange standard offers a really unique solution to the problem of key distribution. The underlying idea is to allow users to agree on a ‘secret key’ using an insecure channel. The insecure channel in this case is the internet and ‘secret key’ is derived by exchanging a set of variables such that knowledge of the variables doesn’t allow an eavesdropper to deduce the ‘secret-key’. Sounds like magic doesn’t it but its more to do with the mathematics of discrete logarithms than magic. For example – Alice and Bob are two users who’d like to agree upon a ‘secret key’. They’d first have to agree on two large numbers say p and q. Subsequently Alice will choose a random number x, compute (A = q^x mod p) and send A to Bob while Bob on other hand does the same thing except he chooses a different random number y, computes (B = q^y mod p) and passes B onto Alice. Finally Alice and Bob compute their ‘secret keys’ individually by raising B^x and A^y i.e.  K1 = B^x mod p  and  K2 = A^y mod p. Now their computed keys happen to be the same

i.e. K1 = K2 = (q^xy mod p) mod p .

This is known as the ‘discrete logarithmic problem’ where given p,q,A,B, the probability of deducing x,y is a computationally intractable problem i.e. it cannot be done within a reasonable amount of time. Considering that this solution requires no prior communication, it is considered to be an ‘almost perfect’ solution to the problem of key distribution (used in TLS and referred to as ‘perfect forward secrecy’ or PFS). The reason I say ‘almost perfect’ and not perfect is because ‘perfect’ solutions usually fall short when it comes to their implementation and PFS doesn’t seem to be exempt from this. A few issues that plague this perfect solution are TLS session resumption issues requiring session tickets and imperfect memory allocation algorithms (i.e. although keys generated using DH persist for a single session and are discarded after the session, imperfect memory allocation algorithms can still lead to a Heart-bleed style vulnerability as the ‘secret key’ generated would still need to be stored locally in memory for the duration of the session).

Barring the implementation level imperfections, DH as a cryptographic standard makes the job of distributing your keys secure and consequently ‘stealing keys’ more difficult. It is for this reason that PFS serves as a much stronger safeguard against persistent monitoring attacks (than alternatives like RSA) where encrypted messages are intercepted (probably over several years) and later decrypted, when an attacker gains access to the corresponding private keys.

Additional Resources –

http://blog.cryptographyengineering.com/2013/12/how-does-nsa-break-ssl.html

https://www.youtube.com/watch?v=xHlSWqJT8lc

http://en.wikipedia.org/wiki/Diffie-Hellman_key_exchange

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s