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

From: Jeff King <peff@peff.net>
Date: Sep 3, 2025, 14:31 UTC
Message-ID: <20250903143134.GA1884731@coredump.intra.peff.net>
In-Reply-To: <05b8e161-9087-4eb8-b049-6e99ff288af7@web.de>

On Tue, Sep 02, 2025 at 08:51:37PM +0200, René Scharfe wrote:

Show 13 quoted lines

> > 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.
>
> I see slightly worse performance, but within the noise.
> 
> However, just stacking two words won't do if only a few bits of the
> resulting hash will be used to find a bucket.  We could mix in more bits
> and smear them all over, but if that's done by a deterministic function
> then it could be applied during the construction of manipulated object
> hash values as well, no?

I think the difficulty in manipulating scales as the number of bits increases. So yeah, if you are worried about the low 8 bits, then XOR-ing in another 8 bits is not going to do much. But your table is only 256 items long, so you don't care much either way.

At even 16 bits, it gets hard for the attacker to choose the low 16 bits _and_ the low 16 bits of the next word (you mentioned a project earlier which claims 28 bits). If you XOR in a third word, now your 16-bit hash is using 48 bits that the attacker has to control. And so on.

> Perhaps salting with a random value determined at runtime would help.
> Not XORing it in (pointless if the other value is controlled by the
> attacker, as the result would still collide), but using it as a mask to
> choose the bits to take from the object hash?

I think that would work, but XOR-ing the higher order bits is easier to do and I think produces a similar effect. Let's shrink the problem for a second. Imagine sha1 was 16 bits, and we wanted to create an 8-bit hash to use in our table. The attacker creates two objects with binary hashes:

  object a: 10111001 11110111
  object b: 01001000 11110111

They collide in the lower 8 bits, but we don't want them to. In your scheme, as I understand it, we'd come up with a 16-bit mask that has exactly 8 bits set, like:

  11010110 01011000

and then picking only the bits where the mask is "1", we get:

  object a: 10111001 11110111
      mask: 11010110 01011000
    hash a: 10100110

  object b: 01001000 11110111
      mask: 11010110 01011000
    hash b: 01000110

So I agree that is hard to foil without the attacker knowing which bits you'll pick. You've made their job 8 bits harder, because they now have to control all 16 bits to get their collision.

But if we instead XOR the words of the object hashes together, we get:

  object a[hi]: 10111001
  object a[lo]: 11110111
        hash a: 01001110

  object b[hi]: 01001000
  object b[lo]: 11110111
        hash b: 10111111

So you're flipping bits "randomly". It's not truly random, but is coming from the rest of the hash the attacker provided. But for any bit they want to control, they have to control that position in both words. So they're back to needing to control all 16 bits to get their desired hash.

And as somebody who just hand-computed those answers, I can tell you that the XOR one is much simpler to do. ;)

-Peff