6 ms·

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

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

enkid 5y ago
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.
- mtreis86 5y ago
  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.
  - enkid 5y ago
    Sure, I guess I wasn't being specific enough. Once of the reasons to use SHA-256 is because that's hard to do.
  - eru 5y ago
    You can only reverse your hash function, if you output is at least as long as your input. 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.
- thaumasiotes 5y ago
  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.
  - eru 5y ago
    Yes, that's possible in general. Though fairly unlikely, if the hash was 'random'. We know the structure of SHA256, so we could actually answer that question. https://en.wikipedia.org/wiki/Preimage_attack 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.
jacquesm 5y ago
> 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. I'll take 12 then.
- bushbaba 5y ago
  Well we know it has to fit in a string data type. And there’s only soooo much ram available to a JavaScript variable.
  - AdamJacobMuller 5y ago
    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.
    - kzrdude 5y ago
      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.
      - mulmen 5y ago
        Huh, I realize I don’t know the answer to this seemingly simple question. Are all 256 bit vectors valid sha-256 hashes?
        talkin 5y ago
        Yes. In a secure hash function, all output bits are without bias. So all combinations exist.
        kzrdude 5y ago
throwawaynay 5y ago
"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 don't have to know the length though, just the length of potential collisions(so between 1 and whatever max length is the hash)
bsurmanski 5y ago
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. So not great odds...
- mlyle 5y ago
  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.
  - acchow 5y ago
    How does the first guess "peel off" 14 bits of entropy?
    - JoshuaDavid 5y ago
      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.
Aeolun 5y ago
> 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.
- SapporoChris 5y ago
  As a proponent for advancement, I will hope for the latter while laughing at your comment.
- jhugo 5y ago
  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...
  - Aeolun 5y ago
    Fair point, I’m just hoping that the author starts from something that could actually be input as an answer (and therefore hashes it at least once).
- eyelidlessness 5y ago
  Why not? You don’t need enough resources, just lazy seq and time!
- eru 5y ago
  > 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.)
eru 5y ago
> 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.)

enkid 5y ago

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.

mtreis86 5y ago
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.
- enkid 5y ago
  Sure, I guess I wasn't being specific enough. Once of the reasons to use SHA-256 is because that's hard to do.
- eru 5y ago
  You can only reverse your hash function, if you output is at least as long as your input. 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.
thaumasiotes 5y ago
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.
- eru 5y ago
  Yes, that's possible in general. Though fairly unlikely, if the hash was 'random'. We know the structure of SHA256, so we could actually answer that question. https://en.wikipedia.org/wiki/Preimage_attack 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.

jacquesm 5y ago

> 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. I'll take 12 then.

bushbaba 5y ago
Well we know it has to fit in a string data type. And there’s only soooo much ram available to a JavaScript variable.
- AdamJacobMuller 5y ago
  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.
  - kzrdude 5y ago
    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.
    - mulmen 5y ago
      Huh, I realize I don’t know the answer to this seemingly simple question. Are all 256 bit vectors valid sha-256 hashes?
      - talkin 5y ago
        Yes. In a secure hash function, all output bits are without bias. So all combinations exist.
        kzrdude 5y ago

throwawaynay 5y ago

"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 don't have to know the length though, just the length of potential collisions(so between 1 and whatever max length is the hash)

bsurmanski 5y ago

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. So not great odds...

mlyle 5y ago
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.
- acchow 5y ago
  How does the first guess "peel off" 14 bits of entropy?
  - JoshuaDavid 5y ago
    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.

Aeolun 5y ago

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

SapporoChris 5y ago
As a proponent for advancement, I will hope for the latter while laughing at your comment.
jhugo 5y ago
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...
- Aeolun 5y ago
  Fair point, I’m just hoping that the author starts from something that could actually be input as an answer (and therefore hashes it at least once).
eyelidlessness 5y ago
Why not? You don’t need enough resources, just lazy seq and time!
eru 5y ago
> 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.)

eru 5y ago

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