Session key with counting nonce or short IV

[riobard]

In #36 I explained why using long-term key with short random nonce is a bad idea. Later in that discussion @wongsryone raised the issue that higher entropy consumption of SIP004 might be problematic on some VM and embedded devices.

Well, technically we are not consuming entropy faster in SIP004 as we are still generating one random number per TCP connection. However we are consuming available nonce space at a much faster pace because we're incrementing it as a counter twice per chunk, effectively increasing the probability of (key, nonce) pair reuse by a few orders of magnitude.

Now I think this is a design flaw which could be avoided by a minor change.

---

In #36 I proposed to deprecate ciphers with short nonce/IV to increase available nonce space. Unfortunately it eliminated some nice ciphers like chacha20 and chacha20-poly1305 (8-byte nonce/IV).

Actually there's a better way.

---

Instead, we could generate a random session key and encrypt it using the pre-shared key (with random nonce/IV if AEAD/stream cipher) and send it at the beginning of a connection. We then use the session key to encrypt the rest of the connection. As a result:

• For stream ciphers, random IV is no longer necessary (but we could still use one) because the key is random.
• For AEAD ciphers, random nonce is also no longer necessary, and we can use a simple counter from zero as nonce.

Since key size is usually longer than nonce/IV, we are free to use ciphers with short nonce/IV. We're looking at 128-bit randomness at least and 256-bit for chacha20, instead of 64-bit or 96-bit nonce/IV. Much, much larger space.

To summarize, here is a structure of a connection encrypted by a stream cipher

[fixed-length random IV to encrypt session key]
[fixed-length encrypted session key using pre-shared key and the random IV above]
[variable-length encrypted content using the session key above with optional IV]

And the structure of a connection encrypted by an AEAD cipher

[fixed-length random nonce]
[fixed-length encrypted session key using pre-shared key and the random nonce above]
[fixed-length tag]

[fixed-length encrypted payload length using session key and nonce 0]
[fixed-length encrypted payload length tag]
[variable-length encrypted payload using session key and nonce 1]
[fixed-length encrypted payload tag]

[fixed-length encrypted payload length using session key and nonce 2]
[fixed-length encrypted payload length tag]
[variable-length encrypted payload using session key and nonce 3]
[fixed-length encrypted payload tag]

...

[madeye]

It looks a good proposal. but I don't think it's really necessary for now.

With a strong password or a random key, current AEADs are able to protect our users, since most of them just want a tunnel through firewall.

I suggest to keep this issue open and implement it as new ciphers in your fork first (e.g. session-key-aes-128-gcm). If it's proven to be necessary in the future, we should make it as a new SIP.

[riobard]

Sure.

The idea just came to my mind today and I wanted to share it here for feedback.

[v2ray]

Welcome to be one step closer to VMess protocol.

How about adding an 'option' field for the type of cipher, so that server can handle multiple ciphers on a single port? lol

[Mygod]

There's a much simpler solution: longer nonce.

[Mygod]

Since using ephemeral key doesn't grant us forward secrecy at all, what you're really doing here is just replacing key in the equation with another random nonce. We can as well use nonce concatenating a serial number as a longer nonce to use. Problem solved.

[v2ray]

Forward secrecy is another thing. The issue here is talking about nonce reuse. It is true that the second key doesn't provide forward secrecy, but it indeed fixes the nonce issue.

[Mygod]

It doesn't. You now have a ephemeral key reuse problem.

[riobard]

@Mygod Yes, using longer nonce is indeed equivalent. The practical concern is that many ciphers have fixed nonce length that cannot be changed.

[v2ray]

If I understand correctly, nonce size always equals to the block size in stream ciphers. Ciphers like AES-GCM accepts longer nonce, but it get normalized into its standard size. Longer nonce doesn't increase the randomness.

[riobard]

@v2ray Do you have any analysis about the nonce handling in AES-GCM? I haven't found anything about longer nonces. I'd like to understand if there is indeed weakness. Thanks!

[v2ray]

Golang's source code of GCM refers to NIST SP 800-38D, section 7.1. From what I can tell, GCM always uses a 16 byte nonce (or 'counter' in GCM's term).

[riobard]

Thanks for the pointer! Actually section 8 gives a very detailed requirement on IVs and keys. I'm now convinced that the way SIP004 uses GCM is indeed flawed. Specifically, section 8.2 echoes my concern at the beginning of the thread.

[Mygod]

Hmmmmm I see. I wonder if we can use a single nonce for a connection by somehow seeking output stream/changing sequence number.

[riobard]

@Mygod It's not helpful if the process is deterministic and the nonce is repeated…

[Mygod]

@riobard Think of this process as encrypting a longer plaintext and inserting authentication tag in the middle of it. This is kind of a mix of AEAD and the old OTA approach.

[riobard]

How exactly do you get around the nonce reuse problem?

[Mygod]

It uses only one nonce per connection or until the internal counter depletes which reduces the chance of nonce collisions.

[Mygod]

As you can see, both aes-gcm and chacha20 has an internal counter which is obviously never going to get depleted in our case since we limited single payload length within 0x3FFF bytes. We can really use that.

[v2ray]

I am afraid that the counter itself is part of the nonce, e.g, GCM takes a 12-byte nonce from input, combines its own 4-byte counter and form a 16-byte nonce. So the 'reuse' problem can't be solved by this approach.

[Mygod]

It doesn't. Neither does the ephemeral key. It uses internal counter for additional nonce space. On that note, we can probably also use some part of key for an even longer nonce.

I'm personally against ephemeral key because it introduces another encryption/decryption (more risk) with only the benefit of reduced nonce collision possibility.

