PDA

Archiv verlassen und diese Seite im Standarddesign anzeigen : Frage an den kleinen Mathematiker (anzahl Möglichkeiten)



Seiten : [1] 2

mamue
08.07.03, 20:24
Ich hatte sonst 6 Zeichen lange Passwörter, bestehend aus a-zA-Z,0-9 und einigen Sonderzeichen.
Wegen der Probleme, die einige mit der Unterscheidung hatten, habe ich O0l1I und ein paar weitere rausgeworfen und dafür die Passwortlänge auf 8 Zeichen verlängert. Passwörter bestehen jetzt leicht vereinfacht entweder aus
A-Z0-9
oder
a-z0-9
Beispiele: BH67QDTC, 9a4t63u8
Für brute-force müsste ich alle Permutationen durchgehen, bei der alten Variante wären das:
Mächtigkeit-des-zeichenvorrates hoch 6 (oder?)
bei der neuen Variante
Machtigkeit-des-Zeichnvorrates-UPPER hoch 8 + Machtigkeit-des-Zeichnvorrates-LOWER hoch 8 (??? eher nicht)

Kann mir jemand helfen?

mamue

michel_vaclav
08.07.03, 20:46
Ich kann keinen Fehler entdecken, und beim Nachrechnen stelle ich fest, dass die neuere Methode sicherer ist. Ich hätt es eigentlich andersrum erwartet, wegen der größeren Zeichenmenge. Aber so täuscht man sich.

michel_vaclav

mamue
08.07.03, 20:55
tausend Dank!
Ich habe eher geraten und glaubte, mich zu täuschen, weil doch bei der zweiten Variante die 0-9 zweimal, also in beiden Zeichenmengen auftritt. Damit ist sie aber sicher nicht mehr gleichverteilt vorhanden in den Passwörtern. Bekomme ich da etwas durcheinander?

mamue

geronet
08.07.03, 21:21
Mein Bruder meint, wenn man z.B. 30 Buchstaben und 8 Stellen hat gibt das

30^8 + 30^7 + 30^6 + .... + 30^1 + 30^0 Möglichkeiten.

Also bei deinem Passwort mit
A-Z (27) + 0-9 (10) - O0l1I(5) = 32 Buchstaben und 8 Stellen gibt das

1.13498*10^12 Möglichkeiten.. sollte wohl reichen :ugly:

- Angaben ohne Gewähr -

Thomas
08.07.03, 22:16
Jetzt bin ich gerade fertig mit lernen und schaue ins Forum: Da geht es gerade so weiter...

