Dieser Artikel ist (samt Implementierung und Beispiel-File) auch auf https://www.cyber-security.online/entschluesseln-des-android-lockscreen-patterns verfügbar.
Den zweiten Teil (Durchführen des Angriffs) gibt es hier: https://www.stacklounge.de/987/informatik-artikel-entschlusseln-android-lockscreen-patterns
In diesem Teil beschäftigen wir uns mit der mathematischen Modellierung und dem Ermitteln der Erfolgswahrscheinlichkeit einer Brute-Force-Attacke.
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 jedwede durch Missachtung dieser Vorgaben entstandenen Schäden! Dieser Beitrag ist lediglich zu Bildungszwecken gedacht! Don't Learn to Hack - Hack to Learn!
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\) 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.
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\)
- \(a_i\in m\wedge a_j\in m \wedge i\neq j\Longrightarrow a_i\neq a_j\)
- \((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).
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.
Im nächsten Teil (https://www.stacklounge.de/987/informatik-artikel-entschlusseln-android-lockscreen-patterns) geht es um die Durchführung des Angriffs.
Das Mitglied hat durch den Artikel 50 Bonuspunkte erhalten. Schreib auch du einen Artikel.
