Passwordle
rsk0315.github.ioThere is like... four people I know I could send this to who'd laugh, it's so niche. Yet I also laughed out loud when I got how conventionally impossible it is.
Winners never quit. And quitters never win.
But those who never win AND never quit are idiots.
That's because winners know when not to play.
That means quitters are winners?
No, winners never quit. Have to be true to your axioms.
"Winners never quit" and "quitters never win" are logically equivalent. It mean that you can't quit and win, ie. quit AND win <=> FALSE
The truth table is:
QUIT | WIN | result -----+-----+------------------ no | no | possible, idiot no | yes | possible, winner yes | no | possible, quitter yes | yes | impossibleTBH, I think we need at least a first-order predicatelogic to adequately model this.
In any case, I'd dispute your logical equivalence. All quitters are not winners. But not all "not winners" are quitters. Some just keep playing and losing. Like I do at chess.
Strange game
this is deep.
Is it?
6 guesses and I have 14 hex digits (56 bits) of the hash, along with knowing the population counts for all the numbers. This is enough to run a password cracker and determine the plaintext if it's a readily guessed password.
Sure, it breaks conventional use of rainbow tables, etc, but...
edit: Eh, 14 characters. OK, that's pretty resistant to anything other than debugging.
How does that help you when any of your inputs' digest is not related to any other's, not even knowing the target length of the original message? what am i missing?
The correct password is impossible to calculate from the given data, but it seems like it should be possible to check whether a password matches the data.
Yeah because the algo is known, it is SHA256.
The thing is you don't know the length of the password. It could be more than the number of hydrogen atoms in the universe, or 12. You still have to brute force or look up one possible solution (or collision thereof).
The whole thing just shows that a hash makes ZERO applicable inferable assertions about the message (password).
Thats the definition of evenly distributed hashing functions: change anything in the message, including length, and there will be no identifiable relation between the hashes of one messsage and the next you try,
I think for something this checking the source for the generation algorithm is fair game. here it is:
looks like it's 14 characters long, and each character has an independent 72.8% / 8% / 19.2% chance of being a random letter / digit / punctuation. There are 94 symbols total, so 94^14 possible solutions; roughly 92 bits of entropy. Even if you assume 10 letters, 1 digit, 3 punctuations (the "likely" distribution) it's still 75 bits of entropy. You might be able to gain an advantage through knowledge of the PRNG state, but the PRNG in v8 (xorshift128+) has a period of 2^128 - 1.function randomInt(n) { return Math.floor(Math.random() * n); } function randomPassword() { let letters = 'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ'; let digits = '0123456789'; let punctuation = '!"#$%&\'()\*+,-./:;<=>?@[\\]^_`{|}~'; let s = letters.repeat(7) + digits.repeat(4) + punctuation.repeat(3); let length = 14; let res = Array.from({length}, (() => s[randomInt(s.length)])).join(''); return res; }So not great odds...
92 bits of entropy, and the first guess peels off about 14 bits of it. Subsequent guesses a little less.
The annoying thing is, you still have to search that whole space to find the password.
But after 9 guesses, you can solve offline for the character string... it's just very expensive.
How does the first guess "peel off" 14 bits of entropy?
The digest is 64 characters long, so on average you should get 4 positions where your guess and the digest are the same, which would narrow it down to (1/16)*4 of the possibilities, corresponding to "peeling off" 16 bits of entropy.
Figuring out how to enumerate only those values which generate a hex digest that matches the known characters in the hash is left as an exercise for the reader.
You may be trolling, but that "exercise for the reader" does not have a known solution. Anyone who found one may wish to keep it secret to get rich on Bitcoin mining...
I think he meant to do it offline via brute force, then entering it
The same applies. You can't "pin" part of the hash when attempting a brute-force - that's part of what it means to be a cryptographic hash function.
There are two layers of entropy in what I'm looking at, but I only got like two hours of sleep last night.
There's the entropy of the password from which the hash is generated, which is clearly what you're addressing.
But in the game I'm seeing, the hash itself is unknown but the game gives you feedback on the contents. So pinning characters of the hash cuts down on that search space. Then there's still the matter of finding a plaintext that hashes to that value, which as you've said should evade this sort of analysis.
He didn't say you could "pin" the hash. He said you could eliminate all hashes, that don't contain the positions known, and just enumerate those which contain the known positions (perhaps by bruteforce), therefore reducing the search-space. It'd still be ridiculously expensive, of course (as in, implausible to compute in this universe). Unless I'm misunderstanding something here.
> Figuring out how to enumerate only those values which generate a hex digest that matches the known characters in the hash is left as an exercise for the reader.
It's always bothered me that the standard security jargon for an oracle for some information is to call it "enumeration". Will your service confirm whether or not a particular email address is associated with a current account? User enumeration!
In my view, it's only enumeration if I can make the service give me the email address without me having to know the address independently. :/
Could you do it with a rainbow table?
I mean, your rainbow table would need to contain 2^92 entries...
> The thing is you don't know the length of the password. It could be more than the number of hydrogen atoms in the universe, or 12.
I'll take 12 then.
Well we know it has to fit in a string data type. And there’s only soooo much ram available to a JavaScript variable.
Not necessarily. The hash could have been generated with something other than javascript.
In fact because functions like sha256 are iterative it's possible to hash a password which is longer than the RAM in a system. Technically possible to hash a password which is longer than storage in a system too, if you don't care about storing the password.
so the puzzle author could "cheat" and just present a 256-bit number and not know the preimage at all, which would be a fun shortcut.
Huh, I realize I don’t know the answer to this seemingly simple question. Are all 256 bit vectors valid sha-256 hashes?
Yes.
In a secure hash function, all output bits are without bias. So all combinations exist.
Sounds like the ideal. Can we prove that sha256 has this property?
Probably not. The point of a cryptographic hash function is to be resistant to analysis.
Can we prove it has the much simpler property that toggling one bit of the input will, on average, toggle half of the bits in the output? (Probably not.)
Depends how you define "prove"
If you calculate a billion sha256 hashes and look at the results you'll have an even enough distribution to say it's proven, but, it's not "mathematically" proven.
I mean, anything past 256 bits is going to have a collision, so that doesn't matter, but you're right that the entire point of a hash is that even if you know the hash, it's very very hard to find what the plaintext is.
There are a number of reversible hash algos. The point of hash is that the small changes in the input produce big changes in the output so even a 1-bit change to the input produces a completely different output. Some hash algos having trap door functionality is really more of a bonus.
You can only reverse your hash function, if you output is at least as long as your input.
The kind of function you describe is useful, too, of course. You can build something like them out of almost any modern encryption method:
Encryption methods have to be reversible, so you can decrypt; and they are expected not to betray anything about their inputs, so there are probably some that have this avalanche property, or can be patched to have it fairly simply.
Sure, I guess I wasn't being specific enough. Once of the reasons to use SHA-256 is because that's hard to do.
It's true that any input length larger than 256 bits will exhibit a collision. It isn't true that it will necessarily exhibit every possible output. Maybe there's an output value that is only available for ridiculously large input.
Yes, that's possible in general. Though fairly unlikely, if the hash was 'random'.
We know the structure of SHA256, so we could actually answer that question.
https://en.wikipedia.org/wiki/Preimage_attack says that pre-image attacks on hash function in general only take 2^n time (ie you don't need to look for passwords longer than 256 bits), but I don't see how they conclude that.
> It could be more than the number of hydrogen atoms in the universe
Not very likely, since the OP wouldn’t be able to hash it. Or he’s secretly demonstrating something much more awesome than Passwordle.
Who said they hashed it? The correct answer is a 256-bit value, and you're trying to guess any string that hashes to that value. Nothing requires that OP generated that value by hashing a string though...
Fair point, I’m just hoping that the author starts from something that could actually be input as an answer (and therefore hashes it at least once).
> Not very likely, since the OP wouldn’t be able to hash it.
Not necessarily. OP might have found the answer with a mathematical short-cut.
To give a really silly example: suppose my hash function just returns the length of the input string. (That's what PHP used to do for hashing at some point.)
I could tell you what my hash of a really big number is, without needing to be able to write that number down. And no shorter number would have the same hash.
SHA256 might have a similar exploit. (Though as you say finding such a shortcut in SHA256 would be much more awesome than Passwordle.)
As a proponent for advancement, I will hope for the latter while laughing at your comment.
Why not? You don’t need enough resources, just lazy seq and time!
> It could be more than the number of hydrogen atoms in the universe, or 12.
Doesn't matter. You don't really have to look at passwords longer than 256 bits, because above that you'll have guaranteed collisions.
(The exact math is a bit more complicated, because there might be so many collisions in the first 256 bits, that there are strings longer than 256 bits that produce hashes that haven't been hit before.
But the order of magnitude of 256 bits is about right.)
"The thing is you don't know the length of the password. It could be more than the number of hydrogen atoms in the universe, or 12."
You don't have to know the length though, just the length of potential collisions(so between 1 and whatever max length is the hash)
i don't think anyone has created a hash collision in SHA-256 yet (meaning, given a hash, create an input that generates the hash)
yeah but who cares? it's still 100% possible, you just need a lot of time
The length of the password is 14.
function randomPassword() { let letters = 'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ'; let digits = '0123456789'; let punctuation = '!"#$%&\'()\*+,-./:;<=>?@[\\]^_`{|}~'; let s = letters.repeat(7) + digits.repeat(4) + punctuation.repeat(3); let length = 14; let res = Array.from({length}, (() => s[randomInt(s.length)])).join(''); debugger; // どうぞ return res; }[ @some-sober-math-guy insert probabilities ]
This isn’t how Sha works
If they were dictionary words, or a similarly constrained search space, fed through SHA, this is exactly how it works. The information given after one guess excludes a whole lot of guesses as being possible solutions.
Here, there's 91.7 bits of entropy in what goes into the hash function. Each guess shaves off more than 10 bits of entropy. After 9 guesses, only one password conforming to the generation format will be possible... yes, it will be very (impractically) hard to find this password, but the rest could be done offline to find the 10th value and solve it in 10 guesses.
e.g. Make 9 random guesses.
Then, for each of the 2^92 possible input strings:
1. Hash it.
2. See if the hash matches the things we know about the hash from the previous guesses.
Right, it's a random password tho not a dictionary word
Even so, I just edited my comment and elaborated.
You can do this in 9 online guesses with feedback + a very large number of offline guesses, and have the solution for the 10th.
The information is there-- just the best search strategies known are very expensive.
> a very large number of offline guesses
Right, the entire search space of random passwords.
The matching hash characters are tongue-in-cheek. They don't help you. They could've just given you the entire hash up front and you would still have to search the entire random password space. Sure, you could do it "offline", but it would still take forever to compute
This is the best description of why it's completely infeasible to make a system to guess it.
It would be only be possible if the password length was below a certain threshold (maybe 30 characters) beyond that limit, there wouldn't be enough atoms in the known universe in order to store every hash/password combination.... making it physically impossible....
In passwordle, the input is a 14 character password made up of letters, numbers, and punctuation, chosen with some bias. There's less than 92 bits of entropy (the bias shaves off a few bits of effective entropy but I'm too lazy to calculate it).
That is-- out of the range of current brute force, but if it were just a few characters shorter, it could be attacked with this oracle technique no problem.
How would the oracle technique help at all? Like the other commenter said, they could just give you the hash upfront, and you'd still be stuck with bruteforcing the entire space of characters.
> How would the oracle technique help at all?
If they give you the hash upfront (or this oracle), you can test passwords offline without using up a limited number of guesses. It may be very computationally expensive to brute force the space, but the information is there.
If they don't, you get 10 guesses, and you have effectively no chance of guessing the password.
Ah, I see what you mean. Yes, if you don't even have the entire hash, you're kind of out of luck.
> It may be very computationally expensive to brute force the space, but the information is there.
If the password is long enough, it will take longer than the heat death of the universe to brute force the space. So in practice, brute forcing secure passwords might as well be impossible.
> Yes, if you don't even have the entire hash, you're kind of out of luck.
Well, no-- I'm saying that if you have 9 guesses, you can get enough of the hash that you can eliminate all of the passwords but 1.
> If the password is long enough, it will take longer than the heat death of the universe to brute force the space. So in practice, brute forcing secure passwords might as well be impossible.
Here, the password has 88-90 bits of entropy. Out of reach to brute force, but just a few characters shorter and it wouldn't be. And, of course, if there's weaknesses in the hash function ever found, it may be able to elide some or all of this search process.
Sure it is, dictionary attacks are extremely efficient, if the password is made out of dictionary words.
I ended up crossposting it to the few security rooms I'm in for quick laughs
But for what it's worth, this also serves as a great initial CTF-type introduction to how debuggers work in web browsers.
If the debugger is open, Passwordle automatically breaks the execution right where the answer is determined.
Now that's service.
TIL there's a "debugger" keyword[0] in JavaScript that auto-sets a breakpoint at that line.
[0] https://developer.mozilla.org/en-US/docs/Web/JavaScript/Refe...
int 3 of Javascript. I use it all the time because webpacked assets make it hard to find the line of code I am looking for.
If you build source maps this isn’t a problem.
And if you're using nodejs woth source maps, but still getting horrid stacks: "--enable-source-maps"
> NODE_OPTIONS="$NODE_OPTIONS --enable-source-maps"
that is so funny, I learned that today too on a completely different page!!!
As someone that works at an authentication API company, there are _dozens_ of us who found this hilarious.
> Yet I also laughed out loud when I got how conventionally impossible it is. Maybe give it a whirl with https://sha256algorithm.com/? haha
It's not impossible. I hear Bruce Schneier got the correct hash on the first try.
https://www.schneierfacts.com/
(Sorry for the very HN:ish post, but I feel it's somewhat in the spirit of this story)
Hah!
I don’t get this one, though: https://www.schneierfacts.com/facts/694
Searching for the number gets me Mill’s Constant, but I don’t get the connection to sugar or why it would be repeated.
Well, it made me laugh. Thanks, that's what the Internet is for! (Namely, amusing content about the technicalities of the Internet.)
You can easily guess the right sha256 just using random strings and overlapping correct characters and then you can run a dictionary attack on it, or a brute force one if it's not too long.
You get a SHA256 hash of each guess. The hints you get on each guess are useless to help you with the next guess.
Nope. Try yourself with a, b, c, d, e, f, g as guesses. You will see that green letters that are coincident will be the same. So to reconstruct the original SHA256 of the password is easy. The problem then turns like every other hash -> password reconstruction: hard if the original secret is hard to guess via dictionary/brute-force, otherwise easy.
Ah, I misunderstood the point you were making. It's still true that each hash won't help you make the next password guess, but you can iteratively fill in parts of the overall hash.
I'm not sure that really helps you much though, as you don't have enough guesses to get the entire hash. And even with that, you may or may not succeed.
Still, good point!
You just need a rainbow table of... 14 character... random passwords... across the allowed symbols. Should be able to build that with Cuda, OpenCL, or OpenMPI in a matter of X weeks given Y hardware budget. Sorry, solving for X and Y is left as an exercise for the reader.
Replying to self, if the password is based on a dictionary word, then it's much more doable, as you almost certainly don't need the entire hash. I think you made that point too...
Well, go ahead, we're waiting.
I laughed. It’s excellent, and great fit for the crowd here.
I laughed so hard
Oh wow! You have a lot of friends!... (unironic self deprecating voice)
Someone more capable than I should make the final form of this: No green or yellow feedback is provided, but only the timing information used to calculate it. If cryptographers are serious about side-channel attacks, why not show off the danger using no-information Wordle?
(edit: Absurdle was taken)
An Absurdle exists[1], but instead of giving no hints it is adversarial, e.g. changing the secret word to dodge your guesses.
If you like this, you might like Quantum Childminding too: https://www.puzzlescript.net/play.html?p=f7712f978d624c66f1f...
It's about looking after Schrodinger's daughter; similar to the above, she appears only if you prove she cannot be anywhere else.
I like this game a lot, especially how it's easy to understand & fun to play with.
Thanks for that, I really enjoyed it. Thats a very imaginative short game
Thanks for highlighting this — I’ve been waiting for something else by QNTM! I’ll note he has done this sort of thing before, in the form of HATETRIS [https://qntm.org/hatetris].
That's actually quite fun!
Given that speed/timing is important, and the rules are designed to impede your progress, how about calling it Hurdle?
Absurdle already exists: https://qntm.org/files/absurdle/absurdle.html ;)
They should name it something else as absurdle is already taken.
Timing of SHA-256 reveals only the length of the input.
Password is randomized on each load. Author has conveniently left a debugger statement in the code.
Part of me wishes the author just took common passwords from rockyou.txt so that they're at least guessable. Though random really does add to the absurdity.
Or use a new password every day like worle. So you have a community effort to guess it
That sounds like Bitcoin with extra steps
Jokes aside, that would actually be fun if the password is actually reasonably guess-able, I would definitely give it a try if that existed
Oh no, now someone will make wordlecoin, where you have to work with others sharing hints to mine each block.
Proof-of-Wordle
Is any of the information (yellow/green for characters) presented getting you closer to the real answer in any meaningful way though?
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.
> 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.
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.
> 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.
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.
> 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.
"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.
> 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"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.
> 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.
Nice write up. It's an unintuitive concept, but this is a good demonstration of the power of cryptography.
"??? 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.
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.
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.
> 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.
The password is not a dictionary word, it’s randomly generated though?
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.
Inherently with a (proper) hashing algorithm, the value and placement of characters in the hash means next-to-nothing in terms of the actual original text. For example:
password = 5e884898da28047151d0e56f8dc6292773603d0d6aabbdd62a11ef721d1542d8
passwurd = 1966e583daff0fce5630d5de44f303f0e77f77940f02c7d648defadc31059c7b
Notice they're very different results, even though the original text only has 1 character difference.
The Avalanche effect for anyone interested in reading more.
No, that's the joke of the site.
It reduces the search space to find the hash, but not the search space of what hashes to that value.
Sort off, if you already have a lookup table of possible solutions.
... which you won't, because the space is too large (around 90 bits of entropy if I'm not mistaken, bit less, so 10^27-ish possible solutions).
My first try was "hunter2", then I gave up.
It's OK, the goal is to find a collision
I did not know about the debugger statement until I read your comment: https://developer.mozilla.org/en-US/docs/Web/JavaScript/Refe... . Thank you.
Massively useful! I also recently learned you can right click a line of code in the chrome debugger to add a logpoint - i.e. "log the value of this expression when you reach this point in the code" - so I don't have to manually add console.log statements. Basically the reverse of discovering the debugger statement!
One more trick:
Add a conditional breakpoint with the condition: `value = "someOverrideValue", false` to make the breakpoint change the value when it is reached without actually stopping execution. Great for when you need state changed but the app is always trying to override it. Here's a video from a talk I gave five years ago that demonstrates that: https://youtu.be/uixXOTCNbhs?t=1182
Woah. Now that is incredibly useful.
It's also used by malicious websites that don't like security researchers looking at their source, just to say.
> you can right click a line of code in the chrome debugger to add a logpoint...so I don't have to manually add console.log statements
Thank you, this is the best thing I've learned in 2022.
Next try https://www.replay.io, which allows you to add logpoints to code that has already executed.
You can also right click a DOM element in the inspector and click `store as a global variable`. It will automatically do the following for you
temp1 = document.querySelector(SELECTOR_FOR_NODE_YOU_PICKED)
This was news to me too
It's pretty powerful. I oftentimes struggle to get VS code to pick up a breakpoint when debugging serverless node functions, but the debugger statement usually gets it working.
Got it in one "guess." Apparently どうぞ means "here you are." Makes me think the brick was deliberately left in the door for folks who look for such things.
My first guess was "friend", a la the Doors of Durin.
It should be mellon.
“The Four Most-Used Passwords Are Love, Sex, Secret, and God”
You hacker... https://www.youtube.com/watch?v=0Jx8Eay5fWQ
I tried hunter2
I copy/pasted ****; no luck.
Wordle has a "hard mode" where guesses aren't accepted unless they reuse hints previously given. This is clearly missing from this adaptation.
0/10 literally unplayable.
They cynical side of me notes what a great phish this could be. People are inclined to enter passwords they regularly use just to see the visualization of their favorite passwords. With a little logging -> send home, you'd be harvesting passwords left and right.
Would the type of people amused by this have that weakness though?
It's hosted on Github Pages which is just static file serving. And thanks to CORS restrictions I don't think you could phone home.
Unless there's a workaround I'm not thinking of.
GitHub pages are served with Access-Control-Allow-Origin: *, so the SOP doesn’t apply.
They also don’t set a CSP header, which opens up the opportunity to exfiltrate data by other means, e.g having the browser load an image on your.site/$password.jpg.
Ah right. Simple!
The CORS policy is set by the server receiving the request, not the page/server sending it.
Can't you embed off-site images?
Well damn, I’ll have to change Hunter2 everywhere now.
is a password very useful without any other identifier though?
Also see dwordle, where you have to guess a function pointer: https://twitter.com/zhuowei/status/1482175505185095682
nice, though I'm very disappointed the answer wasn't hunter2
I don’t get it? Why would the answer be *******?
Because that would be hunter2 hilarious. I'd laugh my hunter2 ass off!
For reference: https://knowyourmeme.com/memes/hunter2
(I omitted the original bash.org link because they seem to be down at the moment!)
I think you should watch your language, young person.
Wait, you can’t see it either?
Yeah same. From the source code, the answer is a random 14-character string, generated on load:
function randomPassword() { let letters = 'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ'; let digits = '0123456789'; let punctuation = '!"#$%&\'()*+,-./:;<=>?@[\\]^_`{|}~'; let s = letters.repeat(7) + digits.repeat(4) + punctuation.repeat(3); let length = 14; let res = Array.from({length}, (() => s[randomInt(s.length)])).join(''); debugger; // どうぞ return res; }I wish it accepted a given password from a url query parameter, so this url would work:
https://rsk0315.github.io/playground/passwordle.html?passwor...
Or the way bikeshed.com lets you configure the color with the domain name, like:
Then they could monetize it by selling gullible suckers NFTs of urls pointing to Passwordle games of their passwords.
Even better would be to link to the hash of the password, then there would be no way to guess.
The point is that most people gullible enough to buy NFTs won't care about having their password in the URL. Those ignorant suckers are the same ones who complain that the government should step in and enforce their precious decentralized Libertarian "ownership" of their ape jpeg when somebody "steals" it with the "Save as..." menu. They fall for NFT scams for the same reason they fall for hunter2 password scams.
I treated this the same way I started when solving absurdle, wordle, and hurdle: find the database, get crackin' on a decision tree. But, after estimating 1.2e17 possible passwords in the "database," it only feels fair to accept the invitation to use the debugger.
Literally my first guess.
I tried in these classics in vain:
- hunter2
- password
- correcthorsebatterystaple
Thinking about this a bit deeper, it's a pretty good system for explaining a bunch of technologies to others (those mentoring, etc). There's the reason why it's not possible to win via the front door, how basic client side JS apps are put together, basics of using debugging tools...
I've tried 123456, password, and secret, and I'm all out of ideas.
hint: it needs to be 14 characters
So password123456 then?
passWORDLE 1/1064 0 ⬜0 https://rsk0315.github.io/playground/passwordle.html
on Chrome, open Dev Tools and type `res` to get the password :)
Gee, I'm so glad somebody posted this so that I can cheat on a game that is not competitive and that I'm playing voluntarily and that has no bragging rights because of how niche it is.
Yes, but the point is to show that each password produces a sha256 not correlated to the sha256 of other passwords. That people actually tried to guess this way shows that not everyone is aware of the sha256's purpose.
Not defined for me
This is begging for a hard mode option
I laughed. I can't wait for this to be used as a problem on some CS final.
literally made me laugh out loud, well done
Me too but this can never be sold right
What, Wired Magazine won't buy this for $3 Million?
I meant solved...
Same here! I love the absurdity of this one given the nature of cryptographic hash functions.
Plain SAH256? Come on, use a salt please!
This would be kind of fun to write a solver for. You'd burn the first few guesses to get some positional constraints, then filter a rainbow table down to viable guesses. I'm not sure you'd be able to get a very good success rate in just 10 possible guesses though.
It could work theoretically (the password contains around 90 bits, and from each row you can glean, dunno, some 64 bits of info (64 characters that can be yellow, gray or green, so 101 bits, but there are constraints on that - very unlikely that all characters are gray, for example)).
In practice, I don't think it's computationally feasible. You can't keep all 2^90 = 10^27 possible solutions around in memory. Bitcoin does 200 EH/s, so 2e20 hashes/s. So the entire bitcoin mining network would have to work for 2 months (5e6 seconds) or so - don't see how you can meaningfully reduce the work (it would indicate a flaw in SHA256, no?).
To me it seems like the password is 14 bytes, because they're 14 characters (112 bits). How do you get 90 bits?
It also uses 96 possible characters for each digit. Just storing the 96^14 different passwords without even adding their corresponding SHA hashes would require 5646 yottabytes. Which is more than 4 orders of magnitude larger than all the world's digital storage capacity combined together.
As you say, each of the characters is not a full 8 bits (namely a character out of an alphabet of 256), but chosen from a smaller alphabet of 96 characters, and log(96)/log(2) = log_2(96) ≈ 6.58, so 6.58 * 14 = 92 bits. Then I deducted a bit or two ad-hoc for the way they're drawn, with letters overrepresented. This could be computed more precisely. But it's not more than 93 bits, and not less than 83 bits, I'd say.
Thank you so, so much for explaining this.
If you can casually write an algorithm to break a modern cryptographic hash in 10 guesses... I would like to know. Because then I have to decide if I want to be a very good friend of you, once you get rich, or if I want to stay as far away from you as possible once the state intelligence agencies come after you.
It's not a cryptographic break.
It's simply a regular password cracking algorithm, but with instead of knowing the full hash, you only know a partial hash.
It should be viable, even without rainbow tables. That's why plain, unsalted sha256 is very unsafe for password storage.
It is not in the slightest bit viable. You’re seeking to reverse a one-way hash function. Knowing the full hash does not help you to find the original password; password cracking algorithms don’t work by reversing the hash, but by trying zillions of passwords, following typical human password patterns to increase the probability of success, and possibly using rainbow tables as precalculated hashess, until they find something that matches.
But we don't need to reverse the one way hash. The goal is simply to find the original password and brute forcing is good enough.
The brute forcing algorithm doesn't care that you only have a partial hash. All that does is increase the chances of collisions. (Side note, rainbow tables might care, I'm not sure how suitable they are for wildcard hash matches)
For example, I burned 8 guesses and I got enough greens to give me 108 bits of the hash. You can scrape out a bit more entropy by processing the yellows and greys, but 108 bits is more than enough to identify the password with very little chance of collisions (the chance of collisions hits only hits 50% once you get to 17 character alphanumeric+symbol passwords).
You can then use the two remaining guesses to resolve any collisions and lock in the correct answer.
The goal is to find the original password, but you’re finding the hash. Finding the hash doesn’t help you in the slightest with finding a password that hashes to that.
Put another way: here, I’ll tell you the hash: DF50B84AFEE438987ECE1542A4D1BCAB4079215EF38C3C3CBB2F4A122886DF27. Now tell me the password. You have 0% chance of succeeding in your lifetime, to at least a dozen decimal places.
It all depends on how complex the password is.
For an 8 char password, it would take a few min.
For a 10 char alphanumeric password, several months on a single GPU
For a 12 char alphanumeric password, Half a century on a single GPU, less if you are willing to throw money at it.
The time would be significantly reduced if the password was vulnerable to a dictionary attack
If passwordle had a list of all possible solutions like wordle does, this would be doable.
If it had a list of all possible solutions, it'd take quite a bit more bandwidth to load...
Hard mode: Password + Salt
Solved mine in Firefox, using the JS debugger, and viewing the scope of the randomPassword function. "nSQXy3Qwl3E<qV". All your wordle are belong to me!
I won*!
*grabbed the expected hash from judgeEvent(), then made hash() return it
edit: I see from other comments he actually pre-loaded randomPassword() with a debugger statement. Oh well!
I feel like Kramer with the moviefone number. "why don't you just tell me..."
This is hilarious, I love it! I've already shared it half a dozen times...LOL!
You could do a version of this with a two-way function like base64 and it would still be possible but very difficult without programmatic guessing.
No bcrypt?
Should've been Argon2id
Just checked the source, I am so sad that the answer is actually random. Couldn't read the comments in Japanese though
Please do not use SHA256 for storing passwords, use Argon2
;)
It's not hunter2, correcthorsebatterystaple, password123, swordfish, or my gmail password. Anyone got it?
Oh my goodness this is the out loudest I have laughed at a tech thing in a long time. Cheers to you :)
this would be a good variant for Grant Sanderson to point his information theoretical solver at as a way to educate us on how/why sha256 leaks information that might be leveraged to crack a password, why to salt our hashes, etc.
What exactly is this showing ?
It's a clone of the popular wordle game where you have to guess a word, except here, you have to guess a password but instead of telling you which characters of the password are correct it tells you which characters of the corresponding SHA-256 hash are, which makes this pretty much impossible to solve as the whole point of a hash are that small changes in the input (such as a different character in the password) results in big changes in the hash.
> pretty much impossible to solve
Literal understatement of all time…
A quantum computer could potentially turn it from impossible to merely nearly impossible.
how so?
https://en.wikipedia.org/wiki/Grover%27s_algorithm
If it works as believed, it should effectively reduce solving SHA-256 to solving SHA-128. Which is extremely difficult, but theoretically possible.
You can make a rainbow table of the possible passwords & converge pretty quickly
Don't hash passwords. Use pbkdf2 or some better alternative (I suggest pbkdf2 because it's widely implemented)
> You can make a rainbow table of the possible passwords
Can you? Here? 14 letters from an alphabet of around 90 characters?
There's a certain network getting through quite a few SHA256s, just give it a couple decades
It's Wordle but it hashes your guess before applying hints.
At least let people change the hash function to MD5 to give them a chance! :D
More or less how PoW works…
I was expecting the hash to be MD5 to at least give people a chance! :D
There's something interesting to note in the visualized gradient distribution after guessing some common English words: https://i.imgur.com/hDSBaYw.png
That's a consequence of certain characters not reappearing in the hash as compared to the hash of the actual password.
This would become more apparent if this traded in sha512s instead.
I have not laughed like this for weeks. Well done OP.
passWORDLE X/10 5 46 ⬜13 5 46 ⬜13 1 44 ⬜19 4 46 ⬜14 5 42 ⬜17 3 42 ⬜19 6 44 ⬜14 0 45 ⬜19 5 41 ⬜18 3 43 ⬜18
I will successfully solve this one day.
the wordle craze is getting out of hand
Well, that’s not "dolphins".
What the hell.
brilliant. now someone do this for Bitcoin/Ethereum address private keys
(asking for a friend. cough)
Incredible. Lol'd pretty hard.
Seems kinda impossible to do, lel
maybe wordle is just a frontend for a human powered distributed dictionary attack
do I gain a bitcoin if I win ?
well if you manage to break sha256, sure you do ;)
This is great fun. Thank you.
My wife was looking at me when I opened this.
“What are you grinning at?”
I just locked my phone and put it face down on the table…
Why would you do that xD - I'd have explained it to her instead, doing what you did I'm not sure I'd be happy about as wifey ...
You see, if he does that when it’s perfectly innocent, then his wife would be conditioned to ignore the behavior in the future. So when he’s truly up to no good at some point, he won’t be doing anything different than “normal”. The man is probably some kind of criminal mastermind.
Ha! Quite true, maybe poor attempt at humour stopping the story there.
I actually did explain after that ellipsis, her response:
“That’s niche!”
She is also well aware of what hashing is.
Aaah this hurts my brain
this is insanely funny
This is insanely funny
This is a masterpiece.