4 ms·

I've been using blake2(b) for file hashing in some content addressable db stuff. What might be a scenario where i would choose Seahash over Blake2? My main con

I've been using blake2(b) for file hashing in some content addressable db stuff. What might be a scenario where i would choose Seahash over Blake2? My main concern was speed and assurance that i would not see collisions. Beyond that, i am clearly naive on the subject.

notheguyouthink 10y ago
And on that note, has anyone seen any benches for blake2 vs Seahash/Metrohash? I'm not finding anything so far
- ticki_ 10y ago
  BLAKE(2) is a cryptographic hash function, SeaHash is not. Even the fastest implementations of BLAKE only gets around 7.8 cycles/byte (hardware might do it twice as fast). SeaHash gets 0.24 cycles/byte. That's a wide difference, around 32x faster.
dom0 10y ago
The main question, aside from performance, is... - Is there an (abstract) attack model? (Assuming that you have one if you ought to) - Then: Can an attacker insert collisions into the DB, and is that problematic? - Then: A non-cryptographic hash might be much easier to "reverse", especially for short inputs. Is that problematic? If none of these are problematic you probably don't need a cryptographic hash. Regarding performance: BLAKE2b on a Haswell gives you, in a "naive", pure C implementation (compiled to pure, non-vectorized AMD64 assembly), about 230 MB/s / GHz. (Referring to https://github.com/borgbackup/borg/issues/45#issuecomment-221234832 https://github.com/borgbackup/borg/issues/45#issuecomment-22... ), ie. something like 850-1000 MB/s on a desktop SKU. There are implementations that are around 10-30 % faster than that. AFAIK all these newer n-c hash functions that popped up in the last couple years perform (on desktop SKUs) in the area of beyond ~10 GB/s.
- leeoniya 10y ago
  https://github.com/ticki/tfs/issues/5#issuecomment-266031657 https://github.com/ticki/tfs/issues/5#issuecomment-266031657
  - ticki_ 10y ago
    SeaHash is obviously not cryptographic (nor is SipHash), but I hope it is a secure PRF (i.e. the keys cannot be extracted), and this was the best attack I was able to construct. Still, it isn't a practical attack, but I suppose it is possible to improve. Note that I am not a cryptographer, and my only piece of advice is: For the sake of god, don't use hash functions not designed for cryptographic security, if you need cryptographic security. It's that simple.
    - tptacek 10y ago
      SipHash is a cryptographic hash with a pretty good pedigree. The distinction between SipHash and Blake2 is more subtle than "cryptographic vs not".
      - dom0 10y ago
        Sure. For starters SipHash targets a lower-end spectrum of device (in a way) than Blake2, and is also less flexible. Since SipHash produces a 64 bit digest it isn't suitable for many applications in the first place. The two also differ significantly in other cryptographic properties, making Blake2 a more secure and easier (safer) to apply choice. I would tend to say that SipHash is, in a cryptographic context, more an "if you know what you're doing" choice, and not at all a general purpose [cryptographic] hash function.
      - ticki_ 10y ago
        No, it's not a cryptographic hash function. It's a MAC function. The paper clearly states that it is not collision resistant.
        kibwen 10y ago
        I believe that you and tptacek may be using differing definitions of "cryptographic", because he tends to knows what he's talking about when it comes to cryptography (e.g. https://gist.github.com/tqbf/be58d2d39690c3b366ad https://gist.github.com/tqbf/be58d2d39690c3b366ad).
