Password Quality

A while back, my old n900 was stolen, so I replaced it by getting a T-Mobile G2 phone. It is rather nice and so far I've been rather happy with it.

Like most Android phones, it allows the use of a 3 by 3 grid on which you can draw and connect symbols.

Someone else's phone showing the logon matrix:


This lets you pick any of the nine points as a start and then connect any number of points, no more than once each, to produce a sort of visual password.

Now, I was wondering this morning, while half awake, how many unique passwords this produces. The trick is that not all possible combinations are valid. For instance, if a password begins in the upper left hand corner, it cannot have the upper right hand corner as its next "digit". Instead, it must first pass through the upper center orb. With no more than 9 possible digits, it seemed like it would be easy to calculate the number of unique combinations recursively, so I did:

(define max-passwords
  (lambda ()
    (letrec
        ((in-list
          (lambda (val lst)
            (cond
              ((eq? lst '()) #f)
              ((eq? (car lst) val) #t)
              (else (in-list val (cdr lst))))))
         (ok-vals
          (lambda (num)
            (cond
              ((eq? num 1) (list 2 4 5 6 8))
              ((eq? num 2) (list 1 3 4 5 6 7 9))
              ((eq? num 3) (list 2 4 5 6 8))
              ((eq? num 4) (list 1 2 3 5 7 8 9))
              ((eq? num 5) (list 1 2 3 4 6 7 8 9))
              ((eq? num 6) (list 1 2 3 5 7 8 9))
              ((eq? num 7) (list 2 4 5 6 8))
              ((eq? num 8) (list 1 3 4 5 6 7 9))
              ((eq? num 9) (list 2 4 5 6 8)))))
         (valid-sucs
          (lambda (ok used)
            (begin
              ;(display (reverse used))
              ;(newline)
              (+ 1 (apply + 
                     (map 
                      (lambda (x) 
                        (if (in-list x used) 0
                            (valid-sucs (ok-vals x) (cons x used))))
                      ok)))))))
      (apply + 
             (map 
              (lambda (x)
                (valid-sucs (ok-vals x) (list x)))
              (list 1 2 3 4 5 6 7 8 9)))))) 

Turns out that if you run this, you end up with 140,249 unique passwords of any length (1 to 9 orbs).

I also calculated what it would be if you could go from (say) upper left to upper right without being forced to go through the center and found that it was 986,409 possible passwords of any length (1 to 9 orbs).

Published by XPost^GTK+