9 ms·
Ask HN: Is there a string which MD5 Sum is all 0xffffffffffff?
- natas 3y agohow many cpus or gpus would it take to find the answer within 1 year?
- lagrange77 3y agoSounds like a NP problem.
- hospitalhusband 3y agoThere's an infinite number of those strings, but barring an edge case in the md5 algorithm, none are known.
- dzek69 3y agoIs the algorithm known to produce all theoretically possible hash values? Imagine a simple algorithm that should hash a string to a number 0-3, but due to an extra condition it actually cannot produce "3", pseudocode: ``` Sum = sumOfAsciiCodeOfString(input); Rest = Sum % 4; Return Rest === 3 ? 2 : Rest; ``` Or due to a bug (replace `% 4` with `% 3`). Can we prove that md5 doesn't suffer from such issues and it actually can output ffffffffffff or deaddeaddeaddead ?
- klyrs 3y agoSimple answer: of course there is. The real challenge is finding such strings. If I wanted to know the answer to that question, I'd first search some precomputed rainbow tables to see if anybody's gotten lucky: http://project-rainbowcrack.com/table.htm http://project-rainbowcrack.com/table.htm
- drdeca 3y agoDo you mean just that it is very very likely that there is, or is there some argument that the MD5 function must be surjective?
- voldacar 3y agoIt is not known to be surjective.
- mdaniel 3y agoThe discussion on security.SE seems to imply it's unknown: https://security.stackexchange.com/questions/107081/does-every-hash-value-have-an-inverse-value/107100#107100 https://security.stackexchange.com/questions/107081/does-eve... so if you have a proof of your simple answer, I'm sure they'd welcome it
- hnfong 3y agoThe linked answer on SE basically says statistically there's a near-100% chance that there's a string where md5(string) is 0xfffffff... but there's no concrete proof. Which is basically the same thing the GP says.
- klyrs 3y agoMy statement is one of statistically-informed confidence. A physicist's proof, not a mathematician's. As I said, proving it is where the challenge lies.
- mdaniel 3y agoI tried seeing if there were any references in log files or forum questions to that, but the bad news is that your specific hash is also what one would get from an "invalid" hash, same as asking about the magic string "00000000000000000000000000000000"
- lphillips0825 3y agoAssuming you meant a 128-bit hash with all bits set to '1' (i.e., '0xffffffffffffffffffffffffffffffff'), it would still be extremely difficult, if not practically impossible, to find a string that hashes to this specific value. The MD5 algorithm is designed to produce seemingly random output for small changes in input, and there are no known methods to easily reverse-engineer an MD5 hash. That being said, MD5 is no longer considered cryptographically secure due to vulnerabilities discovered over the years, such as hash collisions. But finding a specific hash, like the one you mentioned, would still require a brute-force attack or an advanced cryptanalytic method, neither of which is guaranteed to succeed.
- c1yd3i 3y agoFound ChatGPT.
- fnordpiglet 3y agoThis is essentially what crypto mining is, FWIW