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.