5 ms·

According to the best current knowledge of humanity, it provides no information whatsoever. However, proving that is difficult. It is possible that there exist

by jerf 5y ago

According to the best current knowledge of humanity, it provides no information whatsoever. However, proving that is difficult. It is possible that there exists an algorithm that could narrow in on the answer from hashes. Such an algorithm could run quickly, but it could also potentially take quite significant computation. We don't know what the true, optimal answer to this question is.

mlyle 5y ago
> According to the best current knowledge of humanity, it provides no information whatsoever. ??? My first guess has two green letters, or 8 bits of the hash are known. This excludes 255/256 of possible passwords-- so if there's a dictionary, it's way cut down. I also know for the other 30 digits a value that they are not-- this is about .1 bits apiece, for 3 more bits. And I get a few more bits from knowing the population count for each digit. One guess has reduced the search space by a factor of 10000+. If I say, know the word is in /usr/share/dict/words, the number of possibilities has dwindled from 230,000 to something around 20. Now, in this case, with a 14 character randomized password-- the amount of benefit is limited. The search space is still significantly shrunk by each guess, but in a way that is difficult to iterate.
- residualmind 5y ago
  Are you sure thats how evenly distributed hash algorithms work? change one letter of your string, or just make it longer or shorter - none of your green fields will stay.
  - thewakalix 5y ago
    Nothing about this algorithm relies on similar words producing similar hashes. If the word “foobar” has a 0 in the first digit of its hash, and you see a green 1 in the first digit in Passwordle, then you know that the answer can’t be foobar.
  - mlyle 5y ago
    > Are you sure thats how evenly distributed hash algorithms work? change one letter of your string, or just make it longer or shorter - none of your green fields will stay. True. But still, I know the vast majority of words in my dictionary don't match those two green fields after hashing, and can be eliminated from further consideration as the password.
    - lazide 5y ago
      The password is not a dictionary word, it’s randomly generated though?
      - mlyle 5y ago
        Yes, it's a randomly generated string with ~90 bits of entropy. After one guess, I know many fewer of those values could work. Unfortunately, the best known way to test this is to enumerate all of them. 14 character random strings are out of reach; 11 character strings you can enumerate & test them all with a lot of computing.
- 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
- acchow 5y ago
  "??? My first guess has two green letters, or 8 bits of the hash are known. This excludes 255/256 of possible passwords" Sha256 is a one-way hash. Knowing some of the sha256 doesn't tell you anything about the plaintext. Put another way, the matching SHA characters are just a decoy. That's the joke. They could give you the SHA256 hash up front and you'd still have to search the entire password space.

by jerf 5y ago

mlyle 5y ago

> According to the best current knowledge of humanity, it provides no information whatsoever. ??? My first guess has two green letters, or 8 bits of the hash are known. This excludes 255/256 of possible passwords-- so if there's a dictionary, it's way cut down. I also know for the other 30 digits a value that they are not-- this is about .1 bits apiece, for 3 more bits. And I get a few more bits from knowing the population count for each digit. One guess has reduced the search space by a factor of 10000+. If I say, know the word is in /usr/share/dict/words, the number of possibilities has dwindled from 230,000 to something around 20. Now, in this case, with a 14 character randomized password-- the amount of benefit is limited. The search space is still significantly shrunk by each guess, but in a way that is difficult to iterate.

residualmind 5y ago
Are you sure thats how evenly distributed hash algorithms work? change one letter of your string, or just make it longer or shorter - none of your green fields will stay.
- thewakalix 5y ago
  Nothing about this algorithm relies on similar words producing similar hashes. If the word “foobar” has a 0 in the first digit of its hash, and you see a green 1 in the first digit in Passwordle, then you know that the answer can’t be foobar.
- mlyle 5y ago
  > Are you sure thats how evenly distributed hash algorithms work? change one letter of your string, or just make it longer or shorter - none of your green fields will stay. True. But still, I know the vast majority of words in my dictionary don't match those two green fields after hashing, and can be eliminated from further consideration as the password.
  - lazide 5y ago
    The password is not a dictionary word, it’s randomly generated though?
    - mlyle 5y ago
      Yes, it's a randomly generated string with ~90 bits of entropy. After one guess, I know many fewer of those values could work. Unfortunately, the best known way to test this is to enumerate all of them. 14 character random strings are out of reach; 11 character strings you can enumerate & test them all with a lot of computing.
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
acchow 5y ago
"??? My first guess has two green letters, or 8 bits of the hash are known. This excludes 255/256 of possible passwords" Sha256 is a one-way hash. Knowing some of the sha256 doesn't tell you anything about the plaintext. Put another way, the matching SHA characters are just a decoy. That's the joke. They could give you the SHA256 hash up front and you'd still have to search the entire password space.