Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Passwordle

rsk0315.github.io

Post reply on HN
Print view View original

171–180 of 263 posts

Re: Passwordle

#171

Post by Simon_says »

residualmind wrote: post #117
mlyle wrote: post #107

Earlier quoted context omitted.

Is it? 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 length of the password is 14.

  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;
  }

Re: Passwordle

#173

Post by jerf »

mlyle wrote: post #164
jerf wrote: post #148

Earlier quoted context omitted.

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…

> 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 searc…

"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.)

[1]: https://passwordsgenerator.net/sha256-hash-generator/ if you want to play along.

Re: Passwordle

#174

Post by SapporoChris »

Aeolun wrote: post #170
residualmind wrote: post #124

Earlier quoted context omitted.

Yeah because the algo is known, it is SHA256. 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 h…

> It could be more than the number of hydrogen atoms in the universe Not very likely, since the OP wouldn’t be able to hash it. Or he’s secretly demonstrating something much more awesome than Passwordle.

As a proponent for advancement, I will hope for the latter while laughing at your comment.

Re: Passwordle

#175

Post by gitgud »

acchow wrote: post #169
mlyle wrote: post #163

Earlier quoted context omitted.

Even so, I just edited my comment and elaborated. 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.

> a very large number of offline 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....

Re: Passwordle

#176

Post by throwaway6532 »

mlyle wrote: post #160
bsurmanski wrote: post #158

Earlier quoted context omitted.

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…

92 bits of entropy, and the first guess peels off about 14 bits of it. Subsequent guesses a little less. 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.

Could you do it with a rainbow table?

Re: Passwordle

#178

Post by JoshuaDavid »

acchow wrote: post #166
mlyle wrote: post #160

Earlier quoted context omitted.

92 bits of entropy, and the first guess peels off about 14 bits of it. Subsequent guesses a little less. 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.

How does the first guess "peel off" 14 bits of entropy?

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.

Re: Passwordle

#179

Post by jimmydorry »

jerf wrote: post #173
mlyle wrote: post #164

Earlier quoted context omitted.

> 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 searc…

"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…

Nice write up. It's an unintuitive concept, but this is a good demonstration of the power of cryptography.
Post reply on HN