View Issue Details

IDProjectCategoryView StatusLast Update
0012210Talersyncpublic2026-11-18 16:42
Reporterbot-cg [agent]  
Implementeravalos  
PrioritynormalSeverityminor 
Status implementing 
Product Versiongit (master) 
Summary0012210: sync client: bucket_count and k from the reconcile reply are not bounded, and the bloom filter assumes k <= bucket_count
Descriptionhandle_reconcile_finished() (src/lib/sync_api_block_reconcile.c) only requires bucket_count and k from the GET /backups/$KEY/blocks/reconcile reply to be positive. It allocates bucket_count * SYNC_IBF_BUCKET_SIZE bytes with GNUNET_malloc (which aborts above 40 MiB), and passes k on as the filter's hash_num. SYNC_ibf_create() and SYNC_ibf_deserialize() (src/util/sync_ibf.c) accept any hash_num, although each element needs hash_num distinct bucket indices: with k > bucket_count, ibf_get_indices() never finds them and SYNC_ibf_decode() loops forever, inserting asserts, and the buckets[hash_num] stack arrays are sized by k.

The only C user of the reconcile client today is the test harness (the wallet's client is TypeScript).

Confirmed by reading the code at 9f3dac2.

The attached patch bounds bucket_count by SYNC_IBF_MAX_BUCKETS, requires k == SYNC_IBF_HASH_NUM, and makes SYNC_ibf_create() (and so SYNC_ibf_deserialize()) refuse fewer buckets than hash functions.
Additional InformationRecorded as SYNC-029 in sync's review notes; the patch is that review's 0047, which is part of the unmerged combined commit 303a031 on dev/bots/review. It applies unchanged to 9f3dac2.
TagsNo tags attached.
Attached Files
12210-sync-bound-the-reconcile-reply-s-filter-shape.patch (4,171 bytes)   
From 0000000000000000000000000000000000000000 Mon Sep 17 00:00:00 2001
From: Christian Grothoff <christian@grothoff.org>
Date: Wed, 18 Nov 2026 17:41:26 +0100
Subject: [PATCH] sync: bound the reconcile reply's filter shape

The client allocated whatever bucket_count the server sent and accepted
any k, while the filter code needs k distinct buckets per element and
never terminates with fewer.

Issue: https://bugs.taler.net/n/12210

Assisted by LLM
---
 src/include/sync/sync_ibf.h        | 10 ++++++----
 src/lib/sync_api_block_reconcile.c |  9 +++++++--
 src/util/sync_ibf.c                |  6 +++++-
 3 files changed, 18 insertions(+), 7 deletions(-)

diff --git a/src/include/sync/sync_ibf.h b/src/include/sync/sync_ibf.h
index c3c3cf1..57e383d 100644
--- a/src/include/sync/sync_ibf.h
+++ b/src/include/sync/sync_ibf.h
@@ -92,11 +92,12 @@ SYNC_ibf_compute_bucket_count (uint32_t block_count);
 /**
  * Create a fresh invertible bloom filter.
  *
- * @param bucket_count number of buckets
+ * @param bucket_count number of buckets, at least @a hash_num
  * @param hash_num number of hash functions per element
  * @param prefix mixing salt hashed with every element (4 bytes,
  *        network byte order, zero for the default)
- * @return the filter, NULL on failure
+ * @return the filter, NULL if @a bucket_count or @a hash_num is zero
+ *         or there are fewer buckets than hash functions
  */
 struct SYNC_IBF *
 SYNC_ibf_create (uint32_t bucket_count,
@@ -109,10 +110,11 @@ SYNC_ibf_create (uint32_t bucket_count,
  *
  * @param data serialized filter of @a bucket_count buckets
  *        (see #SYNC_ibf_serialize())
- * @param bucket_count number of buckets the serialized filter holds
+ * @param bucket_count number of buckets the serialized filter holds,
+ *        at least @a hash_num
  * @param hash_num number of hash functions per element
  * @param prefix mixing salt the serialized filter was built with
- * @return the filter, NULL on failure
+ * @return the filter, NULL on failure (see #SYNC_ibf_create())
  */
 struct SYNC_IBF *
 SYNC_ibf_deserialize (const void *data,
diff --git a/src/lib/sync_api_block_reconcile.c b/src/lib/sync_api_block_reconcile.c
index ff67462..301171d 100644
--- a/src/lib/sync_api_block_reconcile.c
+++ b/src/lib/sync_api_block_reconcile.c
@@ -121,11 +121,14 @@ handle_reconcile_finished (void *cls,
       }
       rd.version = (uint32_t) json_integer_value (j);
       /* bucket_count */
+      /* bucket_count sizes the allocation below; the server never
+         builds more than SYNC_IBF_MAX_BUCKETS */
       j = json_object_get (json,
                            "bucket_count");
       if ( (NULL == j) ||
            (! json_is_integer (j)) ||
-           (json_integer_value (j) <= 0) )
+           (json_integer_value (j) <= 0) ||
+           (json_integer_value (j) > SYNC_IBF_MAX_BUCKETS) )
       {
         GNUNET_break_op (0);
         rd.ec = TALER_EC_GENERIC_PARAMETER_MALFORMED;
@@ -133,11 +136,13 @@ handle_reconcile_finished (void *cls,
       }
       rd.bucket_count = (uint32_t) json_integer_value (j);
       /* k */
+      /* the protocol fixes the number of hash functions; anything
+         else cannot be reconciled against a local filter */
       j = json_object_get (json,
                            "k");
       if ( (NULL == j) ||
            (! json_is_integer (j)) ||
-           (json_integer_value (j) <= 0) )
+           (SYNC_IBF_HASH_NUM != json_integer_value (j)) )
       {
         GNUNET_break_op (0);
         rd.ec = TALER_EC_GENERIC_PARAMETER_MALFORMED;
diff --git a/src/util/sync_ibf.c b/src/util/sync_ibf.c
index da5e01b..f43c63c 100644
--- a/src/util/sync_ibf.c
+++ b/src/util/sync_ibf.c
@@ -287,8 +287,12 @@ SYNC_ibf_create (uint32_t bucket_count,
 {
   struct SYNC_IBF *ibf;
 
+  /* an element needs hash_num distinct bucket indices, so there
+     must be at least that many buckets or ibf_get_indices() would
+     never terminate */
   if ( (0 == bucket_count) ||
-       (0 == hash_num) )
+       (0 == hash_num) ||
+       (hash_num > bucket_count) )
     return NULL;
   ibf = GNUNET_new (struct SYNC_IBF);
   ibf->size = bucket_count;
-- 
2.47.3

Required notifications

Address or linkRemarkAdded byNotifiedActions

Relationships

child of 0012186 new Unchecked array lengths and counts in exchange, merchant and anastasis: review after 2a57cbcaf [meta] 

Activities

Issue History

Date ModifiedUsernameFieldChange
2026-11-18 16:41bot-cgNew Issue
2026-11-18 16:41bot-cgRelationship addedchild of 0012186
2026-11-18 16:41bot-cgImplementer => avalos
2026-11-18 16:41bot-cgRelease signed by => Florian Dold
2026-11-18 16:41bot-cgDeployed by => avalos
2026-11-18 16:41bot-cgVerifier => avalos
2026-11-18 16:41bot-cgCommunicator => CM_7
2026-11-18 16:41bot-cgFile Added: 12210-sync-bound-the-reconcile-reply-s-filter-shape.patch
2026-11-18 16:42Christian GrothoffStatusnew => implementing