On Encryption

From all the news, it appears that there is one thing clear: Nobody is certain as to the exact capabilities of the NSA, other than the NSA itself. However, as soon as the limited information was released, we began conducting research and were able to draw some conclusions. As of now, Bruce Schneier appears to be our best source of information in regard to this matter, as he is a security and cryptography expert, and often speaks in the defense of civil liberties. He has been given direct access to Snowden’s source NSA materials.  As such, at this point he is the only one, on our side, that is in a position to make conclusive educated guesses about the NSA.

Dead or Alive
To begin, encryption, in general, is neither dead nor useless. Both Snowden and Schneier have made strong statements indicating as much. “Encryption works. Properly implemented strong crypto systems are one of the few things that you can rely on,” said Snowden. In addition, Schneier said, “I believe this is true.” He continued to say, “Trust the math. Encryption is your friend. Use it well, and do your best to ensure that nothing can compromise it. That’s how you can remain secure even in the face of the NSA.” However, the media seems to be spinning things as if encryption is broken in its entirety. If it is not, then the question remains, what is broken?

Long Live the King
It is to our best understanding that 1024bit RSA must be retired. It is most likely able to be cracked in a much smaller time frame than originally thought possible. There are multiple facts that we’ve observed that led us to this conclusion, with the following quote seemingly confirming our suspicions: “Another program, codenamed Cheesy Name, was aimed at singling out encryption keys, known as ‘certificates’, that might be vulnerable to being cracked by GCHQ supercomputers.” This is indicative of the fact that only certain types of certificates are crackable, and the most likely culprit for that is the weak 1024bit RSA certificate which is still commonly used by many websites. If this is true, then it has huge implications for HTTPS traffic, but has minimal impact on OpenVPN traffic. Due to the fact that most web servers do not use an ephemeral key exchange, the vast majority of HTTPS traffic is decryptable by obtaining or cracking the RSA certificate’s private key.

3 Ghosts of Surveillance
Ephemeral key exchanges differ greatly from that of the non ephemeral key exchanges due to the fact that they do not rely, in any way, on certificates for the exchange of their secret keys. In other words, if a criminal is spying on your encrypted connection, even if the criminal were to somehow obtain the private key of the certificate, he or she would not be able to decrypt the transmission. In contrast, a non ephemeral key exchange relies solely on the secrecy of the certificate’s private key in order to maintain exchange secrecy. As such, in this case, once a private key is compromised, then all past, present and future non ephemeral exchanges will be compromised, just by watching them.

The silver lining to this is that if all web traffic simply upgrades to using ephemeral key exchanges, then the fact that 1024bit RSA encryption is broken will not have any effect as to whether dragnet decryption of HTTPS traffic can or will occur. Unfortunately, this is not the case in our contemporary internet, and as such, we have to assume the NSA is performing dragnet decryption of non ephemeral 1024bit RSA HTTPS connections, which makes up most of the web/HTTPS traffic on the internet.

OpenVPN
Fortunately, the open source OpenVPN was designed to use ephemeral key exchanges in order to prevent any kind of mass dragnet decryption. This still leaves OpenVPN connections open to targeted man in the middle attacks assuming they have cracked the private key. We have put in motion several changes that will harden our service and, thus, prevent these new, powerful attacks from occurring.

Kryptonite is not the only weakness
There is yet another less-likely scenario as to what could be broken. It is possible that the 1024bit Diffie Helman key exchange protocol can be cracked in a reasonable amount of time. No one has mentioned anything about this and therefore we believe it unlikely to be the case. However, this would potentially allow the NSA to decrypt past or future OpenVPN or HTTPS sessions (using a 1024bit key exchange) that they may have passively recorded. Although this is most likely not the case, we at Private Internet Access have already upgraded all of our Diffie Helman key exchanges to 2048bit to ensure that this is not even a realistic possibility.

National Security Agency
According to The Guardian, “Documents show that Edgehill’s initial aim was to decode the encrypted traffic certified by three major (unnamed) internet companies and 30 types of Virtual Private Network (VPN) – used by businesses to provide secure remote access to their systems. By 2015, GCHQ hoped to have cracked the codes used by 15 major internet companies, and 300 VPNs.”

