When I first saw Android’s pattern lock screen I was excited. We took a process we thought we had an answer to with things like PINs or textual passwords and turned it on it’s head. Not only did we come up with a touch screen friendly approach that doesn’t require us to even look at our screen but it also didn’t seem to sacrifice security… at first. Once the honeymoon phase wore off we started finding problems. Simultaneously the stupidest and yet most valid of those problems is that your finger leaves a smear on the screen that pretty accurately gives away your pattern (pdf). Simply wiping the screen helps mitigate this “attack” but that either requires a user to modify their routine (something they’re unlikely to do) or for the system to require it of the user which seems less than ideal. I wanted to find a fresh approach.
For lack of a better name, I present the Color Compass.
On the left is a mock-up of the setup screen where you would first create your new pattern. There are 8 clickable items: the 4 colors in the corners and the 4 directions of the compass. Clicking them will add them to your pattern which is displayed just below the setup section (followed by some debug info, more on that in a bit). The clear button will reset the pattern and allow you to put in a new one from scratch. On the right is the actual grid as you would see it when unlocking your device. The colors now overlap the directions and you’ll notice that if you click any of the colors they will move around randomly on the grid. The best way to explain how to unlock it is by example.
In the left hand panel used for setting up, you could put in the pattern RED, SOUTH, BLUE, EAST by clicking on the red square, the southern arrow, the blue square, and finally the eastern arrow. As you click on them you’ll see that the pattern is written out below for you to see. In this prototype you don’t have to do anything to commit to that pattern. Now in the right hand section you’ll be able to enter that pattern. Since the first entry in the pattern is the color Red, click on the Red square wherever it is on the compass. The squares should now reshuffle themselves to new locations (some or all of them may stay in place because with random you never can tell). You’ll also notice that next to the pattern it will now say “1/4.” That’s an indication of where you are in the pattern and is only meant to be visible during prototyping and not the final product. The left number is how many entries in the pattern you have already typed in correctly and the right number is a count of how long the pattern is. Anyway, now that you’ve put in Red, you need to press South. To do so, you simple press the bottom color. It doesn’t matter what color is in the south position. Pressing the south position will cause the colors to shuffle once more. Now you find the blue square and press it, wait while the shuffle happens, then press the east direction (again disregarding whatever color might be in that position). Once you press the final entry in your pattern, the debug information should now indicate that you’ve successfully unlocked the device.
This approach offers many advantages to the current pattern lock screen in use today. Very little information is leaked because of two things: randomized color location and ambiguity of data input. Did you press the north direction because the next entry in the pattern was North? Or because of the particular color located at that position at the time? This ambiguity means that Eve (Alice being you, the operator, and Bob being the device you’re entering the pattern into) can watch you enter your pattern from beginning to end and not have a clear idea of what your pattern is. Each press could have been for 2 reasons (color or direction) so if your pattern contains N entries then Eve can only guess that your pattern was 1 of 2^N possible patterns. However this does fall short if Eve watches you put in your pattern several times as it will become obvious which presses are directions and which are colors. Another benefit to this design is that any input can be repeated in the pattern. This means that your pattern can be arbitrarily long. The prototype offers no minimum or maximum limitation on the length of the password although there probably should be at least a minimum length requirement.
It’s not a perfect solution however. For one thing, you are required to look at the screen in order to put in the pattern. The current design is actually random so anytime you want to input a color, you will need to be looking at your device. This makes it a little more complicated and less user friendly.
The bigger problem I’m facing is coming up with a way to securely store the pattern. In the prototype it’s unencrypted. The existing pattern unlock screen gives each node a number and as you enter the pattern will build a list of those numbers. Upon releasing your finger from the screen and finishing the pattern, that list is hashed and compared to the value set when the pattern was first put in. I’d be hard pressed to do something similar with the Color Compass. Due to the ambiguity of if a color or a direction was the intended input such a simple “hash and compare” approach won’t work. Do I add the color or the direction to the message to be hashed? If I really wanted to force it to work, I could hash every possibility from the input but that means that for a pattern with N entries means I would have to hash 2^N inputs which not only would take a noticeable amount of time to do but would also be a problem. With that many comparisons, an attacker could just continually press inputs and an accidental collision is almost bound to happen.
This brings up another issue. Pattern length could be arbitrarily long so I would need 2^(N+1)-2 hashes on EACH NEW INPUT. On the first input I’d hash 2 things (the color and the direction), on the second input I’d need to hash 6 new things (the new color, the new direction, the old color plus the new color, the old color plus the new direction, the old direction plus the new color, and the old direction plus the new direction). That means that by the 5th input, the device would have to compute 114 hashes, by the 10th press that’s 4072 total computed hashes. What if you make a mistake entering your pattern that’s 10 entries long? It’d be unreasonable to do it this way. The prototype doesn’t do such a crazy number of comparisons because it has the unencrypted pattern. When you provide an input, it can check both values of that input, if either one is correct it just accepts it and waits for the next input. If it’s wrong, go back to the beginning of the pattern and try again. I do not like storing an unencrypted pattern, but for now it’s what I have. The pattern could be stored in a place that only root users (and the app of course) could get to it. Given the limited input that would be hashed, it would probably be easy to brute force the hash anyway.
So far any method I’ve come up with that might help secure the pattern during storage is either unreasonable like the basic hash approach or would reveal so much about the pattern that it might as well be stored unencrypted. I hope to eventually come up with an answer to this problem. There may not be a proper answer for a secure way to compare ambiguous data against a stored secret.
Android prototype has arrived! Ad free, no permissions (aside from vibration for user feedback).