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.
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.
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.
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
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...
But those who never win AND never quit are idiots.