[tveita]

So when you say "if k is 256 random bytes" it's a flat out lie?

e: if k really was 256 random bytes, or bits even, it would mostly be an unnecessary complication. But that's a completely opposite situation from a key derived from a user chosen password.

[maxtaco]

It was a thought experiment to encourage people to think about the issue at hand and not dismiss it with a knee-jerk. Your concern is now key stretching and password selection.

[tveita]

Well, no, my concern is still to tell people to stay away from Keybase.io, or if they have to use it, to not upload their private key even though it seems to encourage you to, or if they have to upload their key, to use a really strong password and not use the key for anything else. In that order.

I think that asking people for their private key is a bad thing that bad sites do.

A password derived key isn't random, and no amount of key stretching or pretending will change that.

[maxtaco]

Many Random Oracle crypto proofs assume a value is random and then substitute in something that's not quite so good, so I think it's a valid thought experiment. And some passwords do have 256 bits of randomness (i.e., ~15 random words from the dictionary). I think we disagree on what margin of password security we feel comfortable with.

[tveita]

Right, in random oracle proofs you assume that values are random, and then you replace them with something that no one can distinguish from random.

Then you consider it broken when someone finds a distinguisher requiring three exabytes of output, because any distinguishable non-randomness breaks the proof.

It's trivial to make a distinguisher for user passwords. Just guess "password".

There's an inherent difference between random keys and chosen passwords. Random keys, used correctly, are secure. Passwords just give you a chance to provide your own security, and most people fail to do so. No one are picking 15 random words from a dictionary to make their passwords.

Passwords are one of the weakest links in IT security, on par with the people, and I don't think making them more of a single point of failure is the way to better security. That's what widespread 2-factor authentication was getting us away from.

Have you tried cracking uploaded keys to check the strength of the passwords?

[maxtaco]

We hope to roll out 2FA shortly. If enabled, you'll need to present a token before retrieving your encrypted private key from the server. Though of course it won't help if our server is hacked or subpoenaed.

We haven't tried cracking uploaded keys. It's a good idea, but expensive, we could be using those cycles to mine litecoins instead!

Thanks for your feedback, we appreciate it.