How to protect user names, passwords and number of users

Question

I'm looking for a stornger scheme than just password salting-and-hashing.

I want passwords file/DB that will not compromise:

1. Number of users
2. User names
3. User passwords

My basic idea is to hash and salt both the usernames and the passwords, and also to add 1000's of 'trap' entries into the database (for example, random user names ending with _xxxx with random passwords ending with _yyyy which won't be valid for real users).

Of course, when someone tries to log in, I'll have to check it against all lines in the database.

Is this scheme secure?

Notes:

1. The users are added manually. If a user has to be removed - the login names are stored in a safe.
2. I'm not sure if I can protect this scheme againt brute-force methods, but I think guessing both name and password is harder

Edit:

I'm protecting against a leak of the user/password file (as well as the application that read this file). As said, I need to protect the actual number of users, as well as their identities (or anything that may disclose their identities).

Answer 1

Number of users seems to be the hardest datapoint to protect. You can mask this by creating large numbers of fake users with nonsense names encrypted as you describe. These can serve double duty as the traps you describe, but then you need to be able to distinguish a trap from a real user which means it is possible for an attacker to do the same if they can compromise the trap-checker.

Who are you trying to secure it against?

Do you want to secure it against someone who compromises the DB, e.g by SQL injection, or a rogue sysadmin?

Do you want to secure it against someone who compromises the OS and gains access to the files that back the database tables?

The former can be mitigated by restricting access to the table to well-reviewed stored procedures, and tough DB access controls.

The latter can be mitigated by putting DB files on an encrypted partition, though this can slow down access and/or complicate startup.

Answer 2

Ironically, the larger the number of users, the more likely a brute force attacer is to stumble on a valid combination - and if they know that you have a lot of users with _xxxx or _yyyy in their usernames/passwords, that may give them a cryptographical advantage.

So, I would absolutely recommend that you give your bogus users no actual privileges, so that even a succesful guess yields no rights to the system.

Secondly, you might want to think about who you're protecting against, and how - it's widely accepted that a good hash/salt combination protects against most credible attacks; adding the username to that scheme just means you're protecting against attacks that don't currently exist.

On the other hand, you're doing nothing to protect against the far more common attack vector of "username on post-it note", "password = sex", etc.

The most common way to improve on "username/password" is to require users to have something physical.