News for hackers. Stuff that matters.
Re:First practical SHA-256 collision for 31 steps. fse2024 by H8crilA on Wednesday March 27, 2024 @05:34AM (#39837055)
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.
Re:First practical SHA-256 collision for 31 steps. fse2024 by tialaramex on Wednesday March 27, 2024 @05:56AM (#39837173)
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" ?
Re:First practical SHA-256 collision for 31 steps. fse2024 by H8crilA on Wednesday March 27, 2024 @06:11AM (#39837262)
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

Re:First practical SHA-256 collision for 31 steps. fse2024 by tialaramex on Wednesday March 27, 2024 @09:31AM (#39838825)
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.

Re:First practical SHA-256 collision for 31 steps. fse2024 by maxcoder4 on Wednesday March 27, 2024 @11:07AM (#39840266)
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.

Re:First practical SHA-256 collision for 31 steps. fse2024 by popol12 on Wednesday March 27, 2024 @05:57AM (#39837181)
twice as difficult ? It doesn't match what you say after that

2²⁵⁶ = 2¹²⁸ * 2¹²⁸

So, isn't it rather 2¹²⁸ times more difficult ?

Re:First practical SHA-256 collision for 31 steps. fse2024 by H8crilA on Wednesday March 27, 2024 @06:08AM (#39837248)
Security is typically measured in bits. But yes you're right, maybe I should have written "square as difficult" to be more clear :)