On: Passwordle

[bsurmanski]

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 → bsurmanski]

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 → mlyle]

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

[JoshuaDavid → acchow]

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.

[3np → JoshuaDavid]

You may be trolling, but that "exercise for the reader" does not have a known solution. Anyone who found one may wish to keep it secret to get rich on Bitcoin mining...

[sva_ → 3np]

I think he meant to do it offline via brute force, then entering it

[3np → sva_]

The same applies. You can't "pin" part of the hash when attempting a brute-force - that's part of what it means to be a cryptographic hash function.

[cestith → 3np]

There are two layers of entropy in what I'm looking at, but I only got like two hours of sleep last night.

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.

[sva_ → 3np]

He didn't say you could "pin" the hash. He said you could eliminate all hashes, that don't contain the positions known, and just enumerate those which contain the known positions (perhaps by bruteforce), therefore reducing the search-space. It'd still be ridiculously expensive, of course (as in, implausible to compute in this universe). Unless I'm misunderstanding something here.

[thaumasiotes → JoshuaDavid]

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

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

[throwaway6532 → mlyle]

Could you do it with a rainbow table?

[paledot → throwaway6532]

I mean, your rainbow table would need to contain 2^92 entries...