+5 Daumen
2,5k Aufrufe

1. Einleitung

In den Sicherheitseinstellungen von Android hat man die Wahl zwischen verschiedenen Lock-Screen-Typen, die ein unterschiedlich hohes Maß an Sicherheit bieten. Als Schutzniveau-Metrik eignet sich beispielsweise die Anzahl an mathematischen Kombinationsmöglichkeiten, die theoretisch zur Umgehung des Schutzes durchprobiert werden müssten, wenn man die Passphrase nicht kennt. Wir werden in diesem Artikel herausfinden, weshalb die Sperrmuster nur einen mittleren Schutz bieten und die Wahl von PINs und Passwörtern eure Smartphones sicherer machen. 

Bevor wir uns dem mathematischen Teil widmen, müssen die verschiedenen Schutzmechanismen verstanden werden:

Wischen - Beim Wischen wird das Smartphone durch einfaches Wischen über den Bildschirm entsperrt. Dass dies keinen Schutz bietet, bedarf keiner weiteren Erklärungen.

Sperrmuster - Ein Sperrmuster wird durch das Verbinden von Knoten in einem Graphen erzeugt. Um für unsere späteren Überlegungen ein geeignetes Modell zu haben, versehen wir die einzelnen Knoten mit Zahlen:

Bild Mathematik

Der Anwender kann das Smartphone nur durch Eingabe des festgelegten Musters entsperren. Wie wir später sehen werden, muss ein solches Muster bestimmte Regeln erfüllen, welche die kombinatorische Betrachtung maßgeblich beeinflussen.

PIN - Ein PIN besteht aus mindestens \(4\) und maximal \(16\) Ziffern von \(0\) bis \(9\). An die einzelnen Stellen des \(4-\) bis \(16-\)stelligen Codes kann jede der \(10\) Ziffern treten. Es ergeben sich somit $$\sum_{k=4}^{16}10^k=11111111111110000$$ mögliche Codes.

Passwort - Im Vergleich zu den PINs setzen sich Passwörter nicht nur aus Ziffern, sondern aus dem gesamten zur Verfügung stehenden Zeichensatz zusammen. Die Passwortlängenregel ist dieselbe wie bei den PINs. Die Berechnung der Passwortmöglichkeiten basiert ebenfalls auf dem PIN-Ansatz, wobei die Basis des Exponenten die Anzahl des jeweiligen Zeichensatzes ist. Deshalb sind Passwörter weitaus sicherer, da mehr als \(10\) Zeichen pro Stelle genutzt werden können.

2. Das Problem

Die Frage ist, wie man die Anzahl an möglichen Sperrmustern berechnen kann. Wichtig ist dabei nicht nur das Muster, sondern auch die Art, auf die es erzeugt werden kann:

Bild Mathematik

Zu beachten ist außerdem, dass das Muster folgende Regeln erfüllen muss:

- Ein Sperrmuster muss aus mindestens \(4\) und maximal \(9\) Knoten bestehen.

- Es sind keine „Sprünge“ erlaubt, d.h. die Folge \(1\rightarrow 3\rightarrow 7\rightarrow 4\) ist nicht möglich. Diese Regel gilt jedoch nicht, wenn ein zwischen zwei Knoten liegender Knoten bereits besucht wurde, d.h. die Kombination \(2\rightarrow 3\rightarrow 1\rightarrow 4\) kann als Sperre verwendet werden.

Kein Knoten darf doppelt besucht werden.

3. Die Lösung

Wenn wir annehmen, dass nur die Längenregel Anwendung findet, ergeben sich $$\sum_{k=4}^{9}{\binom{9}{k}\cdot k!= 985824}$$ Möglichkeiten. Von dieser Anzahl sind nun alle ungültigen Sperrmuster nach der Sprungregel abzuziehen, also diejenigen Kombinationen, die mindestens eine der folgenden Verbindungen enthalten: \(1\rightarrow 3, 3\rightarrow 1, 4\rightarrow 6, 6\rightarrow 4, 7\rightarrow 9, 9\rightarrow 7, 1\rightarrow 7, 7\rightarrow 1, 2\rightarrow 8, 8\rightarrow 2, 3\rightarrow 9, 9\rightarrow 3, 1\rightarrow 9, 9\rightarrow 1, 3\rightarrow 7, 7\rightarrow 3\). Hinzu addieren wir alle Kombinationen, die fälschlicherweise von der vorangegangenen Subtraktion ausgeschlossen wurden, also alle, in denen vor dem jeweiligen Übergang \(m\rightarrow n\) der Knoten \(\dfrac{m+n}{2}\) bereits ausgewählt wurde. So ist also z.B. \(5\rightarrow 9\rightarrow 1\rightarrow 2\) gültig. Die Regel der doppelten Knotenbesuche muss nicht gesondert behandelt werden, da diese bereits durch die Verwendung des Binomialkoeffizienten berücksichtigt wurde.

Ich habe zur Berechnung ein kleines Java-Programm geschrieben (siehe Simulator.txt (9 kb)).

