3 ms·
Honestly, the paper is pretty confusing. It's a weird mix of explaining things people reading a hash paper should already know (e.g. avalanche effect) and not e
by AlotOfReading 2y ago
Honestly, the paper is pretty confusing. It's a weird mix of explaining things people reading a hash paper should already know (e.g. avalanche effect) and not explaining the important bits. The mixing stage looks a lot like a Davies-meyer hash, but it's hard to be sure without reading code. If so, this will be susceptible to fixed point attacks (among others). It doesn't particularly matter because this isn't presented as secure, but worth noting.
The paper also doesn't exhaustively verify numbers when domain=codomain, which is a super common scenario and a weird omission. 32 bits is small enough to check everything.
- vlovich123 2y agoThe hash internally is a 128bit hash & can output 32 or 64 bit as well. Can you speak more to how fixed point attacks are relevant? The only reference I found online was in a cryptographic context which wouldn't be relevant here. Are other hashes like SipHash-1-3 (Rust stdlib hashmap) or XXH3 susceptible to it?
- AlotOfReading 2y agoA fixed point attack would allow creating collisions. Whether that's an issue or not depends on your use case, but the answer is going to be yes surprisingly often in my experience.
- vlovich123 2y agoI don’t know about this at all, but ChatGPT suggests that this attack is thwarted by a secure compression function and block function. As you point out elsewhere, it uses AES for compression but not sure if that’s enough. Do you know?
- AlotOfReading 2y agoChatGPT would be wrong in this case. It applies to (and was originally identified with) hash functions built from cryptographically secure hash functions. Note that this isn't as strong as AES. It's just built with some of the same machinery as AES, it doesn't carry over its guarantees. Still an interesting construction I'll play around with some more when I have time.
- singron 2y agoCan you realistically create fixed-point collisions of a randomly seeded hash function? E.g. to defeat the DOS-resistance of a hash table? I think the papers on fixed-point attacks of Davies-Meyer hashes require selecting the IV or knowing the IV in order to carry out the attack.
- AlotOfReading 2y agoNot sure where the IV would come in, but both the plaintext and the initial key seem to be taken directly from the input as the first two blocks in any "compression group". Let's say you want intermediate key X after the first two steps, the first 3 blocks should be something like m_2 = D(X, E(m_1, m_0)) because we're missing the xor step from davies-meyer. Let me know if I'm wrong though, strictly an amateur here.
- singron 2y agoI took a closer look, and it looks like the compression doesn't depend on the seed at all. This makes it look like any collision is a collision on all seeds. pub(crate) unsafe fn gxhash(input: &[u8], seed: State) -> State { finalize(aes_encrypt(compress_all(input), seed)) } For a hash table, you would normally use just the low bits to select a bucket, so this still protects you from collisions on just a subset of the bits, but if you can produce a large number of collisions on the exact 128-bit output, then it's not DOS-resistant.
- oginiaux 2y agoHi! I'm the author of this document. It indeed covers some concepts that will sound trivial for people experienced like you. However, I am not a cryptography researcher (only a developer passionate about performance and optimization) and nor is my entourage. So I wrote this also for people like them. Still, I tried my best getting into the details, but I learned a lot while developing this hash function, and I still have plenty to learn especially regarding security. That is one of the reasons I made it open source: get feedback from more seasoned peers and improve this :).
- AlotOfReading 2y agoI have to say, despite any nits I have about it the overall construction is pretty clever and I like a lot of your design choices. It's a cool algorithm.