Zero Knowledge Proofs

[ramriot]

Hi Egor, Been seeing a few issues posted here that parallel one concern I was putting into my general analysis, so I thought it better to post it here for clarification rather than leave it until later.

It appears from reading through the code (there really should be a written spec) that the SecureLogin authentication scheme uses an Ed25519 asymmetric key pair to perform a Zero Knowledge authentication by deed of signing a random challenge. It does this by having a user generate a single authentication key pair for all sites via a deterministic hash function that takes as input a provided email address and passphrase. This hash is then used as the feed to generate signing keys for a given challenge.

Issue 1 Having only deterministic inputs to generate signing keys degrades them for their use in Zero Knowledge Proof (ZKP). This is because the root of ZKP is that given perfect knowledge of everything that passes it should be infeasible for an attacker to generate their own proof to any given random challenge.

But, in SecureLogin the 'email' parameter & public key is passed for storage on the server side leaving only the passphrase as an unknown. This reduces the entropy of generated keys to that of the passphrase and thus leaks knowledge of that in the reverse direction making the protocol no longer a ZKP. The task then of finding the private key from captured/exfiltrated data is one of guessing passwords and running the known key generation algorithm to produce public keys for comparison.

This then makes SecureLogin potentially as weak as any traditional stored password hash systems that uses an equivalently strong salted password key derivation function.

Solution It is my belief that signing keys must be generated from an entropy source of equivalent or better strength to the keys being generated. That unfortunately precludes direct password to key generation but does allow randomly generated keys to be encrypted and stored local to the client under a reproducible static key or secured in dedicated hardware where only the results of an inputted signing operation can be accessed.

Other issues will be posted separately

[homakov]

This concern is the same of https://github.com/sakurity/securelogin/issues/25 and few others.

Each way has pros and cons like tabs vs spaces.

This then makes SecureLogin potentially as weak as any traditional stored password hash systems that uses an equivalently strong salted password key derivation function

No, because hashing scheme is different. Current derivation is strong and will only get stronger with more effective implementations.

Randomly generated keys are not an option because of decentralization and scalability principles. Who's going to store the backups? Dropbox? Who's going to store the backups for 3B people? I guess Dropbox doesn't sound good anymore. There's no single authority that can be trusted with root keys of all people on the planet. There's no "backup strategy" that will prevent a natural disaster destroying it all.

Blockchain could, but then it would make encrypted material essentially public again.

We use weak entropy (email and pw) but we apply very strong derivation to it to make it infeasible (to my best knowledge) to bruteforce. That's the idea. We will never rely on 3rd party servers to store our encrypted data. Only memorable passwords must be enough to reconstruct the key.

[ramriot]

That is why I said "equivalently strong salted password key derivation function" to preclude the response that SecureLogin is different, many sites now use sCrypt but PBKDF choice does not undermine the fundamental issue of reducing the entropy of generated keys to that of human derived passphrases.

You are correct that all forms of centralisation for stored encrypted high entropy keys reduces this to the same thing and thus equivalent to stored hashes. That is why decentralization where each user retains an offline backup of their device identity store; is the only scaleable answer. This also fragments and derogates the attack surface to the individual user level.

This does though require each user needs to maintain the responsibility for individually having an offline backup of their identity. The need of this versus the need for common adoption for such schemes should in no way dissuade you from doing it this way.

[menzow]

Hey @ramriot,

Valid concern and also the basis of my argument why a deterministic scheme is flawed. However your suggestion of offline backups beats the entire goal of SL. @homakov his whole key selling point is being hardware independent and capable of running anywhere at anytime.

Our concerns have been summed up pretty well here: https://tonyarcieri.com/4-fatal-flaws-in-deterministic-password-managers

I'm contributing to this project as I hope that @homakov / Sakurity finds a solution to this problem or is able convince us otherwise. The concept at its core is interesting; but in my opinion flawed in its current state. Depending on derivation for entropy / security isn't future proof.

[homakov]

WarpWallet has proven to be secure for 20 btc. We are 20x stronger. If you can offer a better derivation alg or better inputs and salt type - welcome. But there is no way to add state

That is why decentralization where each user retains an offline backup of their device identity store

Like all 3b people figuring out their own way to backup some file? Phones? MacBooks without ports? Lack of usable zero knowledge clouds? And cost to support all that? That does not scale well. And I certainly don't want to pay or be single point of failure in that.

All pw managers losing all their backups wouldn't matter. 99% offer email reset.

But not in our case. Data is frugile and expensive to store at scale. DoS. Sync. Bruteforce. Centralization.

[ramriot]

Hey @menzow,

I don't agree, it is totally feasible to offer offline backup & hardware independence, the work being done on SQRL proves this & also provides hints to I think at least 6 other security and privacy issues demonstrated within SecureLogin (which I need further study to derive, barring a complete written spec).

But note, while this implementation uses a deterministic key generation process it cannot be 'sold' as a replacement for static shared secrets like Passwords, or as a Zero Knowledge Proof because in the end it reduces to the same thing as the existing hashed password safes.

hi @homakov,

A stronger PBKDF does slow down brute forcing for a while, but only in a linear way, while moore's law continues on and an old database leak of a for-all-time key can always be brute forced in the future when processing speed reduces the costs for password guessing. Because Increasing the strength of the PBKDF over time does not affect old leaked data.

