This is discussion archived from a time before the current discussion method was installed.
Seven Seals: "Even worse is when the passwords being tried aren't sequential. It's extraordinarily difficult to go through a large quantity of codes randomly without checking for duplicates, unless you keep a huge list of failed passwords."
Well, to be pedantic, it would be trivial for the password tries to be sequential, but pseudorandom. This wouldn't require a list of duplicates and still appear random. Of course, that doesn't explain why you'd do this instead of picking the natural order, unless password distribution isn't even and you know something about it.
In fact, if systems really did have a sort of "proximity detection" to see whether you're getting "closer" to the password, the sequence wouldn't be random, but moving along a curve to the right point in "password space". Of course, that's exactly the sort of "Mastermind" system that's trivial to defeat...
Webrunner: You'd have a VERY specific pseudorandom algorithm that a) had no duplicates, and b)covered the entire space. Most stock random functions wouldn't do that.
Red Shoe: It's not that hard. It's usually called "shuffle".
Webrunner: Then you're already starting with an array full of the entire sample space, which you had to generate in order already
Seven Seals: OK, OK, I was wrong. It's not trivial. I can't even say for sure you can devise such an algorithm in general. (Of course, it mustn't take up a linear amount of storage.)
Robert: Pick a number co-prime to the number of possible passwords, and advance that many each time. Combine this by ordering the passwords by a permutation of them - e.g order the passwords so that they're in alphabetical order when spelt backwards - and it will look quite random, superficially.
The point of doing this would be to get round any algorithms looking for people trying passwords systematically, having already got round the maximum tries limit, but a security system would have to be pretty badly designed to use a algorithm that could be fooled by this approach
Random832: Linear congruential generator
look for the phrase "The LCG will have a full period if". "a) Had no duplicates" is generally considered a quality of a _poor_ pseudo-random number generator - this is solved in classic UNIX's rand() function by having the output be only a portion (the top 16 bits IIRC) of the actual result.
Looney Toons: While I am in no way an administrator for the board, I think I speak for all the rest of us when I say that's more than enough math geekery for this topic.
Matt: Why even bother worrying about duplicates? If you just try passwords at random, the fact that you'll try some of them twice or more before you happen to hit the right one, does not actually increase the expected time before you DO hit the right one, by much at all. I forget whether it's a factor of 2 or of e (2.78..), but either way if you can afford a brute-force search at all, then you can afford that. There are ways to avoid duplicates without storing a huge table (hint: you don't want a pseudorandom *generator*, you want a pseudorandom *permutation*); it's not all that hard; the details of how to do it are beyond the scope; but you don't need to do it at all. Just let the duplicates happen. I'm going to delete the offending bit, because it seems clear that A. it's wrong, and B. several other people have noticed that it's wrong before now.