Morgen um 8 Uhr "darf" ich höhere Mathematik 3 schreiben, da kommt Freude auf... :(


Was geronet geschrieben hat war völlig korrekt, bei einem Zeichenvorrat von 30 Zeichen und einer Anzahl der Stellen des Passwortes von 8 ist die Anzahl der Kombinationen

30^8 + 30^7 + 30^6 + ... + 30^2 + 30^1


Thomas.

geronet
08.07.03, 22:23
Fehlt da nicht die 30^0 ?

Alex_K
08.07.03, 22:25
also ich kann die rechenweise deines bruders nicht nachvollziehen:

altes passwort:
ich habe einen zeichenvorrat von 62 und ein wort der länge 6, daraus folgt 62^6 möglichkeiten = 5,68e10

neues passwort:
ich habe für wörter mit nur kleinbuchstaben einen zeichenvorrat von 36 und von wörten mit nur großbuchstaben ebenfalls einen zeichenvorrat von 36. bei einem 8 zeichen langen passwort habe ich nun 36^8 möglichkeiten ein passwort aus dem 1. zeichenvorrat zu wählen und 36^8 möglichkeiten aus den 2. vorrat. nun muss man diese möglichkeinen addieren, also 36^8 + 36^8. nun gib es aber noch passwörter die in beiden zeichenvorräten enthalten sein können (z.B. 12345678) diese wurden nun 2x gezähl und müssen daher wieder 1x abgezogen werden. es gibt also 10^8 möglichkeiten die in beiden vorkommen.
das endergebniss sollte nun, falls ich keinen denkfehler drinnen habe, 36^8 +36^8 -10^8 = 5,64e12 sein.

Thomas
08.07.03, 22:38
@ geronet: Wenn du ein Passwort mit 0 Stellen dazurechnest dann ja. Das wäre dann aber kein Passwort, da es aus 0 Zeichen besteht.

@ Alex_K: Du darfst das nicht einzeln berechnen, alle möglichen Zeichen müssen in einem Zeichnvorrat gesammelt werden.
Dann wird mittels Variation ermittelt, wieviele Möglichkeiten es gibt, n Zeichen aus dem Zeichenvorrat zu entnehmen. Danach wird via Permutation die Anzahl der Anordungen der ausgewählten Zeichen ermittelt.
Die Variation mit anschließender Permutation wird als Kombinatorik bezeichnet.

Da sich ein Passwort mit der Länge 8 von einem Passwort mit der Länge 7 unterscheidet, wenngleich die 7 Zeichen gleich sind und gleich angeordnet sind, sind die Kombinationen zu addieren.

Alex_K
08.07.03, 22:40
Original geschrieben von TThomas
30^8 + 30^7 + 30^6 + ... + 30^2 + 30^1


ich glaube ich hab jetzt verstanden wie ihr rechnet!

ich rechnet auch die möglichkeiten dass ein passwort <8 zeichen haben kann.
so wie ich mamue verstanden habe soll ein passwot aber genau 8 zeichen haben.

Alex_K
08.07.03, 22:46
Original geschrieben von TThomas
Du darfst das nicht einzeln berechnen, alle möglichen Zeichen müssen in einem Zeichnvorrat gesammelt werden.

nochmal eine verständnissfrage:
wenn ich dass verstanden habe ist ein passwort aaaabbbb != AAAABBBB und somit sollte meine rechnung mit dem inklusions-exklusions-prinzip stimmen.


Original geschrieben von TThomas

Da sich ein Passwort mit der Länge 8 von einem Passwort mit der Länge 7 unterscheidet, wenngleich die 7 Zeichen gleich sind und gleich angeordnet sind, sind die Kombinationen zu addieren.

... siehe meinen letzten post ...

Thomas
08.07.03, 22:58
Das Passwort soll 8 Zeichen haben, das ist korrekt.
Da es hier um Sicherheit geht, sprich darum, wie leicht/schwer es ist das Passwort zu knacken und ein Angreifer nicht weiß wieviel Zeichen das Passwort hat muss man auch mit den Kombinationen mit weniger als 8 Zeichen rechnen.

mamue
09.07.03, 08:29
Da alle Passwörter automatisch vergeben werden - wo kämen wir da hin, wenn jeder Anwender sich sein Passwort selber ausdachte - sind alle Passwörter genau 8 Zeichen lang. Jeder Angreifer wird das wissen.
Also habe ich 32^8 Für die Grossbuchstaben + 32^8 Für die Kleinbuchstaben. Es ist quasi mein Problem, dafür zu sorgen, dass die 0-9 und (a-z oder A-Z) gleichverteilt sind. Wenn nicht, erhöht das vielleicht die Wahrscheinlichkeit für bestimmte Kombinationen verringert aber nicht die Anzahl der Möglichen Permutationen.

Ich bedanke mich sehr für die Eräuterungen!

mamue

eeknay
09.07.03, 14:13
Original geschrieben von geronet
Fehlt da nicht die 30^0 ?

x^0 ist immer "1", fällt also raus ;)

