shadowsocks-org: Deprecate stream ciphers with insufficient IV length

Sorry if this sounds offending, but @wongsyrone is completely wrong and misunderstands the libsodium document (which is NOT the best source of security advices by the way).

I’d suggest you read DJB’s paper on Xsalsa20 to gain more understanding.

Let me explain in a bit more details. Hopefully we could settle this argument once and for all.

TLDR

• Chacha20, even with only 64-bit nonce, is safe if used properly with ephemeral keys and unique nonces.
• However Shadowsocks uses long-term key and random nonces, thus it’s dangerous to use Chacha20 as the probability of nonce collision is significant.
• Long-term keys with duplicated nonces are vulnerable to Reused Key Attack, allowing adversaries to recover portions of plaintext, and in the context of Shadowsocks, identify the underlying protocol.
• Thus short nonces pose significant threat to the primary design goal of Shadowsocks: being indistinguishible from noises.

Stream ciphers

Stream ciphers generate a key stream to XOR with plaintext to get ciphertext. Generation of key stream is a deterministic process: for a given (key, nonce) pair, the same key stream is produced.

Proper use of stream ciphers must ensure every (key, nonce) pair is unique. Usually we satisfy this requirement by generating a random, ephemeral key and using a monotonic counter value as nonce. Chacha20 uses 256-bit keys and 64-bit nonces. A randomly generated 256-bit key is extremely likely to be unique. We then use a monotonic incrementing 64-bit counter as nonce to form a unique 320-bit (key, nonce) pair, which contains 256-bit randomness. This allows 2^64 messages to be safely encrypted using the same key.

However, in Shadowsocks we use a fixed long-term key and randomly generated nonces, basicaly inverting the randomness property described above. Now we still have a 320-bit (key, nonce) pair, but only 64-bit randomness.

The probability of duplicates while generating 64-bit random nonces is extremely high (about 1/2^32, see Birthday Attack). In practice, no one should ever assume a 64-bit random number to be unique.

AEAD ciphers

The case for nonce reuse with AEAD ciphers is more complicated and the consequences vary depending on AEAD construction. Some new AEAD ciphers are resistant to nonce reuse (so called misuse-resistant ciphers), claiming that if a (key, nonce) pair is reused, full security is still obtained (for example GCM-SIV).

Shadowsocks currently supports AES-GCM and three variants of chacha20-poly1305 AEAD ciphers. AES-GCM ciphers have already been demonstrated to be vulnerable to nonce reuse with practical attacks on GCM in TLS (see GCM-TLS). For chacha20-poly1305, nonce reuse causes loss of confidentiality for messages with that nonce.

The catch is that we are exhausting nonces at much higher rate using Shadowsocks AEAD ciphers. With the original stream ciphers, we use only one nonce/IV per TCP connection (or UDP packet). With AEAD ciphers, each TCP connection is broken up into records (or chunks), and each record/chunk uses two nonces (one for encrypting payload length and one for payload itself). Assuming maximum payload size of 16KB (best case), we are exhausting 128 nonces for every megabyte of traffic carried. 64-bit nonce space will not last long before duplicates occur.

---

Cryptography is tough and security is hard. Don’t be trapped by dogma. Think carefully.

I think we can show warnings, but not deprecate them.