ProtonMail security concerns

However, the server must store some form of the mailbox password so that the user can be authenticated. Should a security breach occur on the server, wouldn't it be just a matter of time for a determined hacker (and a powerful hacker, if, say, a government decides to be one) to figure out the real mailbox password?

Security is about trade-offs. It is sometimes said that the only secure computer is the one that is unplugged from any power source, locked in a safe, sealed in concrete, sitting at the bottom of the Mariana Trench. I would probably add that it must have no device within it capable of storing any information. Such a computer would be (relatively) secure, but it would not be very user friendly, easy to use, or particularly useful for any real-world purpose. Anything more useful than this must trade some degree of security for its usability.

Now, having said that, the question remains: can we mitigate reasonable threats? It turns out that yes, we actually can.

Modern cryptographic algorithms (primitives) are very resistant to attacks. Even SHA1, which is currently being sunset for being weaker than expected (also from Google) is still more than strong enough for most use cases; it is being sunset because it turned out to be not as strong as we believed it was for this particular specific use case. This doesn't mean SHA-1 is broken; it simply means we have reason to switch to something even stronger.

At least in the public, we currently have no idea how we would even approach attacking AES-256 (assuming it is implemented correctly) successfully, given only a ciphertext/plaintext pair (a "key recovery" or "brute force" attack). Wikipedia gives the best publicly known key recovery attack of AES-256 at 2^254.4 complexity, and even that is with ridiculous amounts of data available. That cuts the time by about one third to two thirds (2^-0.6 ~ 0.6596, 2^-1.6 ~ 0.3299; remember that on average, the work factor to break a n-bit key by brute force is 2^(n-1) because with a randomly picked key, you will on average have found it after searching half the key space, with possibilities ranging from finding it on the first try to finding it after testing every single key in the key space), which means an attack that we thought should take utterly totally completely exponentially longer than the life time of the universe now only takes utterly totally almost exponentially longer than the life time of the universe. The difference of 0.6 or even 1.6 bits of security is totally insignificant in practice, and likely overshadowed by any issues in the random-number generation in the session or persistent key generation stage. We can't even realistically count to 2^128 in a reasonable amount of time, let alone do anything useful with the counted value, and 2^256 is another 2^128 times more difficult.

Even if the entity trying to break the encryption has access to a quantum computer, Grover's algorithm only reduces the search time (in terms of elementary operations) from approximately O(2^(n-1)) to approximately O(2^(n/2)), which means that a 256-bit key gives you the same effective security against a quantum capable adversary as a 128-bit key gives you against a classical attacker. This has actually become a major argument for 256-bit keys in symmetric cryptography; against a classical attacker, for all practical purposes, as illustrated, 128 bits is enough to provide a quite good level of security, but using 256 bits of key provides a safety net should quantum computers turn out to be viable on a larger scale. (Note that this is about the symmetric cryptography, not the key exchange! Many asymmetric encryption algorithms, including RSA, would be utterly devastated by for example Shor's algorithm in the face of a viable, large-scale, general-purpose quantum computer.) This is a major driver for work towards what has been termed post-quantum cryptography.

The probability that you are using a password that provides anywhere near 256 bits of entropy is basically zero. For comparison, you'd need a 20-word properly generated Diceware passphrase to get 258 bits of entropy, corresponding to 100 rolls of a perfectly fair six-sided dice; correct horse battery staple would get you only 52 bits of entropy if it were a properly generated Diceware passphrase and not publicly known (it, and probably every permutation of it, is almost certainly in every password dictionary on the planet by now), which at a trillion guesses per second (about 2^40 guesses/second) would last 2^11 to 2^12 seconds or on the order of one hour. That is nothing more than a minor inconvenience to the attacker. However, there is nothing preventing you from using a high-entropy password. ProtonMail does not appear to impose any arbitrary restrictions on password length, so if you want to, you are free to generate and use a 20-25 word Diceware passphrase for security matching that theoretically obtainable by AES-256.

