It is not passwords used by all users, it’s only the passwords that you have used. They simply hash your new proposed password to the last 99 that you used to see if they get a hit.
At one secure facility where I worked, they did things this way:
Users don’t get to choose their passwords at all. You can change your password whenever you wish, but the system just chooses a random 6-letter password for you. (This was mid-1970’s, in a facility that was NOT networked with the outside world. So that was considered secure enough.)
I knew one user who had this strategy for getting a password he could remember: When he wanted a new password, he just kept asking for a new one over and over until he got a 6-letter combination that was pronounceable.
Hi, who summoned me? Do you have a problem ticket? 
Where I’m at now, we’re moving to require 16-character complex passwords for Active Directory, and some applications are moving to two-factor auth with SecurID tokens. I’m just waiting to hear the wailing, and so glad I’m not on the hell desk.
We just keep yubikeys plugged into our machines to serve as a second factor and don’t rotate passwords very often. Memorized and frequently-rotated passwords doesn’t scale well at at.
I do not know where you work but this seems onerous.
If you work in super-secret defense related stuff for the government maybe frequent password changes make sense.
If you work at an animal shelter helping to adopt dogs and cats your IT guy has a serious power trip issue.
Best practice for you (read: anyone) is to use password phrases. Easy to remember and change but difficult for a bad guy to guess.
So not:
- nEr1k!^K6
Instead:
- MydogSUSIEisAwesome123!
When you have to change that password:
- MydogSUSIEisAwesome456!
And so on. Easy for you to remember. Super hard for bad guys to break.
About as secure as you can get without a random password being assigned to you.
I wonder how many users in secure facilities around the country have
as their password.
Song lyrics. I use the first letter of favorite lyrics.
Hello darkness, my old friend
I’ve come to talk with you again
Because a vision softly creeping
Left its seeds while I was sleeping
And the vision that was planted in my brain
Still remains
Within the sound of silence
becomes
Atvtwpimbst&8, using a special character and a number.
I’ve found that random capitalizations cause me problems.
Then there’s the extra fun, due to having a multi-language keyboard layouts. There are very few special characters which are at the same place in both English and German. And I always avoid y and z.
At least with Windows 10 it’s possible to see what I typed, so I can see if my keyboard layout is not what I expected.
I do the song lyric thing too. I end it with the same number and special character. Like the &8 in the other example, but mine is different.
My job requires passwords be changed every 45 days. I’ve been there since 2002. I’ve had to change my password 150 times thus far. From the start I built a specific alphanumeric progression into the password, so all I have to do is substitute the next letter/digit/symbol of the progression into its proper place in the password (the typical 11 character mess of caps, numbers, symbols and lower case) whenever it needs changing.
Failure to change it on time results in hours spent trying to get a hold of the IT helpdesk, so I avoid that.
Once I had the basics of it burnt into my brain, it really works pretty well. I’m sure it’s not as secure as it could be, but it’s good enough for government work.
Great system. Which also doesn’t scale to the general public or the plethora of public-facing websites & apps each with different authentication infrastructures & user bases. I don’t mean that as criticism of you or your employer’s plan; I’m just making an observation about the world.
On a mostly-related note …
I have enjoyed the move over the last couple of years to use mobile phones + SMS as the 2-factor device. i.e. fill in your UserID & PW then we’ll send your phone a text with a secret key for you to enter into our website / app.
Followed a couple weeks later by all those text messages needing to have boilerplate added “We will NEVER call or text you asking for this code! NEVER share it with anyone!”
IOW, it took the bad guys about 47 seconds to invent their social engineering workaround to this 2-factor technique.
The battle rages on.
I prefer using an authenticator app over the SMS system, but I only have six logins that use these apps.
I don’t use song lyrics but instead a phrase about one of my old girlfriends (and rotate between them). I won’t tell you what the phrase is, except to say it’s usually quite memorable. Plus I usually smile as I enter it.
Along those lines: we all have a 4-digit PIN at work for the registers, and because {reasons} wind up needing to use each other’s a lot.
One co-worker uses 3922 for hers. Why?
“My ex husband. When he was 39 he could fuck like he was 22.”
Memorable.
This is actually riskier than you would expect, because some systems silently truncate passwords over a certain length, so you end up only using the first 8/16/32 characters of a long phrase. For example, as recently as six months ago Zoom would silently truncate a password to the first 32 characters, though they seem to have changed to rejecting any over 32 characters instead. Also, while it makes the password hard to guess initially, it’s not as good as a random password over time because ‘change the pattern at the end’ is generally easy for an attacker to figure out. If the plaintext of your password gets leaked one time (like with the Sony website), it’s pretty easy to try varying the ending with things like 234! 124! 456! 123@. (The first part is one to be careful of, the second one is just for pointing out the technical weakness, I don’t think it’s overly risky in real situations).
Back in the 90s, a company I worked at got a firewall that ran on Free BSD. We put it on the network using default setting for the few weeks until the training was scheduled, and once we had training we would customize it. To be sure it was safe, we used this technique, and set the root password to something like “Firewall@RoomName#MispledCompanyName$RandomPersonName&Date” to be safe. When we went to the class, the instructor mentioned that FreeBSD silently truncates all passwords to 8 characters, so instead of a long, impossible-to-guess password we instead had cleverly let a firewall with a root password of “Firewall” sit on the net for several weeks. Good thing bots weren’t as big of a deal back then.
I work for an institution of higher education and we are required to change passwords each semester, so 3 times per year, with no duplication. Several years ago I selected a rather lengthy poem that I know by heart and have been systematically using lines from it (similar to the song lyrics example) with substitutions of special characters and numerals for alpha characters plus case changes where appropriate or easily remembered. As in “0nc3 Up0n @ T!me”. I’m now a couple of stanzas into the poem and it should last me until I retire sometime in the next 3 - 5 years.
Be careful with that. The password hacker/cracker community is on to all those tricks.
My business gets around that by requiring that it must have at least four characters different than each of the last 10 passwords I used. There is also one service I use where the password cannot contain any “common” word of two letters or longer.
I always thought passphrases would be easier because they could try to figure out which words most commonly go with which other words. And I find using random words entirely impossible to remember, despite what Munroe says in his comic. And, yes, the fact that passwords can often get truncated, and that it’s easier to make typos the longer your password is (and the faster you want to type it).
I do one of two things now: initialisms of passphrases, so you don’t know which word each letter represents , or, more commonly these days, just letting my password manager generate the password. It even seems to know if a site won’t accept certain characters.
In order to make that comparison, wouldn’t that mean that the passwords were being stored as plain text somewhere?
A lot of these systems see plaintext when you initially choose your password, and when you type it in to log in. They don’t need to, and probably shouldn’t, store them that way, but they still have the opportunity to examine the plaintext, and you have to trust that the server isn’t logging the plaintext anyway (so don’t reuse that same password elsewhere). Storing hashed passwords also does not stop brute-force guessing the password, though it does slow it down.