A Rainbow Table for Android Pattern Locks

What do you do if you have to examine an Android device which has a pattern lock enabled, but USB debugging is not initialised?

If a physical level acquisition can be performed, our technique can be used to retrieve the lock pattern from the device.

The lock pattern is entered by the user joining the points on a 3×3 grid in their chosen order. The pattern must involve a minimum of 3 points and each point can only be used once (used points can be crossed subsequently in the pattern but they will not be registered).

Each point is indexed internally by Android from 0 to 8. So the pattern in Figure 1 would be understood as “0 3 6 7 8 5 2”.

android_pattern_lock

Figure 1

Storing the pattern “in the plain” would constitute a significant security flaw. Android instead stores an SHA-1 hash of the pattern interpreted as a string of bytes. In order to represent the pattern in our example, the byte string: 0x00030607080502 would be hashed to produce: 618b589aa98dfee743e7120913a0665a4a5e8317.

This behaviour can be confirmed by taking a look at the Android source code shown below:

/*
* Generate an SHA-1 hash for the pattern. Not the most secure, but it is
* at least a second level of protection. First level is that the file
* is in a location only readable by the system process.
* @param pattern the gesture pattern.
* @return the hash of the pattern in a byte array.
*/
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 pattern lock hash is stored as a byte string in a file named gesture.key which can be found in the /data/system folder on the device’s file system.

Although storing the pattern as a hash is a sensible approach as it is a “one-way” operation from the original data to the hash, Android does not apply a salt to the original data; this, combined with the fact that there is a finite number of possible patterns, makes it fairly trivial to create a dictionary of all valid hashes. If you can gain access to the gesture.key file you can easily recover the original pattern using a dictionary attack – it would take seconds.

However; sensibly, the gesture.key file is stored in an area of the device’s file system which is not accessible in normal operation, requiring root access to the device in order to extract the file; of course if you have root access you also have access to every other file on the device as well, so recovering the pattern becomes far less useful. (http://www.oxygen-forensic.com/download/pressrelease/PR_FS2011_ENG_2011-10-31.pdf)

There are situations, though, where root access cannot be gained (for example, where USB debugging cannot be activated on the device) which spurred us on to investigate whether the pattern lock could be easily recovered from a raw read of the device’s storage, the likes of which could be made by using JTAG or chip-off techniques.

One possible solution would be to rebuild the entire file system from a raw dump, and from this identify the relevant file; however, time constraints ruled this out. Instead we decided to examine whether it was possible to identify the contents of the gesture.key file among the rest of the data in the dump. We set a known pattern lock on a test handset (an HTC Wildfire in this case) and acquired the contents of its flash memory by using JTAG.

figure_3_-_androidFigure 3: JTAG test pads on an HTC Wildfire

Loading the dump into a hex viewer, we noted that it was organised into chunks of 2048 bytes: the first 2032 bytes are allocated for the data in files while it appears that the remaining 16 bytes are used to store metadata (tags) relating to the YAFFS2 file system.  We then searched for the SHA-1 hash which corresponds to our known lock pattern. This data was found to be stored as expected, occupying the first 20 bytes of the block; interestingly we also found that the remaining 2012 bytes were zero-bytes – an observation which was repeated in our other tests.

These observations left us with a set of rules which we believed would allow us to identify a gesture.key file in the raw dump without having to rebuild the entire file system:

• The dump is organised into blocks of 2048 bytes each
• The gesture.key file should contain a 20-byte long SHA-1 hash at the start of a block
• The 20-byte sequence at the start of the block must appear in our dictionary of hashes
• The following 2012 bytes should all be zero-bytes

Bearing these rules in mind, we wrote a simple Python script which reads a dump 2048 bytes at a time, disregarding blocks which do not fit our required pattern of 20 arbitrary bytes followed by 2012 zero-bytes. If a block does match these criteria, the script then attempts to look up the prospective hash (the first 20 bytes) in our pre-compiled dictionary which was enough to remove any false positives and recover the correct pattern.

One potential shortcoming of this technique is that in its current form it will also identify any previously set patterns which are still present in flash memory. Due to the nature of flash media and the YAFFS file system, which is still found to be used by the majority of Android devices, the gesture.key file does not get over-written in place. Rather the new version is written to a new block with a higher sequence number.

Despite this potential issue, we have used this technique a number of times since with great success and are happy to be making public the scripts for generating the dictionary and for searching the data for research purposes.

GenerateAndroidGestureRainbowTable.py creates an SQLite database file (AndriodLockScreenRainbow.sqlite) which contains a list of hashes for all possible patterns.

Android_GestureFinder.py takes one argument: the flash dump file, and expects AndriodLockScreenRainbow.sqlite to be present in the same folder.

C:\wildfire> Android_GestureFinder.py WILDFIRE_JTAG.bin

[0, 3, 6, 7, 8, 5, 2] 618b589aa98dfee743e7120913a0665a4a5e8317

We hope that researchers and analysts will find the technique useful, and we welcome any comments or suggestions.

To download the file click here.