Hacker News Reader

Comment by tialaramex | Hacker News Reader

Where on earth did you get this idea from? What is a "generic attack"? How could you turn a collision somehow into a pre-image attack? How is many orders of magnitude "twice" ?

View on HN

You can find this in any introduction to cryptography textbook/course. "Generic attack" is a common term for "just use brute force" [1]. It's called "generic" because it works regardless of the implementation of the primitive. For pre-image resistance the generic attack just hashes messages until it finds the right image, for collision resistance you can get a quadratic speedup via the so called birthday problem / birthday attack [1][2], where you keep hashing messages and storing the hashes until any two of the messages happen to hash to the same value.

[1] https://crypto.stackexchange.com/questions/19194/is-there-an...

[2] https://en.wikipedia.org/wiki/Birthday_problem

I don't think that "look, raw brute force has this property" is at all useful in this context where you'd obviously actually compare a real attack not brute force. There's no reason to believe (and every reason not to) that the same property somehow applies.

That Stack Exchange answer also immediately set off alarm bells in my head because it pretends to be entirely generic, but the obvious thing to do with entirely generic cryptographic intuitions is apply them to the One Time Pad and check their answers work. This intuition doesn't work. Even if you could try all the possible keys you learn nothing, because of the hand-waving about "plausible" plaintext.

Birthday attach is a real attack and often useful in practice. "Just use brute force" is a huge oversimplification, but the SO link explains it in more detail.

One time pad is not a hash algorithm so obviously a generic attack on a collision function doesn't apply to it.

Reply on news.ycombinator.com