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

161–170 of 263 posts

Re: Passwordle

#161

Post by acchow »

mlyle wrote: post #159
acchow wrote: post #156

Earlier quoted context omitted.

This isn’t how Sha works

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…

Right, it's a random password tho not a dictionary word

Re: Passwordle

#162

Post by MattPalmer1086 »

antirez wrote: post #110
moritonal wrote: post #7

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.

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.

You get a SHA256 hash of each guess. The hints you get on each guess are useless to help you with the next guess.

Re: Passwordle

#163

Post by mlyle »

acchow wrote: post #161
mlyle wrote: post #159

Earlier quoted context omitted.

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…

Right, it's a random password tho not a dictionary word

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.

Re: Passwordle

#164

Post by mlyle »

jerf wrote: post #148
mlyle wrote: post #113

Earlier quoted context omitted.

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

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

Re: Passwordle

#165

Post by kzrdude »

AdamJacobMuller wrote: post #153
bushbaba wrote: post #147

Earlier quoted context omitted.

Well we know it has to fit in a string data type. And there’s only soooo much ram available to a JavaScript variable.

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.

so the puzzle author could "cheat" and just present a 256-bit number and not know the preimage at all, which would be a fun shortcut.

Re: Passwordle

#166

Post by acchow »

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.

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

Re: Passwordle

#167

Post by acchow »

mlyle wrote: post #113
jerf wrote: post #76

Earlier quoted context omitted.

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

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

Re: Passwordle

#168

Post by [deleted] »

mlyle wrote: post #107
moritonal wrote: post #7

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.

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.

[deleted]

Re: Passwordle

#169

Post by acchow »

mlyle wrote: post #163
acchow wrote: post #161

Earlier quoted context omitted.

Right, it's a random password tho not a dictionary word

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

Re: Passwordle

#170

Post by Aeolun »

residualmind wrote: post #124
thewakalix wrote: post #121

Earlier quoted context omitted.

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.

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.

Post reply on HN