Verschlüsselung ohne Passworteingabe / Passwortübermittlung

[OrallY]

Hallo.
Ich hatte vor einen kleine Chat zu schreiben, der eine verschlüsselte Verbindung benutzen soll, ohne dass beide Benutzer ein Passwort abklären, welches sie dann eingeben müssen.
Nun habe ich aber ein Problem: Um den empfangen Text wieder zu entschlüsseln, bräuchte der Empfänger ja auch das Passwort, mit dem es der "Sender" verschlüsselt hat. Wenn ich das Passwort in Klartext zuvor noch übermittle, brauch ich das ganze erst gar nicht zu verschlüsseln.
Natürlich kann ich auch das Passwort mit einem Alghorithmus verschlüsseln, der wiederum keinen Schlüssel benötig (z.B. ganz einfach XOR) oder einen stärkeren, aber einem statischen Passwort. Doch auch das könnte man blitzschnell durch disassemblierung entdeckt werden.
Ich hatte mir auch schon überlegt, ob ich Informationen wie IP und MAC usw. verwende, die dann zusammenwürfle und z.B. mit SHA verschlüssle. Doch hinter das System kommt man auch schnell und ist leicht nachzuahmen.

Wie könnte man dieses Problem lösen? Wie wird es bereits in Programmen wie z.B. Trillian gelöst?

[Phoenix]

Such mal nach Public Key Verfahren oder guck mal hier.

Der Trick ist, das Du einen asynchronen Algorithmus (z.B. RSA) verwendest. Die Algorithmen gibts soweit ich weiss auch in einer fertigen Implementierung bei Sourceforge.

Du erzeugst auf jeder Seite ein Schlüsselpaar (öffentlicher/public - key und privater/private key).

Der öffentliche Schlüssel wird nun an den Gegenüber verschickt. Diesen öffentlichen Schlüssel darf jeder abfangen, damit kann er nämlich nur Nachrichten VERschlüsseln.

Jede der Seiten verschlüsselt also die Nachrichten an den Gegenüber mit dessen öfentlichem Schlüssel. Zum ENTschlüsseln braucht nun das Programm seinen EIGENEN private Key. Dieser ist in der Lage, Nachrichten die mit dem dazugehörigen public Key verschlüsselt wurden wieder korrekt zu entschlüsseln.

Die Schlüsselpaare werden bei jeder Session neu erzeugt. Je nachdem wie sicher die Sache sein soll wählst Du halt entsprechend lange Schlüssel (40 bit sollten fast schon reichen, 128 sind imho schon zu stark - das dauert natürlich auch ne Weile das codieren und decodieren zu berechnen...).

Somit kannst Du sicher sein, daß wenn jemand dennoch den kompletten Traffic mitschneidet er für jede Session im Schnitt ein paar Jahre braucht, um nur die Kommunikation in eine Richtung zu lesen, für die andere Richtung gibts ja wieder einen anderen Schlüssel. Noch ein Vorteil von asynchronen Verfahren. :)

[anku]

Das mit dem Public Key ist schon mal ein guter Ansatz. In der Regel benutzt man Public Key Verfahren aber nur um einen sogenannten Session Key auszutauschen, welcher dann für das verschlüsseln der eigentlichen Daten benutzt wird.

Es kommen also zwei Verfahren zum Einsatz, einmal asymetrische Verschlüsselung (z.B. RSA) und einmal symetrische Verschlüsselung ( z.B. DES, AES). Die asymetrische Verschlüsselung ist recht zeitaufwändig und wird desshalb nur zum Schlüsselaustausch benutzt. (siehe z.B. SSL)

Für allgemeine Infos rund um Verschlüsselung und deren Knacken gibt es bei demCrypTool von der Deutschen Bank.

MfG

[negaH]

Zum sicheren Schlüsselaustausch in deinem Falle kommt meistens das Diffie Hellman Verfahren zum Einsatz. RSA wird dafür fast nie benutzt.

