Entschlüsseln des Android Lockscreen Patterns (Theorie)


1

1. 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\) 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.

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

3. 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).

Der praktische Teil des Angriffs wird in einem Artikel auf http://informatikfragen.de erscheinen, sobald es die Plattform gibt :)

 

 

Mathe Artikel, geschrieben vor 4 Monate
letsrockinformatik, verified
Student, Punkte: 4.46K
 
Kommentar schreiben Diesen Artikel melden
0 Antworten