My bad, it's n^s instead of s^n. I don't know where the factorial is coming from in your analysis. Or how it magically disappeared
at the end of your comment.

You have a space of `m' accounts, `n' common passwords and `s' threshold.
The first step is to find a subset of `s' people who all have easy passwords. There is no better
way than to pick all such subsets, so that gives binom(m,s).
For such a subset, you have to try all assignments of passwords. You have s
people, each of which can have one of n passwords. That's s^n tries.
The total time is binom(m,s) * s^n * C, where C is the time it takes to test if your guess is correct.

The latter is not feasible, because you don't need to guess passwords, you need to guess user-password pairs.

Yes, you could. This doesn't have any better security guarantees than just doing that.

His whole argument however is that the salt needs to be reentered in the memory manually
after a system crash, whereas with his mechanism the memory gets the needed data automatically
after a few users login.

Yes, it does make it more secure. The security of the hash files relies on a secret stored in memory. To
get that secret, you either need to know the password of K users (user i has password p_i) or you need
access to memory. The point is that access to disk is not sufficient (regardless of how weak the passwords
of the users are).

Plus, for most websites, you can just register 10 accounts, giving you the 10 known passwords.

In any case, the treat model is that you can access all the data in the db, but not all the data in memory (as
is the case with SQL injection and most other attacks). The
memory is used to cache the first n-1 passwords. The n-th guy needs to wait only after the system crashes
and the cache data is lost.

But in such a treat model, the problem can be solved in a way simpler fashion: just store in memory a key
with which all the hashes are encrypted. Write the key down on a piece of paper. If the machine crashes,
just reload the key from the paper into the server's ram.

And this is the only threat model you can work on anyway: if you assume the attacker gets root,
then there's obviously not much security to preserve. This is why authentication should be interactive (
EKE protocols).

Can you detail how can this support any of the features of a relational database? Filtering rows, joining tables, aggregation, ordering.

To clarify all misconceptions in other posts, having been to a talk of hers a few days ago, here's the encryption types involved:
    * RND (salted symmetric key encryption) - used for columns where no sql manipulation is needed
    * DET (unsalted symmetric key encryption) - used for columns that need to be looked up by equality
    * Partially homomorphic encryption - used for aggregation such as SUM()
    * Order preserving encryption - useful for inequality where clauses, indexes, aggregations such as MIN()
    * Searchable encryption - allows something like ILIKE on text columns

OPE is the most dangerous, but is rarely needed for the most sensitive fields. They've run CryptDB on top of phpBB and
some other thngs with acceptable overhead. Let me know if you have other questions.

Well, other sources do not typically threaten to send you to a special place to burn forever.

The ability to evolve of the ability to evolve may actually evolve.

I wasn't aware TLS-SRP patched browsers exist. In any case, these mechanisms will likely be adopted only if they can be embedded in HTML. Few designers are going to sacrifice their fancy login form for that ugly-ass browser window that asks for credentials. But allowing proper authentication in HTML forms would imply that you get all or nothing. Either all HTML forms that contain an input type="password" must use TLS-SRP for sending the credentials, or this cannot be adopted. Otherwise a MITM would simply alter the form to switch from secure authentication to plaintext authentication.

To the best of my knowledge , HSTS is merely the Strict-Transport-Security response header. The lists are just something
extra. The "not very useful" comes from the fact that you are still unprotected the first time you access the website. If the
attacker is present the first time you visit an website, he can remove that header via MITM. Otherwise you should be fine.

No, I meant what I said. "https.example.com" is an example of a host supporting HTTPS, yet the browser accesses
it by default as "http://https.example.com". You don't seem to have understood what I said at all.

Because of the lack of widely adopted HTTPS, browsers are default-HTTP. So if you type https.example.com in your browser,
it will first try to access it by HTTP. Sure, the host is sometimes nice enough to redirect you immediately to HTTPS. But the
redirection happens over HTTP (because that's how you accessed the website). Therefore, a MITM can easily prevent such a
redirect and keep you in the HTTP land (see sslstrip tool), where attacks are a child's play. So unless your victims are paranoid enough to
check the address bar to make sure "https" appears, or manually write https:/// in front of their links, or use an addon such as "HTTPS Everywhere", then providing HTTPS doesn't matter much.
What addons like HTTPS Everywhere do is they have a huge lists of websites known to support HTTPS, and they force the browser to go default-https instead.

In my opinion, good solutions would include:
a) make HTTPS-everywhere part of the browsers;
b) add some proper authentication and encryption in HTTP2.0 instead of bitching that it's the wrong layer. it's clear no-one is going to adopt HTTPS
        widely anytime soon; most websites require you to login, meaning you can perform encrypted key exchange (EKE) with them, which allows for two-way authentication, plus encryption optionally;
c) widely adoption of something like this: https://en.wikipedia.org/wiki/HTTP_Strict_Transport_Security - not very useful, but still an improvement

As you said, it is the all-or-nothing that concerns me. I am not claiming that sandboxing
would magically solve all problems and that successful exploits would never be able to do
any harm. But being able to mount an attack such as "someone using MS Office somewhere might use it
to open sensible data, which we can steal" is not the same as mounting an attack like "we can use MS Office
to collect all stored passwords from all browsers and send them to us. And to spawn a keylogger". The MS Office
should have no business accessing the sensible data of other applications or their memory space for that matter.
I don't believe that the fact that Windows allows everything to stick its head where it does not belong is really an unsolvable problem.