Gruß Hagen

[OrallY]

Danke für die Antworten. Werd das alles mal abchecken.
@negaH Was genau ist das Diffie Hellman Verfahren? Kennst du vielleicht schon eine Implementation in Delphi?

[negaH]

Das Diffie Hellman Verfahren dient zum sicheren Austausch von Geheimnissen über unsichere Kanäle. Diffie Hellman selber ist ein Professor :) Abgekürzt wird das Verfahren mit DH. Das gute an dem Verfahren ist es das es in jeder beliebigen Zahlendomain funktioniert die modulare Ringe zulässt. Also z.B. über normale Ganzahlen zu einem Primzahlring oder auch über GF(2^m) also Galois Fields in binären Feldern.

Wie arbeitet DH:
Zwei Parteien "Hagen" und "OrallY" wollen einen gemeinsammen sicheren Schlüssel erzeugen um damit im späteren Verlauf über eine öffentliche Leitung verschlüsselte Daten auszutauschen. Wichtig dabei ist es das dieser Schlüssel NICHT über die unsichere Leitung übertragen werden darf, d.h. der Schlüssel wird bei "Hagen" und "OrralY" erzeugt verlässt aber niemals die Computer von "Hagen" und "OrralY". Hier sieht man schon den Unterschied zu RSA.

Zitat:

1.) Hagen und OrallY haben sich auf zwei Zahlen geeinigt.
- große Primzahl (1024Bit) N, wobei (N-1)/2 ebenfalls prim ist, solche Primzahlen nennt man Sophie Germain Primzahlen
- Generator G, der modulo N primitiv ist, also auch Teilerfremd
- beide Zahlen können veröffentlicht werden, also auch über unsichere Leitungen übertragen werden

2.) Hagen wählt Zufallszahl S und sendet an OrallY den Wert X = G^S mod N.

3.) OrallY wählt Zufallszahl T und sendet an Hagen den Wert Y = G^T mod N.

4.) OrallY berechnet K = X^T mod N, wobei K das ausgetauschte Geheimnis ist.

5.) Hagen berechnet K' = Y^S mod N

K und K' == G^(S*T) mod N.

Man kann dieses Verfahren so abwandeln das Hagen z.B. sofort einen Schlüssel berechnet und damit auch eine Message verschlüsselt. Danach kann Hagen den Schlüsselaustausch und die verschl. Nachricht sofort an OrallY verschicken. OrallY wiederum kann den verwendeten Schlüssel erzeugen und die verschl. Message entschlüsseln. Eine Abart des DH Verfahrens das dies kann stammt von Hughes.

Beim DH Verfahren erkennt man schon zwei sehr Wichtige Dinge:
1.) alle sicherheitsrelevanten Paramter, also N und G sind öffentlich zugänglich und können verifiziert werden.
2.) alle Geheimnis tragenden Parameter, also S und T sind privat und einfache Zufallszahlen.

Beide Bedingungen treffen auf RSA eben nicht zu !

Zitat:

Kennst du vielleicht schon eine Implementation in Delphi?

Ja natürlich. Ich habe sogar schon 5 verschiedene Varianten selber programmiert. Allerdings mit meiner eigenen math. Library.



Gruß Hagen

[OrallY]

Wenn ich mal ganz doof fragen darf. Wie kann man eine 1024Bit große Primzahl erzeugen? Leben wir nicht in einer 32Bit Welt?

[Lillebrohr]

Guten Tag,

Muss ich das jetzt verstehen ?

du kannst auch eine 2048 bit große Primzahl erzeugen. Was du meinst sind die 32-bit Register. Oder ?


Die habe n aber nichts damit zu tuhen !

MfG

LB

[OrallY]

Nein, ich glaube das musst du nicht verstehen, da meine Frage aus meinem Unverständis heraus entstanden ist.
Kann mir bitte jemand erklären, was konkret eine 1024Bit große Zahl ist, da ich das offenbar irgendwie falsch verstehe... :?