Jasper
09.07.03, 15:26
Original geschrieben von mamue
Da alle Passwörter automatisch vergeben werden - wo kämen wir da hin, wenn jeder Anwender sich sein Passwort selber ausdachte - sind alle Passwörter genau 8 Zeichen lang. Jeder Angreifer wird das wissen.
Also habe ich 32^8 Für die Grossbuchstaben + 32^8 Für die Kleinbuchstaben. Es ist quasi mein Problem, dafür zu sorgen, dass die 0-9 und (a-z oder A-Z) gleichverteilt sind. Wenn nicht, erhöht das vielleicht die Wahrscheinlichkeit für bestimmte Kombinationen verringert aber nicht die Anzahl der Möglichen Permutationen.


es sind ein paar weniger:

( 2 x 32 ^ 8 ) - ( 10 ^ 8 )

der erste term ist klar. du musst aber von den möglichkeiten einmal alle passwörter bestehend aus ausschliesslich zahlen abziehen. diese sind ja bereits in 32^8 enthalten und würden sonst doppelt gezählt werden. deshalb einfach einmal abziehen.

hier ist die verringerung der zeichenmenge durch die entfernung der ähnlichen zeichen wie 0 und O etc. nicht berücksichtigt.

-j

xare
09.07.03, 16:41
Original geschrieben von mamue
Passwörter bestehen jetzt leicht vereinfacht entweder aus
A-Z0-9
oder
a-z0-9
Beispiele: BH67QDTC, 9a4t63u8


Aus welchem Grund lässt du nicht Groß- und Kleinbuchstaben gemischt zu? Sonderzeichen würden auch noch zur Verfügung stehen...

MfG Xare

Windoofsklicker
09.07.03, 17:02
ganz einfach:

wenn ich mit n stellen zur basis b etwas darstellen will, ist es (b^n) -1
also 8 stellen à 30 zeichen ist (30^8)-1 also ca 6.5 * 10^11

herleitung:

