SIP006 - Getting rid of key derivation once and for all

[shadowsocks]

SIP006 - Getting rid of key derivation once and for all

[librehat]

I'd vote against this proposal as it is enforcing some user behaviour. Users should be allowed to screw up if they may. Even p12 can be encrypted with empty passphrase 🔓

[riobard]

+1

Finally on the correct path to security :)

[Mygod]

True but as I've said having less security hurts the main goal of Shadowsocks.

[Mygod]

Pros:

• Better security;
• Better performance.

Cons:

• Takes a little extra time to set up.

[Mygod]

@wongsyrone Unfortunately having session key introduces handshake which hurts the main goal of Shadowsocks. Also it's super un-friendly to low end boxes.

[riobard]

I agree the KDF is not a very urgent issue for us. That being said, getting rid of it will

1. simplify the code base
2. avoid any arguments on which one to use (and future issue for replacement)
3. allow more compatibility between implementations in different languages
4. be more friendly to low end boxes

Looks like all wins to me.

[Mygod]

I agree it's not very urgent but it's good to put it out there anyway.

[riobard]

We seem to have four solutions:

1. Stick to original KDF in shadowsocks
2. Switch to Argon2i
3. Switch to Blake2b
4. Switch to random keys

Please indicate your current preference and reason below.

[riobard]

Questions for Blake2b: since it's generic hashing, what's the plan to get arbitrary key sizes for different AEAD?

[madeye]

Luckily we have arbitrary size implementation in libsodium: https://download.libsodium.org/doc/hashing/generic_hashing.html

[riobard]

@madeye Sorry I wasn't being clear at my question.

The goal is to get arbitrary output sizes from generic hashing because we want to support AEADs with different key size requirement. Generic hashing produces fixed size output by default, and we must either shorten or lengthen it to get desired output length.

Password hashing has a built-in mechanism to produce arbitrary output sizes, thus more suitable for KDF (what a surprise).

[riobard]

So the question is, what's the proposed solution to shorten/lengthen output from generic hashing without hurting entropy? It's a difficult task from cryptoanalysis point of view. That's why I think dedicated password hashing algo is better than generic hashing here—experts have done the hard job for us.

[madeye]

Blake2b is able to generate at most 64 bytes hash. I think that's why @wongsyrone thinks it's suitable for current AEADs.

If we add something like AES-1024-GCM in the future, then the key size here would be a problem.

[riobard]

Shortening is also an issue. Are we just taking the first 16 bytes of the 64 bytes output for 128-bit keys? What's the effect on entropy loss?

[madeye]

@riobard Yes, it should be the biggest problem. I didn't realize that at first.

So, my choices are

1. Original KDF for original stream cipher.
2. Argon2i for AEAD.
3. Random key for both stream cipher and AEAD as an option for our users.

[madeye]

For random keys, I think @Mygod can just define a new URL schema. I just need to add a new option to CLI and JSON config.

[Mygod]

Wait. Why is shortening an issue? I think shortening should be absolutely fine.

[riobard]

The original KDF is similar in spirit to PBKDF2, and PBKDF2 is also an industry standard used by many (for example MacOS Keychain and 1password). So I'd add PBKDF2 as a possible candidate if we stick to password hashing.

base16/32/64 encode for random keys looks pretty good to me.

My preference would be (in the listed order)

1. Random keys
2. Argon2i
3. PBKDF2
4. Original KDF

[Mygod]

Actually if we are going to use random keys, we should deprecate key derivation as one of its points is to prevent server masters using weak passwords. Otherwise I prefer to having key derivation instead of having both of them to simplify codebase.

[riobard]

@Mygod It's not that simple… For more explanation you could read https://tools.ietf.org/html/rfc5869#section-5

But anyway the point is that generic hashing has no standard way to produce arbitrary output sizes, and if we use generic hashing, we have to come up with our own (likely flawed) construction. Therefore it's better to use dedicated password hashing instead (if we stick to passwords).

