Proposal: Multi-user support in Shadowsocks protocol

[VictoriaRaymond]

Background

Shadowsocks protocol doesn't support multi-user as designed. To support multi-user on a single port, a naive approach on Shadowsocks server is to try to decode the incoming connection with all users' key, until one key succeeds. This way is quite time consuming when user base is large.

Here is a proposal to balance server work load and compatibility of existing protocol.

Proposal

A: Define UserID as uint16, which can be serialized into a two-byte sequence.
B: Define a function fa(user)=>UserID. fa should generate an unique UserID for each user, but collision may be accepted.
C: When SS client generates IV (salt) for a connection, say byte[0...31]:

1. Randomize all bytes as usual.
2. Then reset byte[30...31] to the UserID.
3. Then masks byte[30...31] with fb(IV)=>uint16.

D: When SS server receives an incoming connection. It tries to decode IV with the same fb.

• If UserID is valid, server decodes the entire connection with this user.
• If UserID maps to multiple users, server try decoding the connection with all matching users.
• Optionally if UserID if not found, server can try decoding with a "default" user. This step provides backward compatibility to clients without multi-user support.

Advantage

• Backward compatibility with existing Shadowsocks protocol.
• Constant-time decoding with multi-user support.

Disadvantage

• UserID may be leaked and becomes a fingerprint. To mitigate this issue, fa may take other factors into account, say timestamps, e.g., fa(user, time-in-second)=>UserID. The UserID will dynamically change based on time.

Suggested Functions

• fa: first two bytes of SHA256(user-key).
• fb: Fnv-1a(input[0...len-2]) % max(uint16)

[madeye]

I don't think UserID in IV is a good idea. As you mentioned, it will become a fingerprint. A timestamp based ID cannot solve it, as it will keep the same every several seconds, say 30 seconds.

Previous discussions suggest that we do authentication on the first chunk with different keys, to identify the user based on the success key. As long as you don't need to support thousands of users on one port, this approach should work well without modifying the protocol.

One possible optimization is also discussed before that we can cache the success key for the source IP, which would save most of computation. To prevent potential DDOS attack, the IP tries too many times with authentication failure should be blocked.

[VictoriaRaymond]

Embedding UserID into IV is purely for backward compatibility. It is quite important for new servers to compatible with old clients due to the large user base of Shadowsocks. Otherwise, you may do the user identification in the chunks later on.

As long as you don't need to support thousands of users on one port, this approach should work well without modifying the protocol.

I believe it is common to support thousands of users on a single server for commercial use.

[madeye]

I believe it is common to support thousands of users on a single server for commercial use.

I think that's exactly what we'd like to avoid from the very beginning. It makes no sense to provide commercial service based on shadowsocks. And unfortunately it's illegal in some place. 😞

BTW, @fortuna from Jigsaw is trying the similar authentication based multi-user-single-port idea here: https://github.com/fortuna/ss-example/blob/master/server.go#L40. With the optimization mentioned above, even thousands of active users should not be a problem.

[fortuna]

The code currently at https://github.com/fortuna/ss-example is a prototype. In practice, I haven't seen any issues as is with a small number of users. It's still unclear to me what the overhead will be with over 100 or 1000 users. But I can see how that can be a problem and a cache just like @madeye proposed should be good enough.

[fortuna]

FYI, my experimental server is now at https://github.com/Jigsaw-Code/outline-ss-server and supports any combination of user and port, in a config-driven way. It's backward-compatible: existing clients can connect to it just fine. It runs one process on the server, and can be updated with SIGHUP without interrupting existing connections.
It has Prometheus monitoring to provide data usage information and track the health and resource consumption of the server.

I haven't implemented the suggested optimizations yet, but in a server with 100 access keys I did not find the the cipher finding to have a significant impact on performance (worst case 10-20ms extra connection time).

Here is a real example of the monitoring that is possible: