shadowsocks-org
shadowsocks-org copied to clipboard
shadowsocks
Defend against replay attack
https://en.wikipedia.org/wiki/Replay_attack
A replay attack (also known as playback attack) is a form of network attack in which a valid data transmission is maliciously or fraudulently repeated or delayed. This is carried out either by the originator or by an adversary who intercepts the data and re-transmits it, possibly as part of a masquerade attack by IP packet substitution.
Replay Attack potentially allows adversaries to identify a Shadowsocks server by observing and replaying the data streams between a valid client and the server. Ideally we want to recognize that a data stream is replayed, and react accordingly.
From my comments in #36 :
Just put a timestamp into the request header, then the server verifies that the timestamp should not exceed the server's local time +/- 60s. This timestamp is authenticated by the request's tag. (It is OK to use the timestamp as AD but then we cannot tell timestamp errors from authentication errors...)
The server keeps recording valid incoming requests (by its IV or the seed in the preshared-key protocol or anything that can identify a request) for more than the last 2 minutes (2 * 60s), and rejects duplicated requests. We can use any reasonable data structures such as binary trees, hash tables or bloom filters.
Drawback: sometimes the times on clients and servers are not synchronized...
Also note that the server must handle the replay connections in the same way as other errors.
There two kinds of replay attacks for shadowsocks: short-term and long-term.
To defend any short-term replay, I think our current implementation is already good enough. In shadowsocks, we are maintaining a nonce cache on the server to detect any nonce reuse. The default size of that cache is 1024, which should be large enough for personal usage. Any replay attack detected here would cause the source IP being blocked.
For long-term replay, the easiest way is including a time stamp in our header. However, is it really necessary? If the adversaries are performing this kind of attack for a specific port of your server, I think your shadowsocks service is already exposed.
@wongsyrone A random chunk within a TCP stream? I don't think it's possible, because currently we assume the nonce of each chunk increased by 2. If one chunk is sent twice, then an authentication error would be detected.
I prefer not using storage to defend against replay attack as that would cause additional problems.
I agree that defending against replay attack should be plugins' responsibility.
Plugins are also a part of Shadowsocks. It's just more convenient to put this part altogether with obfuscation since obfuscation protocols usually use handshake that we can transmit additional data with. I'm not saying we don't need to care about replay attack.
Does it mean someone should reconstruct the whole TCP stream or only a request header in the first packet?
As our current design is based on session key and session unique nonce, to perform a replay attack, the adversary should replay the whole TCP stream.
@madeye Currently the nonce cache in libev port is suboptimal in space usage. Since we're not really interested in retrieving anything from that cache, the cache itself provides only test of set membership.
We could instead use a Bloom filter to test if the given salt/nonce has been seen before (with a low rate of false positives). 1MB of space can store millions of entries in a standard Bloom filter.
This is a recommendation for Shadowsocks implementations to defend against bad CSPRNG. It does not change the protocol.
@riobard I did some research for bloom filter before. There two concerns:
- False positive.
- False positive increasea with more inserts.
To overcome these limitations, we may clear the bloom filter from time to time. I think it may introduce new problems.
@madeye With proper handling I think false positive is not a major concern. The server should react in the following way:
- Receive salt from client
- Perform AEAD decryption
- If successful, look up the Bloom filter and check if the salt has been seen before
- If yes, disconnect to force the client to initiate a new connection (with a new randomly generated salt). Possibly logging to warn server operator of potential replay attack.
- Otherwise, add the salt to the filter.
The Bloom filter can be fine-tuned to produce a very low rate of false positive. We can use two Bloom filters: one in active use, and one in standby. If the active one is filled over a pre-defined threshold, future insertions should be directed to the standby filter, and the active filter gets reset.
@riobard Supplement more data to support your claim. How large should the threshold of possibility of false positives be? In this case, how long should a server flush the filter? How does it perform compared to a simple table, considering space usage, and the minimum time for a feasible replay attack considering a number of UDP packets sent steadily to the server? Etcetera.
By the way, I don't think this probabilistic data structure is designed for our needs. If we are going for a probabilistic algorithm, I think there should be something more suitable.
@madeye First of all, I don't think anyone has performed replay attacks because the same request will lead to unexpected result such as submitting a form twice. But if there was any evidence, we would better defend it. Also implementing this feature is a way to acknowledge us whether the attack is happening.
Bloom filter is the best structure if we design it carefully. We can design it with a low false positive rate which can hardly cause a false positive in practice. And if we introduce timestamps and only allow requests of +/- 1min, then we only need to clear and switch to another filter every 2mins. In that way we record the requests in the last 2-4mins.
@riobard Don't just disconnect but we must keep the behavior same to handling authentication errors. Also I am not too concerned about false positives, because I think the rate of network errors is much higher.
I used to implement the protocol with some kind of timing check and, I required the connection to finish the request header in 30 seconds or I will drop the connection. So when someone either replays or sends me fake data, or even connect then do nothing, the server will disconnect at the exactly 30s. Although this can be a character, this is the only behavior for any kinds of active detection and I think the attacker cannot determine the sort of service with only the timeout.
@Mygod There is a formula to calculate the false positive rate. You can find it on Wikipedia.
The math is pretty simple. Classic Bloom filter requires 1.44*log2(1/e) bits per item for storage where e is the false positive rate. Assuming we are aiming for e=1/10^6 (which means very rare), and 1 million salt/nonce to track (which is a LOT even for a very busy server), the Bloom filter needs less than 4MB of memory (which is doable even on low-end routers).
Implemented a Ping-Pong bloom filter in the branch https://github.com/shadowsocks/shadowsocks-libev/tree/bloomfilter.
Current parameters are: 1000000 entries and 0.00001 error rate. The additional memory usage is 2.85 MBytes.
I'm running tests in a production environment. Let's see if this error rate (0.00001) works.
Since it's a Ping-Pong bloom filter, it forgets half of history (500,000 entries) after each resetting.
@madeye 0.00001 error rate is too high. Consider the aftermath of a false positive: legitimate users will be blocked by the server. I think that's pretty catastrophic. I prefer having the error rate comparable to non-recoverable error rate of a hard disk, i.e. 1e-15 to 1e-18.
@Mygod 1e-15 is really a small number, 8 MBytes is required. I'm wondering is there a non-recoverable error rate of a internet connection?
@wongsyrone The endian issue here shouldn't be a problem as we never try to pass this hash between machines.
@wongsyrone AFAIK, all the modern CPUs (x86, ARM, MIPS) support misaligned accesses for scalar instructions. You may have alignment fault on ARM for vector instruction, but it's not our case here.
@wongsyrone Continuous 8 replay errors would cause a IP blocked. Maybe it's already large enough?
The purpose of the Bloom filter is to detect salt/nonce reuse. As for the action to take after replay is detected, we should leave it up to server operators. Would it be better if we take an argument to a shell script, which is invoked each time a replay is detected along with necessary information like IP addresses? Server operators can write their own policy in such shell script to either null route the connection or use tools like fail2ban.
@riobard Yes, the behavior after a replay detected should be not part of this proposal.
@wongsyrone I think it's safe to block scanners.
Hmm I think things are getting a little bit too complicated here (again). Mind you that bloom filter doesn't solve replay attack completely. It's just a slightly better (or not) approach than simply storing IVs.
If one is running Shadowsocks on 80/443, he/she might as well use plugins like simple-obfs. I think plugins can decide what action should be taken when a malicious request is received.
Yes, please go ahead with replay attack related topics here. The bloom filter is just an implementation enhancement, which is not part of shadowsocks protocol.
@wongsyrone It won't. The salt/nonce is only tested against the Bloom filter after successful decryption and authentication. Non-Shadowsocks traffic will not trigger the defensive mechanism against replay attack.
Yep those requests have nothing to do with our protocol and are simply dropped.
@Mygod And what will you do if the banned IP performs more requests? This can be a character.
@wongsyrone No, it should be checked after authentication of the request header. Authentication must be done in the very first, which is the common practice. It makes no sense that someone is attacking with spam data which cannot pass the authentication.
I'm afraid you missed an important keyword in the definition. In a replay attack, the adversary sends a valid data stream. If decryption/authencation failed, the data stream is invalid, and it's not the concern of this proposal.
And you still misunderstood the intention of the Bloom filter. It solves exactly the problem of checking large amount of used salt while using little space. There's no need for a supercomputer.
Here are some updates for the new ping-pong bloom filter:
- The test parameters are: 1,000,000 entries, 1e-5 error rate.
- This test is performed on a server shared by a small startup (10~20 people) with chacha20-ietf-poly1305 cipher.
- In the three days test, no replay attack is observed according to the server log.
- No abnormal connection reset is observed locally.
- To verify that the bloom filter really works, I constructed several valid relay requests and all of them got identified as expected.
In summary, the bloom filter works much better than I thought. I think at least the short-term replay attack won't be a problem for us now.
@madeye Awesome!
There's one thing I'm curious about: have you measured the rate of connection establishment in such setting? It's a measure of how busy the server is. In other words, how often do we switch between the ping and pong filters? This is important because every time we switch, we lose half of the history. I'm interested in the time window of effective defense.
Additionally, we should probably also use the filter to protect UDP packets.