Pin Generation

Question

Hi,

I am looking to develop a system in which i need to assign every user a unique pin code for security. The user will only enter this pin code as a means of identifying himself. Thus i dont want the user to be able to guess another users pincode. Assuming the max users i will have is 100000, how long should this pin code be?

e.g. 1234 4532 3423

Should i generate this code via some sort of algorithm? Or should i randomly generate it?

Basically I dont want people to be able to guess other peoples pincode and it should support enough number of users.

Am sorry if my question sounds a bit confusing but would gladly clarify any doubts.

thank you very much.

UPDATE

After reading all the posts below, I would like to add some more detail.

1. What i am trying to achieve is something very similar to a scratch card.
2. A user is given a card, which he/she must scratch to find the pin code.
3. Now using this pin code the user must be able to access my system.

I cannot add extra security (e.g. username and password), as then it will deter the user from using the scratch card. I want to make it as difficult as possible to guess the pincode within the limitations.

thankyou all for your amazing replies again.

Answer 1

4 random digits should be plenty if you append it to unique known userid (could still be number) [as recommended by starblue]

Pseudo random number generator should also be fine. You can store these in the DB using reversable encryption (AES) or one-way hashing

The main concern you have is how many times a person can incorrectly input the pin before they are locked out. This should be low, say around three...This will stop people guessing other peoples numbers.

Any longer than 6 digits and people will be forgetting them, or worse, writing them on a post-it note on their monitor.

Assuming an account locks with 3 incorrect attempts, then having a 4 digit pin plus a user ID component UserId (999999) + Pin (1234) gives you a 3/10000 chance of someone guessing. Is this acceptable? If not make the pin length 5 and get 3/100000

Answer 2

It seems you want to use the pin code as the sole means of identification for users. A workable solution would be to use the first five digits to identify the user, and append four digits as a PIN code.

If you don't want to store PINs they can be computed by applying a cryptographically secure hash (SHA1 or better) to the user number plus a system-wide secret code.

Answer 3

if i use pseudo random generator, then how will i verify whether entered pin is correct? Should i save all the generated numbers in a database?

I plan to give people scratch cards with the pin in them.

How long should my code be to sufficiently allow 100000 users as well as be short and not be very easy to guess (e.g. if the user increments the number, the pin should not be present)

thank you again.

Answer 4

Should i generate this code via some sort of algorithm?

No. It will be predictable.

Or should i randomly generate it?

Yes. Use a cryptographic random generator, or let the user pick their own PIN.

In theory 4 digits will be plenty as ATM card issuers manage to support a very large community with just that (and obviously, they can't be and do not need to be unique). However in that case you should limit the number of attempts at entering the PIN and lock them out after that many attempts as the banks do. And you should also get the user to supply a user ID (in the ATM case, that's effectively on the card).

If you don't want to limit them in that way, it may be best to ditch the PIN idea and use a standard password (which is essentially what your PIN is, just with a very short length and limited character set). If you absolutely must restrict it to numerics (because you have a PIN pad or something) then consider making 4 a (configurable) minimum length rather than the fixed length.

You shouldn't store the PIN in clear anywhere (e.g. salt and hash it like a password), however given the short length and limited char set it is always going to be vulnerable to a brute force search, given an easy way to verify it.

There are various other schemes that can be used as well, if you can tell us more about your requirements (is this a web app? embedded system? etc).

Answer 5

May I suggest an alternative approach? Take a look at Perfect Paper Passwords, and the derivatives it prompted .

You could use this "as is" to generate one-time PINs, or simply to generate a single PIN per user.

Bear in mind, too, that duplicate PINs are not of themselves an issue: any attack would then simply have to try multiple user-ids.

(Mileage warning: I am definitely not a security expert.)

---

Here's a second answer: from re-reading, I assume you don't want a user-id as such - you're just validating a set of issued scratch cards. I also assume you don't want to use alphabetic PINs.

You need to choose a PIN length such that the probability of guessing a valid PIN is less than 1/(The number of attempts you can protect against). So, for example, if you have 1 million valid PINs, and you want to protect against 10000 guesses, you'll need a 10-digit PIN.

If you use John Graham-Cumming's version of the Perfect Paper Passwords system, you can:

1. Configure this for (say) 10-digit decimal pins
2. Choose a secret IV/key phrase
3. Generate (say) the first million passwords(/PINs)

