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

From: René Scharfe <l.s.r@web.de>
Date: Sep 1, 2025, 19:06 UTC
Message-ID: <84fb48b3-17ae-405c-b7a9-6d48a3c57a36@web.de>
In-Reply-To: <cb192b28-d85a-4866-a312-df4408cae93e@web.de>

On 8/31/25 7:25 PM, René Scharfe wrote:

Show 9 quoted lines

> 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.

There's https://github.com/not-an-aardvark/lucky-commit, which claims to take a quarter of a second on a four year old laptop to give a commit a chosen 28-bit hash prefix by adjusting whitespace in its message. Constructing a history with a common 32-bit prefix that would effectively turn any oidhash()-based hash table into an unordered list seems within easy reach.

René