With all the stories about the NSA spying on the communications of people all over the world, we may have an exaggerated sense of the NSA’s code-breaking capabilities. Matthew Green, the cryptography researcher at Johns Hopkins University who was temporarily censored, explains that there are three ways to get past encryption.
There’s almost too much here for a short blog post, so I’m going to start with a few general thoughts. Readers of this blog should know that there are basically three ways to break a cryptographic system. In no particular order, they are:
- Attack the cryptography. This is difficult and unlikely to work against the standard algorithms we use (though there are exceptions like RC4.) However there are many complex protocols in cryptography, and sometimes they are vulnerable.
- Go after the implementation. Cryptography is almost always implemented in software — and software is a disaster. Hardware isn’t that much better. Unfortunately active software exploits only work if you have a target in mind. If your goal is mass surveillance, you need to build insecurity in from the start. That means working with vendors to add backdoors.
- Access the human side. Why hack someone’s computer if you can get them to give you the key?
Bruce Schneier, who has seen the documents, says that ‘math is good‘, but that ‘code has been subverted‘. He also says that the NSA is ‘cheating‘. Which, assuming we can trust these documents, is a huge sigh of relief. But it also means we’re seeing a lot of (2) and (3) here.
So to sum up, one way is to do the math, which is the hardest. The next hardest is to exploit weaknesses in the software. And the third is to basically cheat, by demanding that the manufacturers of the software and hardware give you the encryption keys. So what NSA has done is not be clever but to basically cheat, using the power of the government to get what it wants. Good encryption can still defeat them and so they are determined to avoid people gaining access to such things.
ProPublica reports that the National Institute of Science and Technology (NIST), that is supposed to set standards for all manner of things, has lowered its own encryption standards. It refuses to comment on whether it did so at the request of the NSA though Green suspects that that is the reason. So not only does the NSA cheat, it makes other parts of the government, that are supposedly working in the public interest and who should be actually raising standards, accomplices in its cheating.
Eh, let’s not be too dismissive here either. Don’t forget what the NSA pulled off in order to spread Stuxnet/Flame/etc. It is likely they are indeed “cheating” pretty heavily (it would be stupid not to exploit human factors first and foremost), but we also know that they have in the past pulled off stuff that was supposed to be just out of reach of what the research community thought possible at present.
The only “conspiracy theory” I really buy is that I do think that the US gov’t has cryptographic technologies that are beyond what is known in the most cutting edge of academia. Not light years beyond it, but enough beyond it that I think it would be enough to inspire a few “holy shits” from even the most talented and knowledgable public sector cryptographers.
Did you hear the latest report that when the British detained David Miranda, the partner of Glenn Greenwald, in England recently, that David was carrying a notebook PC with the Snowden documents, which was encrypted with TrueCrypt whole disk encryption, but he was also carrying a sheet of paper with the TrueCrypt password written on it?!?
No, I did not read that.
One password of many. As Greenwald himself has stated, that one password would not have allowed access to any of the encrypted files.
The following is a short high level look at ECC, Elliptic Curve Cryptography.
A known prime is involved. The formula is y^2 = x^3 + ax +b (mod p). Those with more math than I understand know the relationships between a, b and p that make ECC work. NIST publishes several primes along with a standard starting point, G. They give a, b, p (the prime) the (x, y) for G and the number of points in the curve. Because some of the internal math involves numbers with twice the number of bits as p, the prime is chosen to make the mod p operation efficient in 32-bit hardware.
Alice and Bob can share a secret. Each selects a random private key which must be in the range of 1 to p-1. I would restrict the range to sqrt(p) to p-sqrt(p). Let’s call these private keys a and b.
Alice’s public key: A = aG
Bob’s public key: B = bG
Shared secret: bA = aB (use the x coordinate)
(The above is the Diffie–Hellman key exchange.)
Terminology: (A, a) is Alice’s key pair.
This works because bA = b(aG) and aB = a(bG) and the fact that multiplication is associative i.e. b(aG) = a(bG).
ECC works for cryptography because while A = aG is straightforward, a = A/G is computationally infeasible.
Thus using NIST p-256 with its 256-bit prime, Alice and Bob can share a 256-bit secret via email without any snooping party learning more than the shared secret is 256 bits long. This assumes that both Alice and Bob have each others public keys.
This is how I would use ECC such that snooping the communication will not reveal the contents of any message Alice and Bob send to each other.
The messages will be encrypted using AES-256. I doubt that NSA can break that.
Alice wants to have a private conversion with Bob. She creates a random secret key and its public key counterpart. She sends this to Bob who creates his own random secret key and public key counterpart. He sends that to Alice. Using the Diffie–Hellman key exchange method given above they each compute a common shared secret using it as the 256-bit AES key. After the shared secret is generated both Alice and Bob erase their ECC key pairs. Then after message(s) are sent the shared secret is erased.
Notice that all secrets are ephemeral. No past recorded communication can be decoded from any information held by either party.
Man-in-the-middle attacks against this would be difficult. A well equipped attacker would have to insert himself into the communication channel between Alice and Bob. This attacker would then replace the public keys used by Alice and Bob with his own. It’s also possible to alter messages between them. Altering encrypted voice content in real time would require some really fancy artificial intelligence.
A trusted third party who can not be compromised could prevent man-in-the-middle attacks. I doubt that such a third party exists. I would rather trust in the difficulty of launching a man-in-the-middle attack.