Entscheidungsproblem mit Unendlichkeit

5 Beiträge25.09.2006Archiviert
Marc Ruef25.09.2006 · Beitrag #9845
Admin
Avatar
Mitglied seit: 25.01.2005
Forenbeiträge: 1337
Besuche: 22158
Hallo,

Ich mache mir (mal wieder) Gedanken zum [[Entscheidungsproblem]] und den Turingmaschinen. Dabei stellt sich mir eine Frage, die ich mir, wahscheinlich aufgrund des lueckenhaften mathematischen Wissens, nicht selber beantworten kann. Folgendes sei die These:

Es soll nun die Sicherheit des Eingabefelds für die PIN überprüft werden. Sowohl die minimale als auch die maximale Länge des Textfelds ist auf 4 Zeichen gesetzt, da diese Struktur die Grundvoraussetzung für die Richtigkeit der PIN ist. Durch Fuzzying können nun mittels Bruteforce sämtliche Eingaben getätigt werden, um sich abzeichnende Schwachstellen identifizieren zu können. Durch korrupte Zeichenkombinationen wie %%%% oder „>;’ könnten etwaige Sicherheitslücken (Format String, Cross Site Scripting und SQL-Injection) ausgemacht werden. Sind sämtliche Zeichen des nutzbaren Zeichensatzes (wahrscheinlich ASCI mit 128 Zeichen) durchlaufen und keine Sicherheitslücke gefunden, muss von einer sicheren Eingabe und Verarbeitung der PIN ausgegangen werden.

Jetzt ist es nun aber möglich, dass das Eingabefeld für die PIN nicht mit einer minimalen und maximalen Länge von 4 Zeichen definiert ist. Dies führt dazu, dass nun auch Zeichenkombinationen mit weniger oder mehr als 4 Zeichen eingegeben werden können. Damit ist ebenfalls die Eingabe von a oder aaaaaaa denkbar. Da keine maximale Beschränkung für die Eingabe festgelegt wurde, gibt es nun theoretisch eine unendliche Anzahl an Zeicheneingaben, die durchlaufen werden müssen, um das Ausbleiben einer Sicherheitslücke bestimmen zu können. Wird nun also die Eingabe von aaaaa mit einer Länge von 5 Zeichen eingegeben, müsste irgendwann auch die Eingabe von aaaaaa mit einer Länge von 6 Zeichen erfolgen, usw.


Trifft fuer diese Denkaufgabe die folgende Aussage zu:
Die Chancen, dass eine Sicherheitslücke gegeben und identifiziert werden kann, nimmt zwar theoretisch zwar mit der Weiterführung der Eingaben immer weiter ab, kann jedoch nie auf 0 reduziert werden.


Ist also (UNENDLICH - (n*2)) bei einer [[Inkrementierung]] von n um 1 immer um den Wert 1 näher bei 0? Oder darf man mit unendlichen Werten gar nicht rechnen? Eigentlich muesste (UNENDLICH) = (UNENDLICH - 1) sein, also Nein.

Bye, Marc
[ Bearbeitet ]
squeez25.09.2006 · Beitrag #9846
Mitglied seit: 06.04.2005
Forenbeiträge: 687
Besuche: 668
Guten Tag

Eine interessante Aufgabe.


"Die Chancen, dass eine Sicherheitslücke gegeben und identifiziert werden kann, nimmt zwar theoretisch zwar mit der Weiterführung der Eingaben immer weiter ab, kann jedoch nie auf 0 reduziert werden."


Nun, diese Aussage muss zuerst in eine mathematische Sprache uebersetzt werden, um genauer darauf eingehen zu koennen. Ich versuche es mal.
Wir gehen davon aus, dass wir nicht wissen, bei welcher Kombination ein Fehler auftritt. Dh, jede Zeichenfolge ist, unabhaengig von ihrer Laenge, gleich wahrscheinlich. Die Wahrscheinlichkeit, dass also eine fehlerhafte Zeichenfolge gefunden wird, errechnet sich durch : 1/n, wobei n gegen unendlich strebt.
Der mathematische Grenzwert ([[Limes (Mathematik)]] [[Grenzwert (Folge)]]) dieser Folge geht also streng gegen 0.

limit (1/n, n = infinity) = 0.


Ist also (UNENDLICH - (n*2)) bei einer Inkrementierung von n um 1 immer um den Wert 1 näher bei 0?

Ich weiss nicht genau was du damit meinst, aber bezogen auf meine obige Ausfuehrung, duerfte klar sein, in welche Richtung der Grenzwert (welcher meine Ansicht nach hier das Gewicht hat) geht.