(b-1)*(b^(n-1) + (b-1)*(b^(n-2) + ... + (b-1)*(b^2)+(b-1)*(b^1) + (b-1)*(b^0)

nach ausklammern von (b-1):

(b-1)*(b^(n-1) + b^(n-2) + ... + b^2 + b^1 + b^0)

wir bezeichnen den fetten teil mit S

S = (b^(n-1) + b^(n-2) + ... + b^2 + b^1 + b^0)

erweitern mit b

S*b = (b^n + b^(n-1) + ... + b^3 + b^2 + b^1)

S - S * b = (-b^n + b^0)

S ausklammern

S(1-b) = (-b^n + b^0)

somit ist S (der lange und fette ausdruck von oben)

S = (-b^n + b^0)/(1-b)

dann S oben eingesetzt: ( also mit b-1 erweitern)

bleibt ((b-1) (-b^n + b^0)) /(1-b)

oder (b^n) -1 :)

BLUESCREEN3D
09.07.03, 17:04
Original geschrieben von geronet
Also bei deinem Passwort mit
A-Z (27) + 0-9 (10) - O0l1I(5)
das Alphabet hat nur 26 Buchstaben
aus einer Menge von Großbuchstaben kann man nicht ein kleines 'l' abziehen


Original geschrieben von Jasper
( 2 x 32 ^ 8 ) - ( 10 ^ 8 )

der erste term ist klar. du musst aber von den möglichkeiten einmal alle passwörter bestehend aus ausschliesslich zahlen abziehen. diese sind ja bereits in 32^8 enthalten und würden sonst doppelt gezählt werden. deshalb einfach einmal abziehen.

hier ist die verringerung der zeichenmenge durch die entfernung der ähnlichen zeichen wie 0 und O etc. nicht berücksichtigt.
IMHO stimmt das so - und unter berücksichtigung von den Abzügen sieht das so aus:

Großbuchstaben:
A-Z ohne O und ohne I, also 24 Buchstaben
außerdem 2-9, also 8 Zahlen
das macht 32 verschiedene Zeichen, also schonmal 32^8 Möglichkeiten

Kleinbuchstaben:
a-z ohne l, also 25 Buchstaben
außerdem 2-9, also 8 Zahlen
das macht 33 verschiedene Zeichen, also nochmal 33^8 Möglichkeiten

Jetzt überschneiden sich, wie Jasper schon gesagt hat, aber die Passwörter, die nur aus Zahlen bestehen - also werden diese nochmal abgezogen, um nur einmal gezählt zu werden:
2-9, also 8 Zahlen
das macht 8^8 Möglichkeiten, die doppelt gezählt wurden

Ergebnis:
32^8+33^8-8^8 = 2.5059e+12 = 2505900000000 verschiedene Möglichkeiten bei einer festen Länge von 8 Zeichen

d-0
09.07.03, 18:43
Hmm also ich verstehe eure Logik nicht:


Mein Bruder meint, wenn man z.B. 30 Buchstaben und 8 Stellen hat gibt das 30^8 + 30^7 + 30^6 + .... + 30^1 + 30^0 Möglichkeiten.

Wie kommt er darauf? Angenommen man hat 30 Buchstaben und 8 Stellen, dann hat man für die erste Stelle 30 Möglichkeiten, für die zweite auch und so weiter.

Ergo 30^8 und nichts mehr. Warum ihr die Kombinationen von 7,6,5,4,3,2,1 stelligen Passwörten dazurechnet ist mir ein Rätsel. Mit 8 STellen stimmt jedenfalls definitiv 30^8.

edit: und wenn er vielleicht mein, dass einige Stellen am Anfang oder ende leer sind, so nimmt man halt einfach das Leerzeichen zu den Zeichen hinzu -> 31 zeichen.

Dann ist die Gesamtmenge
\omega = 31^8

Windoofsklicker
09.07.03, 18:49
Original geschrieben von geronet
Mein Bruder meint, wenn man z.B. 30 Buchstaben und 8 Stellen hat gibt das

30^8 + 30^7 + 30^6 + .... + 30^1 + 30^0 Möglichkeiten.


fast. es sind 30^8 -1.
bei acht stellen ist die werthöchste stelle ^7, da bei ^0 angefangen wird.

und die summe aus 30^7 + 30 ^6 + ... +30^1 + 30 ^0 ust das gleiche wie 30^8 - 1

d-0
09.07.03, 18:54
fast. es sind 30^8 -1.

Hmm also:

Stelle1: 30 Möglichkeiten
Stelle2: 30
....
Stelle8: 30

=> \omega=30*30*30...*30=30^8

ich frag mich warum ihr da so einen Akt draus macht :ugly:

edit:

und die summe aus 30^7 + 30 ^6 + ... +30^1 + 30 ^0 ust das gleiche wie 30^8 - 1 _das_ halte ich allerdings auch für ein Gerücht :ugly:

Windoofsklicker
09.07.03, 19:24
Original geschrieben von d-0

_das_ halte ich allerdings auch für ein Gerücht :ugly:

hast recht, aber für 2^64 -1 und summe(2^n,n,0,63) gilt das ;)

michel_vaclav
09.07.03, 20:27
Ich kann d-0 nur beipflichten, und da wären wir wieder bei der ursprünglichen Berechnung von mamue, die ist richtig.

Angenommen, die Zeichen für das Passwort werden per Zufallsgenerator bestimmt. Damit ist doch klar, dass die Wahrscheinlichkeit für ein Zeichen an der Stelle x des Passworts unabhängig von den schon vorhandenen Zeichen ist. Ein Würfel schert sich doch auch nicht um das, was schon gewürfelt ist. Damit gilt für jedes Zeichen gezogen zu werden (egal welche Stelle des Passworts) die Wahrscheinlichkeit: 1/Anzahl der möglichen Zeichen.

michel_vaclav

Jasper
10.07.03, 08:10
Original geschrieben von michel_vaclav
Ich kann d-0 nur beipflichten, und da wären wir wieder bei der ursprünglichen Berechnung von mamue, die ist richtig.


die von mamue (32^8+32^8) ist nicht richtig., wegen den doppelt gezählten, nur aus ziffern bestehenden, passwörtern.

-j