As Lucas pointed out by incorporating the XKCD comic "Security", chances are that an attacker wouldn't be attacking the cryptographic primitives; they would be going after something else. It doesn't have to involve hitting you with a wrench; it could be something as mundane as remotely breaking into your computer, or breaking into your home (perhaps to install a physical key logger, or to try to get their hands on information that will help them bypass the encryption such as unprotected copies or written-down passwords), or getting their hands on shipments to you and doing interesting things with them that you would not agree with, or remotely listening in to the emissions caused by your computer during normal operations, or compelling you to cooperate through some form of blackmail or other power posturing. Because let's make something very clear: if the government is targetting you specifically, and aren't bothered by taking actions that show this, then they will find a way to extract what they need. The saving grace in a way is that most people are not specifically targetted and/or are not worth that level of exposure, but are simply caught up in the dragnet surveillance. (Though if a government-level adversary does later realize that they are interested in you specifically, that does make it easier for them to go back and look at older communications, possibly finding something incriminating there as well. When you can't know whether or not you are being targetted or what they might have if they choose to target you later, that becomes a problem.)

There are also ways of ensuring that someone knows a password without actually having the password stored in any recoverable form. Keyed hashes (HMACs) based in part on the password, zero-knowledge proofs, or simply calculating a cryptographic hash over a given random plaintext and storing only the encrypted plaintext and hash (if the encryption key is related to the password, then the two can only be recovered as a matching pair if the password is correct), are all ways this could be accomplished.

There are ways to slow attackers down. Encryption algorithms like Blowfish accomplish this by having a complicated (and slow) key schedule, or we can use a slow-running key derivation function such as properly tuned PBKDF2, bcrypt, scrypt or others with algorithms with less complex key schedules (such as AES). The idea here is to make attacking the (relatively low-entropy) password nearly as difficult as attacking the encryption key directly, while keeping the performance penalty of the conversion from the password to the encryption key small enough to not bother a human who is using the service. If the KDF is turned all the way up to eleven, this can make attacking a reasonable-entropy password quite impractical without inconveniencing a human user very much. (You probably basically wouldn't notice a 500-1000 ms delay when logging in, but if every tried password takes half a second normally, even with highly optimized implementations or large amounts of powerful hardware this puts a major dent in how many passwords can be tried even in an offline attack in a given period of time.)

While none of this is necessarily how ProtonMail specifically have solved the problem, I hope that with the above I show that, while the problem exists in theory, it is also very much a problem that is perfectly solvable in practice. Any competently written cryptographic software is going to employ a mixture of these techniques, as well as others.

You are correct, however note that there is no indication that AES256 is cracked (and normally it won't be anytime soon either). Considering the strength of AES256 it will take several millions of years (even with quantum computer as the best known theoretical attack is Grover's quantum search algorithm. This allows us to search an unsorted database of n entries in sqrt(n) operations. In case of AES256 it becomes as strong as AES128 is now, (which is still considered strong enough)). If you want to be anonymous then use networks which mask your real origin like Tor (even though there is speculation that Tor can be bypassed if the government holds enough nodes in control).

Also don't live in a fluffy world where you think crypto can protect you if a government wants to get access to your data:

XKCD 538

You are correct in questioning the philosophy of the mailbox password, because it might actually undermine how ProtonMail manages their Public Key Infrastructure (PKI) and security model.

Yes, in this case the mailbox password = the private key, which is the single most important aspect in a PKI. In other words, they have made (intentionally or not) the private key as weak as the password the user has set during the sign up process. Furthermore, they also have made that private key available outside of the user's control or possession. To me, this increases the security risks involved.

You might ask, but is it not better than a plain private key sitting on the desktop of that user? Well, the answer is it depends. In the "user desktop" case, the private key would have to be obtained directly from that user's own computer. The attack surface would have to be a lot more specific and targeted, as the attacker needs to know a lot more about their victim. Of course, if you use VPN to access ProtonMail, then this becomes even harder for the attacker to get to your personal device or computer.

However, when that the private key resides "elsewhere", even if encrypted, and if that password is weak, the risks are exponentially higher.
Now imagine if that private key actually resides on a USB key which the user has in his own pocket? The risks are suddenly much lower.

Let's take a look at some important facts:

• Most user passwords are not strong, this is statistically proven over the last 20 years, and not just a broad or baseless claim. This does indeed increase the chances that many private keys will be made available following a dictionary attack on the encrypted private keys.
• We are not breaking AES(whatever number) through any means here, we are simply attacking the password itself through proven methods, such as dictionary attacks, or through dictionary attacks with special rules. We can guarantee that a good amount of those encrypted private keys might suddenly become plain private keys if ProtonMail handed that database over. It gives a false sense of security that they might be for-ever protected, but in reality, and I will repeat it again, they are actually as weak as the users’ mailbox passwords.

So yes, there are grave concerns about using 2 passwords (login and mailbox passwords) behind a system which is supposed to be based on a PKI infrastructure.

You can also refer to this question and keep an eye on it as well: ProtonMail: Wouldn't it be better if each user had their own private key?