Allgemeines zu Unendlichkeiten.
Unendlichkeiten sind nicht gleich maechtig (die Maechtigkeit einer Menge beschreibt die Anzahl ihrer Elemente |M|). Dh, obwohl die Maechtigkeit zweier Mengen unendlich sind, sind sie nicht gleich gross. So gilt zum Beispiel: R ist mächtiger als N, da es keine [[Bijektion]] von R (reelle Zahlen) auf N (natuerliche Zahlen) gibt.
So ist es muessig, einfach von unendlich zu sprechen. Ein Mittel dagegen stellt die Betrachtung des Grenzwertes dar, wie oben gezeigt.

Vielleicht an dieser Stelle noch ein interessantes Gedankenexperiment zu Unendlichkeiten:
Ein Stift faellt senkrecht (seine Achse ist ebenfalls senkrecht) auf eine Holzplatte. Irgendwann betraegt der Abstand 1/2 mm, dann 1/4 mm und irgendwann 1/8. Geht dies so weiter, duerfte der Stift die Platte auch nach unendlich langer Zeit nicht beruehren. Interessant oder ? ;}

hth

Marco
Marc Ruef25.09.2006 · Beitrag #9848
Admin
Avatar
Mitglied seit: 25.01.2005
Forenbeiträge: 1337
Besuche: 22158
Hallo,

Danke, das hat mir geholfen.

Vielleicht an dieser Stelle noch ein interessantes Gedankenexperiment zu Unendlichkeiten:
Ein Stift faellt senkrecht (seine Achse ist ebenfalls senkrecht) auf eine Holzplatte. Irgendwann betraegt der Abstand 1/2 mm, dann 1/4 mm und irgendwann 1/8. Geht dies so weiter, duerfte der Stift die Platte auch nach unendlich langer Zeit nicht beruehren. Interessant oder ? ;}


Gemeinhin ist dies ja auf Zenons [[Teilungsparadoxon]] ([[Achilles und die Schildkröte]]) zurueckzufuehren. Meines Erachtens ist dieses sehr einfach loesbar. Zenon geht bei seiner Idee davon aus, dass die beiden Masseinheiten [[Zeit]] und [[Raum]] unendlich oft geteilt werden koennen. Ist dies der Fall, ist es tatsaechlich nicht moeglich, dass die Schildkroete den [[Achilles]] ueberholen kann.

Die [[Physik]] lehrt uns aber - und dies war den alten Griechen halt noch nicht bekannt -, dass es in diesem [[Universum]] eine kleinste Menge in Bezug auf Zeit und Raum zu geben scheint. Ist das Herunterbrechen auf diese erreicht, gibt es als Weiterfuehrung nur noch die beiden Zustaende "vor Achilles" oder "nach Achilles". Zenons Idee funktioniert also als Gedankenexperiment - Jedoch nicht in der Realitaet ;) !

Bye, Marc
Helms03.10.2006 · Beitrag #9936
Avatar
Mitglied seit: 08.02.2005
Forenbeiträge: 517
Besuche: 1267
Den Aspekt Zeit könnten wir auch noch weiterführen mit der Ralativitätstheorie von Einstein.

Laut Einstein, ist alles auf dieser Welt relativ. Denn eine Sekunde ist nicht immer eine Sekunde und da alles auf dieser Welt auf die Zeit aufbaut, ist die Zeit genauso relativ wie auch die Welt. xD

---
edit:

Nochmal meine Gedanken zu der Aufgabe:

Weiß aber wirklich nicht ob es dich weiterbringt. Eventuell nur dann wenn du immernoch nach einer Lösung suchst.

Im allerersten Post nanntest du bereits eine Zahlenfolge.

Bisher zusammengefasst kann man sagen, dass es ledigilisch die untere Schranke 0 gibt für keine Schwachstelle, da diese aber nicht erreicht werden kann(mathematisch wiedersprüchlich) ist n ungleich 0.

Allerdings ist die Zahlenfolge(an) durch den Wert n deiner Zahlenfolgen monoton fallend, weil ein Risiko immermehr ausgeschlossen werden kann für eine Zahlenanzahl von mehr als 4.

Somit solltest du 2 Fälle unterscheiden.

Fall 1.: 4 Zeichen, n unglichen 0
Fall 2.: Zeichen > 4, n ungleich 0

Da die Warscheinlichkeit eine Schwachstelle zu finden größer für Fall 1 ist, würde ich lieber Fall 1 untersuchen.

Ich glaube dieser Post von mir war jetzt mal echt überflüssig, sorry xD



Liebe Grüße
Helms


[ Bearbeitet Mi, 04. Okt 2006, 00:00 ]
El Kassem13.01.2009 · Beitrag #19416
Avatar
Mitglied seit: 01.06.2008
Forenbeiträge: 466
Besuche: 2238
Und kam man schon auf irgendein Ergebnis ?
Würde mich sehr interessieren...