How to store and verify digits chosen at random from a PIN/Password

If I have a users 6 digit PIN (or n char string) and I wish to verify say 3 digits chosen at random from the PIN (or x chars) as part of a 'login' procedure, how would I store the PIN in a database or some encrypted/hashed version of the PIN in such a way that I could verify the users identity?

Thoughts:

1. Store the PIN in a reversible (symmetrically or asymmetrically) encrypted manner, decrypt for digit checks.
2. Store a range of hashed permutations of the PIN against some ID, which links to the 'random digits' selected, eg:
   • ID: 123 = Hash of Digits 1, 2, 3
   • ID: 416 = Hash of Digits 4, 1, 6

Issues:

1. Key security: Assume that the key is 'protected' and that the app is not开发者_StackOverflow financial nor highly critical, but is 'high-volume'.
2. Creating a wide-number number of hash permutations is both prohibitively high-storage (16bytes x several permutations) and time-consuming probably overkill

Are there any other options, issues or refinements?

Yes: I know storing passwords/PINs in a reversible manner is 'contentious' and ideally shouldn't be done.

Update

Just for clarification: 1. Random digits is a scheme I am considering to avoid key-loggers. 2. It is not possible to attempt more than a limited number of retries. 3. Other elements help secure and authenticate access.

As any encryption scheme you use to store the password/pass phrase would be either prohibitively expensive, or, easily cracked I am coming down on the side of just plain storing it in plain textr and ensuring that the database and server security is up to scratch.

You could consider some lightweight encryption scheme to hide the passwords from a casual browser of the database, but, you have to admit that any scheme will have two basic vulnerabilties. One -- your program will need a password or key which will have to be stored somewhere and will be almost as vulnerable to snooping as the actual passwords sotred in plain text, and, Two -- if you have a reasonable number of users then a hacker who has access to the encrypted passwords has lots of "clue"s to aid his brute force attack, and if your site is open to the public he can insert any number of "known texts" into your database.

Since 6C3 is 20 and 10C3 is 120, I'll get a false positive (be authenticated) on 1/6th of my guesses.

This scheme is only slightly better than no authentication at all regardless of how you store the token.

I totally agree with msw but that argument is only (or mostly) valid for the six digit scheme. For the n-char approach, the false positive ratio will (sometimes...) be much lower. One improvement would be that the random characters must be entered in the same order as in the password.

Also I think that storing hashed permutations would make it relatively easy to find the key using some brute force approach. For example, testing and combining different combinations of three characters and checking those against the stored hashes. This would defeat the purpose of hashing the key in the first place so you might as well store the key encrypted instead.

Another, totally different argument, is that your users might get very confused by this odd login procedure :)

One possible solution is to use Reed-Solomon (or something like it) to construct an n-of-m scheme: generate an nth degree polynomial f(x), where n is the number of digits needed to log in, and generate the pin digits by evaluating f(x) at x=1..6. The digits combined become your full pin. Any three of these digits can then be used (along with their x coordinate) to interpolate the polynomial constants. If they are equal to your original constants, the digits are correct.

The biggest problem, of course, is to form a field out of numbers 0..9 for polynomial constant arithmetic. Ordinary arithmetic will not cut it in this instance. And my finite field is too rusty to remember if it is possible. If you go 4 bits per digit, you can use GF(2^4) to overcome this deficiency. In addition, it is not possible to select your PIN. It will need to be assigned to you. Finally, assuming you can fix all the problems, there are only 1000 distinct polynomials for a 3 of n scheme, and it is too small for proper security.

Anyhow, I don't think this will be a good method, but I wanted to add some different ideas into the mix.

You say you've other elements for authentication. If you've also passwords, you might do the following:

1. Ask for a password (password is stored as hash only on your side)
2. First check the hash of the entered password against the stored password hash
3. On success, continue, otherwise go back to 1
4. Use there entered (unhashed) password as key for symmetrically encrypted PINs
5. Ask for some random digits of the PIN

This way the PIN is encrypted, but the key is not stored in plain text on your side. The online portal of my bank seems to do just that (at least I hope so that the PIN is encrypted, but from the users view the login process is like the one described above).

• The key is 'protected'
• The app is not financial nor highly critical,
• The app is 'high-volume'.
• Creating a wide-number number of hash permutations is both prohibitively high-storage (16bytes x several permutations) and time-consuming probably overkill
• Random digits is a scheme I am considering to avoid key-loggers.
• It is not possible to attempt more than a limited number of retries.
• Other elements help secure and authenticate access.

You seem to be arguing for storing the PIN in the clear. I say go for it. You're basically describing a challenge-response authentication method, and cleartext storage on the server side is common for that use-case.

Something similar to this is a one-time-pad, or a secret key matrix. The difference is that the user has to keep / have the pad with them to access. The benefit is that as long as you get the key distribution sufficiently secure, you're very safe from keyloggers.

If you want to make it so that exposure of the matrix / pad doesn't cause compromise alone, have the user use a short (3-4 number) PIN with the pad, and keep your sensitive locking mechanism.

Example of a matrix:

  1  2  3  4  5  6  7  8
A ;  k  j  l  k  a  s  g
B f  q  3  n  0  8  u  0
C 1  2  8  e  g  u  8  -

A challenge might be: "Enter your PIN, and then the character from square B3 from your matrix."

The response might be: 98763