//edit: Eine 1024Bit langer String besäße doch 128 Zeichen, oder? Irgendwie steh ich grad total aufm Schlauch und bin total verwirrt :roteyes:

[negaH]

Zitat:

Wenn ich mal ganz doof fragen darf. Wie kann man eine 1024Bit große Primzahl erzeugen? Leben wir nicht in einer 32Bit Welt?

Dazu benötigt man eine mathematsiche Bibliothek die mit solchen Zahlen rechnen kann. Mein eigene Entwicklung geht nun über 3 Jahre hinweg, und hatte zum Erfolg das sie zB. 1 Million Dezimalstellen von Pi als dritt schnellste PC Software der Welt errechnen kann.

Jede 32 Bit Operation, wie Addition,Subtraktion,Multiplikation usw. kann verkettet werden um 64,96,128... Bit Zahlen zu berechnen. Dafür haben die Konstrukteure der Chipsätze schon Sorge getragen.
D.h. statt nur 32Bit zu speichern, speichert man z.B. 32*32Bit hinereinander, also eine 1024 Bit Zahl. Alle Operationen werden nun auf 32Bit Operationen heruntergebrochen. Eventuelle Überläufe einer 32Bit Opration werden als Übertrag in die nächsthöhere 32 Bit Operation übernommen. Man kann sich das so vorstellen als wenn man 4 * 8Bit addieren wollte. Eine 32Bit Addition würde dann mit den 4 * 8 Bit's eines 32Bit Wertes das gleiche machen.

Hat man die Grundrechenoperationen einmal für beliebig große Zahlen programmiert, kann man nun die fehlenden mathematischen Algorithmen programmieren. Zum Erzeugen von "Primzahlen" benötigt man GCD() = Größter gemeinsammer Teiler, Modulare Inversionen per erweitertem GCD, die modulare Exponentation usw. Nun entwickelt man die Algorithmen zur "Primzahl" Erzeugung. Am häufigsten dürfte der Rabin Miller Test sein, der effizient aber nicht der optimalste Algo. ist. In meiner Library nutze ich einen "Strong-Lucas-Pseudo-Primzahl-Test" von Baillie-Selfridge-Wagstaff-Pomerance.
Man erzeugt also keine echten und eindeutigen Primzahlen, sondern sogenannte Strenge-Pseudo-Primzahlen. Die Wahrscheinlichkeit das eine so erzeugte 1024 Bit Zahl keine Primzahl ist, beträgt 1/2^1024. D.h. es kann durchaus vorkommen das eine solche "industrielle" Primzahl garkeine Primzahl ist. Zb. der Rabim Miller test lässt sogenannte Carmichel-Zahlen durch. D.h. der RM Test sagt bei diesen Zahlen das es eine Primzahl ist obwohl es keine ist. Der BSWP Test erkennt solche Carmichelzahlen. Seit Erfindung dieses Testes, 10 Jahren alt, hat man noch keine einzigste Nicht-Primzahl gefunden die diesen Test als Primzahl besteht. Man vermutet das die erste dieser Zahlen weit über 10.000 Bits groß sein muß. Promerance, einer der Professoren die dieses Verfahren analysierten, hat ein Preisgeld von 1.000 Dollar ausgesetzt für denjenigen der die erste solche Zahl findet. Bis heute hat er die Scheine noch :)


Gruß Hagen

[Lillebrohr]

Guten Tag,

also extra für dich:

1 byte sind 4 bits.
1024 bits sind dann 256 bytes.

Ein Zeichen sind 2 Bytes.

Das bedeutet: 1024 Bits sind 128 Zeichen.

Verstanden ?

[OrallY]

Da du an diesem Projekt schon 3 Jahre sitzt, nehme ich an, dass du mir kein bisschen von deinem Code abzugeben bereit bist, richtig? :mrgreen:.
Ich bräuchte aber einen Algo zum DH-Verfahren und mich würds bizeln, einen selber zu schreiben. Nur hakts dann eben an den Primzahlen. Scheint ja um einiges komplizierter zu sein, als ich geglaubt habe.

@Lillebrohr Ich war zurecht verwirrt, wie die Erklärung von negaH zeigt (schonmal an dieser Stelle: Vielen Dank für deine Bemühungen, negaH :mrgreen:). Hast du schonmal versucht mit einer Zahl in Delphi zu rechnen, die 128 Stellen hat? :wink:

[Illuminator-23-5]

zwischendurch 'ne frage:

Zitat:

große Primzahl (1024Bit) N, wobei (N-1)/2 ebenfalls prim ist, solche Primzahlen nennt man Sophie Germain Primzahlen

wenn 'ne zahl durch 2 teilbar is, isse nicht mehr prim, oder? müsst n/2-1 heißen, oder?

[negaH]

Zitat:

Da du an diesem Projekt schon 3 Jahre sitzt, nehme ich an, dass du mir kein bisschen von deinem Code abzugeben bereit bist, richtig? .

Tja, was ich machen kann ist das ich dir die Library zusende. Allerdings nicht vollständig in Sourcen, und ohne das Recht sie in kommerziellen Anwendungen benutzen zu dürfen.

Es gibt eine ganze Reihe schon fertiger Bibliotheken, allerdings nur wenige für Delphi:
- HIT, Huge Integer Tools von Marcel Martin war die beste Shareware in diesem Bereich für Delphi. Allerdings hat Marcel sein HIT vom Markt gezogen, da er zu viel Ärger mit Amerikanischen Firmen bekommen hat die behaupteten er habe Patente verletzt !
- FGInt, Fast Gigantic Integers, liegt als Source vor mit beschränkter Freewarelizens. Im Gegensatz zum Namen ist FGInt eher ineffizient und umständlich.
- IInteger, meine Library dürfte die meines Wissens nach die effizienteste Delphi Bibliothek sein. Nicht nur effizient in der Performance sondern auch in der Benutzbarkeit und dem Funktionsumfang.
- StreamSec II, von Hendrick Hellström, ist ein kommerzielles und preiswertes Produkt eines Schweden. Hendrick hat viele meiner Algorithem aus dem Delphi Encryption Compendium übernommen und sie zu einem eindrucksvollen Stück Software ausgebaut. In dieser Library findet man bestimmt auch das Diffie Hellman Verfahren. Das einzigartige an StreamSec II ist die absolute Unterstützung von Standardverfahren, wie ASN.1, PKCS usw. Allerdings sind seine Implementationen der math. Verfahren durchschnittlich 10-50 mal langsammer als meine. Ok, FGInt ist in vielen Operationen über 500 mal ineffizienter.
Hendrick selber ist ein sehr guter Ansprechpartner in Sachen Kryptographie. Marcel, ein Franzose, wiederum interessiert sich hauptsächlich für mathematsiche Probleme und ist ein hervoragender Mathematiker (ich kenne keinen besseren der auch programmieren kann). Die Leute von FGInt sind experimentelle Studenten.
- TurboPower, hat noch einige OpenSource Implementationen. Deren Qualität scheint aber nicht besonders zu sein. Ich habe sie nur überflogen.

Nur Marcel's und mein Primzahlerzeugungs Algorithmus benutzen den modernen BSWP Test. In fact Marcel hat bei meiner Umsetzung entscheidenden Einfluß gehabt.