I'd vote for random keys.

[Mygod]

@riobard I see. In that case, why not SHAKE128/SHAKE256?

[riobard]

@Mygod The practical concern is to use something more well-proven and wide-spread because implementations in other languages might not have easy access to mature lib to newer or lesser-known algos.

[riobard]

Also, shake128/256 are generic hashing…

[madeye]

@Mygod It would be very hard for me to drop key derivation here... I need a easy way to share server info with others.

[Mygod]

@madeye Random key can be embedded into JSON/ss uri after encoding to base64. I don't think it will be inconvenient.

[riobard]

@madeye Probably easier to stick to original KDF for stream ciphers, and random keys for AEAD? Is that possible?

[madeye]

@riobard The effort of user education is hard to imagine.

@Mygod What do you think of @riobard's proposal?

[Mygod]

That's exactly what I currently have in mind right now.

[madeye]

Hmm, I'm OK with random keys in that way.

[Mygod]

And yes, as @wongsyrone has pointed out, user education would definitely be a pain in the ass.

[riobard]

Yeah, the user education part is tough… Actually not matter what we switch to, there'll be a wave of potential issues.

[Mygod]

And I also think a generic hashing algorithm that supports arbitrary output size like shake128/256 should be as good as password hashing with same salt, right?

[riobard]

@Mygod No. Computation cost matters (i.e. fending off rainbow attacks).

And no existing generic hashing algo produces arbitrary output size out of box. You have to construct your own, which is likely flawed if not careful. None of us are crypto experts here. Why take the risk?

[Mygod]

Well shake128/256 does. And computational cost is a double-edged sword. It also increases load on our own servers which might not be friendly to low end boxes. For adversary like GFW who has abundant computational resources, I don't think the additional computational cost for them is really concerning.

[riobard]

Different scales. For our users, even low end routers, we need to hash only once to derive a key. 1 second computing cost is acceptable.

For attackers, they need to hash millions or billions of times. 1 second adds up really quick.

[riobard]

Sorry, I misread Shake128/256's property. Yes they do produce arbitrary output sizes.

[Mygod]

@riobard Well when we're talking about GFW, we should be thinking of a really big server farm. Parallel computing makes 1 second add up not so quickly as you imagined as rainbow table is pretty parallel at its core.

[Mygod]

Again none of this would be problematic if we had used random key since the beginning huh... 😓

[riobard]

Exactly! @madeye already explained that it's pretty damn hard to speed up Argon2i on GPU.

Remember that GFW has its own budget constraint. We could simply just blow it off to make it infeasible. Generic fast hashing does not grant such protection (may I call it Money Attack please? :)

How about listing all possible password hashing/generating solutions and let users choose on demand? lol

[Mygod]

@riobard I see. So being slow is both its advantage and its disadvantage at the same time.

[riobard]

@v2ray Please no. It'll significantly increase the code base complexity.

@Mygod I'd say advantage for us, and disadvantage for our adversary. Why not? :D

[madeye]

@Mygod About the performance of Argon2i, as it only runs once at the startup of shadowsocks, would it be the bottleneck for us?

[Mygod]

Yeah so I guess the only advantage of using SIP006 is avoiding password misconfiguration then.

[riobard]

@madeye I guess not, unless you're running a server with thousands of clients. Even in that case, you can pre-compute keys and save them to disk instead of re-compute each time after reboot, and the advantage for the server to read keys (instead of passwords) becomes obvious.

[Mygod]

In summary, the security of hashing algorithm is ensured by a strong password and security of the hashing algorithm and implementation (which MD5 does poorly). And the security of random key is ensured by the randomness of GPG.

[Mygod]

