At work the other day I had to change my PIN for a certain application. It was a purely numeric PIN, and the change came with the following restrictions:
But what if you took it more literally? By a strict interpretation of the rules, 74583 should not be allowed, because it contains consecutive digits (45), and 38871 would not be allowed, because it contains repeated digits (88). There is some ambiguity over whether 24682 should be allowed (is the 2 in that string repeated?). If we did take the rule literally, how many combinations would we be left with? Obviously it depends on the length of the PIN - the particular PIN in question was 5 digits, but let's have a look at what happens for various different lengths, with the different rules:
- PIN must not contain repeated digits (e.g. 11111)
- PIN must not contain consecutive digits (e.g. 12345)
But what if you took it more literally? By a strict interpretation of the rules, 74583 should not be allowed, because it contains consecutive digits (45), and 38871 would not be allowed, because it contains repeated digits (88). There is some ambiguity over whether 24682 should be allowed (is the 2 in that string repeated?). If we did take the rule literally, how many combinations would we be left with? Obviously it depends on the length of the PIN - the particular PIN in question was 5 digits, but let's have a look at what happens for various different lengths, with the different rules:
Number of digits |
No restrictions |
No consecutive repeats |
No repeats at all |
1 |
10 |
10 (100%) |
10 (100%) |
2 |
100 |
81 (81%) |
81 (81%) |
3 |
1000 |
656 (66%) |
584 (58%) |
4 |
10,000 |
5313 (53%) |
3689 (37%) |
5 |
100,000 |
43030 (43%) |
19998 (20%) |
6 |
1,000,000 |
348501 (35%) |
90445 (9%) |
As you would expect, the percentage of passwords that aren't allowed goes up as the number of digits goes up (there are more possible pairs of digits which can be consecutive or be repeats. I created this table with a quick Python script, but is there a way we could have done it by hand?
Well, at least for the less restrictive version of the rule, yes there is (or at least of getting very close). Look at the number of 2 digit numbers which are not allowed - there are 19 of them (you can't have a 2 digit string of consecutive numbers that starts with a 9). Now for longer strings, you can essentially just consider each pair of digits as an independent experiment, which has an 81% chance of being allowable under the rule. So for 3 digit PINs, you'd expect to have 81%*81% = 65.61% of the numbers allowed - which gives exactly the right answer. For larger strings you don't quite get exactly the right answer (because the trials aren't actual independent - knowing that one set of digits is consecutive gives you some information about whether or not the others are), but it gets pretty close.
How about for the less restrictive version? Well, it's a bit more complicated, but we I think we can still do it. The number of strings of length n which consist entirely of different digits is 10Cn * n! = 10!/(10-n)! = 10 * 9 * 8 ... * (10-n). ie, for n=2, there are 10*9 = 90 combinations, and we already know that 81 of these 90 are permissible. So, a quick calculation for how many PINs of length n should be 0.9^n*10!/(10-n)!. How close is that? We know it's exactly correct for n=2. For n=3, it gives us 0.81*(10*9*8) = 583.2, so it's pretty good. It gets slightly worse as n gets larger, for the same reason as before.
Is there anything else we can say about these PINs? Well, let's have a look at what they look like (mostly because I wanted to play with TikZ). Here's a map of which PINs of length 4 are allowed under each rule (plotted on a 100x100 grid). This is also generated from the script above.
Well, at least for the less restrictive version of the rule, yes there is (or at least of getting very close). Look at the number of 2 digit numbers which are not allowed - there are 19 of them (you can't have a 2 digit string of consecutive numbers that starts with a 9). Now for longer strings, you can essentially just consider each pair of digits as an independent experiment, which has an 81% chance of being allowable under the rule. So for 3 digit PINs, you'd expect to have 81%*81% = 65.61% of the numbers allowed - which gives exactly the right answer. For larger strings you don't quite get exactly the right answer (because the trials aren't actual independent - knowing that one set of digits is consecutive gives you some information about whether or not the others are), but it gets pretty close.
How about for the less restrictive version? Well, it's a bit more complicated, but we I think we can still do it. The number of strings of length n which consist entirely of different digits is 10Cn * n! = 10!/(10-n)! = 10 * 9 * 8 ... * (10-n). ie, for n=2, there are 10*9 = 90 combinations, and we already know that 81 of these 90 are permissible. So, a quick calculation for how many PINs of length n should be 0.9^n*10!/(10-n)!. How close is that? We know it's exactly correct for n=2. For n=3, it gives us 0.81*(10*9*8) = 583.2, so it's pretty good. It gets slightly worse as n gets larger, for the same reason as before.
Is there anything else we can say about these PINs? Well, let's have a look at what they look like (mostly because I wanted to play with TikZ). Here's a map of which PINs of length 4 are allowed under each rule (plotted on a 100x100 grid). This is also generated from the script above.
 No two consecutive digits the same |  No two digits the same |
There's probably supposed to be some less about password security and system design here, but I'm going to stick with pretty pictures and combinatorics instead.
RSS Feed