by
Jason Fletcher (Inverell IT Technician/Programmer)
| Apr 26, 2016

As some of you may be aware, it has come to light (thanks to Edward Snowden) that the National Security Agency (NSA) is intercepting everyone’s data. The funny thing about all this data is that a lot of it is actually encrypted and is meant to be secure from people being able to read it. If this is the case, how is the NSA able to read your encrypted data?

The answer to this little problem isn’t so simple, but with that said, we will look at a few attack vectors that the NSA could be deploying in order to decrypt all of this data. Please note that this is all speculation for now, as no one knows for sure how the NSA is able to do this, however we are able to draw some conclusions as to how one could go about it.

The issue to this problem lies within the heart of how this technology works and has been implemented. The encryption method that is in question here as being the culprit is known as the Diffie-Hellman key exchange or D-H for short. So why is this D-H encryption so important? Well, D-H is one of the encryption methods that are used for encrypting HTTPS, SSH, and VPN traffic across the internet. Now, when I say it is one of the encryption methods, what I actually mean here is it is one of the main encryption methods that are used. So, if we are able to break this encryption, then we are able to view the majority of the encrypted traffic that flows around the Internet. But why is this ability important? Well, if you are a government agency that partly exists to spy on the public, or someone that wants to know what someone else is doing then this ability is invaluable.

From this point onwards, in order for us to look at this technology we are going to ask Alice, Bob, and Eve to help us out. Alice and Bob just want to be able to talk to each other without anyone else knowing what they are saying. While Eve really wants to know what they are saying and will trying everything she can think of to find out. We will start the article off by first looking at how D-H works and how we are able to setup a secure communications channel. Once we understand how we can use D-H to secure our communications, we will then move onto the attack vectors and look at some possible options that are available to Eve.

We have already explained what D-H is, and what it is actually used for. Before we can go any further we are going to have to look at how we use D-H to setup a secure communications channel for us. In order to do this, we are going to have to go into a little bit of maths behind how it actually works (in order to understand how we can break this kind of encryption, we first need to understand how we encrypt our data).

Before Alice and Bob are able to communicate with each other they must first agree on two prime numbers. We will let these two numbers be ‘g’ and ‘p’, now p is actually a really large number (typically 1024bit), where g is just a primitive root modulo p. These two values are actually chosen in this way to ensure that the resulting shared secret can take on any value from 1 to p-1. Once we have picked these two values we don’t actually need to keep them secret, we don’t care if someone is able to get a hold of them, they are actually pointless to anyone that has them (well, kind of, more on this later). This means that we can transfer these values across an insecure communications link to each other.

The next stage in the encryption method has both Alice and Bob picking their private key. This key should never be known by someone else except for the person that owns it (if you have the private key then you have the key to the kingdom, this will become more evident later on when we look at the attack vector). So now Alice picks a large random number, which we will call ‘A’ as her private key. Just like Alice, Bob also picks a large random number as his key, we will call this value ‘B’.

The next step is for Alice to then compute A which is the value that she needs to send to Bob. Alice works out A by using the following formula A = ga mod p.

Just like Alice, Bob also needs to work out this value and send it to Alice. We will give Bob’s value the name ‘B’. So Bob works out his value for ‘B’ with the following formula B = gb mod p and sends it to Alice. Once Alice and Bob have this value they are then able to work out the shared key. It is this shared key that allows Alice and Bob to decrypt all the encrypted messages, and encrypt all their messages. We are going to give the shared key the name ‘S’. Alice is able to work out the shared key with the following formula s = Ba mod p, and Bob can also work out s with the same formula s = Ab mod p. the value that both Alice and Bob work out will be the exact same value, they both now know the same secret without having to tell each other what that secret is.

One thing to note about this encryption method is that the following values are always kept secret (that is they are never transmitted to each other) a, b, and (gab mod p = gba mod p), while all the other values are sent in plain text (anyone can listen in on these values) p, g, ga mod p, and gb mod p.

Once Alice and Bob are able to compute a shared key, they are then able to use this key in order to encrypt all their data so that both sides are able to decrypt the message.

We have now just seen how D-H is able to setup a “secure” communication’s channel for both Alice and Bob. Now what if Eve wants to know what Alice and Bob are saying? What is Eve to do?

The most logical answer to this question is to just find a way around the encryption so that she can also decrypt all the messages. Sounds easy, right? Well, it kind of is. In order to find out how Eve could potentially decrypt all these messages, you are going to have to wait and tune in for part 2 which is coming soon!