A reasonable way to do password-based encryption is:

• put the passphrase¹ and nonce in a well-parametrized memory-hard iterated hash function like Argon2, to derive a key 128-bit or larger.
• output the nonce, followed by the ciphertext per some strong authenticated encryption; AES-GCM-SIV or ChaCha20+Poly1305 comes to mind.

Legitimate decryption with the password is trivial. The best generic attack enumerates passwords from most to least common, starts to decrypt, obtains the start of the plaintext, tests it per some criteria and moves to the next password until one matches. Assume known plaintext at the start of the file².

The security depends on the good choice of password and the parametrization of the iterated hash. It's very hard to give figures, but assume 32-bit² entropy for password and a few seconds of Argon2 on one's PC. However one counts, the security in bits is far from academically acceptable levels.

Main question: Can we do better, assuming a plaintext of significant size, say $$n=2^{20}$$ or $$2^{30}$$ bits? How much better? What's the theoretical limit of the gain we can get from large $$n$$?

I'm thinking of using an all-or-nothing transform, perhaps approximated by 2 passes of AES-128 in PCBC mode, and two keys derived from the password, because we can at almost no cost. That idea is not new: ref1; ref2. But I still hope for an answer that takes into account memory-hardness.

Here is my work so far, very tentative. One can raise questions: criticize!

Taking the scheme at the start of the question as a reference method, let $$t$$ be the time (in seconds) spent in password-to-key conversion by Argon, $$m$$ the memory (in bits) used for that, $$c$$ the throughput (in bit/s) of the cipher itself, and $$\ell$$ the message length (in bits). The total time to encipher is thus about $$T=t+\ell/c$$. We do not want to wait more than that.

There is something to be gained by loading whatever of the plaintext fits in memory, and spending the time $$T=t+\min(\ell,m)/c$$ on password-to-key transformation while enciphering the plaintext at the same time in an hypothetical iterated-all-or-nothing memory-hard transform, performing the encryption for free; then using the key thus produced for the rest of the plaintext. If we assume there is at least 128-bit of entropy in the part of the plaintext that fits memory, which is a plausible assumption, good: that makes the rest essentially invulnerable until the password is found by crunching all the beginning.

Assuming our iterated-all-or-nothing memory-hard transform is as good at password-stretching as Argon2 is, I tentatively get as gain on "stretched password entropy" (or, more rigorously, for the base-2 log of the multiplicative factor for attacker cost): $$\log_2\left(1+\frac{\min(\ell,m)}{c\,t}\right)\text{ bit}$$

That's next to nothing when $$\min(\ell,m)\ll c\,t$$, and otherwise grows with $$\ell$$ until reaching a maximum at $$\ell=m$$, then stops growing.

Assuming $$t=2^2$$ (4 s), $$c=2^{32}$$ (512 MiB/s), $$m=2^{36}$$ (8 GiB), we gain ≈2.32 bit. That's much less than a decimal digit in a random passcode (≈3.32 bit), and at best in the order of a character more in a passphrase.

The faster the cipher we replace, the less gain. The more RAM, and until the plaintext does not fit, the more gain.

Unless I err, asymptotically, when we double the RAM and until all the message fits in there, we seem to quadruple rather than double a memory-bound attacker's cost. I'm still scratching my head for CPU-bound.

¹ Rather call it that: it is easy, unobtrusive, and has gone miles to improve security of PGP.

² In practice, a compressibility test will do if there is even mild redundancy in the plaintext.

³ The only power of two in [28-44].

• So the idea would be to add the work of regular decryption to the work that needs to be done by each decryption attempt? – SEJPM May 31 '20 at 13:40
• @SEJPM: If I knew, I wouldn't ask, thus I'm thinking aloud here... Stated as you do, it becomes clearer that if the AoNT/bulk encryption is sizably faster than the entropy-streching hash, we do not gain much.security. OTOH perhaps we can build a memory-hard AoNT, ... Perhaps the only interesting part of the question is: what's the theoretical limit of the gain we can get from large $n$? – fgrieu May 31 '20 at 16:29
• Personally I don't like the idea of the plaintext / ciphertext size having anything to do with the security strength of encryption / decryption. Using AONTs seem to be a move in that direction. – Maarten Bodewes May 31 '20 at 18:30
• @MaartenBodewes: Your point makes sense. But what if instead of 4s for secure key derivation plus 1s/GB, time was constant to 4s up to 2GB, then growing 1s/GB, with no loss of security? I mean, let's use all those CPU cycles doing iterative hashing for actual work. I think that at least this is achievable. My point is: how far could we get, to see if that's worth the trouble. Currently, my PoW is that password security is at best medium, and existing password security low. – fgrieu May 31 '20 at 20:29
• I agree with that, but I don't really see a generic solution to that. Passwords are fine when there are possible counter measures to be taken. But for offline encryption I'd rather use public key crypto (and that might be using a private key with a strong password). Using the same passwords for many ciphertext is even more dangerous - so at that point I'd rather use a strong password and a password manager with a single strong password. Remembering multiple passwords for offline encryption is just one big failure waiting to happen; go around! – Maarten Bodewes May 31 '20 at 21:29

An $$O(\log l)$$ cost for $$l \le m$$ seems a little simple given the many components (Argon, AES, hard & soft optimisations and bounded RAM & I/O).