(Alternativer Link: https://github.com/kazutokirigayakun/Mathelounge/blob/master/Simulator.java)

Bild Mathematik 

Insgesamt sind also „nur“ \(389.112\) Sperrmuster möglich, wobei die Muster der Länge \(8\) und \(9\) insgesamt ca. \(72.32\%\) ausmachen. Die Tabelle zeigt also, auf welche Vielfalt man bei der Wahl des „visuellen“ Passwortschutzes verzichtet.

Ob man nun zwecks vermeintlich simplerer Merkmöglichkeit ein Sperrmuster als Lock-Screen nutzt, muss jeder für sich selbst entscheiden.


Das Mitglied hat durch den Artikel 50 Bonuspunkte erhalten. Schreib auch du einen Artikel.
geschlossen: mathe-artikel
von Lu
Avatar von

Beachtet bitte, dass das Java-Programm erst noch kompiliert werden muss. Zudem wurde nicht auf Laufzeitoptimierung geachtet (es läuft für die Berechnung der Gesamtzahl an Sperrmustern der Länge 4 bis 9 ca. 600 Sekunden) ... das Programm soll nur "leicht verständlich" sein. In Mathematica würde man vermutlich nicht einmal die Hälfte an Code benötigen.

Toller Artikel. Die Fragestellung wurde schonmal vor längerer Zeit hier im Forum heiß diskutiert, wobei die unterschiedlichsten Lösungen herauskamen. Vielleicht könntest du noch hinzufügen, wie lange man für das Knacken des Codes benötigen würde. Bei mehrmaliger Falschausführung wird das Feld ja immer für eine bestimmte Zeit gesperrt. Gibt man es dann nochmal falsch ein wird die Zeit verdoppelt, usw.

Frontliner: Du sprichst von https://www.mathelounge.de/18906/wieviel-moglichkeiten-codes-gibt-beim-android-lockscreen ?

Was mich ärgert, ist, dass ich das Android-Gerät entsperren muss, wenn ich z.B. Musik hören will. Mir würde genügen, wenn nur, was ich Passwort geschützt habe, alle paar Minuten verschlossen würde.

@Lu Das funktioniert unter Einstellungen > Gerätesicherheit > Sichere Sperreinstellungen > Automatisch sperren

Dort kannst du dann den Zeitraum wählen in dem das Handy nach Ausschalten des Bildschirms gesperrt wird.

Frontliner,

ich hatte noch einiges an Content ... leider waren die 8000 Zeichen schon voll:-( Ich werde die fehlenden Aspekte, die leider nicht mehr in den Artikel gepasst haben, mit der PDF-Version, die ich in den nächsten Tagen zum Download zur Verfügung stellen werde, veröffentlichen.

Es freut mich, dass Dir der Artikel gefallen hat:-)

@Lu

Der Thread war mir nicht bekannt. Es scheint aber einer mit mir d'accord zu sein. Die anderen Ansätze sind ebenfalls interessant.

André

@André: Dein Artikel hat mir ebenfalls gefallen, da du gleich zu Beginn erklärst, worum es genau geht. Ich hätte den andern Thread auch nicht gesucht, wenn Frontliner nicht darauf verwiesen hätte. Dort war das zu Beginn weniger offensichtlich.

@Frontliner: In den Einstellungen kann ich aber nicht entscheiden, welche Programme offen bleiben sollen und wo ich genau die Sperrung haben will. Es verschliesst mir praktisch das ganze Gerät. Oder?

@Lu Ja, aber die systemeigene Musik-App öäuft auch bei gesperrtem Handy.

Toller Artikel! Gefällt m ir. Ist bei Smartphones eigentlich immer diese regel mit dem nicht überspringen vorhanden? Kann man das ausstellen?

@MathFox

Schön, dass Dir der Artikel gefallen hat. So weit ich weiß ist das bei allen Android-Devices so. Man kann es nicht ausstellen, weil das nun einmal Teil des definierten Regelwerks für Sperrmuster ist.

Ich habe den Simulator auf meine github-Page verschoben (siehe: https://github.com/kazutokirigayakun/Mathelounge/blob/master/Simulator.java). Das .txt-File kann gerne aus dem Artikel entfernt oder dieser Link stellvertretend dort platziert werden.

Danke:-)

EDIT: Hallo André,  ich habe nicht die Berechtigung Text aus einem Artikel durch Links auf fremde Seiten zu ersetzen. Melde dich mit deinem Anliegen besser beim admin.

@Lu: Warum sollte das nicht gehen, oder habe ich etwas missverstanden?

@André: Habe die txt-file mal im Beitrag gelassen. So kann man sich diese entweder intern oder extern ziehen. Geht das in Ordnung?


Grüße

@Unknown

Ja, das ist völlig in Ordnung.

@Unknown: Ich habe das wohl missverstanden. Ich dachte, dass der ganze Text oben einfach durch diesen Link zu ersetzen ist. Was du gemacht hast, ist bestimmt ok.

@Lu

Um Himmels Willen, nein:-D Das ist nur der Link zu dem Programm, mit dem die Anzahl an Sperrmustern ausgerechnet wird.

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community