Deprecate stream ciphers with insufficient IV length

[riobard]

Summary

For Shadowsocks deployment using stream ciphers, long-term key and randomly generated IV of insufficient length causes (key, IV) pair reuse with high probability, which allows Reused Key Attack. Adversaries can recover plaintext within reasonable budget constraint.

Proposal

• Stream ciphers with IV length less than 12 bytes MUST be deprecated. Namely, bf-cfb, chacha20, and salsa20.
• Users SHOULD choose stream ciphers with IV length of 16 or more bytes.
• Users are RECOMMENDED to use the new AEAD ciphers.

[madeye]

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

[riobard]

I suggest we split this table https://shadowsocks.org/en/spec/cipher.html into four sections:

1. RECOMMEND for new AEAD ciphers.
2. PHASING OUT for stream ciphers with sufficient IV length and strong security.
3. DEPRECATED for stream ciphers not in 2 or 4.
4. DANGEROUS for stream ciphers with insufficient IV length and weak security.

[riobard]

Additionally, non-IETF variant of Chacha20-Poly1305 should also be removed right now in order to prevent widespread use.

[madeye]

A pull request? I'm OK with the change of that page.

[riobard]

Working on it.

Could you please kill chacha20-poly1305 so no one uses it? So I can remove it from that page and no need for future deprecation.

[madeye]

Fixed via shadowsocks/shadowsocks-libev@894eae5

[madeye]

OK, I think @wongsyrone is right about nonce reuse of chacha20. If we generate nonces properly, we're safe with 8 bytes nonce here.

@riobard What do you think?

[riobard]

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.

[madeye]

@riobard Thanks for the long explanation. So, the key point here is shadowsocks is using random nonce, leading to much larger posibility of nonce reuse?

The reason why TLS doesn't have this issue is that it exahanges keys at the beginining of a session and increases the nonce for each message. It ensures ephemeral keys and unique nonces?

[Mygod]

@madeye Correct.

@riobard Can you give an estimation about how many connections are safe against nonce reuse attack for different nonce length? Also nonce reuse attack is very expensive because adversary has to record all traffic to identify nonce collisions and recover underlying traffic. We can assume that it will only be used when targeting specific server so this problem isn't very severe if the underlying traffic doesn't need that kind of security.

[madeye]

Luckily, we still have chacha20-ietf-poly1305 and xchacha20-ietf-poly1305 here. Users can pick their favorite cipher from these two choices and won't blame us for lack of flexibilty... 👌

EDIT: To fix a typo.

[riobard]

@madeye Correct. To be more precise, the problem is we are using random nonce with insufficient length AND long-term key. The choice of long-term key is deliberate to avoid handshake (exposing protocol), thus the only remedy is to use longer nonce.

@Mygod As explained above, randomly generated 64-bit number has a birthday bound at 2^(64/2). So in the best case we can only encrypt (2^32)/2 chunks. In practice the collision could happen much earlier, and it's not acceptable to rely on the estimation because the safety margin is too thin.

nonce reuse attack is very expensive because adversary has to record all traffic to identify nonce collisions and recover underlying traffic

This is sadly not true in our case. Adversaries need to only record a couple of packets per TCP connection to the same server/port because the first few packets contain nonce in plaintext and Shadowsocks request header in ciphertext with known structure. The cost to perform a successful Reused Key Attack on stream ciphers with 64-bit nonce is actually very reasonable: ~10TB storage if my math is right.

[riobard]

@madeye You mean chacha20-ietf-poly1305 with 96-bit nonce. xchacha20-ietf-poly1305 is even better with its 192-bit nonce.

[madeye]

@riobard Yes, sorry for the typo.

[Mygod]

@riobard Sorry, I just realized there are two nonces here so let's use "IV" for the one used in stream cipher and "nonce" for the one used in authentication. The previous comment is talking about IV instead of nonce used in authentication.

About nonce reuse attack, I thought it's pretty hard to take advantage of. I didn't carefully read that paper but after skimming through it, it seems like nonce reuse attack can have a catastrophic effect because of the design flaws of the authentication algorithm. That's why we have a better algorithm using SIV.

[hellofwy]

Is TLS 1.3 good for using as the cipher method?
TLS 1.3 now support 1-RTT or even 0-RTT handshakes.
TLS 1.3 will be a widely used protocol, so Shadowsocks's traffic can't be recognized from others.

[riobard]

@Mygod Actually the name "nonce" is better, as it reminds us that it should be used only once. The term "IV" is technically more accurate for stream ciphers, but it looks too innocent and it's very easy for people to forget that it has to be unique per key.

In this discussion we can distinguish the two: nonce for AEAD and IV for stream ciphers.

There's no evidence that adversaries are launching Reused Key Attack (note: only stream ciphers are vulnerable to RKA). However I'd like to increase the cost of doing so by choosing longer IV sizes. Hopefully it will blow off the adversary's budget constraint.

SIV hasn't been widely adopted yet. Cryptoanalysis is also lacking. It'll be years before we'll consider it. We have only AES-GCM and chacha20-poly1305 variants right now, and the former has known weakness with nonce reuse. Better to be safe than sorry.

[riobard]

