ChaCha20 Rekey Frequency

[Damien Miller]

On Wed, 29 Mar 2023, Chris Rapier wrote:

> I was wondering if there was something specific to the internal chacha20
> cipher as opposed to OpenSSL implementation.
> 
> I can't just change the block size because it breaks compatibility. I can do
> something like as a hack (though it would probably be better to do it with the
> compat function):
> 
> 	if (strstr(enc->name, "chacha"))
> 	        *max_blocks = (u_int64_t)1 << (16*2);
> 	else if (enc->block_size >= 16)
> 		*max_blocks = (u_int64_t)1 << (enc->block_size*2);
> 	else
> 		*max_blocks = ((u_int64_t)1 << 30) / enc->block_size;
> 	if (state->rekey_limit)
> 
> to force it to reduce the rekey rate but I'm deeply unsure of what impact that
> would have on the security of the cipher as it's implemented. Especially the
> without-openssl internal implementation.

This is what I'm playing with at the moment:

diff --git a/cipher.c b/cipher.c
index c7664a3..ec6fa4f 100644
--- a/cipher.c
+++ b/cipher.c
@@ -150,6 +150,39 @@ cipher_blocksize(const struct sshcipher *c)
 	return (c->block_size);
 }
 
+uint64_t
+cipher_rekey_blocks(const struct sshcipher *c)
+{
+	/*
+	 * Chacha20-Poly1305 does not benefit from data-based rekeying,
+	 * per "The Security of ChaCha20-Poly1305 in the Multi-user Setting",
+	 * Degabriele, J. P., Govinden, J, Gunther, F. and Paterson K.
+	 * ACM CCS 2021; https://eprint.iacr.org/2023/085.pdf
+	 *
+	 * Cryptanalysis aside, we do still want do need to prevent the SSH
+	 * sequence number wrapping and also to rekey to provide some
+	 * protection for long lived sessions against key disclosure at the
+	 * endpoints, so arrange for rekeying every 2**32 blocks as the
+	 * 128-bit block ciphers do (i.e. every 32GB data).
+	 */
+	if ((c->flags & CFLAG_CHACHAPOLY) != 0)
+		return (uint64_t)1 << 32;
+	/*
+	 * The 2^(blocksize*2) limit is too expensive for 3DES,
+	 * so enforce a 1GB data limit for small blocksizes.
+	 * See discussion in RFC4344 section 3.2.
+	 */
+	if (c->block_size < 16)
+		return ((uint64_t)1 << 30) / c->block_size;
+	/*
+	 * Otherwise, use the RFC4344 s3.2 recommendation of 2**(L/4) blocks
+	 * before rekeying where L is the blocksize in bits.
+	 * Most other ciphers have a 128 bit blocksize, so this equates to
+	 * 2**32 blocks / 64GB data.
+	 */
+	return (uint64_t)1 << (c->block_size * 2);
+}
+
 u_int
 cipher_keylen(const struct sshcipher *c)
 {
diff --git a/cipher.h b/cipher.h
index 1a591cd..68be9ed 100644
--- a/cipher.h
+++ b/cipher.h
@@ -63,6 +63,7 @@ int	 cipher_get_length(struct sshcipher_ctx *, u_int *, u_int,
     const u_char *, u_int);
 void	 cipher_free(struct sshcipher_ctx *);
 u_int	 cipher_blocksize(const struct sshcipher *);
+uint64_t cipher_rekey_blocks(const struct sshcipher *);
 u_int	 cipher_keylen(const struct sshcipher *);
 u_int	 cipher_seclen(const struct sshcipher *);
 u_int	 cipher_authlen(const struct sshcipher *);
diff --git a/packet.c b/packet.c
index a71820f..377f608 100644
--- a/packet.c
+++ b/packet.c
@@ -55,6 +55,7 @@
 #include <poll.h>
 #include <signal.h>
 #include <time.h>
+#include <util.h>
 
 #ifdef WITH_ZLIB
 #include <zlib.h>
@@ -850,6 +851,7 @@ ssh_set_newkeys(struct ssh *ssh, int mode)
 	const char *wmsg;
 	int r, crypt_type;
 	const char *dir = mode == MODE_OUT ? "out" : "in";
+	char blocks_s[FMT_SCALED_STRSIZE], bytes_s[FMT_SCALED_STRSIZE];
 
 	debug2_f("mode %d", mode);
 
@@ -917,20 +919,18 @@ ssh_set_newkeys(struct ssh *ssh, int mode)
 		}
 		comp->enabled = 1;
 	}
-	/*
-	 * The 2^(blocksize*2) limit is too expensive for 3DES,
-	 * so enforce a 1GB limit for small blocksizes.
-	 * See RFC4344 section 3.2.
-	 */
-	if (enc->block_size >= 16)
-		*max_blocks = (u_int64_t)1 << (enc->block_size*2);
-	else
-		*max_blocks = ((u_int64_t)1 << 30) / enc->block_size;
+	*max_blocks = cipher_rekey_blocks(enc->cipher);
 	if (state->rekey_limit)
 		*max_blocks = MINIMUM(*max_blocks,
 		    state->rekey_limit / enc->block_size);
-	debug("rekey %s after %llu blocks", dir,
-	    (unsigned long long)*max_blocks);
+
+	strlcpy(blocks_s, "?", sizeof(blocks_s));
+	strlcpy(bytes_s, "?", sizeof(bytes_s));
+	if (*max_blocks * enc->block_size < LLONG_MAX) {
+		fmt_scaled((long long)*max_blocks, blocks_s);
+		fmt_scaled((long long)*max_blocks * enc->block_size, bytes_s);
+	}
+	debug("rekey %s after %s blocks / %sB data", dir, blocks_s, bytes_s);
 	return 0;
 }