How to choose a VPN service

Someone asked me to recommend a VPN service. Since I’m a security professional, I’m supposed to know how to evaluate things like that. But that question makes me very uncomfortable, for reasons I’ll explain in a bit. I’d rather tell you what to look for so you can choose one. So here’s how to choose a VPN service.

There are three things I want to know about any VPN provider: How do they encrypt, what countries do they operate in, and do they log?

How does the VPN service encrypt?

First and foremost, there’s the question of how the VPN service encrypts. This is fundamental but it’s easy to mess up, so that’s why I discuss this first in regards to how to choose a VPN service.

Two showstopper phrases to run away from are proprietary encryption and military grade encryption. You need specifics. Now, I’m guilty of explaining good enough encryption as military grade, but I’ll still give you specifics of what that means.

The VPN provider I use has AES 256-bit encryption with SHA-512 authentication and an RSA 4096-bit key. If those three things mean something to you, you might be a CISSP. Then again, I’ve seen CISSPs get this wrong. So let’s step through it.

In encryption, more bits is better. What we have here is two forms of encryption and a digital signature. If you want a TLDR, AES-256, SHA-512 and RSA-4096 is a good combination. You can halve all of those and it will still be acceptable, but why do that if someone is offering to max them out? Deviations from that formula are a sign of someone who doesn’t know what they’re doing.

AES

AES is the gold standard for encryption. While there are rumors that certain state actors can crack AES, they’re just that, rumors. When properly implemented, AES cannot be cracked in a reasonable length of time. There is a roughly equivalent encryption scheme called Rijndael, which became AES. AES has slightly tighter specifications. I once took a vendor to task for telling me their encryption was, “Rijndael, it’s like AES.” Rijndael is much harder to pronounce and understand, and if you’re not going to follow the AES specifications, you need to have a good reason for it and be ready to defend it.

At this point there’s not really any reason to settle for less than 256-bit encryption.

If you don’t trust AES because it was originally designed for the United States government, there were other candidates besides Rijndael. They were called MARS, RC6, Serpent, and Twofish. Theoretically they’d be OK to use, but Rijndael won largely because of its efficiency, and AES is better tested. I’ve had these conversations with other security professionals about whether to trust AES and what to use instead, and I’ve argued both sides, but, frankly, I’m not qualified to choose something better than AES. Neither is anyone else I know. Since people who actually understand the math and specialize in cryptography recommend AES, I’ll defer to their judgment just like they defer to my judgment on my specialty, vulnerability management.

SHA

SHA isn’t encryption, it’s a digital signature. More bits is better, since it increases the possibility of every signature being unique. As of this writing in the summer of 2021, SHA 512, or more properly, SHA3-512, is the maximum bit size for SHA. According to NIST Special Publication 800-57, which is the document I always refer to when evaluating encryption, SHA-512 is equivalent in security to AES-256. Using less than SHA-512 introduces a weak point in your crypto.

RSA

RSA is an asymmetric encryption algorithm. It needs a much larger bit size to keep up with 256-bit AES and 512-bit SHA. RSA’s job in this application is to generate a secure key to feed into AES. The minimum acceptable number in this case is 2,048, according to NIST Special Publication 800-57. But 2,048-bit RSA is only equivalent to 128-bit AES. So 4,096-bit RSA is a better match for 256-bit AES and SHA-512.

The problem with the encryption the Germans used in World War II (the Enigma machine shown above) was because they got lazy with their keys. That was what permitted the Allies to bruteforce their encryption with 1939 technology. It’s possible to bruteforce the combination of AES-256/SHA-512/RSA-4096 when properly implemented, but the statute of limitations for high crimes and misdemeanors like watching Seinfeld on Netflix from another country will be over by the time they crack it. If you’re doing something there is no statute of limitations on, you deserve what you get.

Why to avoid proprietary encryption

Proprietary encryption is a showstopper. Never, ever, ever roll with someone’s proprietary encryption. Theoretically, someone good at math can come up with an encryption scheme. But if the 1990s taught us anything, it’s that it’s very easy to make mistakes in your encryption that cause the wheels to fall off. If you’re the type who trusts an Intel or AMD CPU more than you trust a CPU designed by my buddy Bob in his basement, then don’t trust an encryption algorithm designed by my buddy Bob in his basement either.

Use a time tested encryption algorithm with secure keys. That’s how governments protect their top secret information, so that’s how you should protect yourself too.

The problem with “military grade encryption”

NIST 800-57 defines military grade encryption. There are multiple grades. Any time someone throws those three words as me, I ask which grade. Because there’s crypto that’s acceptable for unclassified information but I wouldn’t use that to encrypt the details of the delivery I got yesterday.

As of this writing, AES-256/SHA-512/RSA-4096 is good enough to protect classified information. If you describe that as military grade encryption in a vendor pitch or a job interview, I won’t end the discussion and have you escorted out of the building. But I probably will politely ask you not to patronize me.

What countries do they operate in?

Ideally you want a VPN operator headquartered in a country you trust other than your own, with servers in countries you trust other than your own. Pick a VPN provider headquartered in a country you trust, with servers in another country you trust.

Telling you who I trust isn’t helpful, so instead, I’ll give you a thought exercise. If you woke up in North Korea against your will, whose embassy would you go to for help if yours wasn’t an option, or your country doesn’t have one?

Sweden, Norway, and Switzerland are popular choices. But if there are different countries on your short list, use one of those. I’m here to give security advice, not to impose my values on you.

Do they log?

The last important question is whether the VPN provider logs. This question is also why I’m reluctant to just name a specific provider. If a VPN provider doesn’t claim not to log, keep looking. If they do claim not to log, I might believe them.

Not logging is important, because someone can’t subpoena information that doesn’t exist. You can subpoena me all you want for information about 3M Corporation. All I can give you is my hardware store receipts.

I’ve administered log servers in the past, so I can say from experience that logging your activity takes some doing. It’s much cheaper and easier not to log anything. But the value of the information a VPN provider could snarf up is extremely high, so the temptation would be there. And unfortunately, it’s easier for me to know if my local police department is listening to my phone calls than it is to know if my VPN provider is logging me.

Since I can’t answer this question with certainty, I tend to change VPN providers from time to time just to spread out my risk.

How to choose a VPN service: In conclusion

I can’t say which of these three things is more important, because they’re all important. And unfortunately one of the questions is almost impossible to answer. So you have to compensate for the last point.

But that’s a security professional’s take on how to choose a VPN service. It’s not the most straightforward question, but showing how I think through the question is important in a case where there isn’t a clear-cut answer.