[Mygod]

Keep in mind we're still using one nonce per connection to encrypt and authenticate the much longer session key. For chacha20-ietf-poly1305:

• Additional data transmitted: 76 bytes
• Benefits: Use only one nonce per connection (nonce space is still 96 bit)
• Also comes with the risk in using ephemeral key, etc.

This solution is way too ugly and inefficient.

[v2ray]

Neither does the ephemeral key.

Ephemeral key provides 16 (key) + 16 (nonce) bytes of space. It is much larger than nonce (16 byte) itself. Personally I do believe 16 byte is enough. But under the context of this issue, there is nothing wrong to increase it.

Additional data transmitted: 76 bytes

Given that a typical HTTP header size is ~700 bytes, 76 bytes is not an issue. (Although I am not sure where the number 76 bytes comes from)

Also comes with the risk in using ephemeral key, etc.

Bottom line is security doesn't become worse with this approach.

[Mygod]

1. Don't forget you need to transmit the session key itself. You don't suppose it's safely transferred. The rest of the data is safe only if the session key is safe. I think you're just missing the point here.
2. "Additional" 76 bytes. Also if 700 bytes are negligible, why HTTP/2?
3. Prove it. The security becomes worse because the safety of your algorithm now depends on more stuff that can get compromised. Also now you have more stuff to collide with each other.
4. Also this is against KISS.

[v2ray]

The session key is encrypted in the same way as other data gets encrypted in Shadowsocks. If you believe the session key is crackable somehow, same for other data. This basically makes the whole Shadowsocks protocol pointless.

There is no need to prove something "don't" exist. If you believe there is an additional attack vector, please elaborate.

[madeye]

@riobard I'm wondering is it still safe if nonce reuse happens for the first chunk? It seems that the probability of nonce reuse of this proposal equals to our current stream cipher approaches.

[Mygod]

@madeye Thank you. That's exactly what I was talking about.

[riobard]

I think it's still safe.

In order for Reused Key Attack to be successful, the adversary needs to understand the statistical property of the payload before they can deduce anything useful from the XOR'ed result of two ciphertext using the same (key, nonce) pair.

In this proposal, the payload in the first chunk is a random key. If the CSRNG to generate that key is of high quality, there should not be any statistical bias.

[riobard]

In case of AES-GCM, nonce reuse is vulnerable to the Forbidden Attack, which allows adversaries to forge messages. To defend against such attack, the random session key should be derived from the pre-shared key, for example by using HKDF

session key = HKDF(pre-shared key, random bits)

So instead of encrypting the session key directly in the first chunk, we encrypt the random bits and send the encrypted output. The receiving side should decrypt the random bits first and use it to produce the actual session key to decrypt the rest chunks.

In the extreme case that (pre-shared key, nonce) pair reuse leaking the plaintext of the first chunk, the second HKDF mechanism ensures adversary cannot forge a session key without knowing the pre-shared key.

[riobard]

Thanks for the feedback, I think this proposal is getting better! 👍

[riobard]

Actually, instead of sending an initial random string as nonce to encrypt the first chunk, a simpler construction would be to use that random string as input to the HKDF to derive the session key directly. This provides the same security as the revised proposal in #40 (comment)

[madeye]

use that random string as input to the HKDF to derive the session key directly. This provides the same security as the revised proposal in #40 (comment)

It sounds interesting.

[Mygod]

@riobard This is really similar to what I proposed, i.e. use part of the key as additional nonce space.

[riobard]

Yeah, let's continue thinking on this direction and see if there's any issue. I'm summarizing the revised protocol below:

For stream ciphers

[fixed-length random bits to derive session key]
[variable-length encrypted content using the session key with optional IV]

For AEAD ciphers

[fixed-length random bits to derive session key]

[fixed-length encrypted payload length using session key and nonce 0]
[fixed-length encrypted payload length tag]
[variable-length encrypted payload using session key and nonce 1]
[fixed-length encrypted payload tag]

[fixed-length encrypted payload length using session key and nonce 2]
[fixed-length encrypted payload length tag]
[variable-length encrypted payload using session key and nonce 3]
[fixed-length encrypted payload tag]
...

[riobard]

An unintentional benefit of using HKDF to derive session key from pre-shared key is that even if the pre-shared key is weak, the derived session key would be cryptographically strong.

I like the new construction even better now! :)

[madeye]

So, HKDF is used like this?

session key = HKDF(nonce, pre-shared key)

[riobard]

Yes. The "nonce" would be used salt to HKDF.

[Mygod]

Okay. I think it's best to deprecate this proposal and SIP006 and use HKDF. Now we should discuss nonce size next.

[madeye]

I just found it's quite similar to the nonce extension suggested by libsodium for chacha20-poly1305: https://download.libsodium.org/doc/key_derivation/

[riobard]

This and SIP006 are two related but slightly different issues. SIP006 attempts to solve the weak pre-shared key problem by preventing popular passwords.

We still have to generate a pre-shared key anyway. With the changes proposed here, derived session keys will be strong even if the pre-shared key is weak. Ideally we want both to be strong.

[Mygod]

OK.

[riobard]

@madeye Yes, the principle is the same, basically we need to move from (PSK, short nonce) pair to (PRF(PSK, salt), short nonce) pair to significantly increase useful randomness.

[riobard]

This is why the extended xsalsa20 and xchacha20 are reasonably safe.

[madeye]

Great! I suggest to file a new SIP. We can discuss more details there.

[riobard]

Sure! I'll open a new issue later.

[riobard]

Formalized as SIP007 in #42