Hash collisions

[mxhbl]

Following the discussion here, it has become clear that we need to do something about hash security.

Some options for future reference:

• use the SHA stdlib. This is fine for large arrays/graphs (for which we already use it), but probably too slow for small graphs.
• use the new Base Julia hash to be introduced in 1.13.
• use other libraries, such as XXHash.jl, or KangorooTwelve.jl. These seem promising.
• the newly released version of nauty ships with a sha implementation, as far as I understand.

[JanPastorek]

@mxhbl Does this problem mean that two different graphs can get the same canonical_hash by calling nautyhash function? Version 0.4

[mxhbl]

Hi, yes that is correct. Hash collisions are of course always possible, but depending on the hash algorithm used they should be very rare. Unfortunately, the Julia Base.hash is not very collision resistant. I recently had a hash collision in a set of about 80.000 graphs, each with size between 10 and 100. This will be fixed in the future, probably by switching to XXHash. In the meantime, if you want to minimize the chance of hash collisions, you can use the SHA stdlib. This is already the default choice for large graphs (more than about 8000 vertices), but it should be easy to write a custom ghash that uses that choice also for small graphs.

[mxhbl]

If this is a concern, I would recommend that you update to v0.6.0. The new version changes the internal representation of DenseNautyGraphs, which should make them a bit more resistant to collisions (although the main problem is still the use of Base.hash, which will only be improved in the future). In any case the breaking changes from 0.4.0 to 0.6. should not be that big of a barrier to upgrade (I think).