Hacker News Reader

Comment by AlotOfReading | Hacker News Reader

A 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.

View on HN

Can 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.

Not 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.

I 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.

I 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?

ChatGPT 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.

Reply on news.ycombinator.com