ticki_ 10y ago
There's a huge difference between cryptographic and non-cryptographic. Note that blake2 has various length, whereas SeaHash is fixed to 64-bit (although I suppose it's not to hard to make a version with bigger length), and thus naturally collisions will happen. If you need fingerprints, don't use SeaHash, but if you are looking to insert into e.g. a hash table, you shouldn't use BLAKE2. It's awfully slow for that.
JoshTriplett 10y ago
For a content-addressable database, you absolutely want a cryptographic hash. (And please, don't make the mistake Git did: please include the name of the hash function in the "address", to make it possible to change the hash function.)
- loeg 10y ago
  It seems like Git could change the disk format eventually with backwards compatibility for current SHA1 addresses. You don't even need to rewrite old objects. You just need to know which hash method a given tree/commit object is using to verify history or perform checkout. That could be a flag or tag in the object.
  - JoshTriplett 10y ago
    Git has some work in progress in that direction, starting by changing all the internal data structures to use a struct rather than a hardcoded array of bytes the size of a SHA1.

notheguyouthink 10y ago

And on that note, has anyone seen any benches for blake2 vs Seahash/Metrohash? I'm not finding anything so far

ticki_ 10y ago
BLAKE(2) is a cryptographic hash function, SeaHash is not. Even the fastest implementations of BLAKE only gets around 7.8 cycles/byte (hardware might do it twice as fast). SeaHash gets 0.24 cycles/byte. That's a wide difference, around 32x faster.

dom0 10y ago

The main question, aside from performance, is... - Is there an (abstract) attack model? (Assuming that you have one if you ought to) - Then: Can an attacker insert collisions into the DB, and is that problematic? - Then: A non-cryptographic hash might be much easier to "reverse", especially for short inputs. Is that problematic? If none of these are problematic you probably don't need a cryptographic hash. Regarding performance: BLAKE2b on a Haswell gives you, in a "naive", pure C implementation (compiled to pure, non-vectorized AMD64 assembly), about 230 MB/s / GHz. (Referring to https://github.com/borgbackup/borg/issues/45#issuecomment-221234832 https://github.com/borgbackup/borg/issues/45#issuecomment-22... ), ie. something like 850-1000 MB/s on a desktop SKU. There are implementations that are around 10-30 % faster than that. AFAIK all these newer n-c hash functions that popped up in the last couple years perform (on desktop SKUs) in the area of beyond ~10 GB/s.

leeoniya 10y ago
https://github.com/ticki/tfs/issues/5#issuecomment-266031657 https://github.com/ticki/tfs/issues/5#issuecomment-266031657
- ticki_ 10y ago
  SeaHash is obviously not cryptographic (nor is SipHash), but I hope it is a secure PRF (i.e. the keys cannot be extracted), and this was the best attack I was able to construct. Still, it isn't a practical attack, but I suppose it is possible to improve. Note that I am not a cryptographer, and my only piece of advice is: For the sake of god, don't use hash functions not designed for cryptographic security, if you need cryptographic security. It's that simple.
  - tptacek 10y ago
    SipHash is a cryptographic hash with a pretty good pedigree. The distinction between SipHash and Blake2 is more subtle than "cryptographic vs not".
    - dom0 10y ago
      Sure. For starters SipHash targets a lower-end spectrum of device (in a way) than Blake2, and is also less flexible. Since SipHash produces a 64 bit digest it isn't suitable for many applications in the first place. The two also differ significantly in other cryptographic properties, making Blake2 a more secure and easier (safer) to apply choice. I would tend to say that SipHash is, in a cryptographic context, more an "if you know what you're doing" choice, and not at all a general purpose [cryptographic] hash function.
    - ticki_ 10y ago
      No, it's not a cryptographic hash function. It's a MAC function. The paper clearly states that it is not collision resistant.
      - kibwen 10y ago
        I believe that you and tptacek may be using differing definitions of "cryptographic", because he tends to knows what he's talking about when it comes to cryptography (e.g. https://gist.github.com/tqbf/be58d2d39690c3b366ad https://gist.github.com/tqbf/be58d2d39690c3b366ad).

ticki_ 10y ago

There's a huge difference between cryptographic and non-cryptographic. Note that blake2 has various length, whereas SeaHash is fixed to 64-bit (although I suppose it's not to hard to make a version with bigger length), and thus naturally collisions will happen. If you need fingerprints, don't use SeaHash, but if you are looking to insert into e.g. a hash table, you shouldn't use BLAKE2. It's awfully slow for that.

JoshTriplett 10y ago

For a content-addressable database, you absolutely want a cryptographic hash. (And please, don't make the mistake Git did: please include the name of the hash function in the "address", to make it possible to change the hash function.)

loeg 10y ago
It seems like Git could change the disk format eventually with backwards compatibility for current SHA1 addresses. You don't even need to rewrite old objects. You just need to know which hash method a given tree/commit object is using to verify history or perform checkout. That could be a flag or tag in the object.
- JoshTriplett 10y ago
  Git has some work in progress in that direction, starting by changing all the internal data structures to use a struct rather than a hardcoded array of bytes the size of a SHA1.