4 ms·

This is one of those places where it's easy to conflate computer bits with information theory bits. You may have eight computer bits, but in order for you to ha

by jerf 5y ago

This is one of those places where it's easy to conflate computer bits with information theory bits. You may have eight computer bits, but in order for you to have eight bits of information, you must have your search space cut down by a factor of 256, not just the abstract concept of a search space cut down. Can you enumerate the remaining 1/256th of the search space? Not with anything other than a brute force search, minus the one password you tried. The exact same brute force search that you would have needed to solve the problem in the first place. Your one password attempt has yielded one password's worth of knowledge. You, a human, don't have eight bits of information. You have almost nothing. In principle, such a guess does eliminate 8 bits of information, but we have no way of manifesting that. In principle if we had a full list of the shortest passwords that led to the given hash, we could strike off the non-matching entries, but no human can do that. In principle an easier algorithm than the brute-force search exists, but we have no idea what it is, and we don't know what it would look like, whether it would be an incremental improvement over brute force or if there's hypothetically an algorithm that could do it on your cell phone in a couple of seconds or what. Hashing and cryptography in general hide in this space between the theoretical information leakage and the practical inability to do anything with it. You have 8 theoretical bits and just shy of 0 real, practical bits.

mlyle 5y ago
> Can you enumerate the remaining 1/256th of the search space? Not with anything other than a brute force search, minus the one password you tried. The exact same brute force search that you would have needed to solve the problem in the first place. Your one password attempt has yielded one password's worth of knowledge. You, a human, don't have eight bits of information. You have almost nothing. Eh, the actual search space for reasonable online guesses is cut down by 10000x. Yes, you still need to search an impractically large number of passwords here-- 2^92 or so. But you only have to provide 10 guesses to the oracle. Described here: https://news.ycombinator.com/item?id=30367095 https://news.ycombinator.com/item?id=30367095 Or, if you tell me that the password is in /usr/share/dict/words, I can figure out what the password is in 2 online guesses.
- jerf 5y ago
  "Eh, the actual search space for reasonable online guesses is cut down by 10000x." Only in theory. In order to determine which 9999 out of 10000 guesses are no longer relevant, the only known method you have is to compute the hashes of all the 10000 representatives anyhow... which is, again, the exact same problem you started out with at the beginning. You have theoretical information because you've made theoretical progress, but you have no real information, because you've made no real progress. This program uses a number of random characters each time you load it. You have no list for this program. In principle you could look at your random number generator and possibly narrow it down beyond the sheer size of the SHA256 space, if it has fewer bits of internal state. I don't know how many bits of internal state it has or even if the answer is constant per browser, and that's really just a practical detail. To put this in even more stark relief, suppose I bring up Passwordle and by some magic, I hand you a password at the beginning that has a hash that is identical to the hash of the answer in all but one bit. In theory, that constitutes enough information to name the answer on the next guess. In practice, you can't do that. In fact, we can play that game right now. The SHA256 hash [1] of "mlyle" is "CAD9051E126DA9BC7CB4048C4CA28804CCFEE0E3824F4E63FC151BC5E30B96D0". Using this information, please produce a password with the hash CAD9051E126DA9BC7CB4048C4CA28804CCFEE0E3824F4E63FC151BC5E30B96D1, differing only in the last bit. Ideally the shortest password using letters, numbers, and symbols in US ASCII, but honestly I'll take any binary string. How much help does that provide you? In theory, like I said, you should be able to do it in one guess now, if what you say is true. In practice, you don't have the lookup table to do it, you can't have the lookup table to do it in our real universe, and we have no known better algorithm for it. (Observant people may note that providing the mlyle hash is irrelevant and this challenge is equivalent to simply directly asking for something that hashes to the target string. And that's the point. Providing you the hash of mlyle provides zero assistence. You must still enumerate everything.) [1]: https://passwordsgenerator.net/sha256-hash-generator/ https://passwordsgenerator.net/sha256-hash-generator/ if you want to play along.
  - jimmydorry 5y ago
    Nice write up. It's an unintuitive concept, but this is a good demonstration of the power of cryptography.

by jerf 5y ago

mlyle 5y ago

> Can you enumerate the remaining 1/256th of the search space? Not with anything other than a brute force search, minus the one password you tried. The exact same brute force search that you would have needed to solve the problem in the first place. Your one password attempt has yielded one password's worth of knowledge. You, a human, don't have eight bits of information. You have almost nothing. Eh, the actual search space for reasonable online guesses is cut down by 10000x. Yes, you still need to search an impractically large number of passwords here-- 2^92 or so. But you only have to provide 10 guesses to the oracle. Described here: https://news.ycombinator.com/item?id=30367095 https://news.ycombinator.com/item?id=30367095 Or, if you tell me that the password is in /usr/share/dict/words, I can figure out what the password is in 2 online guesses.

jerf 5y ago
"Eh, the actual search space for reasonable online guesses is cut down by 10000x." Only in theory. In order to determine which 9999 out of 10000 guesses are no longer relevant, the only known method you have is to compute the hashes of all the 10000 representatives anyhow... which is, again, the exact same problem you started out with at the beginning. You have theoretical information because you've made theoretical progress, but you have no real information, because you've made no real progress. This program uses a number of random characters each time you load it. You have no list for this program. In principle you could look at your random number generator and possibly narrow it down beyond the sheer size of the SHA256 space, if it has fewer bits of internal state. I don't know how many bits of internal state it has or even if the answer is constant per browser, and that's really just a practical detail. To put this in even more stark relief, suppose I bring up Passwordle and by some magic, I hand you a password at the beginning that has a hash that is identical to the hash of the answer in all but one bit. In theory, that constitutes enough information to name the answer on the next guess. In practice, you can't do that. In fact, we can play that game right now. The SHA256 hash [1] of "mlyle" is "CAD9051E126DA9BC7CB4048C4CA28804CCFEE0E3824F4E63FC151BC5E30B96D0". Using this information, please produce a password with the hash CAD9051E126DA9BC7CB4048C4CA28804CCFEE0E3824F4E63FC151BC5E30B96D1, differing only in the last bit. Ideally the shortest password using letters, numbers, and symbols in US ASCII, but honestly I'll take any binary string. How much help does that provide you? In theory, like I said, you should be able to do it in one guess now, if what you say is true. In practice, you don't have the lookup table to do it, you can't have the lookup table to do it in our real universe, and we have no known better algorithm for it. (Observant people may note that providing the mlyle hash is irrelevant and this challenge is equivalent to simply directly asking for something that hashes to the target string. And that's the point. Providing you the hash of mlyle provides zero assistence. You must still enumerate everything.) [1]: https://passwordsgenerator.net/sha256-hash-generator/ https://passwordsgenerator.net/sha256-hash-generator/ if you want to play along.
- jimmydorry 5y ago
  Nice write up. It's an unintuitive concept, but this is a good demonstration of the power of cryptography.