Are Android unlock patterns as secure as numeric PINs?
Unlock pattern may be easier to remember than a string of numbers.
This post is a digression. It’s not about constructing mathematical models of real world phenomena. It’s about sequences of numbers like the famous Fibonacci sequence and the Android pattern unlock screen shown here.
The rationale for a graphical pattern instead of a numeric PIN is clear. Humans are much better at remembering patterns than strings of digits. But is the pattern as secure? Other issues aside, such as traceability of fingerprint smudges that allows an attacker to recover the pattern, are there as many patterns as there are numeric PINs of the same length?
Well that’s where understanding recursion relations is useful. A recursion relation defines a sequence of numbers 
Depending on the type of recursion relation (whether it is linear, for example), there are a variety of methods for solving them. Let’s use the power of recursion to find the number of possible Android unlock patterns that connect 
To make the problem seemingly more complicated (but really simpler) let’s separately compute the number of patterns that start at the center, side and corner of the 3×3 grid of dots. Let’s call those numbers 
Because there are 4 corner and 4 side dots in the 3×3 grid.
Let’s now derive a recursion relation for 
Now let’s imagine that we managed to compute 
When starting from the side dot, there are 4 ways to get to a corner dot, one way to get to the center dot and 2 ways to get to other side dots, therefore
And finally when starting from a corner dot, there are 4 ways to get to a side dot and one way to get to the center dot, thus
The above three relationships can be summarized as
using matrix notation by defining a vector 
Hang on tight, we are almost there. The simple recursion relation (1) means that we can obtain the numbers of patterns connecting 
I won’t bore you with the rest of the calculation which is quite routine. As my eccentric math tutor used to say: “After this point it’s just algebra!”
Here is the result of the calculation:
| N | Number of patterns connecting N dots | Number of numeric PINs of N digits |
| 2 | 56 | 100 |
| 3 | 360 | 1,000 |
| 4 | 2,280 | 10,000 |
| 5 | 14,544 | 100,000 |
| 6 | 92,448 | 1,000,000 |
| 7 | 588,672 | 10,000,000 |
| 8 | 3,745,152 | 100,000,000 |
Clearly, the number of patterns grows slower than the number of numeric PINs. This may not matter, however, if patterns are easier to remember and therefore one can comfortably have a longer pattern.
The only sure way to determine whether it is indeed easier to remember patterns, is through careful experiments with human subjects. Until such data are available, all statements about memorability and security of patterns vs PIN’s are pure speculation…
PS:
The restriction that a dot cannot be used more than once in a pattern *dramatically* reduces the number of allowed patterns. Please see comments for the true number of unlock patterns.
Playing with models: quantitative exploration of life. 
I don’t really understand all that mathematical jargon, but I don’t think it really holds up in the real world.
First of all, Android limits you to not being able to reuse a dot once it’s already been used. And there are some ways you cannot easily go between dots with your finger. You also have to have at least four dots selected (you can’t just do a clean swipe diagonally, for example).
So, yes, in theory you could draw the pattern in your screenshot. In reality, if the phone is set to turn off the screen and lock after one minute of idling, it’s highly unlikely anyone will choose that unlock pattern. It requires too much concentration and finger dexterity.
Humans are much better at remembering patterns than strings of digits.
I think it really depends on the human. Maybe what you’re saying is true for most people or a certain kind of person. I am definitely better at remembering strings of digits, especially if they’re fewer than 10 digits in a row. The way I remember a string of digits is by repeating in my head over and over again the sound of the digits one after the other. I don’t, for a visual pattern drawn in the Android unlock screen, have an easy way to repeat it in my head.
If there are restrictions on the pattern like not using the same dot twice or not allowing crossings, the calculation of the number of patterns will get much more complicated. The result, of course, will be a reduction in the number of patterns since some of the patters will no longer be legal.
I object to the use of the word jargon. Mathematics is a beautiful language for those who understand it…
To those who don’t understand, it is jargon, by definition. I realize there are some secondary definitions of the word jargon that have a pejorative component to them. I didn’t mean those.
And, yes, the restrictions are that you have to connect at least four dots and you cannot repeat dots.
before worrying about security that much you should just buy a device with a fingerprint reader and be done with it
I am not worried about security at all. Computing the number of patters is an interesting problem in combinatorics.
A fingerprint reader is a great addition to pattern entry. Fingerprint reader by itself is quite useless as far as security is concerned.
Ok, so fingerprint readers are the easiest way to get into someone’s phone. You can replicate the fingerprint that is oh so very frequently left on the reader more easily than the pattern of smudges, because you use the screen for so much more than that. And why else would ALL phones with fingerprint readers have a fingerprint lock timeout, such as Motorola’s 72 hour, if-you-haven’t-used-your-PIN-or-swipe-pattern-in-72-hours-we’ll-lock-you-out policy.
Motorola, though, does have the fingerprint-reader-becomes-your-home-back-and-open-button feature that makes it harder to get your fingerprint through the pattern of smudges. I’d recommend sticking to a PIN rather than a swipe pattern or any other unlock method, particularly voice unlock, as this is the easiest to replicate. And whichever one you use(other than voice, obviously), clean your screen & fingerprint reader as thoroughly as possible, every time you put it down or stop using it.
After learning that the pattern cannot contain the same dot more than once, I went back to the drawing board and recalculated the numbers of patterns with that restriction.
The numbers of restricted patterns are significantly smaller, especially for longer patterns. There is almost no advantage in having a pattern longer than 6 dots.
I just broke a 4 digit swipe password on my sisters tablet with 36 trys… I once saw her type it in and since patterns are easy to remember I vaguely remembered the shape and position of it! I only remembered it being a square type shape on the bottom row… It’s actually a U on the bottom right.
Thanks! I was in the pub last night discussing this with my mate who was going to write an algorithm to calculate this but you seem to have done the hard work for me!
If you want I can send you the c++ code which computes the number of restricted patterns. It’s a recursive depth first tree search.
Hey Alex.
can i get the code you are talking about?
Thanks
[…] […]
Here’s some TCL code that gives the similar numbers to Alex’s. I think the differences are because I don’t allow strokes between unselected dots (too hard to do reliably).
I think that patterns of length 9 are also useful to consider because an attacker doesn’t know beforehand the length of the pattern.
I originally wrote this code to help me randomly pick a secure pattern. At this point I’m thinking that numeric PIN’s are just better because a short PIN has as much random information as a long pattern.
40 patterns of length 2
40 patterns of length 2 or less
176 patterns of length 3
216 patterns of length 3 or less
680 patterns of length 4
896 patterns of length 4 or less
2440 patterns of length 5
3336 patterns of length 5 or less
7544 patterns of length 6
10880 patterns of length 6 or less
19000 patterns of length 7
29880 patterns of length 7 or less
35328 patterns of length 8
65208 patterns of length 8 or less
35328 patterns of length 9
100536 patterns of length 9 or less
#!/usr/bin/tclsh
# 0 1 2
# 3 4 5
# 6 7 8
set paths1 {}
# 0 1 2 3 4 5 6 7 8
lappend paths1 { -1 -1 1 -1 -2 { 1 4 } 3 { 3 4 } 4 } ;# 0
lappend paths1 { -1 -1 -1 -2 -1 -2 { 3 4 } 4 { 4 5 } } ;# 1
lappend paths1 { 1 -1 -1 { 1 4 } -2 -1 4 { 4 5 } 5 } ;# 2
lappend paths1 { -1 -2 { 1 4 } -1 -1 4 -1 -2 { 4 7 } } ;# 3
lappend paths1 { -2 -1 -2 -1 -1 -1 -2 -1 -2 } ;# 4
lappend paths1 { { 1 4 } -2 -1 4 -1 -1 { 4 7 } -2 -1 } ;# 5
lappend paths1 { 3 { 3 4 } 4 -1 -2 { 4 7 } -1 -1 7 } ;# 6
lappend paths1 { { 3 4 } 4 { 4 5 } -2 -1 -2 -1 -1 -1 } ;# 7
lappend paths1 { 4 { 4 5 } 5 { 4 7 } -2 -1 7 -1 -1 } ;# 8
set num 0
proc mysearch { depth points knight jumps diags longjumps } {
global paths1 num
#puts “mysearch $depth $points”
set matches 0
if { $depth == 0 } {
incr num
#puts “[expr 2*$knight+$jumps+$diags+$longjumps] $knight $jumps $diags $longjumps $num: $points”
return 1
}
if { [llength $points] } {
set last [lindex $points end]
set blockers [lindex $paths1 $last]
for { set try 0 } { $try < 9 } { incr try } {
#puts "try = $try"
set blocker [lindex $blockers $try]
#puts "blocker = $blocker"
set blocked 0
set knight2 0
set jumps2 0
set diags2 0
set longjumps2 0
# don't do knight moves
if { [llength $blocker] == 2 } {
set knight2 1
foreach blocker2 $blocker {
if { [lsearch -exact -integer $points $blocker2] = 0 } {
if { [lsearch -exact -integer $points $blocker] < 0 } {
set blocked 1
} else {
set jumps2 1
}
if { $blocker == 4 } {
set longjumps2 1
}
} elseif { $blocker == -2 } {
set diags2 1
}
}
if { !$blocked } {
#puts "lsearch -exact -integer \"$points\" \"$try\""
if { [lsearch -exact -integer $points $try] < 0 } {
set tryl $points
lappend tryl $try
incr matches [mysearch [expr $depth-1] $tryl [expr $knight+$knight2] [expr $jumps+$jumps2] [expr $diags+$diags2] [expr $longjumps+$longjumps2]]
}
}
}
} else {
for { set i 0 } { $i < 9 } { incr i } {
set tryl $points
lappend tryl $i
incr matches [mysearch [expr $depth-1] $tryl 0 0 0 0]
}
}
return $matches
}
set total 0
for { set i 2 } { $i <= 9 } { incr i } {
set res [mysearch $i {} 0 0 0 0]
puts "$res patterns of length $i"
incr total $res
puts "$total patterns of length $i or less"
}
David,
While it is true that there are more PINs than patterns, a pattern might be easier to remember which means that you could have a longer pattern.
Also, in a brute force attack, the attacker will have to have to try of all possible patterns which is near to impossible whereas trying all possible pins is just a matter of time.
Thanks for your contribution!
I agree that random patterns may be easier to remember than a random PIN.
I disagree regarding brute force. If you uncomment a line from my script, it will print a list of all the patterns to try. An attacker can start trying those just as easily as he can try sequential PIN’s. What’s really needed (and may already exist) is the ability to lock the device after a certain number of invalid attempts, and for a user to be able to have a backup method of unlocking a locked device.
Point well taken. Another popular method is to progressively increase the waiting period between allowed failed unlocking attempts until brute force is not longer tenable, but the legitimate owner can unlock the device after a relatively short wait.
That’s a good idea, but it is quite possible for an owner to forget his pattern, and it would be nice if there was an alternate method to verify ownership. A call to customer service (611) to send a remote unlock might be an option.
Most (if not all) Android devices have a recovery system which is triggered by a key combination during boot. Among the tasks of the recovery system, there should be an option to turn off the pattern unlock.
If you forget your pattern then you can enter in your Google username and password to gain access.
Really interesting post. From my own experience, it is trivial to use an 8 or 9 point pattern, which is still more secure than a 4 digit PIN.
I would also add that I think patterns are less vulnerable to poor user choices (best practices in consumer devices should never be assumed). Having a variety of keys across different services makes your security more resilient in the event of a breach if you reuse PINs. So, if your phone pattern is broken your ATM PIN remains effective. Plus, patterns are less susceptable to being deduced than PINs chosen for their significance (birthdays etc.).
Thanks for your comment. I agree that the true security can only be measured experimentally and may have little to do with the number of possible PIN/patter choices.
Does this take into account that you can’t skip a dot between two dots? e.g.
123
456
789
It’s not possible to select 7 then 9 then 8, you’re forced into 789.
Yes, this is taken into account.
Also, you can skip a dot between dots, if you have already used it. e.g.
123
456
789
it’s possible to go directly from 3 to 7, if you use 5 beforehand: e.g. 159637. I think the possible combinations are even less.
Are you sure about this? If so, this is not taken into account. This feature will increase the number of patterns since dots that I thought were inaccessible, are actually accessible under some conditions.
Yeah, I thought of this because my password does this.
My script (posted above) takes that into account, so the numbers I listed are accurate.
Thanks for your comment, David.
I would like to see an improved version of pattern unlock. A 4×4 matrix that allowed repeating dots, would help a lot. Has anyone heard of anything like this?
[…] in nearly as simple as the finger swipe that unlocks iOS gadgets and far harder to crack than Android’s nine-point pattern authentication. With a multitouch gesture system that captures enough variables unique to users like hand size, […]
[…] in nearly as simple as the finger swipe that unlocks iOS gadgets and far harder to crack than Android’s nine-point pattern authentication. With a multitouch gesture system that captures enough variables unique to users like hand size, […]
great work, just when I was also wondering how secure pattern unlock is – mathematically.
I guessed it right with much simpler nCr formula. e.g. for a 4 dots pattern number of combinations are – 9C4 = 126, and subtract from that due to the various restrictions, e.g. in those 126 combinations, some would result in non-adjacent dots, dots cannot be repeated etc.
Comparing that to a 4 digit PIN – 10^4. – it is way too less.
Hey,
I guess the mathematics in this article is much to complicated. We have 9 dots. Every dot might be used at most once. A pattern is a sequence of dots. Therefore the number of patterns is the number of different sequences. In mathematics, such a sequence is called a permutation. Generally, the number of different permutations of lengh n is n! (faculty of n).
When we use all 9 dots, there are 9! different patterns, which is 362880.
This is much less than a the number of different pin codes of length 9, which is 10^9=1,000,000,000.
Sure we have to consider that we might have a pattern of length 4 to 9, that’s why we have to sum up the number of patterns of length 4 to 9, i.e. 4!+5!+…+9!, but since faculty is a very fast growing function, it is not much more than 9!.
If the pattern were attackable by software using a brute force approach, it would be cracked in not time.
It would be much better to have patterns in a 4×4 square, where we would have 16!=2.0923e+13 ;)
Your calculation is not correct because you cannot reach all 8 dots from any dot without having to go through other dots. If you are in a corner, for example, you have to go through the center do to reach the opposite corner dot.
Mathematics aside the pin is more secure regardless of the math. I used to use the patern and prefer it for everything aside from security which is the whole point.
If you have not cleaned your screan since the last unlock there is a very good chance a person can guess the pattern by looking at the smudges. if the smudge is visible the phone will be unlocked in 2 attempts. If smudges from a pin are visible the individual only knows which numbers are used but does not know the order or if there are any duplicates.
Pins are much less secure in over-the-shoulder attacks. iOS7 does a light show by default where anyone within 6 feet can easily tell which numbers and what sequence you pressed. It’s like a modern Simon Says, but easier.
[…] unlocking sequence? Maths blogger Alexander Lobkovsky Meitiv did a very detailed investigation <https://playingwithmodels.wordpress.com/2010/04/14/andorid_unlock_patterns/> into a relationship between the number of dots in a password and the number of possible […]
Hi,
I thought about this problem and wrote some code. Then I googled it to see if my solution is correct. (and found this post).
The way I understand it the limitations are: (a) path has to be between 4 and 9 points long, (b) points must be adjacent, and (c) you can’t visit a point twice.
Based on that, I calculated 10,096 paths, with a python backtracking implementation
see code at: textsnip.com/cc6467
If you see an error in my implementation, please let me know,
Thanks!
OK, I played with the pattern a bit on my android and discovered it doesn’t have to be adjacent points.
denoting the points:
0,1,2
3,4,5
6,7,8
you can also (very carefully) move from 1 to 6 or 8 (or similar).
so forbidden moves are either from corner to corner or from middle to middle across (e.g. 1 to 7)
updated code at : textsnip.com/e18151
now it results in a total of 139,880 paths
The nodes that can connect are a little more dynamic. For example, you can go from 1 to 4 to 0 to 2, i.e. 0 to 2 is possible, which is not allowed by the “edges” array in your code.
Here is my try. It’s almost a direct translate of your code from python to c. You simply have to take the current “visited” table into account.
The result is 389112.
Forgot the link… https://gist.github.com/2687787
I think the restrictions a a bit different in different versions of Android.
I think (needs checking) that in Gingerbreaad (2.3) the points don’t have to be adjacent, and the same point can be used more than once if the second path through this point is at a different angle.
You’re right. I noticed that (on 2.3) after the second revision. However, the code strategy I showed isn’t easily changed to support that.
BTW, one of the strangest path you can walk is : 4,1,6,5,0,7,2,3,8
This has been a very interesting post to read…
I have android 2.3.5
it doesn’t seem to allow any points to be reused. At least, using the scheme above, 0,4,8,5,2,4 does not work, for example.
I’m not really sure I understand: on my android i can use just 2 dots if i want to, or use all 9 of them, and everything in between: doesn’t this mean that all the possibilities for each number of dots have to be added to each others, which makes a lot more combinations than a pin which has a fixed length? in other words somebody who wants to guess my pattern would not only need to know the order of nodes, but also how many nodes there are in my pattern – one too many and it’s incorrect… doesn’t this makes patterns more secure, or at least give them an advantage that pins don’t have? in a way it’s between the pin and the password…
I’ve always been crap at maths so maybe I’m making a fool of myself :)
i think Android PINs can be variable length. The minimum length is 4, but it can be pretty long.
Though there may be fewer available combinations of patterns than PINs, the system is substantially harder to crack than a numerical PIN. Here’s a piece of news from a couple of weeks ago showing that this years-old technology has stumped the FBI. http://m.wired.com/threatlevel/2012/03/fbi-android-phone-lock/
Clearly these so called “experts” don’t know what they are doing. All you have to do is install Clockworkmod recovery and then mount “data” from it to have complete access to the partition. To my knowledge the databases on the /data partition are not encrypted by default.
But how do you install Clockworkmod without getting past the lock screen or wiping the data from the phone?
There was another article on Slashdot yesterday about a company that can break phone security, but the article doesn’t say whether or not they can get past pattern protected phones:
http://www.forbes.com/sites/andygreenberg/2012/03/27/heres-how-law-enforcement-cracks-your-iphones-security-code-video/
You can install a recovery on Samsung phones by putting the phone into download mode and flashing the recovery using heimdall or odin.
The number of valid patters of at least 4 dots is 389112.
The result can be “easily” achieved using SQL with ORACLE DB:
create table android(id varchar2(9), primary key (id));
insert into android
with nums as (select rownum d from dual connect by rownum <= 9)
select seq from (
select n1.d || n2.d || n3.d || n4.d || n5.d || n6.d || n7.d || n8.d || n9.d seq from nums n1
inner join nums n2 on n2.d not in (n1.d)
inner join nums n3 on n3.d not in (n1.d, n2.d)
inner join nums n4 on n4.d not in (n1.d, n2.d, n3.d)
inner join nums n5 on n5.d not in (n1.d, n2.d, n3.d, n4.d)
inner join nums n6 on n6.d not in (n1.d, n2.d, n3.d, n4.d, n5.d)
inner join nums n7 on n7.d not in (n1.d, n2.d, n3.d, n4.d, n5.d, n6.d)
inner join nums n8 on n8.d not in (n1.d, n2.d, n3.d, n4.d, n5.d, n6.d, n7.d)
inner join nums n9 on n9.d not in (n1.d, n2.d, n3.d, n4.d, n5.d, n6.d, n7.d, n8.d)
) a where not regexp_like(seq, '13.*2|17.*4|19.*5|28.*5|31.*2|37.*5|39.*6|64.*5|93.*6|97.*8|91.*5|82.*5|73.*5|71.*4|79.*8|46.*5');
select (select count(distinct substr(id,1,9)) from android) +(select count(distinct substr(id,1,8)) from android)
+(select count(distinct substr(id,1,7)) from android) +(select count(distinct substr(id,1,6)) from android)
+(select count(distinct substr(id,1,5)) from android) +(select count(distinct substr(id,1,4)) from android)
as num from dual;
Hey guys – I’m just interested in the combinatorial solution to this problem, so Alex if you (or anyone else that may have the solution) can post it I’d be grateful. I was also wondering if we extrapolate the rules, but instead apply them to NxN squares of nodes, what would be the general solution? Finally, what would happen if you tweaked the geometry so it’s not arranged in a square, but a rectangle or a straightedge, or some other weird shape – would that affect the general solution?
Unfortunately, there is no general solution. The search algorithm would have to be modified for each new geometry. Also, there is no analytical solution even for the simplest geometries.
If you mean no general solution at all versus no general solution has been found yet, that would be a real shame. There are some pretty cool symmetries there.
[…] pattern lock is the biggest joke of a “secure” lockscreen you can get, but it’s a little better than nothing at […]
[…] Are Android unlock patterns as secure as numeric PINs? | What can scientific models tell us about th… […]
[…] de 5 puntos, la combinaciones posibles son 5,328 (de acuerdo a este blog de modelos matematicos, Are Android unlock patterns as secure as numeric PINs?). Con un sistema que combina un inicio al azar, formas y tiempo, las posibilidades de adivinar ese […]
i just want to know how many combinations are possible and what are they.. if possible, pattern images in pdf is better.. who can share?
How do you handle hundreds of thousands of pattern images?
i made a twelve point pattern in the nine point pin has anyone made higher
All math and theoretics aside, Patterns aren’t safer, you can just read it from the grease-trail on the screen itself if the user doesn’t wipe the screen after each use. Even if the user has tapped his screen to open apps you can still see the trail. With a number pattern you can still see where the user pressed on the screen but you still need to know the right order. Also, after unlocking, the chance that the user taps his/her screen is large, so you will have exponentially more combinations possible with numbers. Only if you can reuse dots on a trail you can make it safer, because it will be more difficult to see afterwards.
I arrived at this post after trying to figure out the answer on my own. I started with a different (wrong!) assumption that one could use any number of dots (from one to nine) but without repeats. That means if you use all 9 dots to total will be 9! If you use 8 it will be 9! (no times 1). Not being sure how one handles primes where you lose the begining bit of the prime, I calculated the first 5 values (1,4,15,64,325) and then Googled to see if it was a “known” series. It is.
Interestingly, I found out if you want to calculate the next number in this series, it works in the following way.
(64 + 1) * 5 = 325
(325 + 1) * 6 = 11742
(11742 + 1) * 7 = 82201
(82201 + 1) * 8 = 657616
(657616 + 1) * 9 = 5918663 which is what I think the number of combinations is if you are allowed any number between 1 and 9 not using any dot more than once.
What I dont understand is the relationship between what logically seems a calculation about primes and the way I found to solve it. And like others have said, this is more about the maths than whether it is a good way to lock a phone