I suspect this is a generic procedure that could, for example, be used to generate 25-alphanumeric product ids, too.

Sorry for doing it by successive approximation; I hope that comes a bit nearer to what you're looking for.

Answer 6

If the PIN is the only form of identification, and you need to be able to differentiate between these users later, then you need a PIN that is larger than your intended user base.

Thus, if you use a 4 digit pin, the absolute maximum is 10,000 users, and the probability of someone "guessing" another PIN is almost a certainty (as you have a saturated set). The first thing you could do is to add some form of check-digit with an algorithm of your choice -- anything from a fairly simple: ((first digit + second digit * 2 + third digit * 4 + fourth digit * 8) / 11) mod 10

This adds a single digit without increasing capacity, but does allow you to check whether it was a PIN you might have generated, and reduces the chance of guessing a PIN to just under 1 in 10 (just under as the user would have to know the length of a valid PIN). If you tweak the divisor/modulo/length of your check you can reduce the chance of the PIN being guessed (whatever approach you have, the chance of a PIN being guessable will still be there, as it would be open to a brute force attack if it is the only authentication)

So. for a user base of 100,000 with about a 1% chance of guessing, then you're looking at a 7 digit pin (which isn't too dissimilar to the length of phone numbers, so it shouldn't be too hard for people to memorise should the need to)

Answer 7

The question should be, "how many guesses are necessary on average to find a valid PIN code, compared with how many guesses attackers are making?"

If you generate 100 000 5-digit codes, then obviously it takes 1 guess. This is unlikely to be good enough.

If you generate 100 000 n-digit codes, then it takes (n-5)^10 guesses. To work out whether this is good enough, you need to consider how your system responds to a wrong guess.

If an attacker (or, all attackers combined) can make 1000 guesses per second, then clearly n has to be pretty large to stop a determined attacker. If you permanently lock out their IP address after 3 incorrect guesses, then since a given attacker is unlikely to have access to more than, say, 1000 IP addresses, n=9 would be sufficient to thwart almost all attackers. Obviously if you will face distributed attacks, or attacks from a botnet, then 1000 IP addresses per attacker is no longer a safe assumption.

If in future you need to issue further codes (more than 100 000), then obviously you make it easier to guess a valid code. So it's probably worth spending some time now making sure of your future scaling needs before fixing on a size.

Given your scratch-card use case, if users are going to use the system for a long time, I would recommend allowing them (or forcing them) to "upgrade" their PIN code to a username and password of their choice after the first use of the system. Then you gain the usual advantages of username/password, without discarding the ease of first use of just typing the number off the card.

As for how to generate the number - presumably each one you generate you'll store, in which case I'd say generate them randomly and discard duplicates. If you generate them using any kind of algorithm, and someone figures out the algorithm, then they can figure out valid PIN codes. If you select an algorithm such that it's not possible for someone to figure out the algorithm, then that almost is a pseudo-random number generator (the other property of PRNGs being that they're evenly distributed, which helps here too since it makes it harder to guess codes), in which case you might as well just generate them randomly.

Answer 8

There's a difference between guessing the PIN of a target user, and that of any valid user. From your use case, it seems that the PIN is used to gain access to certain resource, and it is that resource that attackers may be after, not particular identities of users. If that's indeed the case, you will need to make valid PIN numbers sufficiently sparse among all possible numbers of the same number digits.

As mentioned in some answers, you need to make your PIN sufficiently random, regardless if you want to generate it from an algorithm. The randomness is usually measured by the entropy of the PIN.

Now, let's say your PIN is of entropy N, and there are 2^M users in your system (M < N), the probability that a random guess will yield a valid PIN is 2^{M-N}. (Sorry for the latex notations, I hope it's intuitive enough). Then from there you can determine if that probability is low enough given N and M, or compute the required N from the desired probability and M.

There are various ways to generate the PINs so that you won't have to remember every PIN you generated. But you will need a very long PIN to make it secure. This is probably not what you want.

Answer 9

If we assume 100,000 users maximum then they can have unique PINs with 0-99,999 ie. 5 digits.

However, this would make it easier to guess the PINs with the maximum number of users. If you can restrict the number of attempts on the PIN then you can have a shorter PIN. eg. maximum of 10 failed attempts per IP per day.

It also depends on the value of what you are protecting and how catastrophic it would be if the odd one did get out.

I'd go for 9 digits if you want to keep it short or 12 digits if you want a bit more security from automated guessing.

