Hacker News Reader

Comment by singron | Hacker News Reader

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.

View on HN

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.

Reply on news.ycombinator.com