[mlyle]

> 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.

[jerf]

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]

> 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

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.

[oefrha]

I can give you the full hash so that you can be done in one guess if you have a giant rainbow table of precomputed hashes. Still, the full hash doesn’t reduce the search space at all, assuming SHA256 is secure. Sure, you can cut down on the number of oracle queries, but that’s not the limiting factor of this game.

[mlyle]

> Sure, you can cut down on the number of oracle queries, but that’s not the limiting factor of this game.

To win the game, you must make fewer than 10 oracle queries.

You can solve the game in 9 oracle queries + 1 massive (impractically large) offline search. The width of the search is 2^92, because that's the entropy of the input to the hash function.

Without the oracle telling you information about the hash, you have to do 2^91 online attempts.

[jerf]

"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/ if you want to play along.

[mlyle]

> 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.

Just to note: this is not the game.

The game is, given a bunch of bits of the hash output, identify which of a known set of input produces that hash output.

Identifying which word in /usr/share/dict/words has the hash:

0f??????????????????????????????9d??????d2??????????????????????

is trivial.

Yes, enumerating all possible 14 character passwords is impractical... but if it was a 10 character password input, it again would be trivial.

The point is, the hints make it possible to know whether you've got the correct answer. You have an oracle, that tells you whether a given password you're considering is correct. Without this information, you don't have that oracle and cannot complete the search offline.

edit: woops, I didn't narrow the search space quite enough! There's two matching words.

    mlyle@powerbook ~ % time ./meh.py | grep '0f..............................9d......d2......................'
     0feeefd1e67f9c16131f9fa0c581cfef9d7f1fc3d2801f157c18d5dff5db4a53 abdominocystic
    0f6fe3980f4d7d6d642868e125ebb00a17a02cec9d8e9a6cd2cdce137b63735f feminility
    ./meh.py  0.22s user 0.01s system 89% cpu 0.264 total
    grep '0f..............................9d......d2......................'  0.21s user 0.00s system 83% cpu 0.260 total

[jerf]

"The game is, given a bunch of bits of the hash output, identify which of a known set of input produces that hash output."

No, it isn't. You don't have a list. This game generates a fully random password. I did one just now and the answer is "]=-CrGl0Sv.'L:". You don't have that on your list. This is Passwordle, not Wordle. Passwordle does not operate on a fixed list of answers.

Technically, it's drawing from a smaller set of possibilities than a full 256 bit search space but it's still large enough it won't matter.

You can not enumerate the possibilities for Passwordle.

Yes, if you cut the search space arbitrarily by something like 110 bits or so, the math works differently. So? That's not the game.

The difficulty of this game, and for that matter of reversing the hash in general, from a constant list is uninteresting. The whole point is stranding you in an infeasibly large search space.

Your strategy completely depends on having a list of precomputed hashes for the entire search space. You don't and can't, so your strategy is completely nonfunctional and useless. Pounding on the details of your nonfunctional strategy will not make it functional.

[mlyle]

> Yes, if you cut the search space arbitrarily by something like 110 bits or so, the math works differently. So? That's not the game.

See- the search space is already significantly under 256-110 bits.

The search space is a bit smaller than 92 bits in passwordle. If it drew uniformly from the possible characters it would be 92 bits; it's more like 87-88 bits since it does not draw uniformly.

This is out of reach of brute force--- as I've said the entire time-- but if it were just a few characters shorter it would be within reach. 11 is doable with a lot of computing; 9 would be trivially doable. They chose 14 characters of input.

This is an interesting offline-online tradeoff. 10 guesses doesn't get you far vs. a 9 character random password in practice. But 10 guesses with this oracle lets you defeat 9 character random passwords easily. (and provides enough information to defeat 14 character random passwords, but with no feasible search strategy known at this time).

This is very different from "provides no information whatsoever". I suspect you not appreciating this is why we have a difference of opinion.

> Your strategy completely depends on having a list of precomputed hashes for the entire search space.

It depends upon being able to do a meaningful amount of search offline-- either precomputed or before your last guess.

[jimmydorry]

Nice write up. It's an unintuitive concept, but this is a good demonstration of the power of cryptography.

[acchow]

"??? 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.

[residualmind]

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]

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]

> 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]

The password is not a dictionary word, it’s randomly generated though?

[mlyle]

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.