Package: release.debian.org
Severity: normal
Tags: bullseye
User: release.debian....@packages.debian.org
Usertags: pu
[ Reason ]
cyrus-imapd before 3.2.8 allows remote attackers to cause a denial of
service (multiple-minute daemon hang) via input that is mishandled
during hash-table interaction. Because there are many insertions into
a single bucket, strcmp becomes slow. This is fixed in 3.4.2, 3.2.8,
and 3.0.16.
[ Impact ]
Medium vulnerability
[ Tests ]
The new cunit/strhash.testc passed.
[ Risks ]
Low risk, patch is easy to read
[ Checklist ]
[X] *all* changes are documented in the d/changelog
[X] I reviewed all changes and I approve them
[X] attach debdiff against the package in (old)stable
[X] the issue is verified as fixed in unstable
[ Changes ]
New string hashing algorithm and test.
Cheers,
Yadd
diff --git a/debian/changelog b/debian/changelog
index c8259297..bd11af8d 100644
--- a/debian/changelog
+++ b/debian/changelog
@@ -1,3 +1,9 @@
+cyrus-imapd (3.2.6-2+deb11u1) bullseye; urgency=medium
+
+ * Replace string hashing algorithm (Closes: #993433, CVE-2021-33582)
+
+ -- Yadd <y...@debian.org> Wed, 01 Sep 2021 07:58:38 +0200
+
cyrus-imapd (3.2.6-2) unstable; urgency=medium
* Update gbp.conf for Bullseye branch
diff --git a/debian/control b/debian/control
index 3a4556b0..9b31670e 100644
--- a/debian/control
+++ b/debian/control
@@ -3,7 +3,7 @@ Maintainer: Debian Cyrus Team <team+cy...@tracker.debian.org>
Uploaders: Henrique de Moraes Holschuh <h...@debian.org>,
Ondřej Surý <ond...@debian.org>,
Anthony Prades <toony.deb...@chezouam.net>,
- Xavier Guimard <y...@debian.org>
+ Yadd <y...@debian.org>
Section: mail
Priority: optional
Build-Depends: bison,
diff --git a/debian/patches/CVE-2021-33582.patch
b/debian/patches/CVE-2021-33582.patch
new file mode 100644
index 00000000..af48b338
--- /dev/null
+++ b/debian/patches/CVE-2021-33582.patch
@@ -0,0 +1,632 @@
+Description: Fixed CVE-2021-33582
+ Certain user inputs are used as hash table keys during processing. A
+ poorly chosen string hashing algorithm meant that the user could control
+ which bucket their data was stored in, allowing a malicious user to direct
+ many inputs to a single bucket. Each subsequent insertion to the same bucket
+ requires a strcmp of every other entry in it. At tens of thousands of
+ entries, each new insertion could keep the CPU busy in a strcmp loop for
+ minutes.
+ .
+ The string hashing algorithm has been replaced with a better one, and now
+ also uses a random seed per hash table, so malicious inputs cannot be
+ precomputed.
+ .
+ Discovered by Matthew Horsfall, Fastmail
+Author: ellie timoney <el...@fastmail.com>
+Origin: upstream,
https://github.com/cyrusimap/cyrus-imapd/compare/cyrus-imapd-3.2.7...cyrus-imapd-3.2.8
+Bug: https://security-tracker.debian.org/tracker/CVE-2021-33582
+Forwarded: not-needed
+Reviewed-By: Yadd <y...@debian.org>
+Last-Update: 2021-09-01
+
+--- a/Makefile.am
++++ b/Makefile.am
+@@ -677,6 +677,7 @@
+ cunit/squat.testc \
+ cunit/strarray.testc \
+ cunit/strconcat.testc \
++ cunit/strhash.testc \
+ cunit/times.testc \
+ cunit/tok.testc \
+ cunit/vparse.testc
+--- a/configure.ac
++++ b/configure.ac
+@@ -191,7 +191,7 @@
+
+ AC_CHECK_HEADERS(unistd.h sys/select.h sys/param.h stdarg.h)
+ AC_REPLACE_FUNCS(memmove strcasecmp ftruncate strerror posix_fadvise strsep
memmem memrchr)
+-AC_CHECK_FUNCS(strlcat strlcpy strnchr getgrouplist fmemopen pselect futimens
futimes)
++AC_CHECK_FUNCS(strlcat strlcpy strnchr getgrouplist fmemopen pselect futimens
futimes getline)
+ AC_HEADER_DIRENT
+
+ dnl check whether to use getpassphrase or getpass
+--- a/cunit/hash.testc
++++ b/cunit/hash.testc
+@@ -117,6 +117,9 @@
+ hash_enumerate(&ht, count_cb, &count);
+ CU_ASSERT_EQUAL(0, count);
+
++ /* check hash_numrecords */
++ CU_ASSERT_EQUAL(0, hash_numrecords(&ht));
++
+ /* free the hash table */
+ free_hash_table(&ht, NULL);
+ }
+@@ -146,6 +149,9 @@
+ hash_enumerate(&ht, count_cb, &count);
+ CU_ASSERT_EQUAL(1, count);
+
++ /* check hash_numrecords */
++ CU_ASSERT_EQUAL(1, hash_numrecords(&ht));
++
+ /* re-insert into the hash table */
+ d = hash_insert(KEY0, VALUE1, &ht);
+ /* get the old value back */
+@@ -160,6 +166,9 @@
+ hash_enumerate(&ht, count_cb, &count);
+ CU_ASSERT_EQUAL(1, count);
+
++ /* check hash_numrecords */
++ CU_ASSERT_EQUAL(1, hash_numrecords(&ht));
++
+ /* delete from the hash table */
+ d = hash_del(KEY0, &ht);
+ CU_ASSERT_PTR_EQUAL(VALUE1, d);
+@@ -173,6 +182,9 @@
+ hash_enumerate(&ht, count_cb, &count);
+ CU_ASSERT_EQUAL(0, count);
+
++ /* check hash_numrecords */
++ CU_ASSERT_EQUAL(0, hash_numrecords(&ht));
++
+ /* free the hash table */
+ free_hash_table(&ht, NULL);
+ }
+@@ -239,6 +251,9 @@
+ hash_enumerate(&ht, count_cb, &count);
+ CU_ASSERT_EQUAL(N, count);
+
++ /* check hash_numrecords */
++ CU_ASSERT_EQUAL(N, hash_numrecords(&ht));
++
+ /* delete from the hash table */
+ for (i = 0 ; i < N ; i++) {
+ d = hash_del(key(i), &ht);
+@@ -256,6 +271,9 @@
+ hash_enumerate(&ht, count_cb, &count);
+ CU_ASSERT_EQUAL(0, count);
+
++ /* check hash_numrecords */
++ CU_ASSERT_EQUAL(0, hash_numrecords(&ht));
++
+ /* free the hash table */
+ freed_count = 0;
+ free_hash_table(&ht, lincoln);
+@@ -286,6 +304,9 @@
+ hash_enumerate(&ht, count_cb, &count);
+ CU_ASSERT_EQUAL(N, count);
+
++ /* check hash_numrecords */
++ CU_ASSERT_EQUAL(N, hash_numrecords(&ht));
++
+ /* free the hash table */
+ freed_count = 0;
+ free_hash_table(&ht, lincoln);
+--- /dev/null
++++ b/cunit/strhash.testc
+@@ -0,0 +1,230 @@
++#include <config.h>
++
++#include <sys/types.h>
++#include <sys/stat.h>
++
++#include <errno.h>
++#include <stdio.h>
++#include <stdlib.h>
++#include <string.h>
++#include <unistd.h>
++
++#include "cunit/cyrunit.h"
++#include "lib/util.h"
++#include "lib/strhash.h"
++
++extern int verbose;
++
++static const char *repeat(int c, unsigned n)
++{
++ static char buf[1024];
++ char *p = buf;
++
++ /* always leave room for a \0 */
++ if (n >= sizeof(buf))
++ n = sizeof(buf) - 1;
++
++ memset(buf, 0, sizeof(buf));
++ while (n--) {
++ *p++ = c;
++ }
++
++ return buf;
++}
++
++static void test_repeated(void)
++{
++ /* repeated chars on the end should not obliterate earlier input */
++ unsigned suffix_lengths[] = { 15, 31, 63, 127, 255, 511, 1023 };
++ unsigned i;
++
++ for (i = 0; i < sizeof(suffix_lengths) / sizeof(suffix_lengths[0]); i++) {
++ char *cat = strconcat("cat", repeat('a', suffix_lengths[i]), NULL);
++ char *dog = strconcat("dog", repeat('a', suffix_lengths[i]), NULL);
++ char *mouse = strconcat("mouse", repeat('a', suffix_lengths[i]),
NULL);
++
++ unsigned xcat = strhash(cat);
++ unsigned xdog = strhash(dog);
++ unsigned xmouse = strhash(mouse);
++
++ CU_ASSERT_NOT_EQUAL(xcat, xdog);
++ CU_ASSERT_NOT_EQUAL(xdog, xmouse);
++ CU_ASSERT_NOT_EQUAL(xmouse, xcat);
++
++ free(cat);
++ free(dog);
++ free(mouse);
++ }
++}
++
++static void test_seeded(void)
++{
++ const char *const words[] = { "lorem", "ipsum", "dolor", "sit", "amet" };
++ const size_t n_words = sizeof(words) / sizeof(words[0]);
++ unsigned hashes[n_words];
++ unsigned i, j;
++
++ memset(hashes, 0, sizeof(hashes));
++
++ /* with no seed, same input should produce same hash */
++ for (i = 0; i < n_words; i++) {
++ unsigned h1 = strhash(words[i]);
++ unsigned h2 = strhash(words[i]);
++ CU_ASSERT_EQUAL(h1, h2);
++ }
++
++ /* with explicit zero seed, same input should produce same hash */
++ for (i = 0; i < n_words; i++) {
++ unsigned h1 = strhash(words[i]);
++ unsigned h2 = strhash_seeded(0, words[i]);
++ unsigned h3 = strhash_seeded(0, words[i]);
++ CU_ASSERT_EQUAL(h1, h2);
++ CU_ASSERT_EQUAL(h2, h3);
++ CU_ASSERT_EQUAL(h3, h1);
++ }
++
++ /* with some seed, same input should produce same hash */
++ for (j = 0; j < 5; j++) {
++ uint32_t seed;
++ do {
++ seed = rand();
++ } while (seed == 0);
++
++ for (i = 0; i < n_words; i++) {
++ unsigned h1 = strhash_seeded(seed, words[i]);
++ unsigned h2 = strhash_seeded(seed, words[i]);
++ CU_ASSERT_EQUAL(h1, h2);
++ }
++ }
++
++ /* with different seed, same input should produce different hash */
++ for (i = 0; i < n_words; i++) {
++ uint32_t seed1, seed2;
++ do {
++ seed1 = rand();
++ seed2 = rand();
++ } while (seed1 == 0 || seed2 == 0 || seed1 == seed2);
++
++ unsigned h1 = strhash_seeded(seed1, words[i]);
++ unsigned h2 = strhash_seeded(seed2, words[i]);
++
++ CU_ASSERT_NOT_EQUAL(h1, h2);
++ }
++}
++
++/* We can't define-out an entire test function when a feature is missing
++ * (in this case getline), because it confuses cunit.pl. So instead we
++ * make sure it will at least compile, but then return early without doing
++ * anything if the feature we wanted was missing.
++ */
++#ifndef HAVE_GETLINE
++#define getline(a,b,c) (((void)(b)), -1)
++#endif
++
++#define NBUCKETS (0x10000)
++static void test_quality(void)
++{
++ const char *wordsfile = "/usr/share/dict/words";
++ unsigned buckets[NBUCKETS] = {0};
++ FILE *stream;
++ char *line = NULL;
++ size_t len = 0;
++ ssize_t nread;
++ unsigned i;
++ unsigned inputs = 0;
++ unsigned contains_none = 0;
++ unsigned contains_one = 0;
++ unsigned contains_many = 0;
++ unsigned contains_many_sum = 0;
++ unsigned highest_count = 0;
++ unsigned highest_count_freq = 0;
++ unsigned max_acceptable_count;
++ double load;
++
++#ifndef HAVE_GETLINE
++ /* can't do anything anyway */
++ return;
++#endif
++
++ stream = fopen(wordsfile, "r");
++ if (!stream) {
++ if (verbose)
++ fprintf(stderr, "%s: %s (skipping) ", wordsfile, strerror(errno));
++ return;
++ }
++
++ while ((nread = getline(&line, &len, stream)) != -1) {
++ /* chomp */
++ if (line[nread - 1] == '\n')
++ line[nread - 1] = '\0';
++
++ unsigned hash = strhash_seeded_djb2(0, line) % NBUCKETS;
++
++ buckets[hash]++;
++ inputs++;
++ }
++ free(line);
++
++ /* arbitrary declaration of quality: no buckets should have more
++ * than ten times the expected load
++ */
++ load = inputs * 1.0 / NBUCKETS;
++ max_acceptable_count = load * 10;
++
++ unsigned bucket_counts[max_acceptable_count + 2];
++ memset(bucket_counts, 0, sizeof(bucket_counts));
++
++ for (i = 0; i < NBUCKETS; i++) {
++ switch (buckets[i]) {
++ case 0:
++ contains_none++;
++ break;
++ case 1:
++ contains_one++;
++ break;
++ default:
++ contains_many++;
++ contains_many_sum += buckets[i];
++ break;
++ }
++
++ if (buckets[i] > max_acceptable_count) {
++ bucket_counts[max_acceptable_count+1]++;
++ }
++ else {
++ bucket_counts[buckets[i]]++;
++ }
++
++ if (buckets[i] > highest_count) {
++ highest_count = buckets[i];
++ highest_count_freq = 1;
++ }
++ else if (buckets[i] == highest_count) {
++ highest_count_freq++;
++ }
++ }
++
++ if (verbose) {
++ putc('\n', stderr);
++ fprintf(stderr, "buckets: %u inputs: %u load: %g\n",
++ NBUCKETS, inputs, load);
++ fprintf(stderr, "empty: %u unique: %u busy: %u\n",
++ contains_none, contains_one, contains_many);
++ fprintf(stderr, "avg count in busy buckets: %g\n",
++ contains_many_sum * 1.0 / contains_many);
++ fprintf(stderr, "busiest %u buckets contain %u each\n",
++ highest_count_freq, highest_count);
++ fprintf(stderr, "max acceptable count: %u\n", max_acceptable_count);
++ fprintf(stderr, "\nbucket count histogram:\ncount frequency\n");
++ for (i = 0; i <= max_acceptable_count; i++) {
++ fprintf(stderr, "%4u %u\n", i, bucket_counts[i]);
++ }
++ fprintf(stderr, "%4u+ %u\n", max_acceptable_count + 1,
++ bucket_counts[max_acceptable_count + 1]);
++ }
++
++ CU_ASSERT_EQUAL(bucket_counts[max_acceptable_count + 1], 0);
++}
++#undef NBUCKETS
++
++/* vim: set ft=c: */
+--- a/imap/http_dav.c
++++ b/imap/http_dav.c
+@@ -2678,13 +2678,10 @@
+
+ if (!propstat) {
+ /* Prescreen "property" request */
+- if (fctx->req_tgt->collection ||
+- (fctx->req_tgt->userid && fctx->depth >= 1) || fctx->depth >= 2) {
+- /* Add namespaces for possible privileges */
+- ensure_ns(fctx->ns, NS_CYRUS, fctx->root, XML_NS_CYRUS, "CY");
+- if (fctx->req_tgt->namespace->id == URL_NS_CALENDAR) {
+- ensure_ns(fctx->ns, NS_CALDAV, fctx->root, XML_NS_CALDAV,
"C");
+- }
++ /* Add namespaces for possible privileges */
++ ensure_ns(fctx->ns, NS_CYRUS, fctx->root, XML_NS_CYRUS, "CY");
++ if (fctx->req_tgt->namespace->id == URL_NS_CALENDAR) {
++ ensure_ns(fctx->ns, NS_CALDAV, fctx->root, XML_NS_CALDAV, "C");
+ }
+
+ return 0;
+@@ -6047,7 +6044,7 @@
+ xmlDocPtr indoc = NULL, outdoc = NULL;
+ xmlNodePtr root, cur = NULL, props = NULL;
+ xmlNsPtr ns[NUM_NAMESPACE];
+- struct hash_table ns_table = { 0, NULL, NULL };
++ struct hash_table ns_table = HASH_TABLE_INITIALIZER;
+ struct propfind_ctx fctx;
+
+ memset(&fctx, 0, sizeof(struct propfind_ctx));
+@@ -8011,7 +8008,7 @@
+ xmlNodePtr inroot = NULL, outroot = NULL, cur, prop = NULL, props = NULL;
+ const struct report_type_t *report = NULL;
+ xmlNsPtr ns[NUM_NAMESPACE];
+- struct hash_table ns_table = { 0, NULL, NULL };
++ struct hash_table ns_table = HASH_TABLE_INITIALIZER;
+ struct propfind_ctx fctx;
+
+ memset(&fctx, 0, sizeof(struct propfind_ctx));
+--- a/imap/jmap_mail.c
++++ b/imap/jmap_mail.c
+@@ -4044,7 +4044,7 @@
+ memset(&touched_ids, 0, sizeof(hash_table));
+ construct_hash_table(&touched_ids, mdcount + 1, 0);
+
+- hashu64_table touched_cids = HASH_TABLE_INITIALIZER;
++ hashu64_table touched_cids = HASHU64_TABLE_INITIALIZER;
+ memset(&touched_cids, 0, sizeof(hashu64_table));
+ construct_hashu64_table(&touched_cids, mdcount + 1, 0);
+
+--- a/lib/hash.c
++++ b/lib/hash.c
+@@ -43,10 +43,12 @@
+ assert(table);
+ assert(size);
+
+- table->size = size;
++ table->size = size;
++ table->count = 0;
++ table->seed = rand(); /* might be zero, that's okay */
+
+ /* Allocate the table -- different for using memory pools and not */
+- if(use_mpool) {
++ if (use_mpool) {
+ /* Allocate an initial memory pool for 32 byte keys + the hash table
+ * + the buckets themselves */
+ table->pool =
+@@ -72,7 +74,7 @@
+
+ EXPORTED void *hash_insert(const char *key, void *data, hash_table *table)
+ {
+- unsigned val = strhash(key) % table->size;
++ unsigned val = strhash_seeded(table->seed, key) % table->size;
+ bucket *ptr, *newptr;
+ bucket **prev;
+
+@@ -93,12 +95,13 @@
+ }
+ (table->table)[val] -> next = NULL;
+ (table->table)[val] -> data = data;
++ table->count++;
+ return (table->table)[val] -> data;
+ }
+
+ /*
+ ** This spot in the table is already in use. See if the current string
+- ** has already been inserted, and if so, increment its count.
++ ** has already been inserted, and if so, replace its data
+ */
+ for (prev = &((table->table)[val]), ptr=(table->table)[val];
+ ptr;
+@@ -124,6 +127,7 @@
+ newptr->data = data;
+ newptr->next = ptr;
+ *prev = newptr;
++ table->count++;
+ return data;
+ }
+ }
+@@ -142,10 +146,10 @@
+ newptr->data = data;
+ newptr->next = NULL;
+ *prev = newptr;
++ table->count++;
+ return data;
+ }
+
+-
+ /*
+ ** Look up a key and return the associated data. Returns NULL if
+ ** the key is not in the table.
+@@ -159,7 +163,7 @@
+ if (!table->size)
+ return NULL;
+
+- val = strhash(key) % table->size;
++ val = strhash_seeded(table->seed, key) % table->size;
+
+ if (!(table->table)[val])
+ return NULL;
+@@ -183,8 +187,7 @@
+ * since it will leak memory until you get rid of the entire hash table */
+ EXPORTED void *hash_del(const char *key, hash_table *table)
+ {
+- unsigned val = strhash(key) % table->size;
+- void *data;
++ unsigned val = strhash_seeded(table->seed, key) % table->size;
+ bucket *ptr, *last = NULL;
+
+ if (!(table->table)[val])
+@@ -205,15 +208,10 @@
+ int cmpresult = strcmp(key, ptr->key);
+ if (!cmpresult)
+ {
++ void *data = ptr->data;
+ if (last != NULL )
+ {
+- data = ptr -> data;
+ last -> next = ptr -> next;
+- if(!table->pool) {
+- free(ptr->key);
+- free(ptr);
+- }
+- return data;
+ }
+
+ /*
+@@ -226,15 +224,16 @@
+
+ else
+ {
+- data = ptr->data;
+ (table->table)[val] = ptr->next;
+- if(!table->pool) {
+- free(ptr->key);
+- free(ptr);
+- }
+- return data;
+ }
+- } else if (cmpresult < 0) {
++ if(!table->pool) {
++ free(ptr->key);
++ free(ptr);
++ }
++ table->count--;
++ return data;
++ }
++ if (cmpresult < 0) {
+ /* its not here! */
+ return NULL;
+ }
+@@ -292,6 +291,7 @@
+ }
+ table->table = NULL;
+ table->size = 0;
++ table->count = 0;
+ }
+
+ /*
+@@ -340,19 +340,8 @@
+
+ EXPORTED int hash_numrecords(hash_table *table)
+ {
+- unsigned i;
+- bucket *temp;
+- int count = 0;
+-
+- for (i = 0; i < table->size; i++) {
+- temp = (table->table)[i];
+- while (temp) {
+- count++;
+- temp = temp->next;
+- }
+- }
+-
+- return count;
++ /* XXX macro or inline this if we keep the count field long term */
++ return table->count;
+ }
+
+ EXPORTED void hash_enumerate_sorted(hash_table *table, void (*func)(const
char *, void *, void *),
+--- a/lib/hash.h
++++ b/lib/hash.h
+@@ -3,10 +3,11 @@
+ #define HASH__H
+
+ #include <stddef.h> /* For size_t */
++#include <stdint.h>
+ #include "mpool.h"
+ #include "strarray.h"
+
+-#define HASH_TABLE_INITIALIZER {0, NULL, NULL}
++#define HASH_TABLE_INITIALIZER {0, 0, 0, NULL, NULL}
+
+ /*
+ ** A hash table consists of an array of these buckets. Each bucket
+@@ -32,6 +33,8 @@
+
+ typedef struct hash_table {
+ size_t size;
++ size_t count;
++ uint32_t seed;
+ bucket **table;
+ struct mpool *pool;
+ } hash_table;
+--- a/lib/strhash.c
++++ b/lib/strhash.c
+@@ -42,17 +42,32 @@
+
+ #include "config.h"
+
+-EXPORTED unsigned strhash(const char *string)
++#include "lib/strhash.h"
++
++/* The well-known djb2 algorithm (e.g. http://www.cse.yorku.ca/~oz/hash.html),
++ * with the addition of an optional seed to limit predictability.
++ *
++ * XXX return type 'unsigned' for back-compat to previous version, but
++ * XXX ought to be 'uint32_t'
++ */
++EXPORTED unsigned strhash_seeded_djb2(uint32_t seed, const char *string)
+ {
+- unsigned ret_val = 0;
+- int i;
++ const unsigned char *ustr = (const unsigned char *) string;
++ unsigned hash = 5381;
++ int c;
++
++ if (seed) {
++ /* treat the bytes of the seed as a prefix to the string */
++ unsigned i;
++ for (i = 0; i < sizeof seed; i++) {
++ c = seed & 0xff;
++ hash = ((hash << 5) + hash) ^ c;
++ seed >>= 8;
++ }
++ }
++
++ while ((c = *ustr++))
++ hash = ((hash << 5) + hash) ^ c;
+
+- while (*string)
+- {
+- i = (int) *string;
+- ret_val ^= i;
+- ret_val <<= 1;
+- string ++;
+- }
+- return ret_val;
++ return hash;
+ }
+--- a/lib/strhash.h
++++ b/lib/strhash.h
+@@ -41,7 +41,11 @@
+ */
+
+ #ifndef _STRHASH_H_
++#include <stdint.h>
+
+-unsigned strhash(const char *string);
++unsigned strhash_seeded_djb2(uint32_t seed, const char *string);
++
++#define strhash(in) strhash_seeded_djb2((0), (in))
++#define strhash_seeded(sd, in) strhash_seeded_djb2((sd), (in))
+
+ #endif /* _STRHASH_H_ */
diff --git a/debian/patches/series b/debian/patches/series
index 27fc0ec9..1577d428 100644
--- a/debian/patches/series
+++ b/debian/patches/series
@@ -8,3 +8,4 @@
0012-Use-UnicodeData.txt-from-system.patch
0018-increase-test-timeout.patch
CVE-2021-32056.patch
+CVE-2021-33582.patch
