views:

136

answers:

6

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 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.

+1  A: 

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.

msw
Thx for answer. Not sure if you have your sums right, you still need to guess 1/1000, but yes, the 'keyspace/entropy will be much lower than say 6 digits. Other factors reduce the risk but I am trying to avoid key-loggers. See update in main question.
andora
+1  A: 

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 :)

André Laszlo
@Andre: Yes, agree, same order is a must. Of course a salt would be used in the hash, but essentially, you are correct. As for confusion caused by 'odd' scheme, I doubt it, at least 3 of my online banks use a similar scheme (2 of which are 'global names').
andora
Reminds me of http://thedailywtf.com/Articles/Classic-WTF-Banking-So-Advanced.aspx ;)
André Laszlo
One of my online banks uses this scheme, along with a graphic key pad (i.e you select a picture of the number rather than the number itself, the image names have no reltionship to the number displayed so it defeats any script based snooping.) Its all pretty straighforward and obvious in use.I would recommend a rigourous classic jacobsen use case approach during design to ensure that there are no glitches or confusion for the end user.
James Anderson
A: 

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.

Dysaster
Oooh - interesting - something for me to think about there! Thank you! However, users will have to select their own PIN, we couldn't possibly dictate them.
andora
You are right, assigning PINs instead of letting people choose their PINs is not a very good approach. If you are OK with multiple people using the same underlying secret, you could store 3 polynomial constants a_0, a_1, a_2 which can be found by interpolating the first three digits of the chosen PIN, and another three constants dx_3, dx_4, dx_5 to transform the chosen digits into interpolated x_3, x_4, x_5 by simple addition, or subtraction (the first three dx_i are 0, because they generate the secret polynomial). That should give you the ability to select any PIN you want.
Dysaster
Ops, I forgot that the 6 values you've got are enough to reconstruct the PIN. :) You need to pass a_0, a_1, a_2 through a one-way function and store that to ensure the PIN cannot be reconstructed from stored data.
Dysaster
A: 

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).

jkramer
A: 
  • 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

Slartibartfast
Comprehensive answaer - thanks - I will probably end up storing an ecrypted version of the PIN in the DB, and extract, decrypt and process a pattern match on the input vs the stored PIN. Not ideal, but better than storing in clear. Will use a 'very safe' method to store the encryption key!
andora
+1  A: 

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.

James Anderson
Fairly accurrate assesment, thanks for your comments. +1
andora