This statement was, at first, alarming. However, after we analyzed all of the reports thoroughly as well as consulted subject matter experts both in-house and externally, we are in belief that they are referring to different types or implementations of PPTP VPN solutions including hardware, software, or even open source PPTP implementations. After all, PPTP has historically used many cryptographic algorithms that were subsequently proven to be broken or weakened to the point of uselessness. In addition, it’s also an extremely aged/legacy protocol, so there are most likely many different variants included in commercial offerings. We believe the NSA is merely referring to attempts to set up their systems to automatically detect and decrypt all of the different PPTP variants. This would, of course, enable them to obtain traffic from many large organizations, institutions, and even some governments that still use these expensive legacy commercial systems.

A second, less likely (update: this is seeming much more likely than we originally estimated), possibility is that they are referring to cracking commercial IPSec VPN offerings. This is probably not the case, because IPSec is a much more secure protocol which uses the same building blocks as TLS. With that said, there are still many possibilities where the NSA could have either found or coerced weaknesses into commercial hardware IPSec offerings. For example, this could include something similar to the HTTPS issue where non ephemeral key exchanges are used, using weak or broken cryptographic primitives, random number generator weaknesses where the NSA can predict the random numbers, or flaws in the IPSec implementation which could leak secret information.

A third possibility is that they are referring to network routing technologies which are sometimes referred to as VPNs and may or may not even be encrypted, such as MPLS.

We do not believe that they are referring to OpenVPN in any way, shape or form at this time based on the statements that have been made. OpenVPN relies on the same cryptographic building blocks as TLS, is built as an open source project, always uses ephemeral key exchanges, and finally, must be interoperable with all other OpenVPN protocol/versions. These 4 facts make it extremely unlikely that there is some fatal flaw in OpenVPN which makes it subjectable to decryption in a dragnet fashion by the NSA. Even Schneier agrees when he states, “Try to use public-domain encryption that has to be compatible with other implementations.”

Private Internet Access has got your back
As stated above, we have already increased our key exchange security to 2048bit preventing any sort of unknown NSA cracking ability. In addition, within a few weeks, we will be releasing a new client that will allow people to select how much security they want, both for the certificate and the key exchange, as well as the symmetric cipher security. Our default certificate will be 2048bit, but we will allow users to choose both 3072bit and 4096bit if they want to be especially cautious. We will also be adding support for something no other provider is currently offering called Elliptic Curve Cryptographic security, with both 256bit and 521bit curves. This is cutting edge cryptography that we want to make available to our users who choose to use it.

About coderrr

