Re: [PATCH] describe: use khash in finish_depth_computation()
- From
Jeff King <peff@peff.net>
- Date
- Sep 4, 2025, 11:16 UTC
- Message-ID
- <20250904111619.GA2474144@coredump.intra.peff.net>
- In-Reply-To
- <f6b4c1fb-9f59-4072-a796-e2971524ffa5@web.de>
On Wed, Sep 03, 2025 at 05:41:49PM +0200, René Scharfe wrote:
Show 6 quoted lines
> How does an attacker control object hashes? Hash it, check if it fits > the criteria, if it doesn't then make some inconsequential changes like > adding whitespace to a commit message and repeat. That criteria can be > "bits 1-16 are all zero", but it can just as well be "bits 1-8 XORed > with bits 9-16 are all zero". For the former they'd have to roll the > dice in the order of 2^16 times, for the latter just 2^8 times.
Hmm, yeah, you're right. I was counting the wrong thing. It is not one expensive action to generate a byte (or word) of sha1 hash. It is one action to generate the whole hash. And then cheap to XOR it and find out what the result would be in our XOR-bucket scheme. So if you are just brute-forcing anyway, it is the same number of hash attempts, which is what the attacker cares about minimizing. My proposal adds nothing there.
Show 5 quoted lines
> The attacker in our scenario doesn't have to care about the individual > bits of object hashes, just the resulting hash table hashes, which > reduces their search space a lot. Making the deterministic function > more complicated or using more attacker-supplied input bits doesn't > change that.
Yep. Thanks for a dose of sanity.
-Peff