michel_vaclav
11.07.03, 18:29
Ich gebs ja nur ungern zu, aber ich hab die doppelt gezählten Ziffern in der Tat vergessen.

michel_vaclav

mamue
11.07.03, 19:07
Umpf. Diesen Teil des Forums betrete ich nur selten und dachte, die Frage wäre bereits beantwortet gewesen.
Wie ich jetzt gelernt habe, muss ich also die doppelten (Ziffern) herausrechnen.
Ich habe mich für die Passwörter mit jeweils nur klein+ziffern oder GROSS+ziffern entschieden, weil sich erfahrungsgemäss viele Anwender schwergetan haben mit dieser gemischten Schreibweise. Viele Anfänger bekommen das nicht hin, sondern schreien nach dem dritten Versuch einfach los ("Ich kann mich nicht anmelden, der Computer geht nicht!")

Danke,
mamue

RapidMax
12.07.03, 00:03
Es ist zwar nett, die Anzahl Kombinationen auszurechnen, aber um die Stärke des Passwortes zu bestimmen, reichen ein paar einfache Berechnungen und Daumenregeln.

Man geht davon aus, das mit der momentan verfügbaren Rechenleistung (auch mit tausenden von Rechnern) ein Passwort von 80 Bit sicher ist. (2^80 Möglichkeiten). Wenn man damit rechnet, dass die Rechenleistung steigt, dann ist man mit 128Bit auf der sicheren Seite (min. die nächsten 10 Jahre). Da ein Passwort regelmässig geändert werden sollte - es also kurzlebig ist - kann man bei weniger grossen Sicherheitsansprüchen auch 64-Bittige Passwörter verwenden. Mit einzelnen Rechnern (ein bis ca. zehn) sind 48-Bittige Passwörter nicht mal kurz über Nacht mit Brute-Force zu knacken: Ein unkritischer Useraccount kann deshalb auch 48-Bit Passwörter verwenden, sofern man das Passwort regelmässig ändert.

Apropos: Was heist Brute-Force? Ich gehe hier davon aus, dass der MD5-Digest des Passwort bekannt ist. Gegen eine netzseitige Bruteforce-Attacke z.B. auf den SSH-Account genügen weit weniger Bits pro Passwort.

Nun kann ich nicht einfach rechen: 8 Zeichen mit 8-Bit-Zeichensatz ist gleich 8*8=64Bit. Man muss berücksichtigen, dass in einem Passwort weniger Zeichen vorkommen.

Bei Texten ist die Redundanz so gross, dass man mit ca. 1.2 Bit pro Zeichen rechnen kann. Für ein einzelnes Wort kann man mit ca. 4 Bit pro Zeichen rechnen.

Verwendet man rein zufällige Zeichenfolgen, so muss mit dem verwendeten Zeichenumfang gerechnet werden. Um das Beispiel am Anfang dieses Threads zu nehmen:
A-Z: 26 Zeichen
0-9: 10 Zeichen
Das sind 36 Zeichen, d.h. ein wenig mehr als 2^5. Es entspricht etwa 5.2 Bit pro Zeichen: 8*5.2 ~ 42 Bit. Das Passwort ist damit eigentlich zu klein.

Nehmen wir noch die Kleinbuchstaben hinzu: 2*26+10 = 62.
Das entspricht ca. 2^6 Möglichkeiten was ca. 6 Bit pro Zeichen entspricht: 8*6=48. Damit sind wir schon bei den unkritischen User-Accounts gelandet.

