John Faben's Homepage
  • Home
  • CV
  • Maths
    • Research >
      • Mouse Maze
      • My PhD Thesis
    • Teaching >
      • Counterparty Credit Risk
      • Outreach
  • Bridge
  • Blog

PIN Codes

10/9/2016

0 Comments

 
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: 
  • PIN must not contain repeated digits (e.g. 11111)
  • PIN must not contain consecutive digits (e.g. 12345)
Now, I think it's pretty clear that the restriction is intended to apply to only those strings which consist entirely of repeated or consecutive digits (ie, strings that look like the examples given), so there are in fact only 10 + 7 = 17 out of 100,000 possible PIN codes being excluded by this rule, and it isn't doing too much harm. 

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. 
Picture
No two consecutive digits the same
Picture
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.
0 Comments

    John Faben

    This is a blog. It doesn't currently contain anything, but one day it might, in which case this note will be incorrect, unless it changes.

    Archives

    August 2020
    July 2020
    February 2019
    August 2018
    July 2018
    June 2017
    March 2017
    September 2016
    July 2016

    Categories

    All

    RSS Feed

Proudly powered by Weebly