Android Forensics: Cracking the Pattern Lock Protection

[Aerosol]

Introduction

In this paper I’ll show you how to find an Android’s user pattern lock. I assume that the technique that I’ll demonstrate can work only on a rooted device. Actually, this article will be based on a problem given on a web-based CTF (Capture the Flag, a computer security competition).

Problem statement:

• Having doubts about the loyalty of your wife, you’ve decided to read SMS, mail, etc., in her smartphone. Unfortunately it is locked by schema. In spite of this, you still manage to retrieve system files.
  
• 
  
• You need to find this test scheme to unlock smartphone.
  
• 
  
• You can find a link to download the full dump of system files on references sections.
  

Abstract

Nowadays many, if not all, smartphones offer, in addition to the traditional password lock protection, a pattern lock one, which is a mix of gestures done by the phone owner joining points on a matrix in order to unlock his phone. This “new security approach” lets you avoid any undesired taps on the device and it will be asked to authorize its access. This manipulation seems to be complicated and secure enough, which is totally wrong!

If you have a closer look at what a pattern lock actually is and how it works, you can easily conclude that it’s no more than a 3×3 matrix with some built-in conditions: The pattern drawn by the user must contain at last four points and each point can only be used once; since it’s a 3×3 matrix, the maximum of points a lock pattern can contain is nine.

Studying Pattern Scheme

The 3×3 points of the pattern lock can be represented by numbers (digits); in fact, the points are registered in order starting 0 to 8 (top left corner is 0 and ending by 8):

So the pattern used in the image above is

1 – 2 – 5 – 8 – 7 – 4.

Statistically, it’s not a very big deal having all combination between 0123 and 876543210, its not even 0.2% of all possible nine-digit numbers and we should have about 895824 pattern scheme possibilities available in an Android device.

Android devices do store pattern lock data in an unsalted SHA-1 encrypted bytes sequence format, using something similar to this code snippet in order to achieve this:

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;
    }
}

This means that, for example, instead of storing directly 125874 it stores an encrypted byte array in a system file called gesture.key located in the /data/system folder. We can read most of this information directly on “The Android Open Source Project” java files

* 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.

* @return the hash of the pattern in a byte array.

According to this piece of code, our sample pattern should be saved as 6c1d006e3e146d4ee8af5981b8d84e1fe9e38b6c

The only little problem facing us now is that SHA-1 is a one-way cryptographic hash function, meaning that we cannot get the plain text from the hashed one. Due to fact that we have very finite possible pattern combinations and the other fact that Android OS does not use a salted hash, it does not take a lot to generate a dictionary containing all possible hashes of sequences from 0123 to 876543210.

Problem solving

We know enough to analyze the file system dump we’ve got; it’s not hard to find gesture.key and to explore its content:

You can open it using any text or hexadecimal editor:

The last thing to do right now is to compare the bytes of this file, 2C3422D33FB9DD9CDE87657408E48F4E635713CB, with values in the previously generated dictionary to find the hash that recovers the pattern scheme.

A previously made dictionary can be downloaded in the reference section and, using any SQLite browser, you can easily find the original pattern scheme: Select * from RainbowTable where hash = “2c3422d33fb9dd9cde87657408e48f4e635713cb”.

Which means that this is the pattern that unlocks the “wife’s device”:

Conclusion

There are no difficulties cracking or bypassing this kind of protection an Android-based device; the only real obstacle is that we cannot directly access the /data/system/ folder and gesture.key file except when we are dealing with a rooted device. This is done for fun and curiosity purpose since, if you have full access to a mobile, you can just remove or replace the file containing the SHA-1 hash with a prepared one; in addition to this, in most cases lock files are valueless from a forensic point of view.

More complicated techniques could be used if the device is not rooted. We are talking about a physical dump of the memory chip and the use of some special hardware tools like Riff-Box and an JIG-adapter, but this is not our concern for now.

References:

• The Android Open Source Project (LockPatternUtils.java) : https://android.googlesource.com/platform/frameworks/base.git/+/f02b60aa4f367516f40cf3d60fffae0c6fe3e1b8/core/java/com/android/internal/widget/LockPatternUtils.java
  
• Link to download the dictionary: SHA1-android-pattern
  
• Link to download the partial phone dump: chandroid
  

Source

[MariusM]

Multumesc pentru informatii, foarte utile.

ca si chestie, daca nu avem baza de date cu cele 800 de mil. de hash-uri, cu o placa video cu 96 unitati CUDA se poate face brute-force in cateva ore.

Cu o placa mai rasarita, cu mai multe unitati CUDA (nVidia) sau OpenCL (ATI) se poate face brute-force in cateva minute (sau cateva secunde si 1$ pe Amazon computing).

Intrebare: cam cat dureaza inserturile din baza aia de date si cam cat spatiu ocupa? Ca poate e mai convenabil brute-force-ul decat cautarea in dictionar, daca nu avem spatiu sau timp de el....

Bafta!

[blech]

daca nu ma insel a mai fost postat pe RST ceva asemanator... si daca ai acces la /data poti direct sa urci alt pattern si nu-ti mai bati capul sa-l spargi.

corect?

[Byte-ul]

O mare prostie. Daca ai acces la acel fisier (nu ai acces daca nu ai root), il poti sterge si aia e. De ce ar sta cineva sa crackuiasca acel hash?

[wildchild]

Dac? bine ?in minte, am v?zut mai demult un tutorial asem?n?tor doar c? ar?ta direct unde era stocat patternul în plaintext, chiar pe când ap?ruse nenea Android. S-au prins ?i dup? aceea l-au encriptat, oricum cel mai simplu ar fi s? generezi hash-ul, dai rename la fi?ier, pui pe al t?u iar dup? ce ai luat ce ai avut de acolo pur ?i simplu faci override cu cel vechi, s? nu dai de b?nuit.

[andrei98M]

O mare prostie. Daca ai acces la acel fisier (nu ai acces daca nu ai root), il poti sterge si aia e. De ce ar sta cineva sa crackuiasca acel hash?

Nu trebuie sa isi dea seama persoana ca i-ai spart codu