Re: [PATCH] describe: use khash in finish_depth_computation()

From: Jeff King <peff@peff.net>
Date: Sep 2, 2025, 12:38 UTC
Message-ID: <20250902123834.GA711442@coredump.intra.peff.net>
In-Reply-To: <cb192b28-d85a-4866-a312-df4408cae93e@web.de>

On Sun, Aug 31, 2025 at 07:25:13PM +0200, René Scharfe wrote:

Show 25 quoted lines

> > diff --git a/builtin/describe.c b/builtin/describe.c
> > index edb4dec79d..e024feb080 100644
> > --- a/builtin/describe.c
> > +++ b/builtin/describe.c
> > @@ -289,7 +289,7 @@ static void lazy_queue_clear(struct lazy_queue *queue)
> >  
> >  static inline unsigned int commit_index(const struct commit *commit)
> >  {
> > -	return commit->index;
> > +	return oidhash(&commit->object.oid);
> >  }
> >  
> >  static inline int ptr_eq(const void *a, const void *b)
> > 
> > I get similar results (actually faster, but I think within the noise).
> 
> Sure.  I'm not comfortable with oidhash() though, because it allows
> attackers to influence the hash value, cause collisions and thus
> increase the cost of lookups and inserts to O(N), leading to quadratic
> complexity overall.
>
> They "just" need to construct commits with a common hash prefix.  I
> guess that's easy for two bytes and hard for four bytes.  Not sure how
> what an attacker would get out of planting such performance traps, but
> I guess some people would do it just for the heck of it.

I doubt that commit->index is any better in that regard. If I can influence the order in which Git loads the commits (e.g., by creating a bunch of refs which get loaded when we walk over for_each_ref), I can choose the index for each. They'll be unique, but I can still cause collisions modulo the number of buckets.

Likewise for oidhash(), I'd guess that colliding 4 bytes is not even necessary to cause trouble, since probing starts by throwing away everything mod n_buckets. So really you just need to collide however many low bits you need to make your desired N, and then get O(N^2) behavior.

I'm not super worried about it, because in my experience Git is already a perfectly tuned device for convincing other people to waste CPU. ;) But if we want to address it, I'd rather do so by improving oidhash() than avoiding it. Specifically...

> Letting oidhash() XOR in another word would close that line of attack
> for quite a while, I assume.

Yeah. We have at least 160 bits in an object hash, and we only bother with the low 32. We could XOR up to 5 times, but I agree that even a single extra word would probably be plenty. Might be an interesting experiment to time something like the patch below on a hash-heavy workload.

diff --git a/hash.h b/hash.h
index fae966b23c..c9d21f589e 100644
--- a/hash.h
+++ b/hash.h
@@ -457,7 +457,10 @@ static inline unsigned int oidhash(const struct object_id *oid)
 	 * platforms that don't support unaligned reads.
 	 */
 	unsigned int hash;
+	unsigned int entropy;
 	memcpy(&hash, oid->hash, sizeof(hash));
+	memcpy(&entropy, oid->hash + sizeof(hash), sizeof(entropy));
+	hash ^= entropy;
 	return hash;
 }
 

I suspect it won't make a big time difference. The old code should have
been optimized down to a single word load, and now we have two word
loads and an xor. That probably isn't important compared to the actual
5-word memcmp() we have to do in order to verify that we found the right
bucket anyway.

-Peff