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;
}
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.
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!
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
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.
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.
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:
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.
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.
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.
"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.)
> 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:
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.
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.
"??? 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.
There 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.
TBH, 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.
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.
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,
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.
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.)
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.
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.
I think for something this checking the source for the generation algorithm is fair game. here it is:
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;
}
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.
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...
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. :/
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...
> 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.)
> 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.)
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;
}
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, 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.
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.
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.
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.
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...
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.
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.
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...
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.
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.
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.
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.
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?
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].
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.
262 comments
[ 4.4 ms ] story [ 254 ms ] thread(I omitted the original bash.org link because they seem to be down at the moment!)
https://rsk0315.github.io/playground/passwordle.html?passwor...
Or the way bikeshed.com lets you configure the color with the domain name, like:
https://bisque.bikeshed.com/
Then they could monetize it by selling gullible suckers NFTs of urls pointing to Passwordle games of their passwords.
- hunter2
- password
- correcthorsebatterystaple
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.
https://en.wikipedia.org/wiki/Avalanche_effect
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.
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.
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
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:
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.
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)
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.)
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.
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?
*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!
http://tolkiengateway.net/wiki/Doors_of_Durin
“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.
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.
(edit: Absurdle was taken)
https://qntm.org/files/absurdle/absurdle.html
[1] https://qntm.org/files/absurdle/absurdle.html
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.