Servers overhauled, Italy is back!
October 27, 2014
Germany going offline
October 30, 2014
Show all

Reports on Slowdowns on Encryption Upgrade

Since our upgrade to AES256 for the data channel (previously AES128) and SHA2-512bit (from SHA1-160 bit) for the HMAC authentication channel, we’ve been receiving reports on slowdowns especially for those using routers/integrated devices whereby CPU processing power is limited.

We had previously decided on this upgrade because of numerous complaints and several review sites marking us down for using AES128 only when the competition is using AES256. We have previously expressed that AES128 in many cases is just as good as AES256 and in certain cases better since AES128 implements a better key schedule. It is an opinion we still hold today and our opinion is that for the average VPN user, AES128 is pretty good.

However, after implementing AES256, our servers do not show any additional CPU impact and are therefore investigating the reports on slowdowns. It is also possible that the SHA-512 upgrade to the HMAC is causing the slowdown, however, SHA-1 is already considered insecure as it is vulnerable to collision attacks and therefore we believe it is prudent to upgrade this despite the performance hit.

Therefore, in light of this, before we decide on what to do, we would wish to monitor the situation for the next few days. If the speed issues persist and cannot be attributed to other causes we would be doing the following:

  • Announcing our decision via this blog, Facebook and an e-mail to all current users giving at least two days notice.
  • Moving back from AES256 to AES128 for the data channel for all configurations except xCloak configurations which will maintain AES256.
  • Maintaining SHA-512 for added security on the HMAC authentication channel despite the performance hits. It is noted that SHA-256 in many cases is slower than SHA-512 especially on modern PCs. This however still will have an impact on weaker routers.

The alternative would be to segregate high security servers and keep them as xCloaks with the highest protection while keeping the weaker SHA-1 for regular servers for maximum performance. The problem with this is that for most people it will reduce security and introduce inequal distribution of users. We probably would see heavily underutilized high security servers.

Feedback is greatly appreciated and thank you for your patience and understanding as we move to improve our service and achieve a balance between performance and security. Please note that comments especially for first time posters may take time to be moderated as they will need to be processed manually.

