It actually would, as long as you reject a candidate password with probability proportional to it’s relative frequency. “password” in the above example would be almost certainly rejected as it’s wildly more common that one of those 1000-character passwords.
Well, the counterexample I have in mind is: flip a coin until it comes up tails, your password is the number of heads you got in a row.
While you could rejection-sample this to e.g. a uniform distribution on the numbers [0,k), this would take 2k samples, and isn’t very feasible. (As you need 22n work to get n bits of strength!)
I do agree that your trick works in all reasonable cases, whenever it’s not hard to reach k different possible passwords.
It actually would, as long as you reject a candidate password with probability proportional to it’s relative frequency. “password” in the above example would be almost certainly rejected as it’s wildly more common that one of those 1000-character passwords.
Well, the counterexample I have in mind is: flip a coin until it comes up tails, your password is the number of heads you got in a row.
While you could rejection-sample this to e.g. a uniform distribution on the numbers [0,k), this would take 2k samples, and isn’t very feasible. (As you need 22n work to get n bits of strength!)
I do agree that your trick works in all reasonable cases, whenever it’s not hard to reach k different possible passwords.