Secure single-port multi-user authentication

[riobard]

Summary

Current commercial deployments of Shadowsocks suffer from a social-engineering weakness that any client knows the Symmetric Pre-Shared Key (SPSK) and can use it to MitM attack other clients of the same server.

To counter this weakness, SPSK must be abandoned in favor of asymmetric private/public key pairs. The server's private key must be kept secret at all times. Clients only know the server's public key, and must derive a per-session subkey to talk to the server. No clients can pretend to be the server because it does not have the server's private key.

An additional benefit of using asymmetric key pairs is that multiple users can share the same port securely without revealing their own client identifiers.

Update

Please see #54 (comment) for the latest proposal. The following section is the original proposal without forward secrecy protection.

Details (OBSOLETED)

1. The server randomly generates a pair of keys on Curve25519: a private key sk that must be kept secret, and a public key pk that is distributed to all clients beforehand.

   sk, pk = curve25519_keypair(random_seed)

2. Each time a client wants to talk to the server, it randomly generates another pair of keys on Curve25519: a private key sk' that must be kept secret, and a public key pk' to be sent to the server.

   sk', pk' = curve25519_keypair(random_seed)

3. The client computes the shared secret with the server using x25519 ECDH function:

   shared_secret = x25519(sk', pk)

4. The client derives the per-session subkey using HKDF_SHA256:

   subkey = HKDF_SHA256(shared_secret || pk' || pk)

5. The client encrypts payload using the subkey and sends the encrypted data to server.

6. The server receives the client's public key pk' and computes the shared secret using x25519 ECDH function:

   shared_secret = x25519(sk, pk')

7. The server derives the per-session subkey using HKDF_SHA256:

   subkey = HKDF_SHA256(shared_secret || pk' || pk)

8. The server uses the subkey to decrypt the encrypted payload.

Note that x25519 ECDH function ensures x25519(sk, pk') == x25519(sk', pk).

To implement secure multiuser support, the client can include its Client Authentication (e.g. username/password) in the payload for the server to verify against a database. Detailed format will be discussed separately.

[madeye]

There two key assumptions of shadowsocks protocol:

1. Users set up shadowsocks themselves on public cloud services.
2. A user use his service privately or share it with a small group of people.

Based on these two assumptions, I don't think we should worry about the MitM attacks mentioned above. Also, based on these two assumptions, we are able to provide a very easy-to-use tool for our target users.

However, if anyone wants to use shadowsocks as a commercial service and try to let many people connect to one same server port with one same key, the problem above indeed exists.

So, here are some suggestions from my side:

1. It's important to set up and use shadowsocks "privately". It ensures both security and performance.
2. For the multi-user usage, we'd better put this kind of proposals (including user authentication) in a new protocol instead, since it's already not a shadowsocks protocol.

[riobard]

Indeed. This is strictly necessary only for large-scale (e.g. more than a few trusted friends) deployments (though anyone will benefit from this if they have more than one client).

I don't have stats but from personal observation more friends are using commercial services than running their own for various reasons (e.g. lack of technical acumen, ISP and VPS choices, time constraint etc). This proposal is for them.

I'll implement this in my experimental branch first and see how it goes. But in order for this to be adopted by major clients, we need to make it official. Somehow I think this is the necessary sales pitch for them to accept the new AEAD ciphers. Right now there's a sentiment from client devs that AEAD ciphers do not bring enough benefits to worth the trouble.

I think they'll like the multiuser mode.

[hellofwy]

I think:

• The link speed is the strongest demand.

• As for routers, the encrypt/decrypt speed may also a concern.

• A multi-user mode is a concern only if ports like 80 or 443 are more QoS or firewall friendly.

If people prefer your design, you can actually re-brand it, and it'll be official. Putting it into Shadowsocks here will be confusing for not-tech people.

[riobard]

@hellofwy This proposal will most likely ended up being shadowsocks2. I think there's already enough confusion now, and clean, backward-incompatible revision might be a better way.

[v2ray]

Just want to point out that, "Diffie–Hellman key exchange" itself doesn't prevent from MITM attacks. Without a certificate authority, there is no way to ensure that the public key gets transferred securely. The DH algorithm only provides forward secrecy.

[riobard]

@v2ray No. Like SPSK, the server's public key is pre-shared, and CA is not necessary. The additional benefit brought by PKI is icing on the cake.

And the way we use DH does not provide forward secrecy either. In fact, FS is not possible without handshake. We'd like to avoid handshake for obvious reasons.

[Popwax]

With enough traffic, plain curve25519 public keys are vulnerable to deep packet inspection. See https://elligator.cr.yp.to

The threat that the new protocol try to prevent is not an issue caused by shadowsocks itself, but by user reusing the same public key. The security provided by pre-shared keys is based on the assumption that the user absolutely trust anyone who have the knowledge of the pre-shared keys, and all traffic would be transparent to them.

With all these considered, the "MitM attack" you mentioned is actually unclear. The victim "trust" the attacker by sharing the same PSK. But this doesn't provide the attacker any further advantage to perform attacks. If the attacker somehow controls routing node between the user and shadowsocks server, he/she will be able to capture or interrupt traffics. But that's all. It's basically the same threat as if shadowsocks is not being used. If you insists that current shadowsocks implementation should prevent this from happening, remember that victim actually "trust" the attacker.

That being said, I understand that there are use case for multi-user proxy server. I just don't feel it's necessary to have it in shadowsocks with such distinct purposes.

[riobard]

@Popwax It's easy to disguise the public key sent from the client to the server by encrypting it with the server's public key using a symmetric cipher (e.g. AES). This does not provide any additional security, but just a means to make the structure of the public key indistinguishable from random noise.

If the attacker somehow controls routing node between the user and shadowsocks server, he/she will be able to capture or interrupt traffics. But that's all.

This is false. With the symmetric PSK, the adversary can perform MitM without being detected.

victim actually "trust" the attacker

This makes no sense security-wise.

[Popwax]

This is false. With the symmetric PSK, the adversary can perform MitM without being detected.

This makes no sense security-wise.

Maybe I didn't put it straight. The victim shouldn't use the same PSK with others in the first place. Otherwise, the victim should expect those attack being undetected.

[riobard]

The victim shouldn't use the same PSK with others in the first place.

Right. The sad truth is that currently that's what people are doing in the field. The alternative (one password/cipher/port per user) is such a hassle that it's quite unpopular.

[shinku721]

That's not shadowsocks anymore...
Handshakes will generate extra traffic, which I think is not what shadowsocks wants. And if we need it why not use TLS directly?

[riobard]

@shinku721 There's no handshake in this proposal. Server's public key is pre-shared.

[riobard]

@shinku721 TLS requires handshake, which we want to avoid.

[v2ray]

@riobard Your assumption is that the public key can be transferred through a trustable way. In the context of MITM attack, this is not true. The attacker can intercept the public key, replace it with his own public key without the client knowing it. Then the attacker can decrypt traffics from the client with his own keys, and the encrypt it with server's public key. Without a CA's signature, there is no way for the client to check whether the key has been tempered or not.

[riobard]

@v2ray No.

The assumption is only that the server's public key is pre-shared and thus trusted. The client's public key can be sent in clear text (or disguised as random noise as mentioned in #54 (comment))

The attack you described will not work. The adversary cannot decrypt any traffic because it lacks either the client's or the server's secret key.

[v2ray]

The "key pre-shared" process is where MITM attack starts. You have to make sure that the public key received by client matches exactly the one sent from the server.

[riobard]

That's a completely different threat model and way beyond the scope of this project.

In this proposal we assume the client can get a trusted copy of the server's public key (e.g. copy from the proxy service provider's TLS-protected webpage).

[shinku721]

@riobard Well, you're right. However, it may be a bit too far beyond shadowsocks... If a user know the pre-shared key and is able to perform a MitM attack then why not she/he invite the server provider to tea directly?

[riobard]

@shinku721 There are more types of adversaries than just state-level organizations. If you only care about GFW, the original Shadowsocks with stream ciphers is proven to be more than sufficient to get the job done.

My take is that Shadowsocks could be a more general tool to improve security. For example, it could protect you from a local (e.g. company-wide) filtering/monitoring agent.

Remember that HTTPS is still not everywhere yet.

[Mygod]

I agree with @madeye wholeheartedly and Shadowsocks is never meant to cover the use cases you mentioned. If you want to do that, using other projects or starting off something anew is a better option.

[riobard]

@Mygod I don't mind if it's called something else.

[Mygod]

So I think we should close this since it's off-topic. Feel free to continue your discussions.

[riobard]

I'd like to keep this issue open because it's basically the continuation of https://github.com/shadowsocks/shadowsocks/issues/169 which I just found a couple of days ago.

[Mygod]

A helpful reminder: keep second-system effect in mind.

[Riatre]

I'd like to suggest refering to the previous TLS 1.3 drafts as what you're trying to eventually (re)invent is very similar to 0-RTT ECDHE-ECDSA-AES128-GCM-SHA256 cipher suite with hardcoded public keys (the "PSK").

[riobard]

@Riatre So? TLS leaks protocol identity at record layer and it requires handshake even with PSK. None of which is acceptable in the scope of this project.

[Riatre]

@riobard I mean you may want to check how the cipher suites are designed in TLS (the right combination of key exchange algorithms, authentication algorithms and encryption algorithms to provide identification, authentication, confidentiality and integrity), which doesn't depend on the other parts of the TLS protocol and can be borrowed.

[Riatre]

@riobard The handshake in TLS basically serves three four purposes:

1. Confirm the client and the server both talk TLS.
2. Negotiate a suitable cipher suite supported by both sides.
3. Identify the server and the client.
4. Do a secure key exchange.

Clearly 1 and 2 is not needed, we can simply hardcode which cipher suite to use like we currently do.
3 (Identification) is what you're trying to resolve in this issue.
4 (Key Exchange) is required to provide forward secrecy.

TLS 1.3 actually describes a 0-RTT method (which means you can carry data in the first round trip like TCP fast open, and the only scarification is it doesn't guarantee forward secrecy for the first two packets) to accomplish 3 and 4 and it is similar to what you described in this issue, which is the reason why I suggest you reading it.

[riobard]

@Riatre Ah, I see. I thought you were suggesting that we should just use TLS 1.3. There were suggestions like that before without fully comprehension of the scope of the project. Sorry for the misunderstanding.

[AlvisZhang]

嗯，插个队，想问下，你们的多用户支持是否也会设计成插件式的，就是好似 @Riatre 那种流程，但 3 的身份识别是可以配置不同 backend 的，好比是类似于 freeradius 的那样的

想做伸手党等个支持 LDAP 认证的模块等好久了，嘿嘿

[riobard]

@AlvisZhang That was the intention.

[fortuna]

@riobard , I like your proposal a lot. Privacy of past communication is very important for certain types of users. Do you have a working prototype?

There are two things that worries me:

• Will it be easier to fingerprint the protocol?
• It makes me a little nervous to see new crypto schemes being created, as it may be hard to prove that it's correct (unlike standard protocols, which have a lot of eyes on it).

[riobard]

@fortuna Unfortunately I haven't got time to implement it yet.

To address your worries:

• If we do it correctly, the new protocol should look the same as the current AEAD-based protocol, i.e. a complete random stream of bytes. Curve25519 public keys have some known structure, but there're ways to transform them into random-looking bytes.
• No, we do not invent anything new here. All techniques used in this proposal are well-studied modern crypto work.

[joeytwiddle]

If you don't mind me asking, does this vulnerability also affect ss-manager?

We plan to have lots of users, but each user gets a unique port and password.

Can one user MitM the traffic of another user using a different port+password?

[riobard]

@joeytwiddle I don't think so.

[Mygod]

Okay I will redirect my comments regarding this here. I read through the proposal and okay if you know server's public key you can do DH key exchange non-interactively, fair enough. However, let me point out that your protocol does not do what you plan to do.

The goal is to share shadowsocks with multiple users, and it should protect other users even if one of them is compromised -- pretty reasonable. However, as you mentioned pk' needs to be encrypted under symmetric key pk before transmission, otherwise it will not be indistinguishable to random noise. However, a compromised party can learn pk and therefore distinguish all other traffic (although not being able to decrypt them), and indeed pk is usually a group element, in particular, the log of the order of the cyclic group generated by x25519 is not going to be divisible by 8, so an attacker can indeed distinguish this pk.

[riobard]

@Mygod The original proposal is pretty old now and there're newer and better ways to address the issue you mentioned. x25519 public keys can be transformed to be random without that encryption step, see https://godoc.org/github.com/riobard/go-x25519 (based on https://www.imperialviolet.org/2013/12/25/elligator.html)

[Mygod]

@riobard Sorry I don't know enough about elliptic curve to evaluate your fix. Anyway the uniform representative will definitely be statistically far from uniform. I am not sure if it is computationally uniform but according to what you cited:

I have not carefully reviewed the code, so beware. There are also some non-obvious concerns when using Elligator: for example, if you are hiding a uniform representative in an nonce field then the attacker might assume that it's a field element, negate it and let the connection continue. In a normal protocol, altering the nonce usually leads to a handshake failure but negating an Elligator representative is a no-op. If the connection continues then the attacker can be pretty sure that the value wasn't really random. So care is required.

So if you think that Elligator might be right for you, consult your cryptographer.

Pretty bold of you.

[riobard]

@Mygod Don't worry about statistic analysis. If one is under such attack, Shadowsocks is not the right choice anyway.

The quoted attack is not a major concern because if client public key is altered, later decryption and authentication will fail anyway. Remember that the primary concern of ss-server is to not respond (or fake response) to invalid requests. It's the same requirement here.

[riobard]

Here's the updated proposal. It's basically a simplified TLS 1.3. Please criticize if you find any problems.

Details

1. The server generates a pair of long-term identity keys: a private key sk that must be kept secret, and a public key pk that is distributed to all clients out-of-band (e.g. when distributing the server address and config).

   sk, pk = x25519_keypair(random_seed)

2. When a client wants to talk to the server, it generates another pair of ephemeral keys: a private key sk' that must be kept secret, and a public key pk' to be sent to the server (pk' can be additionally transformed to look random if necessary).

   sk', pk' = x25519_keypair(random_seed)

3. The client computes a pair of initial session keys using kx25519:

   cli_rx0, cli_tx0 = kx25519.ClientSessionKeys(pk', sk', pk)

4. The client encrypts early data (usually containing user authentication like username/password) using cli_tx0 and sends the encrypted data to the server. Note this early data is not protected by forward secrecy so the client has to decide what data should be included here. This is the similar to the caution necessary to use TLS 1.3 early data.

5. The server receives the client's public key pk' and computes the shared session keys using kx25519:

   srv_rx0, srv_tx0 = kx25519.ServerSessionKeys(pk, sk, pk')

6. Note that kx25519 guarantees that srv_rx0 == cli_tx0 and srv_tx0 == cli_rx0.

7. The server uses srv_rx0 to decrypt the encrypted early data (if any) from client. If early data contains user authentication, the server should check if it is legitimate and respond accordingly (e.g. drop connection if auth fails).

8. The server generates another pair of ephemeral keys

   sk", pk" = x25519_keypair(random_seed)

9. The server computes a new pair of session keys

   srv_rx, srv_tx = kx25519.ServerSessionKeys(pk", sk", pk')

10. The server sends pk" ^ srv_tx0 to the client. Future data sent from the server to the client is encrypted by srv_tx (NOT srv_tx0) and is protected by forward secrecy.

11. The client receives pk" ^ srv_tx0 from the server and computes pk" = pk" ^ srv_tx0 ^ cli_rx0. (srv_tx0 ^ cli_rx0 cancels out because they are the same, see step 7.)

12. The client computes the new shared session keys

    cli_rx, cli_tx = kx25519.ClientSessionKeys(pk', sk', pk")

13. Future data sent from the client to the server is encrypted by cli_tx.

14. After the session is finished, the client erases sk', and the server erases sk".

Caveats

• Early data is not protected by forward secrecy. Future compromise of the server's long term sk will only reveal encrypted early data if traffic is recorded, and everything else enjoys forward secrecy.
• The client's initial pk' can be sent in the SYN packet using TCP Fast Open if the network condition allows, making the exchange truly 0-RTT. But TCP Fast Open does not work universally and has its own security implication (e.g. tracking cookies) so worst case is 1-RTT for TCP connection establishment.
• pk' and early data can be replayed, especially if used with TCP Fast Open. The server should deploy some mechanism (e.g. Bloom filters) to detect and reject replayed traffic.

[Mygod]

Criticisms since you are still trying to push it:

1. It is not TLS. In fact, it is not even simplified TLS so there is little security guarantee.
2. Security goal of Shadowsocks is different from TLS. If you want to transmit sensitive data securely (forward security/MitM/whatever), just use TLS/SSH over Shadowsocks. On the other hand, security of TLS does not directly grant you security here.

Feel free to make your proposal a plugin but I will not personally use it until it gets enough test.

[riobard]

@Mygod First, it's pretty rude to close other contributors' issue without prior agreement, especially while they're still working on it. Are you the owner of the issue? Or are you the owner of the organization? Stop doing it and apologize.

Second, if you don't like it, just don't use it. No one is forcing you.

Third, if you have a better proposal to provide forward secrecy and secure multi-user authentication without forcing people to pay for domain names, I'm all ears.

[Mygod]

Have it your way. I do not come here to waste time playing word games with you.

[riobard]

@Mygod Apologize. cc @madeye

[riobard]

@madeye Apparently @Mygod is not responding to my request to apologize for their rude actions and offensive words. As the current owner of the organization, I'm formally asking you to intervene. Specifically

1. I demand you to ask @Mygod to personally apologize to me and promise no future offenses like this will ever occur.
2. If @Mygod refuses or ignores the request, I demand you to remove his right to moderate the issues and discussions in this organization.
3. If you find my demands unreasonable or unacceptable, please state your reasons and I will respond accordingly.

[riobard]

@madeye Are you going to say something or not? Or do you think this is not up to you to decide?