0 Comments

  1. Indingo says:

    Hello BolehVPN.

    (SHA-512) is first of all, a great upgrade and one you must keep for sure, even Google is suggesting people more away from the weaker (SHA1-160). I think with the cipher that 128bit vs 256bit AES are reasonably comparable. I mentioned in the other post about how its not going to be the key size that is broken but the cipher itself, which I believe to be truth. I for one am fine with AES 256 and AES 128, both are good and if your not noticing any impact on your servers then that is great. I personally notice a %10 speed drop on a WiFi connection through walls, but for the most part 10% drop on WiFi is to be expected. I honestly prefer myself AES 256bit just for pure paranoia’s sake. I do hope you do not fall into the trap of review sites however, if you change the way you run BolehVPN because of peer pressure from an outside entity saying your not good enough, then that’s no good. Be proud of not caving in to review sites, look at them…. look at them all…. 1’st 2’nd and 3’rd place are always given to less deserving and quite frankly terrible services from a privacy standpoint, and why? because they pay ransom to those same review websites to get a better score. Don’t let them get the better of you, I spread your company around via word of mouth and so many others do too because of your superior service and commitment to privacy and your users. I guess what I’m saying is, don’t let the review sites take away your integrity for a higher score, we like you just the way you are , and for the record I’m fine with either 128bit or 256bit AES but prefer 256bit purely for theoretical security benefits larger key sizes have. 🙂

  2. krasnal says:

    Good write up. I’m using a router and will run some tests to see how things are performing. A nice juicy torrent should be able to max things out.

    FYI, you might not see any extra CPU use at the server end because many modern processors (and probably all server grade CPUs) have a dedicated AES instruction set that minimises the computational impact of AES.

    Also, your observation doesn’t necessarily mean that those using less powerful CPUs, eg routers, will be unaffected by the change. We are likely to be only a smal subset of your user base, so you’re unlikely to notice the small drop in data *throughput*.

  3. krasnal says:

    Just a quick update on my test torrent (Linux Mint, BTW)

    Previously, I’d have expected to see around 800-900 KiB/sec on a maxed-out torrent. I’m now seeing closer to 650 KiB/sec. Router CPU (on an Asus RT-N16) is running around 95%.

    So, yes, throughput is down, in my case somewhere between 20-30% less.

    My take on Reuben’s dilemma:

    1. Router-based VPN users and those with integrated devices are likely to be affected, though the effect will vary depending on the power of the CPU. While I suspect we are only a small subset of Boleh’s customer base, I’m only guessing. Perhaps Reuben has a better idea.
    2. For most people on a normal PC, the CPU should have more than enough spare capacity to perform the extra work with no noticeable effect on data throughput.
    3. I really doubt the NSA are going to waste energy trying to decrypt any of our traffic, whether it’s 128-bit or 256-bit encrypted. Even if they do find the key, it’s good only for one hour’s data. (So one possible enhancement could be to get a new key every 30 minutes.)
    4. My main reason for using a VPN is that I feel that it’s none of “their” damn business what I do on the internet. The VPN effectively stops “them” from seeing – and recording – what I do unless “they” put considerable effort into overcoming the VPN. That’s good enough for me.
    5. Regarding the move to SHA512, is the threat of SHA-1 hash clashes realistic in the real world — and in real time? If we come across such an adversary, it’s probably time to head for the hills! 😉

    In the end, Reuben has to decide whether the extra security and marketing kudos of the upgrade are worth the slight, but measurable, degradation of service to an unknown percentage of his user base. The rest of the user base should be largely unaffected.

    • Reuben says:

      Yes the SHA-1 risk is a risk. In fact, the performance hit is probably due to SHA-512 being implemented as opposed to AES256. This literally kills a Raspberry Pi device.

      I loathe to go through the hundreds of tickets again if we are to change the AES256 to 128 bit and security and speed wise there isn’t a big hit. We have also received e-mails asking us to keep to AES-256.

      Another way to get around this is to have a handful of servers with a lower security setting but this confuses things for many users. But perhaps for the surfing streaming servers where security isn’t so big, the SHA-1 can be kept with AES-128 though it limits the usefulness as you can’t do torrenting through it. We could probably have a single server for DD-WRT use but I’m not sure if DD-WRT users would be happy with the limit of choice.

      More feedback needs to be sought still.

  4. Indingo says:

    @krasnal

    Threat of (SHA1-160) being weaker then (SHA-512) is very real, Google is even starting to enforce the phase out of the less secure (SHA1-160), and encouraging websites with HTTPS onto more secure hashes. I think what is done is done, and honestly reverting the changes now will just confuse and annoy people who have updated their configs and DDWRT for the new configs. (SHA-512) has to stay for the reasons mentioned and since 256bit AES is already up now and working for most, I think it should probably stay, most other VPN services are using 256bit AES anyway, and BolehVPN may as well be one of them, I am a big fan of Blowfish which was BolehVPN’s original cipher. I’m cool with whatever they choose though.

    (Reference for Google and SHA)
    ( http://googleonlinesecurity.blogspot.com/2014/09/gradually-sunsetting-sha-1.html )

  5. krasnal says:

    @indigo

    I’m not suggestion that BolehVPN reverts to using AES-128.

    However, I think there might be some confusion on the HMAC hashing with regard to which is an appropriate hash (ie message digest) function – although I’m quite prepared to admit that perhaps the confusion lies with me.

    Everyone agrees that SHA-1-160 is unfit for signing SSL *certificates* because of the possibility of so-called hash collisions – and that’s the gist of the article you linked to. That’s because, with sufficient computing power being available, usind SHA-1 can potentially allow an SSL certificate to be forged. But any such forgery will probably require a bit of time and computing power before a forged certificate could be produced. That is to say, it’s going to be an offline attack, not something that needs to be performed in real time.

    But here we’re not dealing with SSL certificates. My understanding (and I’m quite happy to be corrected) is that we are talking about a function used to hash each and every packet of data that passes through the VPN “pipe”. It is designed to prevent active attacks in real time whereby the already encrypted data is somehow modified by a man-in-the-middle. HMAC offers no benefit to us *at all* if we are simply worried about someone snooping on the VPN data stream. See https://www.privateinternetaccess.com/pages/vpn-encryption for further information.

    So, my question is: why are we adding a large processing overhead that protects us only from hypothetical *active attacks* when we’re already protected? While the SHA-1 function is no longer suited to the task of signing SSL certificates, I’m still not persuaded that it’s no longer suited to the task of hashing each and every data block that passes through the VPN. I contend that SHA512 is simply overkill for the very slight risk of an active attack, when SHA-1 should suffice (or SHA256 for the super paranoid).

    Like I said at the beginning, perhaps I’m just confused by all this techie stuff. I’m still open to persuasion.

  6. krasnal says:

    See also Bruce Schneier’s blog for details of the *cough* “ease” of finding SHA-1 hash collisions.

    Bottom line: not in a month of Sundays and absolutely not in real time.

    https://www.schneier.com/blog/archives/2012/10/when_will_we_se.html

  7. krasnal says:

    At the risk of belabouring the point, also from Bruce Schneier’s blog:

    https://www.schneier.com/blog/archives/2005/02/sha1_broken.html

    Quotes from the blog entry and comments:
    “it doesn’t affect applications such as HMAC where collisions aren’t important”
    “With a digital signature all you have to do is find another blob of data which hashes to the same hash. You are free to choose any blob of data. With HMAC you are not free to choose any other blob of data because a secret key is always added to the data before it is hashed and you don’t know that secret key. So you still need to guess the key or the person verifying the HMAC will get a different hash than you.”
    “HMAC is harder to attack because the attacker doesn’t know the internal values of the hash function when she’s choosing her message blocks. To the extent that she needs to know what some bits of the hash chaining value are to choose the next message bit, her attack is blocked.”

    So, the already minuscule risk of hash collisions is further reduced (or eliminated) by there being a secret key added to the data before each block is hashed. And none of this is possible in real time, anyway.

  8. Luce says:

    I am of the opinion that the recent security upgrade was prudent and should be maintained. If security is to be rolled back on servers it should probably be on those that are designated as surfing/streaming. They are not likely to be utilized for things under scrutiny, like P2P and so on. My desktop, laptop and mobile device all handle the upgrade without any noticeable change in speed. If the previous encryption and hash were remotely vulnerable you can be assured the rest of the world will migrate away from it as well. This will force those having speed issues due to hardware to find a way of dealing with it eventually anyway.

  9. Indingo says:

    @krasnal

    Yes, you are pretty much right that its a different implementation in BolehVPN then would be in a SSL certificate, I was just using it as an example of the gradual phase out of (SHA1-160). I guess for me noting multiple other bigger companies and services moving away from (SHA1-160) is a sign of the times and that its probably prudent to move away from it too, even if for BolehVPN’s implementation its only theoretical active attacks you need to worry about. I guess to lean on the side of caution is wise in this industry. I do however not see any problem with it being used on the surf-streaming servers due to them being only used for video streaming. 🙂

  10. krasnal says:

    @indigo.

    The industry is moving away from SHA-1 only for SSL certificates.

    Bruce Schnier says that SHA-1 is not broken for HMAC, which is the subject under discussion. OpenVPN still uses SHA-1-160 as its default HMAC – and they should know what they’re talking about.

    I can find no discussion on the Internet suggesting (based on sound technical reasoning) that SHA-1 is no longer fit for HMAC – andI I challenge anyone else to find one.

    We should keep SHA-1 for HMAC unless anyone can come up with a strong, fact-based argument for moving to something stronger. Links to the technical details should be provided.

    • Reuben says:

      The question I suppose is that given that there is vulnerability within SHA-1 and although there isn’t a known way to break it just yet within HMAC, should we still use SHA-1? We really don’t know what kind of capabilities other people have and the best we can do is that there’s an indication of some vulnerability, to simply not use it anymore.

      Our business of being a VPN provider in a way is also based on a lot of distrust on the authorities and some degree of paranoia.

      Schneier didn’t elaborate much in his further post https://www.schneier.com/blog/archives/2005/02/cryptanalysis_o.html but you are correct that the collision attack is harder to use in HMAC because it requires a use of a further secret key. But VPNs and its architecture is all about redundancy. Why do you think we have so many layers of encryption for a VPN? 😀 If one layer is broken, there are still further layers to break and this is the beauty of it. Now knowing that one layer is potentially weak, are we going to be lazy and say oh it’s ok, the other layers would protect it?

      As mentioned, those who break encryption especially Governments would not publish their methods or let people know of their capabilities. What if more of the functions that we use are also broken? It just makes sense to not use proven bad methods to reduce the chances of crap happening.

      Note that unlike AES128 and AES256 which there are no successful theoretical attacks, just successful ones against handicapped versions of it, it’s different than SHA-1 in which a full version of SHA-1 is broken.

      There’s an excellent discussion on SHA-1 and its use in HMAC here:
      http://stackoverflow.com/questions/2889473/when-is-it-safe-to-use-a-broken-hash-function

      “So, while collisions do not per se imply weaknesses on HMAC, they are bad news. In practice, collisions are a problem for very few setups. But knowing whether collisions impact a given usage of hash functions is tricky enough, that it is quite unwise to keep on using a hash function for which collisions were demonstrated.”

  11. krasnal says:

    @Reuben.

    Yes, a well-informed technical discussion. (I note that it doesn’t say that SHA-1 is broken for HMAC.)

    There’s talk about whether you need 2^69 or 2^61 iterations to produce a hash collision on vanilla SHA-1 and discussion of the *theoretical* limitations of using MD4 for HMAC – though it’s pointed out that nobody has succeeded (as far as we know) in breaking even MD4 with HMAC. But 2^69 or 2^61 computations are both HUGE numbers that require serious computing power and lots of time. At the risk of sounding like a stuck record, HMAC is designed to stop real-time tampering of in-transit packets – and HMAC has the secret key so hash collisions are therefore not really an issue.

    As one of the commenters noted: “The answer entirely depends on what you’re using it for. If you need to prevent somebody producing a collision with a few milliseconds I’d be less worried than if you need to prevent somebody producing a collision within a few decades.” We’re most certainly in the milliseconds camp with OpenVPN and HMAC. Quite simply, nobody is going to be able to be to calculate a hash collision of each VPN data packet in near real time – and that’s before we take account of the HMAC secret key.

    I’m still not convinced by the argument that we might as well do it because “SHA-1 is known to be broken” (it isn’t), so it’s just being prudent to upgrade to something stronger. I don’t have five locks on my front door for a reason, even though there’s a theroretical possibility that one (or two) might be picked by a professional thief. The fundamental problem with moving to SHA512 for HMAC is cost.

    I checked for myself the costs of each SHA algorith and whether SHA512 is actually faster than SHA256 – which turn out to be true, but only on 64-bit Intel processors. Put the same comparison test onto a 32-bit Intel processor (an Intel Atom) and the result is horrendous. Hers is the CPU use on two Ubuntu 12.04 systems, one with a 64-bit i3 processor and the other with a 32-bit Atom processor. The file was 1.3 GB in size. Times are an average of 3 runs.

    64-bit i3 processor
    SHA-1 5.63 secs
    SHA256 10.65 secs
    SHA512 7.50 secs

    32-bit Atom processor
    SHA-1 19.39 secs
    SHA256 37.07 secs
    SHA512 267.12 secs

    Yes, that really is 267 seconds of CPU time on the 32-bit processor. That’s 13 times longer than SHA-1. The result was so bad that I ran the same test on a 32-bit Pentium 4 processor running Linux Mint. It was a bit better but SHA512 still took 8 times more CPU than SHA-1 (and SHA256 only 20% longer, which was a surprise).

    So, while SHA512 has a small performance benefit over SHA256 on a 64-bit processor, it absolutely murders performance on both of my 32-bit processors. And you’ve already said that SHA512 brings a Raspberry pi to its knees.

    I still stay stick with SHA-1 for HMAC until OpenVPN advises us to move off it. Moving to SHA-2 is IMO currently unnecessary and SHA512 has severe performance penalties for 32-bit users, routers end other embedded systems. But if you really, really feel that you must, for whatever reason, abandon SHA-1, then SHA256 has to be the better choice than SHA512.

    That’s about it from me. You know my position and I’ve provided you with a lot of hard facts, including running my own performance tests, to support my case. Over to you, my good man.

  12. Indingo says:

    “I don’t have five locks on my front door for a reason, even though there’s a theroretical possibility that one (or two) might be picked by a professional thief.”

    I think the problem is less about your front door having the adequate amount of locks, and more about making sure we don’t forget to lock the windows as well. Sometimes we overlook or don’t think about a perceived threat simply because it does not come to mind, it does not mean one does not exist.

  13. krasnal says:

    @indigo

    The analogy is meant to illustrate the importance of a good engineering principe – cost versus utility. I could have said that we don’t over-engineer bridges so that they’re ten times stronger than they need to be, since it’s a waste of money. It’s all about cost versus utility (ie usefulness).

    You’re absolutel right about back doors and windows, which is why this whole HMAC business is IMO a distraction from where a real attack would occur. A “real” adversary would most likely exploit, for example, a weakness in the Diffie Hellman key exchange mechanism or use obscure weaknesses in random numbergenerators. Hence, I’m simply not persuaded that the reduced bandwidth I will experience (the cost) is worth the usefulness of the (questionable) extra protection SHA512 confers.

    As for BolehVPN’s key-exchange key length, my router log lists it as being: “Control Channel: TLSv1, cipher TLSv1/SSLv3 DHE-RSA-AES256-SHA, 1024 bit RSA” which I take to mean that is has an RSA key length of 1024 bits. A quick search came up with this item: https://security.stackexchange.com/questions/5487/is-1024bit-diffie-hellman-key-exchange-secure

    Quote: “As a baseline, they about all agree that 1024-bit DH is close, in security, to what a 77 to 80-bit symmetric key offers. Note that a 64-bit symmetric key was broken in 2002, and 77-bit is “only” 8192 times more difficult.

    Since the best known discrete logarithm attack (IC with GNFS) has many common parts with the best known factorization algorithm (GNFS), DH with a k-bit modulus should be roughly equivalent to a RSA key with a k-bit modulus. So you should use 2048 bits for DH too.

    In your list, “AES-256” is overkill (AES-128 would still be “more secure” than 2048-bit RSA or DH), but mostly harmless overkill (AES-256 is only 40% slower than AES-128).”

    So, if I read this correctly, our 1024-bit key-exchange RSA/DH key is significantly less secure than AES-128. Looks like it could be our equivalent of a poorly secured side window. Reuben?

  14. Jordan Kratz (AKA gorehound) says:

    Hello Guys:
    I have been having a lot of issues since this Morning.Many servers either will not connect or if they do you can not browse the Internet.Now I know the reason why.And I have tried to update this with same issues.
    If this still persists then tomorrow I will have to either contact you or post in the forums.

  15. Alex says:

    I’m having a lot of slowness as well. I’m using the proxied connections and I didn’t see these addressed. These should be set to lowest grade encryption imho.

Leave a Reply

Your email address will not be published. Required fields are marked *