coderrr has been involved with network and computer related security for over a decade. Foreseeing how important security and privacy would become, coderrr co-founded Private Internet Access. In addition, he co founded Mt. Gox Live, and previously, worked with high frequency Forex and online poker. coderrr also worked on some early privacy extensions to Bitcoin.

  • Impressed

    Very informative article, and such rapid service upgrades after the latest revelations on the extent of the NSA and GCHQ’s attacks on privacy and security online!

    PIA continues to amaze me.

  • TINFOIL HAT GUY

    have to agree – this is pretty damn informative

  • Lee

    This article and the on going recent blog posts are exceptional and are another reason I love the service and the company; right alongside the swift ongoing hardware, software and implementation upgrades.
    Everyone just don’t forget to use a decent true FOSS OS with good security updates and a proper open-source OpenVPN library. I like Fedora, but almost anything is better than Windows or OS X with their inbuilt back doors… they kinda render additional security layers moot.
    As Alexander Chen said this week on Twitter, the tech security companies are running one hell of a racket… Sell locks to the public then sell keys to the government.
    As much as I actually loved Windows 7 I doubt I’ll ever use a commercial/closed source OS or program again. It’s a shame because the PIA Windows app is fantastic. Maybe time to concentrate on the Linux side to bring it to the same standard? Millions of people use Linux globally and not all are tech wizards, they have many reasons for using *nix and geekery isn’t necessarily one of them! What say you, PIA?

    • Impressed

      I believe a recent post here (or interview elsewhere with this post’s author) said work was nearly finished on bringing the Windows/OS X PIA client to Linux distributions too. Great news for us if it includes the optional security settings detailed here.

      • Daimonion

        why would you use a proprietary binary anyway, when you can use OpenVPN with GUI?

  • Curious

    “Prefer symmetric cryptography over public-key cryptography. Prefer conventional discrete-log-based systems over elliptic-curve systems; the latter have constants that the NSA influences when they can.”

    You’re implementing elliptic-curve cryptography but Bruce himself warns it’s compromised??……

  • http://www.Empower.me/ Bryan Starbuck

    “256bit and 521bit curves”. I think that was a typo. Should it be “256bit and 512bit curves”?

  • LPBak

    This is why I choose P.I.A. over others. You fully admit that weaknesses exist and I trust that our privacy is your top priority. Thank you!

  • Daimonion

    so why don’t you let people change their passwords themselves but send them via plain-text e-mail instead?

    • Ht

      A nice question, I’d like to know the answer too.

  • Anon

    PIA seems to be the leader in VPN services with many, many positive reviews.

  • http://cryptostorm.is/ ⚶ cryptostorm ⚶

    1. 1024 bit DH keys have been considered too short for real-world deployment for years… long before the latest NSA revelations. Anyone using them in production systems is either reckless, or foolish, or both.

    2. OpenVPN has no requirement that it “must be interoperable with all other OpenVPN protocol/versions” – that’s a silly statement, as OpenVPN can itself be configured to require specific cipher selection, handshake protocols, and so on… none of which will interoperate with other ovpn.exe instances unless also configured as such. Further, ovpn.exe is not universally backwards-compatible to all earlier versions of same; making this a design requirement of the codebase would simply cripple it.

    3. If you’re going to push out ECC as part of the default cipher suites (in which part of the auth protocol, specifically? Ephemeral DH? Symmetric ciphers? Public key validation?), what’s your selection criteria for curve class? Because, as we all know, the NIST standard for certain forms of “default” curve configuration are crippleware, NSA-generated. To roll out ECC without fully understanding this, and mitigating against it, is to crack wide open any resulting “crypto” deployed.

    4. If you’re distributing a closed-source OpenVPN-”based” client, and your code running server-side is obviously not subjected to independent code audit (binary or source), what does it mean to keep touting “open source” with regards to your system? How can anyone authenticate that your closed-source client binaries have anything to do with OpenVPN, let alone that they’re not backdoored? Packet capture and analysis could – eventually – uncover some such trickery, but certainly not all…

    5. Given that your Terms of Service explicitly state that you cooperate with all LEO requests – and have a NO TOLERANCE policy for all sorts of network activity by paying customers – does it matter what cipher suites you claim to be using, if your corporate policy is published to be congruent with cooperation with any request by the NSA – or any other law enforcement agency – for complete and unfettered backdoor access to all network data?

    6. What value does certificate-based, public-key cryptography add to a “consumer” VPN service in the first place? Schneier explicitly suggests minimising reliance on public key technologies unless mandatory… and there’s no mandatory use-case for it in this model. Why is it part of the model – simply because OpenVPN defaults to it?

    7. Do you enforce CBC on streaming ciphers? What streaming ciphers are your current default provisions, and what historically have been your streaming cipher selection choices? Given the deep flaws in RC4 and other default options in earlier TLS versions, have you been relying on those tools historically? Are you currently?

    8. Can you provide an example of an “open source PPTP implementation?” We’re curious…

    Cheers.

    • Brad

      Thank you so much for this comment

    • Sally_Oh

      Was this ever answered?

      • http://cryptostorm.is/ ⚶ cryptostorm ⚶

        Publicly, no.

        We did receive an email on this matter, but since it was not intended to be disclosed publicly (or doesn’t appear to be), it doesn’t feel morally right to post it – in full, or in part.

        Given that, we have to say that no public answer was provided. There is an open thread in our forum, to which anyone can post any replies they choose – no registration required. No replies from PIA or anyone claiming to represent them have been seen thus far…

        In particular, naive/default deployments of ECC – in particular, ECDHE – have been flagged by many smart folks as a terrible idea given what we now know. It’s mostly a moot point atm, as OpenVPN doesn’t actually support ECDHE in current production builds… which is a bit ironic.

        Finally, note that the 1024/2056 RSA keylength issue relates to the initial public-key handshake that underpins the identification of client & server for a given network session. It’s completely distinct from the ongoing asymmetric key exchange that happens in the control channel in order to support symmetric key “PFS” cycling in the data channel. It’s very clear that, in the original post above, the author has no understanding of these two different elements of the OpenVPN security model – he confuses the two several times, and treats them as one and the same.

        This is, in a word, frightening. Mis-specifying and/or mis-implementing these ciphers can (and often does) result in “secure” VPN services that are completely useless as protection in real-life situations. When a company doesn’t even understand the difference between entire _classes_ of encryption algorithms… well, that sort of speaks for itself. And not in a good way.

  • Daimonion

    And let us restate this again:

    This experience has taught me one very important lesson: without congressional action or a strong judicial precedent, I would _strongly_ recommend against anyone trusting their private data to a company with physical ties to the United States.

    Sincerely,
    Ladar Levison
    Owner and Operator, Lavabit LLC

    • joecairns

      I hate to be a downer, but why would you believe this is exclusive to the US? I think just about every developed country with enough budget is either developing, or executing a program similar to the NSA’s in their country.

      This problem knows no borders.

      • Daimonion

        1) There are stricter laws in many (mainly European) countries;
        2) Have you seen NSA’s officially approved budget for invigilation?
        3) The NSA can influence more major companies offering Internet services.

        EDIT: typo

      • KMagnum

        Ladar Levison’s company is widely believed to have received a very broad FISA warrant, national security letter, or some other sort of secret pseudo-warrant that he believed was illegally broad, but it’s really difficult to fight secret government orders that you could go to jail for disclosing.

        Kudos to Ladar for shutting the company down rather than playing ball with a secret pseudo-warrant.

        Other countries have programs like this, but one would hope one could run a company in a country without a parallel shadow court system. It’s the secret court system that provides an illusion of oversight that is the real sinister aspect of all of this.

  • Menachem Began

    Isn’t some of the core ECC tech patented by a company in Ottawa?

    • KMagnum

      The original ECC paper was published more than 20 years ago, so the core technology is out of patent. There are some patents on some particularly efficient curves, but those patents are disputed.

      There is a patent on serializing an ECC point by sending the x-coordinate and one bit to indicate which of the two possible y-coordinates is meant. On the other hand, the original ECC paper mentions that if you’re concerned about space, you can just drop the y-coordinate in your calculations, at the cost of one bit of security.

      A bunch of people are promoting DJB’s EC25519 work, using the prime 2**255 – 19 and discarding the y-coordinate of the point. 2 ** 255 – 19 allows for fast modular reduction, but isn’t patented, and because it drops the y-coordinate, each point takes up 255 bits on the wire.

  • south

    You say you take encryption seriously…but yet this page has mixed-mode content :-(

  • Skripka

    This series of blog entries on the NSA shens NEEDS to be more visible on the front PIA webpage. As a current customer I wanted to know what PIA knew and was doing about the NSA programs that have/are being leaked…and was stunned that there was nothing on the PIA front page about it….and that what has been said is relatively buried on the Blog page where many people both customers and not do not necessarily think to look.

    Thanks for taking the time to explain this.

  • aaomidi

    Is there any ETA for these changes?

  • yosemitesammy217

    it is extremely unlikely that the documents are referring to MPLS VPN (or L3VPN as it is sometimes referred to in network engineering contexts) when the 30 VPN types are mentioned. MPLS VPN does not have a native encryption capability.

    It is an enormous hassle to encrypt an MPLS network, and must generally be done by the customers of the MPLS VPN service, not the service provider. The best current method is to use RFC 3547 GDOI to manage the encryption key management mechanisms of IPSec (Cisco refers to this technology feature as GETVPN). There are also other IPSec-based encryption management features which can be used, but are not optimal for use with MPLS VPN services: DMVPN, P2P IPSec tunnels, etc.

    I would venture that there is not a *single* commercial service provider which natively encrypts their MPLS network links (which requires link encrypters and is prohibitively expensive), forcing on the customer to implement their own encryption, and furthermore, that the vast majority of customers of MPLS VPN services do not encrypt their data over the private MPLS VPN services they purchase from the telecom companies.