To generate the PINs, I would take a high resolution version of the time along with some salt and maybe a pseudo-random number, generate a hash and use the first 9 or 12 digits. Make sure there is a reasonable and random delay between new PIN generations so don't generate them in a loop, and if possible make them user initiated.

eg. Left(Sha1(DateTime + Salt + PseudoRandom),9)

Answer 10

Lots of great answers so far: simple, effective, and elegant!

I'm guessing the application is somewhat lottery-like, in that each user gets a scratch card and uses it to ask your application if "he's already won!" So, from that perspective, a few new issues come to mind:

War-dialing, or its Internet equivalent: Can a rogue user hit your app repeatedly, say guessing every 10-digit number in succession? If that's a possibility, consider limiting the number of attempts from a particular location. An effective way might be simply to refuse to answer more than, say, one attempt every 5 seconds from the same IP address. This makes machine-driven attacks inefficient and avoids the lockout problem.

Lockout problem: If you lock an account permanently after any number of failed attempts, you're prone to denial of service attacks. The attacker above could effectively lock out every user unless you reactivate the accounts after a period of time. But this is a problem only if your PINs consist of an obvious concatenation of User ID + Key, because an attacker could try every key for a given User ID. That technique also reduces your key space drastically because only a few of the PIN digits are truly random. On the other hand, if the PIN is simply a sequence of random digits, lockout need only be applied to the source IP address. (If an attempt fails, no valid account is affected, so what would you "lock"?)

Data storage: if you really are building some sort of lottery-like system you only need to store the winning PINs! When a user enters a PIN, you can search a relatively small list of PINs/prizes (or your equivalent). You can treat "losing" and invalid PINs identically with a "Sorry, better luck next time" message or a "default" prize if the economics are right.

Good luck!

Answer 11

I've done this before with PHP and a MySQL database. I had a permutations function that would first ensure that the number of required codes - $n, at length $l, with the number of characters, $c - was able to be created before starting the generation process.

Then, I'd store each new code to the database and let it tell me via UNIQUE KEY errors, that there was a collision (duplicate). Then keep going until I had made $n number of successfully created codes. You could of course do this in memory, but I wanted to keep the codes for use in a MS Word mail merge. So... then I exported them as a CSV file.

Answer 12

If you want to generate scratch-card type pin codes, then you must use large numbers, about 13 digits long; and also, they must be similar to credit card numbers, having a checksum or verification digit embedded in the number itself. You must have an algorithm to generate a pin based on some initial data, which can be a sequence of numbers. The resulting pin must be unique for each number in the sequence, so that if you generate 100,000 pin codes they must all be different. This way you will be able to validate a number not only by checking it against a database but you can verify it first.

I once wrote something for that purpose, I can't give you the code but the general idea is this:

• Prepare a space of 12 digits
• Format the number as five digits (00000 to 99999) and spread it along the space in a certain way. For example, the number 12345 can be spread as __3_5_2_4__1. You can vary the way you spread the number depending on whether it's an even or odd number, or a multiple of 3, etc.
• Based on the value of certain digits, generate more digits (for example if the third digit is even, then create an odd number and put it in the first open space, otherwise create an even number and put it in the second open space, e.g. _83_5_2_4__1
• Once you have generated 6 digits, you will have only one open space. You should always leave the same open space (for example the next-to-last space). You will place the verification digit in that place.
• To generate the verification digit you must perform some arithmetic operations on the number you have generated, for example adding all the digits in the odd positions and multiplying them by some other number, then subtracting all the digits in the even positions, and finally adding all the digits together (you must vary the algorithm a little based on the value of certain digits). In the end you have a verification digit which you include in the generated pin code.

So now you can validate your generated pin codes. For a given pin code, you generate the verification digit and check it against the one included in the pin. If it's OK then you can extract the original number by performing the reverse operations.

It doesn't sound so good because it looks like security through obscurity but it's the only way you can use this. It's not impossible for someone to guess a pin code but being a 12-digit code with a verification digit, it will be very hard since you have to try 1,000,000,000,000 combinations and you just have 100,000 valid pin codes, so for every valid pin code there are 10,000,000 invalid ones.

I should mention that this is useful for disposable pin codes; a person uses one of these codes only once, for example to charge a prepaid phone. It's not a good idea to use these pins as authentication tokens, especially if it's the only way to authenticate someone (you should never EVER authenticate someone only through a single piece of data; the very minimum is username+password)