@hellofwy Obfuscation is a separate concern. The pluggable transport will address that.

[Mygod]

@hellofwy TLS provides better privacy but is harder to set up and is not random noise indistinguishable. Shadowsocks's traffic still can be identified from normal TLS connections by using certificate in TLS. Also 1/0-RTT handshakes are used to resume connections and reuse ephemeral key exchanged previously if I'm not mistaken.

@riobard So could you give an estimation of connections that should be safe (like >99.7% or larger?) for different IV sizes?

Yes. By using SIP003, we are putting the responsibility of obfuscation/steganography off for plugins.

[Mygod]

Okay just found a probability table. So by using 8 bytes for IV size, the chance of reusing IV is smaller than 10^-15 within only ~190 connections. For 12 bytes, the chance is smaller than 10^-15 within ~13 million connections.

For comparison, 10^-18 to 10^-15 is the uncorrectable bit error rate of a typical hard disk.

[riobard]

@Mygod Yes, that's the quick lookup table for all the math mentioned in this issue.

Now you see why 8-byte IV provides very thin safety margin.

[Mygod]

However it's hard to tell how much security we (and/or the user) need against this kind of attack. 10^-15 may be too strict since it is very unlikely that the adversary is able to record all traffic.

[riobard]

I don't think it's an active threat yet. Nevertheless we should be more careful. Increasing IV size incurs minimal cost. The cost/benefit analysis is straightforward.

[madeye]

@wongsyrone Cool!

I think @riobard teaches us a very important lesson about nonce-misuse issues. Thanks again for the info!

[riobard]

Glad to be helpful ^_^

[Mygod]

@wongsyrone AEAD isn't designed for TLS 1.3. What other downsides do you think SIP004 have?

[Mygod]

Hmm... Replay attack is also possible before SIP004 so maybe we should open a separate issue to discuss it?

[madeye]

An easy way to defend replay is using a timestamp as the AD of our AEAD, e.g. time() / 60 +/- 1. As we still have two reserved bits in the 16-bit length, one bit can be used as a flag to disable/enable this timestamp.

But I don't think it's really necessary. SIP004 aims to provide IND-CCA2 and replace OTA. At least, cheap attacks by modifying our request header won't work anymore. If we decide to deprecate OTA, then SIP004 is necessary to us.

[riobard]

Protection from replay attack is not the job of shadowsocks.

Statistical analysis of packet property can be obfuscated by pluggable transport.

[shinku721]

用AES时候的那个IV也是不能重复的，说到底是block cipher的时候叫IV，加上operation mode后第一个IV就是nonce了（因为部分mode比如CTR，有没有CFB我不记得了，实际上就是XOR搞出来的，和chacha的操作模式一样）
@riobard IMO shadowsocks should get rid of replaying requests
@madeye the timestamp is a reasonable idea with caching of nonces in the allowed time period

[madeye]

@shinku721 Yes, replay attack is still a open problem for us. Any suggestion?

[hellofwy]

@madeye
OTA's HMAC is calculated with a Chunk ID which is an unsigned integer counted per connection from 0. I think the Chunk ID may be useful for preventing some kinds of replay attacks.
And I think a server side request id cache may be be useful for preventing request replay attacks.

[shinku721]

@madeye

1. 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...)
2. 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...

@hellofwy We are focusing on replaying of the requests... And chunks must be replayed after the attacker replays the request.

[qinyuhang]

Do u mean a UTC timestamp？bad network will have affect on it？orGFW can just fake the one timestamp？ 二階堂 真紅 <notifications@github.com>于2017年2月11日 周六15:46写道：

…

@madeye <https://github.com/madeye> 1. 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...) 2. The server keeps recording valid incoming requests (by its IV or the seed in the AEAD 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... @hellofwy <https://github.com/hellofwy> We are focusing on replaying of the requests... And chunks must be replayed after the attacker replays the request. — You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub <#36 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/AF8zUSzzNzx_Sedoa1b0BOg6rdajZUz3ks5rbWdSgaJpZM4L3IDs> .

[hellofwy]

The time stamp part is encrypted and authenticated as other parts in AEAD ciphers, so can't be faked.

[qinyuhang]

I mean the verification ofof thetimestamp is too wide range，GFW pick 1s probably hit a 2 min range. This cannot work on a tream communication hellofwy <notifications@github.com>于2017年2月11日 周六17:49写道：

…

The time stamp part is encrypted and authenticated as other parts in AEAD ciphers, so can't be faked. — You are receiving this because you commented. Reply to this email directly, view it on GitHub <#36 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/AF8zUZ9OOSi03B4o1qFb4vY8fztASNMXks5rbYQsgaJpZM4L3IDs> .

[shinku721]

@qinyuhang GFW requests either a manipulated header or an original header.

• A manipulated header is not authenticated.
• An original header contains the unmodified timestamp.
  • If the timestamp is out of the allowed range (GFW replays the request after 2mins), it is rejected.
  • If the timestamp is in the range, since we have cached all valid requests in the range of time, it is found to be a duplicate. So we reject it, too.

[riobard]

This thread is getting off-topic.

I've opened a new issue to discuss replay attack #44

[riobard]

Closing now that we have cipher guidance.