Timeline for Why are hash functions one way? If I know the algorithm, why can't I calculate the input from it?
Current License: CC BY-SA 3.0
10 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 7, 2021 at 7:05 | history | edited | CommunityBot |
replaced http://tools.ietf.org/html/rfc with https://www.rfc-editor.org/rfc/rfc
|
|
| Sep 24, 2019 at 20:23 | comment | added | user24343 | years after your answer (and some before this comment), an actual SHA-1 collision was computed | |
| Apr 19, 2019 at 2:57 | comment | added | forest | @cnd That equation was just an example of a one-way function called a "trapdoor function". Functions of that kind are normally one-way, but not if you have access to certain secret variables used in creating the function, in that case the primes multiplied together to derive n. Real hashes do not use trapdoor functions, so their one-wayedness is unconditional and not dependent on the secrecy of some value. | |
| Apr 19, 2019 at 2:54 | comment | added | forest |
@AsheKetchum A one-way function is by definition preimage resistant, so the meaning is not exactly what you would expect. If you have floor(n) = 7, I can "invert" that with n = 7.2. Even if that is not the original value, I still "inverted" it. I didn't discover the original value of n that you may have had in mind, but I did discover a value which solves the equation, proving that it is not one-way in the cryptographic sense.
|
|
| Feb 12, 2019 at 17:14 | comment | added | AsheKetchum | Hi , When you say "It is unclear whether one-way functions can actually exist. Right now, we have many functions that no one knows how to invert; but this does not mean that they are impossible to invert, in a mathematical sense", what are you referring to? For example, if we look at the function "floor", do we claim that it is "not impossible to invert"? Thanks! | |
| Oct 26, 2017 at 7:12 | comment | added | cnd | " x ⟼ x2 mod n is hard to invert " ... This seems unlikely, especially since you (or whoever is using this inside a hash function they designed, e.g., the NSA) have access to those big primes. | |
| Mar 8, 2016 at 22:06 | comment | added | B Seven | Fascinating. This should be the answer. | |
| Dec 31, 2014 at 18:21 | comment | added | Max | I don't care that it's late, I need to say this: Really good explaination that really shows the complexity you can create using algorithms. I had this ignorant thought that everything easily could be done backwards if you knew how to do it forward (using computers), and this clearly shows that it's not that easy. The example with MD5 was great as well, since it lets you actually see the complexity for what it is (unlike with analogies [which are great too, don't get me wrong]). Again, really great and enlightening article; hope to read more from you. | |
| Apr 15, 2013 at 14:22 | comment | added | k1DBLITZ | Best TL;DR quote ever. I think I need to create a new stack in my evernote just for your answers. Do you author any articles or books by chance? | |
| Sep 3, 2012 at 2:17 | history | answered | Thomas Pornin | CC BY-SA 3.0 |