Auf C Schiene gibts die meisten Implementationen:
- GMP, ist die bestoptimierteste Grundlage in dieser Richtung. Reicht aber auch nur als Grundlage. GMP selber ist in den meisten Teilen die effizientest Bibliothek, allerdings wird sie in entscheidenden Teilen von Miracl und meinen IIntegern überboten. GMP enthält keinerlei Crypto-Stuff.
- Miracl, ist von Micheal Scott. Das besondere an Miracl ist deren Polynomarithmetik. Sie enthält auch DH.
- HFloat, ist eine Libraray die große Fließkommazahlen unterstützt, ?.Arndt ist der Programmierer
- Cryptix, ist eine JAVA Enginge für Cryptostuff

Naja, es gibt noch viele mehr. So insgesamt habe ich wohl 30-40 solcher Libararies getestet und analysiert.

Gruß Hagen

[negaH]

Zitat:

wenn 'ne zahl durch 2 teilbar is, isse nicht mehr prim, oder? müsst n/2-1 heißen, oder?

Nein, sondern wie ich es geschrieben habe (N -1) / 2, das ist ein Unterschied.

Gruß Hagen

[OrallY]

Es wäre klasse, wenn du mir die Library zuschicken könntest ([e-mail]).
Vielen vielen Dank!

[negaH]

Welche Delphi Version ?

[Illuminator-23-5]

Zitat:

Zitat von negaH

(N -1) / 2

entweder sie is durch 2 teilbar, oder es kommt kein int raus - eine primzahl ist ein integer! (soweit ich weiß!)

[OrallY]

Delphi 7 Enterprise

[negaH]

Zitat:

entweder sie is durch 2 teilbar, oder es kommt kein int raus - eine primzahl ist ein integer! (soweit ich weiß!)

Ja und ? ist doch alles richtig mit (N -1) / 2. Wenn N ungerade ist so ist (N -1) gerade und somit durch 2 teilbar.
Bei N / 2 -1, würde X.5 rauskommen plus -1 würde eine Rundung erfordern. Da bei Ganzzahlen dies implizit runtergerundet wird käme es zum falschen Ergebnis, um 1 kleiner als gewünscht.

Gruß Hagen

[anku]

Zitat:

Zitat von Lillebrohr

Guten Tag,

also extra für dich:

1 byte sind 4 bits.
1024 bits sind dann 256 bytes.

Ein Zeichen sind 2 Bytes.

Das bedeutet: 1024 Bits sind 128 Zeichen.

Verstanden ?

autsch :)

1 byte ergibt 8 bit
1024 sind 128 Bytes

Ein Zeichen sind 1 Byte :)

mfg

*lach*

[moin339]

Moin!

Zitat:

Zitat von negaH

Zum sicheren Schlüsselaustausch in deinem Falle kommt meistens das Diffie Hellman Verfahren zum Einsatz. RSA wird dafür fast nie benutzt.

Da RSA anscheinend ja weitaus einfacher ist: Wo ist der Vorteil von dem Diffie Hellman Verfahren?

ciao, moin339

[anku]

Wieso ist das RSA Verfahren einfacher?
Dort benötigt man, einfach gesagt, ähnlich viele Werte. Du brauchst
1. 2 große Primzahlen ( p und q, beide geheim!) für den PublicKey ( n)
2. e als öffentlicher Exponent
3. d als privaten Exponenten

Der Aufwand dürfte also in etwa gleich sein. Nur kann hier nicht von aussen geprüft werden ob p und q tatsächlich groß genug und damit der öffentliche Schlüssel auch "wirklich sicher" ist.

mfg

[negaH]

Zitat:

Da RSA anscheinend ja weitaus einfacher ist: Wo ist der Vorteil von dem Diffie Hellman Verfahren?

