Timeline for Just how surjective is a cryptographic hash like SHA-1?
Current License: CC BY-SA 3.0
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 31, 2021 at 4:46 | comment | added | Meir Maor | I must side with @tylo on this. We do not know for a fact SHA1 behaves like a PRF. Even with recent attacks we did not find sufficiently many collisions. But the evidence is significant we do have some collisions yet they are not plentiful and we can easily analyze truncated versions and see they behave as expected. Most importantly however the question said " any hash function like SHA-1" so a generic answer seemed in order and not focus on SHA-1. | |
| Mar 30, 2021 at 20:47 | comment | added | tylo | @PaulUszak I don't think that's proven at all. On the contrary - it is proven in theory that there are some constructions are secure in the random oracle model (which is a random function in a blackbox) but insecure with any real hash function. There is a difference between the two, and it's impossible to estimate how close the actual result with a specific function is to the random function. It's like drawing a value from a probability distribution. | |
| Mar 30, 2021 at 15:23 | comment | added | Paul Uszak | @tylo Isn't that consideration proven beyond any reasonable doubt? We can verify the collision rate with just a few lines of code. It tallies (at high certainty) with an avalanche characteristic of $\mu = \frac{\text{block-width}}{2}, \sigma = \frac{\sqrt{\text{block-width}}}{2}$. Ergo, 37% of bins must remain empty. | |
| Jun 26, 2017 at 11:40 | vote | accept | Paul Uszak | ||
| Jun 26, 2017 at 8:36 | comment | added | tylo | @PaulUszak If you consider a random function as a proper model for SHA1, then yes, that's the answer. Probably it's a good approximation, but unless we can actually test all $2^{160}$ input values, we don't know how close it actually is. | |
| Jun 25, 2017 at 20:13 | history | edited | Ella Rose | CC BY-SA 3.0 |
fixed small errors/added tex
|
| Jun 25, 2017 at 19:33 | history | answered | Meir Maor | CC BY-SA 3.0 |