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,
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.
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.
> 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.
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.
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...
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].
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.
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.
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:
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.
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.
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.
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.
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...
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.
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.
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 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.
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!
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.
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.
There's something interesting to note in the visualized gradient distribution after guessing some common English words: https://i.imgur.com/hDSBaYw.png
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.
