Passwordle
rsk0315.github.io
rsk0315.github.io
But for what it's worth, this also serves as a great initial CTF-type introduction to how debuggers work in web browsers.
Now that's service.
[0] https://developer.mozilla.org/en-US/docs/Web/JavaScript/Refe...
> NODE_OPTIONS="$NODE_OPTIONS --enable-source-maps"
> Yet I also laughed out loud when I got how conventionally impossible it is. Maybe give it a whirl with https://sha256algorithm.com/? haha
But those who never win AND never quit are idiots.
The truth table is:
QUIT | WIN | result
-----+-----+------------------
no | no | possible, idiot
no | yes | possible, winner
yes | no | possible, quitter
yes | yes | impossibleIn 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.
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.
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'll take 12 then.
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.
In a secure hash function, all output bits are without bias. So all combinations exist.
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.)
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.
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.
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.
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)
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...
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.
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.
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.
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. :/
Not very likely, since the OP wouldn’t be able to hash it. Or he’s secretly demonstrating something much more awesome than Passwordle.
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.)
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.)
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;
}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.
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.
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
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....
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.
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.
> 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.
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.
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!
https://www.schneierfacts.com/
(Sorry for the very HN:ish post, but I feel it's somewhat in the spirit of this story)
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.
(edit: Absurdle was taken)
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.
Thank you, this is the best thing I've learned in 2022.
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
temp1 = document.querySelector(SELECTOR_FOR_NODE_YOU_PICKED)
password = 5e884898da28047151d0e56f8dc6292773603d0d6aabbdd62a11ef721d1542d8
passwurd = 1966e583daff0fce5630d5de44f303f0e77f77940f02c7d648defadc31059c7b
Notice they're very different results, even though the original text only has 1 character difference.
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.
??? 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.
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.
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.
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.
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.
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.
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 totalNo, 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.
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.
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.
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.
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
Unless there's a workaround I'm not thinking of.
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.
(I omitted the original bash.org link because they seem to be down at the moment!)
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;
}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.
- hunter2
- password
- correcthorsebatterystaple
on Chrome, open Dev Tools and type `res` to get the password :)
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?).
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.
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.
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.
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.
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
*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!
;)
Literal understatement of all time…
If it works as believed, it should effectively reduce solving SHA-256 to solving SHA-128. Which is extremely difficult, but theoretically possible.
Don't hash passwords. Use pbkdf2 or some better alternative (I suggest pbkdf2 because it's widely implemented)
Can you? Here? 14 letters from an alphabet of around 90 characters?
This would become more apparent if this traded in sha512s instead.
(asking for a friend. cough)
“What are you grinning at?”
I just locked my phone and put it face down on the table…
I actually did explain after that ellipsis, her response:
“That’s niche!”
She is also well aware of what hashing is.