Hacker News Reader

Comment by deathanatos | Hacker News Reader

But wait… if the entire key is derived from the passphrase, if two people both choose the passphrase "password", would they not then get the same public and private keys? Can I not brute force people's private keys by taking millions of common passwords¹ and generating public keys from them, and then seeing which ones match my friends?

Am I wrong? Doesn't this seem much easier to brute force than a RSA key? (Presuming the private key hasn't been compromised; if it has, it's likely protected by a password, and then these two are about equal.)

¹accepting that some will get rejected because of "uses the zxcvbn library in order to impose a strict limit on the amount of detected entropy present in entered passphrases. miniLock will not allow passphrases that fall below the threshold of 100 bits of entropy"

View on HN

Yes, and it clearly stated in the demo[1]. The key feature that this approach is trying to accomplish is allowing the user to not have to store anything beyond a password. Keeping track of a keyfile is HARD for a lay-user, so miniLock is trying to do the best it can securing files with only a password.

[1] - https://github.com/kaepora/miniLock/blob/master/src/index.ht...

Except that since there's no salt or other measures involved, there isn't even a trivial protection against rainbow tables letting me create one table and crack all the passwords. It's using ECC as a fun buzzword but tossing all the actual realworld benefits of key-pair crypto out the window by having a single user-provided string map to a single keypair.

Alright, what do you propose? As I said, dealing with keyfiles is HARD for the lay-user.

What about making the user choose two passphrases, which are concatenated together by the tool? Cracking a single passphrase may be easy, but cracking two concatenated passphrases is significantly harder.

E.g. password 1: "the quick brown fox jumps over the lazy dog"

Password 2: "jack be nimble jack be sick"

Final result, used to derive a keyfile: "the quick brown fox jumps over the lazy dogjack be nimble jack be sick"

Notice how "quick" was switched with "sick" in the last word. Now there's no pattern that can be easily cracked. If we force a user to explicitly do something like that, then this can still work.

That example was chosen intentionally to be weak. It shows that even with two relatively weak passphrases, the result is still somewhat strong. If we add extra requirements on top of that, such as forcing the user to use numbers and capitalizations, then the result should be sufficiently unique.

No, because then the person generating their table just takes that into account. It's slighly harder, but not noticeably so compared to how secure it needs to be.

It seems like as long as the complexity of the passphrase is sufficient, then a rainbow table can't be effective. For example, a 128-bit random AES key is a kind of passphrase that's generally not susceptible to a rainbow table attack (though it's very hard for humans to remember). So the problem here is, how do you force the user to make their passphrase sufficiently complex?

Passphrases also don't protect against keyloggers, which is a downside of this approach.

You force the password to be sufficiently complex by doing what you said: creating it (pseudo)randomly. The aforementioned 128 bit random AES key is robust, assuming the PRNG is solid. A user-provided password utilizing the human mind as its PRNG will never come close.

There's no difference between that and just requiring the user to use a longer password.

Anyone trying to attack the system will just program their cracker to be more likely to try concatenating words together awkwardly in the password somewhere.

It's easier for humans to remember two distinct passwords with individual complexity requirements than one gigantic passphrase.

By forcing the user to choose two passphrases which are then concatenated, the result is one gigantic passphrase that a cracker can't easily crack, yet is easy for humans to remember. It seems like this solves the problem of rainbow tables.

A keylogger could still break this system. But if an adversary has planted a keylogger, they could've simply stolen your keyfile.

I mean, you could just tell users to pick two sentences, if that's what you're after.

What makes dealing with key pairs hard for the lay user?

If the issue is "they have to transport them to use the crypto on systems other than their own": We should not be teaching lay-users (or non-lay-users) to enter passphrases or use private keys on untrusted systems.

For using multiple trusted systems, having the client software support multiple keypairs (like OpenSSH) or providing an easy way read the key off removable media (like an encrypted thumb drive) are great.

Use the tuple (email,passphrase). Still easy to remember and the email functions as a salt, and will prevent any rainbow attacks

Why not just store the salt with the data in the same file? Its not as though the program needs to maintain the files' binary compatibility with anything since the encrypted file isn't supposed to be readable by any other program other than the decryption program.

Actually, that's exactly what I proposed in my pull request[1], but it got rejected :(

[1] - https://github.com/kaepora/miniLock/pull/14

Please enlighten us on how to generate rainbow tables for passphrases. Assuming they use a lower bound of 6 bits per character, a 100 bit phrase is 46 characters long.

Off the top of my head, I'd use a book of quotations, popular lines from movies, etc. And try to hit common permutations of each. So there's a bit of low hanging fruit. But that could be detected when they generate their key.

Remember, salt doesn't really prevent anyone from using "password" or the first line of Billie Jean.

Assuming they were actually keeping the contents of such wordlists out and actually ensuring high-entropy passphrases, we would be in an OK place, though still far removed from the security provided by randomly seeded ECC keypairs.

But that's not the case:

https://github.com/dropbox/zxcvbn/issues/39

And as an attacker, I'm using my rainbow tables specifically to target the low hanging fruit. It gives me the best initial odds, and also the best return on any given hit: I'm way more likely to get more users per match for things in the common phrasebook, by nature of it being the common phrasebook.

I don't get your point with your link. It says it cannot detect certain repeated character runs, or the word "password" in Morse code.

Basically you're arguing against memorizing the key. That means users are forced to keep a file around. It ignores the many cases where you don't want to have to maintain a file.

Anyway what will be easy to remember for a human will be sequences exhibiting high ngrams correlation, which is efficiently modeled by markov chains. Wondering if studies have been done from this perspective on password strength, and how chains generated from leaked password / passphrase collections would deviate from ones generated from common language.

>Assuming they were actually keeping the contents of such wordlists out and actually ensuring high-entropy passphrases, we would be in an OK place, though still far removed from the security provided by randomly seeded ECC keypairs.

I'm fairly skeptical of the ability of software to "ensure high-entropy passphrases". I don't think it's trivial to anticipate the entropy-lowering strategies that people will come up with in order to help them remember their passwords.

That's my point.

> Please enlighten us on how to generate rainbow tables for passphrases.

Pick P, the set of passwords, to be something like "4-6 dictionary words appended". Pick R, the reduction function, such that it maps from a hash to a random value in P.

How about my proposed salting change? This would thwart a one-table attack.

https://github.com/kaepora/miniLock/pull/14

Reply on news.ycombinator.com