[homakov]

law continues on and an old database leak of a for-all-time key can always be brute forced in the future when processing speed reduces the costs for password guessing

There's credential rotation functionality built in https://github.com/sakurity/securelogin/wiki/How-password-is-changed

Once in a while planned (or after finding a flaw in current alg) new derivation scheme dropdown will be added just below email/pw fields: all users will be offered to use "Change Password" to rotate to new system (they would have to choose a new password, so old broken pw won't matter).

It's not just about derivation, same can be done about crypto_box primitive being used, just would take more effort to communicate with all services.

I don't agree, it is totally feasible to offer offline backup & hardware independence,

That can routinely be added: just using secretbox on a random string, then download the result. The problem is everything afterwards. It's been a disaster in fact in cryptocurrency community: so many wallets lost, or coins sent to never backed up private keys. They moved on to mnemonic phrases which are also no go for us (just today our maid "lost" my paper backup)

it reduces to the same thing as the existing hashed password safes

I don't know how it can be same thing. Even md5(masterpw + domain) protocol would be a major improvement over what we have now simply because services won't get plaintext of masterpw (we all know reuse is prevalent, right?).

[homakov]

Btw let me add to

law continues on and an old database leak

There is no need for a "leak" in traditional meaning. Public keys are considered public, and it must be ok to share or expose to leaks. One of selling points would be if your accounts table was exposed there's nothing to worry about.

E.g. take github w/o private repos. Once they use SL leak of their entire DB with users/comments/likes etc would worth $0. Even no need for an announcement for "change your pw" Because all that data is already public.

[ramriot]

Hi @homakov, I get where you are coming from, unfortunately it is my opinion that your choice of key derivation so undermines the tenets of a ZKP that it reduces it to little more than a global hashed PW table.

Your comment about public keys being public it I think determinant upon the entropy used to derive the key being approximately equivalent to the RSA symmetric key strength, for Curve25519 that is assumed to be 2^128 (Yes I know this is less than the key length, it i also equivalent to the strength of a 3072 bit RSA asymmetric key). If you can have a key derivation function with at least that much entropy you may call the result a Public key and treat it such because the key itself is the weakest part of the system & the cracking of that is presently computationally infeasible. Where the strength is much less than that it makes more sense to crack the key by guessing the input to the generator which for a 10-char Case-sensitive Alphanumeric password is only 34.6 Bits.

Another point I neglected to mention is that it also appears that your signing key-pairs are not generated site-specific but global across all services. This means that an attacker who has exfiltrated one sites user table & knows the public key email (salt) association is free to brute force for weak passwords and then use the gained private keys to authenticate on all other services.

It is my strong recommendation then that:-

a) As part of the key generation algorithm you include a fixed service provided string to make each sites signing key unique e.g. The sites fully qualified domain name. b) That the direct entropic link between password and key is broken in such a way that the derived key has sufficient strength to be equivalent to the strength of the signing keys.

The first I see as an easy gain, the second is a hard pill to swallow but there is I think no other way.

[homakov]

i'm half way to add per-origin pubkey, but for a different reason, some people ask for privacy within same profile: https://github.com/sakurity/securelogin/issues/3

In fact origin-derived pubkey would not stop the bruteforce because after the site finds right password they can derive keys for other origins as well.

There's no way to stop that bruteforce without an additional to pw secret which the website does not know from public sources.

It's not that I don't like your offer, it's that it's impossible to implement which I outlined in previous comments. Who's going to support this kind of seed backup system? Distributed, reliable, free to use etc. I wouldn't trust key to the kingdom even to Google (who's known for routinely closing down unprofitable projects).

It's not a hard pill to swallow, it's an impossible task for the vision I have. If i were to develop a pw manager with yet another few million users, then 1) not critical to lose as all sites have email reset 2) not expensive to store for few millions.

Leaving backups to the user would be outright irresponsible for a protocol targeting general public.

If you have a solution to this which would cost us $0, I will add it

Where the strength is much less than that it makes more sense to crack the key by guessing the input to the generator which for a 10-char Case-sensitive Alphanumeric password is only 34.6 Bits.

Big difference. It doesn't matter how many bits are in an original password, it matters how expensive it is to crack.

6 digits pin code is 20 bits entropy, right? But can you break it for scrypt

See this tweet by scrypt creator https://twitter.com/cperciva/status/866775451104034817 he says trying 1M (20 bits) costs 2^57. That's hash power per second of bitcoin 3 years ago https://blockchain.info/charts/hash-rate?timespan=all

Can't stress enough: current scheme is considered weak and is only this way because 1) no one is going to seriously focus SL users in the beginning 2) we want to improve quality of our derivation bindings. As soon as we decide it's time, alg will be bumped to 10x+ strength.

[ramriot]

Hi @homakov, I can see your point & on this matter I can agree to disagree because of where my other work is going that necessitates such storage and how implementers are finding ways to do that efficiently and securely. This is one matter were convenience really does seem to be the enemy of security.

Glad to hear per-site keying will be included, that is a huge gain. One hint if it comes up, don't fret about sites having to change domain name we found with SQRL that the eventuality can be handled by a simple process of authenticating the change and then re-authenticating to migrate to new keys.