Monthly Archives: October 2015

What is Diffie Hellman Key Exchange Protocol and Does the NSA really broke the algorithm ?

There are a lot of rumors going on that NSA has attempted to break Diffie Hellman key exchange protocol.. Former NSA contractor Edward Snowden revealed in the leaked documents that NSA had already decrypted a tons of encrypted Internet traffic, and James Bamford published an article titled : “The NSA Is Building the Country’s Biggest Spy Center (Watch What You Say)” comments that NSA had a computing breakthrough, and that fit exactly as what Snowden said, In the leaked documents Snowden stated that NSA has decrypted VPN, HTTPS and SSH  traffics that specifically used the implementation of Diffie Hellman 1024-bit primes, Till now we don’t have a full details about how much they could achieved from the attack  but if they do a major threat will occure on the users cause Diffie Hellman is fundamental to many protocols including HTTPS, SSH, IPsec, SMTPS, and protocols that rely on TLS. And here is the 2 major Attacks:

1- Logjam attack against the TLS protocol

2- Threats from state-level adversaries

now every major browsers don’t support 512-bit prime though they still support 1024-bit that the NSA trying to break , The problem is most of the people who implemented Diffie Hellman they implemented a common prime number that appear to be safe to use as long as you generate different private key for, But the case now is different because NSA trying to break the prime number and the best way to do this is by Sieve algorithm the most efficient classical algorithm known for factoring integers and of course this will take a lot of computational power and money to deploy but I think NSA will pay this amount of money to collect users information for their massive surveillance program, but what concerns me that bunch of VPN users  and HTTPS website still using the algorithms which make them vulnerable against the attack and when NSA will do this and break the algorithm this will make even the american companies in danger.

And you know that most of the applications online uses the Diffie Hellman Algorithm and some hackers could decrypt the results it’s not the matter of a week algorithm but sadly most of the people who deploy the algorithm don’t care about the factors they just implement with no prior knowledge of the risks or what the criteria of how the algorithm works so bottom line is always try to read the specification don’t just trust the vendor or the website by the name of the algorithm

Okay I’m going to explain how  Diffie Hellman Algorithm works briefly, Diffie Hellman is a key exchange protocol to share a secret key without the need of two parties to meet in person, note here that Diffie Hellman is not an encryption scheme it’s just way to exchange the key then we take the key and put it in one of the  encryption algorithms let say AES or Blowfish.

let say that we have to people (Alice,BoB) who never met in person and they want to share some secret key k without putting the key in the traffic:

1- First they have to choose a multiplicative group of integers modulo p, where p is prime, and g is a primitive root modulo p, this P and G will be publicly know for the attacker and for the whole world.

2- Alice have to choose a secret key  a, This key should remain secret so no one should know about it, Then she have to compute it like this  ga mod p ,  g will be as the generator and a is the secret key that Alice choose, let say that we assign the result into the variable A  so it’s like this :  Aga mod p

3- BoB also will do the same thing will choose a secret key b,  and he should also keep it a secret and he will compute it like this gb mod p and I will assign it to the variable

4- Now Alice will send her results (A) to Bob and Bob will compute the following  Abmod p. he will put the value that he received and compute the power of his secret key  and let’s assign the results to the variable S =  Abmod p and Alice will do the same thing she will take the result of Bob (B) and she will compute the same thing  Bamod p and let denote the result by the variable S and believe it or not the result (S) of Alice BoB is the same  and now they have that same key without leaking the actual key in the traffic,

Just a small note this is just a brief description of how Diffie Hellman works (you have to read the full spesification to understand it in a perfect way) but please don’t implement it by your self, and I have to say that Diffie Hellman it self dosn’t guarantee authenticity and it’s vulnerable against man-in-the-middle-attacks

Okay now you understand how Diffie Hellman works in a brief way,  So  how can I be safe from this, If you have a server that runs Diffie Hellman you should disable support for export cipher suites and use a 2048-bit Diffie-Hellman group. or switch to Diffie Hellman over Elliptic Curve

If you are Interested in the topic I suggest that you read the following paper :

– https://weakdh.org/imperfect-forward-secrecy-ccs15.pdf