- RSA ist nicht einfacher
- RSA benötigt mindestens zwei Primzahlen, DH nur eine
- da RSA zwei Primzahlen benötigt isr deren Erzeugung schneller als die eine bei DH. Bei RSA benötigt man für 1024Bit Sicherheit zwei 512Bit Zahlen, bei DH dementsprechend eine 1024 Bit Primzahl. Allerdings, für jeden RSA Schlüssel muß man 2 solcher Primzahlen erzeugen. Beim DH Verfahren spricht überhauptnichts dagegen das ALLE eine einmalig berechnete 1024 Bit Primzahl gemeinsamm benutzen. Dies wäre sogar von enormen Vorteil. Keine Neu-Berechnungen, Verifizierbarkeit durch echte aber sehr aufwendige Primzahltests, keine separate Verteilung mehr und somit Einsparung von Übertragungbandweite.
- die beiden RSA Primzahlen sind Bestandteil des privaten Schlüssels, somit stellen sie gleichermaßen die Sicherheit von RSA und dessen Unsicherheit dar. Eine böswillge Implementation des RSA Verfahrens ermöglicht dem Bösswilligen die enorm schnelle Wiederherstellung des Privaten Schlüssels aus dem öffentlichen Schlüssel. Somit ist RSA als unsicher einzustufen wenn man die Sourcen der RSA implementierung nicht hat.
- RSA arbeitet mit dem Faktorizationsproblem, DH dagegen mit dem Problem des Logarithmus
- RSA benötig mehr modulare Exponentationen, und ist somit langsammer
- die sicherheitsrelevanten Parameter beim RSA sind Bestandteil des privaten Schlüssels und somit nicht verifizierbar, beim DH sind sie verifizierbar
- RSA ist kein Randomisiertes Verfahren, im Gegensatz zu DH. Beim DH wird für jeden Schlüsselaustausch auf BEIDEN Seiten eine neue Zufallszahl erzeugt, was zu Folge hat das der gemeinsam berechnete Schlüssel zufällig ist und aus ZWEI unabhänigen Zufallsquelle erzeugt wurde. Somit kann wenn Hagen bescheisst OrallY denoch guten Zufall beisteuern.
- das eigentliche Schlüsselaustasuchverfahren basiert auf komplett anderen math. logischen Erfordernissen. DH wurde als Schlüsselaustausch Verfahren konzipiert und RSA als verschlüsselungsverfahren. Man sollte niemals einen speziell entwickelten Algorithmus für andere Aufgaben mißbrauchen wenn es für die anderen Aufgaben ebenfalls speziell entwickelte Verfahren gibt.

Gruß Hagen

[Lillebrohr]

Guten Tag,

anku:

hehe, upps da hab ich wohl was verwechselt.

:dancer2:

MfG

LB

[negaH]

Der Berechnungsaufwand ist höher beim RSA. Beim DH wird die große Primzahl nur eimalig berechnet und es entstehen 4 Modulare Exponentationen die sich auf 2 Rechner evteilen. Bei einer RSA Verschlüsselung müssen erstmal die Schlüssel erzeugt werden. Um dies genauso Protokolllogisch richtig zu machen müsste man also für jeden Schlüsselaustausch ein neues RSA Schlüsselpaar erzeugen. Also 2 Primzahlen, mehrere GCD Berechnungen, und eine Exponentation + eine Exponentation (identisch mit DH) um zu verschlüsseln und mindestens eine Exponentation bei der Entschlüsselung. Diese eine letzte Exponentation kann ca. 4 mal beschleunigen, aber das wars dann schon. Somit ist DH erstmal logisch sicherer auf Grund seines Protokolles und zweites effizienter als RSA, da die Erzeugung der Primzahl einmalig ist.

Es geht aber garnicht darum was effizienter ist sondern nur darum was sicherheitstechnisch das bessere ist. Und für den Schlüsselaustausch ist DH konzipiert.

Mit einer guten math. Bibliothek dürften die Berechnungen beim Schlüsselaustausch unter einer Millisekunde liegen. In fact meine Library schafft 1000-1500 solcher Exponentationen pro Sekunde.
Die Erzeugung der 1024 Bit Primzahl sollte innerhalb von 1-4 Sekunden erledigt sein. Damit stellt sich die Rechentechnische Effizienzfrage nicht mehr.

Gruß Hagen