Um noch bessere Passwörter zu erhalten, haben wir nur zwei Möglichkeiten:
[list=1]
Noch mehr Zeichen verwenden: Sonderzeichen, die einen ASCII-Wert von mehr als 127 haben, sollte man vermeiden, d.h. es sind die restlichen Sonderzeichen unterhalb von 128 ohne die Steuerzeichen (0-31) zu Verwenden (z.B.: +"*[( usw.). Damit brigen wir es auf auf ca. 6.8 Bit pro Zeichen: Keine wirklich grosse Verbesserung.
Längeres Passwort bei gleichem Zeichenvorrat ([0-9a-zA-Z]). Bei 16 Zeichen erreichen wir damit problemlos mehr als 80Bit. Der Nachteil hier liegt darin, dass nicht alle Systeme mehr als 8 Zeichen berücksichtigen. Der alte crypt()-Mechanismus vom Unix-Login kann das z.B. nicht, wärend das neue MD5-Verfahren das kann.
[/list=1]

Gruss, Andy

mamue
12.07.03, 12:02
Original geschrieben von RapidMax

A-Z: 26 Zeichen
0-9: 10 Zeichen
Das sind 36 Zeichen, d.h. ein wenig mehr als 2^5. Es entspricht etwa 5.2 Bit pro Zeichen: 8*5.2 ~ 42 Bit. Das Passwort ist damit eigentlich zu klein.
Nehmen wir noch die Kleinbuchstaben hinzu: 2*26+10 = 62.
Das entspricht ca. 2^6 Möglichkeiten was ca. 6 Bit pro Zeichen entspricht: 8*6=48. Damit sind wir schon bei den unkritischen User-Accounts gelandet.


Ich gehe grundsätzlich von einiger Boshaftigkeit der user aus, also keine shell, bzw. /bin/false, Schreibschutz auf den PC (reborn/Wächter-karten) und keine executables in den Homeverzeichnissen, - unter anderem.
Ich glaube, das verstanden zu haben. Mehr als 8 Zeichen kann ich denen nicht zumuten, die bisherigen 6 mit gemischter Schreibweise und Sonderzeichen kamen aber wie gesagt auch nicht gut an. Ich werde mir wohl überlegen, wie ich gefahrlos den Zeichenvorrat (,-.+#!"%&/()=? vielleicht) erhöhen kann.

Danke,
mamue

RapidMax
12.07.03, 15:12
Original geschrieben von mamue
Ich gehe grundsätzlich von einiger Boshaftigkeit der user aus, also keine shell, bzw. /bin/false, Schreibschutz auf den PC (reborn/Wächter-karten) und keine executables in den Homeverzeichnissen, - unter anderem.
Ich glaube, das verstanden zu haben. Mehr als 8 Zeichen kann ich denen nicht zumuten, die bisherigen 6 mit gemischter Schreibweise und Sonderzeichen kamen aber wie gesagt auch nicht gut an. Ich werde mir wohl überlegen, wie ich gefahrlos den Zeichenvorrat (,-.+#!"%&/()=? vielleicht) erhöhen kann.

Damit hast du recht: Wenn das Passwort zu kompliziert ist, dann landet es auf einem Zettel neben dem Bildschirm. Es gibt ein Program pwgen (oder ähnlich) das besonders "merkbare" Passwörter generiert. Ich kombiniere die Ausgabe dieses Programms mit zusätzlichen Sonderzeichen, dann ist es ziemlich sicher. (z.B. pwgen 6 Zeichen generieren lassen, dann noch ein + und ein # in das Passwort einfügen).

Gruss, Andy

mamue
13.07.03, 14:30
Original geschrieben von RapidMax
Es gibt ein Program pwgen (oder ähnlich) das besonders "merkbare" Passwörter generiert.
Gruss, Andy
Ich habe mir erwähntes Programm in Java geschrieben, das mir eine ausreichende Anzahl von Passwörtern generiert. pwgen könnte ich genauso gut nehmen, aber der fleißige macht so etwas eben selber <:-)

mamue

Jasper
13.07.03, 17:00
Original geschrieben von mamue
Ich habe mir erwähntes Programm in Java geschrieben, das mir eine ausreichende Anzahl von Passwörtern generiert. pwgen könnte ich genauso gut nehmen, aber der fleißige macht so etwas eben selber <:-)


da nehm ich lieber apg und heb mir meinen grips für andere sachen auf :)

-j