(but trust me, weak password does exist. I've seen people configure their password for their shadowsocks server with only ~23 bits of entropy)

@riobard seriously, why is the "rainbow table attack" practical in the context of Shadowsocks communication? What is the benefit for an attacker to get the original password?

[riobard]

@Mygod GPG is unnecessary. /dev/urand is good enough on modern OS.

[Mygod]

@riobard I would use GPG anyway if this were implemented since I'm a little OCD. 😜

@v2ray If one can get the key, the underlying traffic becomes plain text which makes censoring very easy.

[riobard]

@v2ray Attackers don't need to get original passwords.

Because people tend to use short passwords with insufficient entropy, pre-computed keys from popular passwords pose significant threat to expose Shadowsocks server.

To counter that, we can increase the cost to precompute keys (e.g. using Argon2) or use random keys with sufficient entropy.

[riobard]

@Mygod haha that's all up to you bro! :P

pre-computed keys from popular passwords

@riobard IMO, rainbow table is for guessing original passwords from a hashed value. Then the original password can be used for other attacks. If the original password is not meaningful to attackers, the precautions (for rainbow table attack) discussed above are also not meaningful.

Once the hashing algo is put into use, the attacker can start to compute keys based on popular passwords. Let's say it requires 1 second to compute a key, and there is a million of popular passwords. This will cost the attacker 11 days (1000 * 1000 / 3600 / 24) to compute all the passwords. Even if the computation time increases to 10 seconds per password, that's just over 100 days, which is trivial to any attackers.

As a conclusion, changing password hashing algo from MD5 to a modern/fancy one, you are only protecting users for 100 days. After that, all the development effort on this change are wasted.

[Mygod]

@v2ray That's why weak password is such a bad idea. And I'd say GFW can easily calculate 1M hash per second no matter which algorithm we use. A password with 23-bit entropy can be easily broken within seconds.

[riobard]

@v2ray Yes, you're right. Weak password sucks. Best we could hope is that users don't pick popular passwords.

[Mygod]

Or we can deprive user the freedom to choose password by enforcing a random key.

So, just enforce a long random key for encryption. Don't spend time on this hashing algo discussion anymore.

[madeye]

What about suggesting a strong password when starting a shadowsocks server? It looks a good trade-off here.

[madeye]

Then with a simple 8 character password, brute-force against Argon2i costs 26^8 / 3600 / 24 / 365 = 6621 CPU years.

[Mygod]

However a single Argon2i doesn't need 1 CPU second and we will have to take parallel computing into consider. The random key is still the cheapest and safest for end users.

[madeye]

@Mygod I think that's why we choose Argon2i here, it's very hard to parallel: highly dependent, memory-hard algorithm.

[Mygod]

@madeye However being hard to parallel compute one hash is different from being hard to parallel compute a billion hashes. An adversary would need to try a lot of combinations. It's always easy to compute a lot of hashes in parallel.

[Mygod]

If you'd like to display a warning, then we have to do the estimation of the strength of the password. Here's something relevant to look at.

[madeye]

@Mygod What about suggesting a strong random password like generating random key.

[Mygod]

If we're suggesting doing that, we might as well take this proposal. I think it makes sense because unlike a PC logon password or your password database master key, it's almost always saved in local configuration file, shared via ss URI or QR code - you almost never need to type it manually.

[madeye]

@Mygod If we can keep both key derivation and random key, I totally agree with this proposal.

[Mygod]

What about random key only for AEAD? And print instructions to generate a new password when the input password seems invalid.

[madeye]

@Mygod I'm OK with this.

[madeye]

Instead of gpg ways, I suggest generating key using randombytes_buf of libsodium (/dev/urandom). No more dependencies please...

[riobard]

@madeye You don't need to generate random keys. Users are expected to supply them.

[Mygod]

We should probably make generating random key easier for users since the purpose of this proposal is meant to prevent users screwing up.

[riobard]

Do we generate a random key for users on startup?

[Mygod]

I imagine we would ask user if we should generate a new key if the key supplied doesn't seem valid.

Just ask user to supply an UUID in string form. There are plenty of services (both online and offline) for generating such things. There is no need to build it into Shadowsocks.

[riobard]

UUID is fixed at 128 bits and its canonical string representation is fixed in hex.

We need keys of arbitrary length and (ideally) shorter string representation in base64url.

User won't care about this. The key is always copy-pasted from server to client (or by scanning QR code). As long as the key has enough value space, it is fine for Shadowsocks use case.

[madeye]

If it's a UUID or fixed length random string, maybe we can just run key derivation on it.

(Hmm, it seems we're still using password?)

[Mygod]

Yes. We plan to get rid of key derivation in this proposal so we're not going to use UUID.

[riobard]

Just read from /dev/urandom.

@madeye key derivation doesn't increase value space. It is a deterministic algorithm. 8-byte password has 26^8 possible combinations (say [a-z]), no matter how you derivate it, the target value space has also 26^8 combinations. This approach doesn't increase the difficulty of a brute-force attack.

What you need is a large enough value space for passwords

Variable length of password doesn't provide larger value space than fixed length ones at all.

[riobard]

@v2ray We need 192 and 256 bits keys for AES-192-GCM and AES-256-GCM. UUID is limited to 128 bits.

Then ask user to provide 2 UUIDs, or derivate from the first one.

What I wanted to say is:

1. 16 random bytes is good enough for anti brute-force attack.
2. UUID is a well-known concept
   • Easy for user education.
   • Standardized string presentation, no need for base64.
   • Easy to generate with cross platform tools and online services.

Sorry @madeye, I misread your comment when posting my previous one.

[riobard]

Asking for two UUIDs is weird… 😓

[testcaoy7]

I believe that “Signcryption” is the best choice.
Detail of Signcryption:
www.cs.bham.ac.uk/~mdr/teaching/modules04/security/students/SS3/IntroductiontoSigncryption.pdf

In that case, we can provide data confidentiality, integrity, and authenticity like AEAD while verify client's identity in a single pass which means a password is on longer needed.

Signcryption can be built on all kinds of digital signature. A scheme built on ECDSA:
https://eprint.iacr.org/2006/126.pdf

[Mygod]

@testcaoy7 We're using private key cryptography.

[madeye]

Add SIP006 via https://github.com/shadowsocks/shadowsocks-libev/tree/sip006. Any suggestion?

[Mygod]

1. Use url-safe base64, i.e. [0-9a-zA-Z-_].
2. Persist the generated key?

[madeye]

Persist the generated key?

It'd be tricky where to store the key.

[Mygod]

@madeye Good point. Ask user to change their key and exit?

[madeye]

@Mygod Yes, I think so.

[madeye]

@Mygod Any spec or implementation for URL safe BASE64.

[Mygod]

@madeye

1. Spec: RFC4648 Section 5.
2. Implementation: https://android.googlesource.com/platform/frameworks/base/+/master/core/java/android/util/Base64.java#565

[Mygod]

It should be as simple as changing the alphabet.

[riobard]

@madeye @Mygod so what is the conclusion now? Stick with old password hash for stream ciphers and require key for AEAD?

[madeye]

Right, I've updated specs and shadowsocks-libev to follow this SIP.

[Mygod]

@librehat The difference is that in p12, user usually needs to enter passphrase manually.

[riobard]

Ok, I took a middle ground in https://github.com/riobard/go-shadowsocks2

It takes both -key and -password arguments. If -key is empty, derive a key from -password using the original MD5-based KDF.

Users are encouraged to generate random keys. But if they have to use passwords, it's same as before.

Note that -key applies to old stream ciphers as well.

[testcaoy7]

If the server and the client has the same time, can a time-based session key be derived?

[madeye]

Actually, I personally prefer the approach from @riobard.

What do you think? @Mygod

[Mygod]

In that case we might as well use only password to keep things simple. I actually don't have a strong preference anyway.