[Hacking] Android lock pattern

Hello ! In this new post, I will explain how to retrieve current pattern of an Android device. For you information, this problem has been proposed on a web-based CTF (Capture the Flag) in a computer security competition. I always tried on a rooted device but if someone can try this trick on a non-rooted device, please send me back your results :-). I believe that the file where is stored the pattern is only readable by the system process.

How does the pattern lock works ?

To start correctly, you must be award how the Android Lock Pattern works. The pattern scheme is a 3×3 points. Each possible point is identified by a digit number, starting 0 to 8,  simply like that:

So, if you use the pattern used in the right image above, the sequence will be : 1 – 2 – 5 – 8 – 7 – 4 or 4 – 7 – 8 – 5 – 2 – 1. Please note that the minimal pattern length is composed of 3 points and the maximal of 8.

Internally, Android stores this sequence as a SHA-1 hash in a specific file which can be found into /data/system/gesture.key. For example. if your pattern is “1 – 2 – 5 – 8 – 7 – 4“, the SHA-1 hash will be the output  of SHA1(“\x01\x02\x05\x08\x07\x04”). We can be really happy that Android does not use salted-hash… According to this, this pattern should be saved as 6c1d006e3e146d4ee8af5981b8d84e1fe9e38b6c. In the Android Open Source Project”, I found this java file:

private static byte[] patternToHash(List pattern) {
    if (pattern == null) {
        return null;
    }
 
    final int patternSize = pattern.size();
    byte[] res = new byte[patternSize];
    for (int i = 0; i < patternSize; i++) {
        LockPatternView.Cell cell = pattern.get(i);
        res[i] = (byte) (cell.getRow() * 3 + cell.getColumn());
    }
    try {
        MessageDigest md = MessageDigest.getInstance("SHA-1");
        byte[] hash = md.digest(res);
        return hash;
    } catch (NoSuchAlgorithmException nsa) {
        return res;
    }
}

The only little problem facing us is that SHA-1 is a one-way cryptographic hash function (yes, it’s better for an hash…), meaning that we cannot get the plaintext from its hash.

How to crack it ?

We know that the pattern sequence is composed of sequence of number, between 0 and 8 and of length of between 3 and 8 digits. Based on this constatation, so we know that there is a finite number of possible hashs. We can imagine to generate a dictionary that contains all SHA-1 hash of sequence starting from 0123 to 876543210. This dictionary can be downloader here.

Once downloaded, just use this python script to get the pattern corresponding to the hash.

#Quick and Easy Android Pattern Lock Cracker - Kieron Craggs 2014

#****MODULES*************#
import argparse
import sqlite3 as lite
import gzip
import os
#************************#

parser = argparse.ArgumentParser(description = "Easy Android Pattern Lock Cracker")
group = parser.add_mutually_exclusive_group(required=True)
group.add_argument("-f", "--file", help="Path to a gesture.key file", required=False)
group.add_argument("-r", "--rawhash", help="Raw text input of SHA1 hash", required=False)
args = parser.parse_args()

if args.file:
    gesturekey = open (args.file,'rb').read()
    inkey = str(gesturekey).encode('hex-codec')
elif args.rawhash:
    inkey = args.rawhash
else:
    print "Supply a valid gesture key file or raw text hash"


try:
    dbin = gzip.GzipFile('rainbow.db.gz','rb')
except IOError:
    print "Database archive doesn't exist, put rainbow.db.gz in current working directory"
    exit()
else:
    dbbuf = dbin.read()
    dbin.close()

    dbout = file('rainbow.db','wb')
    dbout.write(dbbuf)
    dbout.close()    

try:
    db = lite.connect('rainbow.db') 
except NameError:
    print "Nothing was given to the database to check. Check gesture input file."
except IOError:
    print "Cannot find db file."
else:    
    with db:
        cur = db.cursor()
        cur.execute('SELECT pattern FROM RainbowTable WHERE hash = ?',(inkey,))
        rows = cur.fetchone()

        if rows:
            for row in rows:
                result = row
                print """   

        The Lock Pattern code is %s

        For reference here is the grid (starting at 0 in the top left corner):

        |0|1|2|
        |3|4|5|
        |6|7|8|

                """ % (row)
        else:
            print "No match, check input."                    

if os.path.exists("rainbow.db"):       
        os.remove("rainbow.db")
        exit()

This script just need to be placed at the same location than rainbow.db.gz. It simply decompress the archive, and make a SQL query to find which pattern match with the current value of gesture.key. Here an example with my rooted phone. Note : my python script is called gesturecrack.py

gremaudc@ub1410:~$ python ./gesturecrack.py -f android/data/system/gesture.key
   

        The Lock Pattern code is [1, 4, 5, 2, 6, 3, 7, 8, 0]

        For reference here is the grid (starting at 0 in the top left corner):

        |0|1|2|
        |3|4|5|
        |6|7|8|

 Just wait some seconds, and the sequence of point is displayed.