3 ms·

Pre-image is approximately "twice as difficult" as a collision. A generic attack on, say, a 256 bit long hash function takes 2^128 time to find a collision, but

Pre-image is approximately "twice as difficult" as a collision. A generic attack on, say, a 256 bit long hash function takes 2^128 time to find a collision, but 2^256 time to find a preimage. And like you say, this also shows up in practice: both MD-5 and SHA-1 are completely broken when it comes to collision resistance, but both are (probably) still OK for preimage resistance. I would still not recommend either of them for anything.

tialaramex 3y ago
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" ?
- H8crilA 3y ago
  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-any-definition-for-generic-attack-in-context-of-cryptography-or-more https://crypto.stackexchange.com/questions/19194/is-there-an... [2] https://en.wikipedia.org/wiki/Birthday_problem https://en.wikipedia.org/wiki/Birthday_problem
  - tialaramex 3y ago
    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.
    - deleted 3y ago
      [deleted]
    - maxcoder4 3y ago
      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.
popol12 3y ago
twice as difficult ? It doesn't match what you say after that 2²⁵⁶ = 2¹²⁸ * 2¹²⁸ So, isn't it rather 2¹²⁸ times more difficult ?
- H8crilA 3y ago
  Security is typically measured in bits. But yes you're right, maybe I should have written "square as difficult" to be more clear :)

tialaramex 3y ago

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

H8crilA 3y ago
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-any-definition-for-generic-attack-in-context-of-cryptography-or-more https://crypto.stackexchange.com/questions/19194/is-there-an... [2] https://en.wikipedia.org/wiki/Birthday_problem https://en.wikipedia.org/wiki/Birthday_problem
- tialaramex 3y ago
  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.
  - deleted 3y ago
    [deleted]
  - maxcoder4 3y ago
    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.

popol12 3y ago

twice as difficult ? It doesn't match what you say after that 2²⁵⁶ = 2¹²⁸ * 2¹²⁸ So, isn't it rather 2¹²⁸ times more difficult ?

H8crilA 3y ago
Security is typically measured in bits. But yes you're right, maybe I should have written "square as difficult" to be more clear :)