[HaBo]

zzador

Anzeige

Hallo alle miteinander,

Ich bin Student und im Rahmen eines Kurses über IT-Sicherheit an meiner Schule (Fachhochschule) wurde mein Interesse an asymmetrischen Verschlüsselungen geweckt. Auch, wenn der Versuch auf dem Gebiet etwas Neues zu erschaffen etwas naiv wirkte, habe ich mich dennoch nicht abbringen lassen und denke auch, dass ich damit Erfolg hatte (So lange mir hier keiner das Gegenteil beweist ). Mein Professor hatte diese Verfahren bereits begutachtet und keinen Grund gefunden warum dieses Verfahren NICHT sicher sein sollte. Das besondere an dem Verfahren ist, dass es OHNE komplexe Mathematik auskommt (tatsächlich ist die einzige Operation der XOR-Operator). Da ich mir auf der einen Seite natürlich nicht davon ausgehen kann, dass das Verfahren sicher ist, nur weil mein Professor es sich angeschaut hat, und ich auf der anderen Seite auch auf Unterstützung aus der Industrie angewiesen bin, habe ich mich entschieden, dass Verfahren so einfach wie möglich publik zu machen. Das folgende Diagramm sollte eigentlich keine Fragen offen lassen, jedoch werde ich natürlich versuchen jede aufkommende Frage so schnell es geht zu beantworten. Die im Diagramm verwendeten Matrizen sowie die Anzahl der "Untersummen" (Subsets) sind für das Beispiel der Übersichtlichkeit halber natürlich klein gehalten...Die Höhe und Breite der beiden Matrizen sollten bei min. 1024x256 liegen und die Anzahl der Untersummen sollte aufgrund der Fehlerminimierung bei mindestens 10 Summen a 8 Bit liegen.

Diagramm:http://www.bilder-hochladen.net/file...-c4ca-png.html

killgenerals

Ich hab zwar nur ganz kurz und grob drüber geschaut, aber trotzdem wage ich einfach zu fragen: Bei der Entschlüsselung siehst du dir einfach nur die Parität der verschlüsselten Worte an, oder? Irgendwie begreife ich den Sinn der Verschlüsselung als solche gerade nicht, aber ich habe mir das, wie gesagt, nicht gründlich genug angesehen.

Eigentlich schreibe ich nur um das hier unterzubringen: Wenn es deine Idee ist, und die Idee neu und praktikabel sein sollte: findest du nicht, dass du irgendwo deinen Namen dazuschreiben solltest um sicher zu gehen, dass dir das niemand wegnimmt, bevor du dir sicher genug bist und es .... patentieren (lässt man Kryptographieverfahren patentieren?) lässt?

Darkslide

Ja man kann Verfahren patentieren lassen (Siehe Anklage gegen PGP Autor, der ohne Erlaubnis RSA implementiert hat).

Hab mir das Verfahren auch nur flüchtig angeschaut aber das ganze Verfahren auf dem Bild ist irgendwie verwirrend (oder ich bin einfach zu blöd). Was genau ist der public key?Was genau ist der private key?Warum wird bei der Verschlüsselung L1, L2 und L4 genommen und das nächste mal L2, L3 und L5? Mehr Informationen wären wirklich hilfreich. Aber vom allgemeinen Aufbau sieht das Verfahren irgendwie nicht wirklich sicher aus.

zzador

Okay, damit das ganze Verfahren etwas einfacher zu verstehen ist habe hier ein kleines Dokument (PDF) von mir beigelegt, in dem ich unter Anderem auch auf die Angriffsmöglichkeiten eingehe. Das PDF sollte keinesfalls als offizielle Publizierung sondern als kurze Erklärung angesehen werden.

Gruß,
Marc

Dokument: Netload Serious Filehosting - Netload

Darkslide

Nur mal als kurze Bemerkung:

Du gehst sicher davon aus, dass dein Verfahren den Vorteil gegenüber anderen Verfahren hat, dass es bedeutend schneller ver-und entschlüsseln kann, da ja nur XOR benutzt wird, oder irre ich da?

Du hast aber folgendes Problem:

Gehen wir davon aus, dass das Verfahren sicher ist und du empfehlst 1024 Bit Sequenzlänge. Da Bob jedes Bit einzeln verschlüsselt, hast du bei dem Verfahren einen unglaublich hohen Overhead (1 Bit -> 1024 Bit). Willst du also einen 128 Bit AES Key verschlüsseln, so musst du 16 Kbyte übertragen. Eine Verschlüsselung von langen Nachrichten ist daher mit deinem Verfahren vollkommen unsinnig... und für den Autausch von Schlüsseln für symmetrische Verfahren kann ich DHKE benutzen ohne Probleme mit Rechenaufwand zu bekommen.

zzador

In erster Linie betone ich die Tatsache, dass mein Verfahren NUR den XOR-Operator verwendet und daher bedeutend einfacher ist (keine komplexe Mathematik). Außerdem ist es dadurch auch BEDEUTEND einfacher in Hardware zu implementieren (ggf. sogar ohne MC).

Was deinen Einwand bezüglich des Overheads betrifft: Eine Asymmetrische Verschlüsselung kommt NIEMALS ohne Aufblähen des Chiffretextes aus. Selbst RSA erzeugt längere Cyphertext-Nachrichten im vergleich zum Klartext (und DHKE erzeugt ebenfalls grössere Werte als der eigentliche Schlüssel). Natürlich erzeugt mein Verfahren im Gegensatz zu RSA grössere Ciphertext-Chiffrate. Aufgrund der Tatsache, dass die Daten-Bandbreite von Übetragungen heute jedoch sehr schnell wächst (exponentiell) und mein Verfahren wie bereits erwähnt per Hardware (ohne MC) realisierbar wäre (daher auch sehr schnell auszuführen), sehe ich keinen Grund, warum es sinnlos sein sollte.

Tsjuder

Sieht interessant aus. Werds mir wenn ich am PC bin mal genauer angucken.

Der signifikante Overhead ist mir aber auch aufgefallen. Wenn du für 1 Bit die komplette Länge von 1024 Bit brauchst...also 1 Bit wird auf 128 Byte gestaucht.

Darkslide

Die Implementierung in Hardware ist denke ich nicht so das große Thema aber der Rechenaufwand stellt bei asymmetrischen Verfahren ein Problem dar. Deshalb werden diese auch hauptsächlich zusammen mit symmetrischen Verfahren verwendet um einen Schlüsselaustausch zu realisieren oder für Signaturen. Dort besteht wie gesagt kein Problem mit dem Rechenaufwand wodurch der Geschwindigkeitsvorteil deines Verfahrens irgendwie verpufft. Und AES und 3DES erreichen ausreichend hohe Geschwindigkeiten in rechenleistungsbegrenzter (tolles Wort) Hardware wie Bankkarten etc.

Natürlich steigt die Übertragungsgeschwindigkeit...aber um 10 Mbyte Daten zu verschlüsseln soll man 10 Gbyte an Daten übertragen...man muss schon realitätsnah bleiben....

Ich will dein Verfahren hier keineswegs schlecht reden...aber du wolltest von uns Feedback haben und in diesen Punkten sehe ich nunmal ein Problem an deinem Verfahren.

//edit: Zudem gibt es auch vermehrt symmetrische Verfahren die extremen Wert auf leichte Implementierung und schneller Ver - und Entschlüsselung legen (z.B. PRESENT).

killgenerals

Nein, neinm Geschwindigkeitsprobleme dürfte das Verfahren nur in der Software und über die durchsatzrate machen, da es Hardwareseitig kaum etwas einfacheres als ein XOR-Gatter gibt... da kämen zwar noch einige Gatter dazu, aber trotzdem bleibt es sehr einfach ... hardwareseitig unglaublich einfach und daher auch billig zu implementieren - und hardwarealgorithmen sind bekanntermaßen wesentlich schneller...

zzador

Okay...gut bei 4 MB Daten sollte mein Verfahren dann natürlich nur zum Austausch eines Schlüssels (AES, 3DES etc.) genutzt werden. Nichtsdestotrotz bleibt das Verfahren damit dennoch einfacher als Diffie-Hellman-Key-Exchange.

Darkslide

"It is possible to realize the cipher with as few as approximatley 1000 gate equivalences, where the encryption of one 64-Bit plaintext requires 547 clock cycles. A fuly pipelined implementation of PRESENT with 31 encryption stages achives a throughput of 64 bit per cycle, which can be translated into encryption throughputs of more than 50 Gbit/s"

Quelle: Understanding Cryptography

//edit: Abgesehen davon braucht man keine unglaublich hohen Verschlüsselungsgeschwindigkeiten in solcher Hardware, da dort keine Massen an Daten verschlüsselt werden müssen.

Elderan

Hallo,
die Ausdehnung des Textes stellt wie erwähnt ein großes Problem dar, da Datenübertragung (egal ob in den RAM, auf die Festplatte oder per Netzwerk) im Vergleich zur CPU extrem langsam ist.
Ebenso dürfte der Algorithmus wohl nicht ganz so schnell sein bei heutigen Software-Implementierungen, da das feststellen ob die Untersummen 0 oder 1 ergeben nur recht imperformant gelöst werden kann.

Aber der Algorithmus an sich ist auch gegen einen Chosen-Ciphertext-Angriff anfällig.

Angenommen Bob möchte etwas an Alice senden und nutzt dazu ein hybrides System. Die Daten werden per AES verschlüsselt, der symmetrische Sitzungsschlüssel wird mit deinem Verfahren verschlüsselt und an Alice gesendet. Alice entschlüsselt den Sitzungsschlüssel und nutzt diesen dann fortlaufend für ihre Antworten an Bob. Ein normales System wie Alice und Bob sicher über eine unsichere Leitung kommunizieren könnten.

Wenn Bob nun den Geheimtext '000...000' (128 mal 1024 nullen für einen 128 Bit Key) sendet, so haben alle Untersummen gerade Parität und Alice würde als Sitzungsschlüssel '111...111' entschlüssel.

Wenn Bob nun '100...0' sendet, dann gibt es zwei Fälle: Entweder die 0. Stelle ist in einer Untersumme, dann würde der entschlüsselte Sitzungsschlüssel von Alice '0111...1' sein, oder die 0. Stelle ist in keiner Untersumme, dann wäre der Sitzungsschlüssel weiterhin '111...1'. Da Alice diesen nutzt um eine Antwort/Bestätigung an Bob zu senden, muss Bob nur checken ob '011...1' oder '111...1' von Alice genutzt wurde zur Verschlüsselung ihrer Antwort.
Dies kann Bob nun fortführen, indem er nun '010...0', '0010...0' usw. an Alice sendet, sie das entschlüsselt und den Sitzungsschlüssel extrahiert.
Damit bekommt Bob alle Stellen, die Teil einer Untersumme sind.

Um die einzelnen Untersummen nun exakt zu bestimmen, geht Bob wie folgt vor:
Angenommen die 0. Stelle ist in einer Untersumme, der Geheimtext '100...0' würde damit zum Sitzungsschlüssel '011...1' führen.
Bob sendet nun '110...0', '1010..0', '10010...0' usw. an Alice. Wenn nun das 0. Bit und das z.B. 2. Bit in der gleichen Untersumme sind, würde '1010...0' wieder den Sitzungsschlüssel '111...1' ergeben. Wenn das 0. und das 2. Bit nicht in der gleichen Untersumme sind, würde '011...1' als Sitzungsschlüssel rauskommen.



Damit kann Bob in relativ wenig Schritten den privaten Schlüssel von Alice knacken. Die Anzahl der gewählten Ciphertexte dürfte denke ich kleiner als 10 000 sein (grob überschlagen), bei den vorgeschlagenen Parametern.


Damit ist dein System leider unsicher für den praktischen Gebrauch.

zzador

Hallo Elderan,

Erstmal vielen Dank, dass Du dir die Mühe gemacht hast Dir das Verfahren näher anzusehen. Ich bin sehr überrascht über Deine Äußerung, habe jedoch Probleme Deiner Begründung zu folgen. Um diese besser verstehen zu können, gestatte ich mir, sie hier noch einmal aufzuführen. Betrachtet wird der folgeden Fall:

Mein Verfahren wird zum Austausch eines 128 Bit-Schlüssels für ein Symmetrisches Verfahren verwendet. Das Vorgehen sieht dabei wie folgt aus:

1. Alice generiert mit meinem Verfahren den öffentlichen Schlüssel (die 2 Matrizen) und schickt diesen an Bob.

2. Bob generiert einen 128 Bit Schlüssel für die AES-Verschlüsselung, verschlüsselt diesen Bit für Bit mit meinem Verfahren und sendet das Ergebnis (einen 128x1024 Bitstrom bestehend aus zufälligen Bits) zurück an Alice.

3. Alice entschlüsselt den 128 Bit Schlüssel mithilfe ihrer Kenntnisse über die Positionen der Paritäten.

4. Beide kommunizieren nun NUR noch mithilfe des symmetrischen Verfahrens (AES) und die Sicherheit der Kommunikation beruht jetzt nur noch auf der Sicherheit von AES und der Schwierigkeit für Eve die Paritäten in einer der beiden Matrizen des öffentlichen Schlüssels zu finden.

Basierend auf dem, was Du geschrieben hast, gehst Du nun davon aus, dass Bob einen AES-Schlüssel bestehend aus NULLen erzeugt und diesen an Alice zurück sendet...auch wenn ein AES-Schlüssel NUR aus NULLen möglich ist, so sollte doch selbst ein blutiger Anfänger erkennen, dass man einen solchen Schlüssel unter keinen Umständen für eine sichere Verbindung vereinbaren sollte.

Sollte Bob dennoch auf seinen 128 bit NULL-Schlüssel bestehen, so wird es jedoch EXTREM unwahrscheinlich sein, dass die beiden Matrizen 128x1024 Nullen generieren, da über das Verfahren ja ein Random-Oracle realisiert wird, welches einen zufälligen Bitstrom erzeugt auch für Bitsequenzen, die aus gleichen Bits bestehen.

Was den Punkt deiner schrittweisen Suche nach den Untersummen/Paritäten angeht, so kann ich mich auch hier Deinem Einwand nicht anschliessen. Warum sollte Alice mithilfe ihres selbst erzeugten öffentlichen Schlüssel etwas an Bob senden? Bob weiß überhaupt nicht wo die Paritäten sind und könnte die Antwort/Bestätigung überhaupt nicht entschlüsseln. Eine mögliche Bestätigung wäre, dass auch Bob einen eigenen öffentlichen Schlüssel generiert und Alice dann diesen benutzt um den AES-Schlüssel erneut zu verschlüsseln und zu Bob zurück zu senden...so könnten beide sicher gehen, den gleichen Schlüssel zu haben und mögliche Übertragungsfehler ausschliessen.

All das hilft Eve allerdings recht wenig. Sie hätte nun 2 öffentliche Schlüssel bestehend jeweils aus 2 sehr grossen Matrizen und einen Datenstrom, der mithilfe von AES verschlüsselt worden ist...der AES Schlüssel liegt jedoch in 2 Datenströmen mit jeweils 128x1024 Bit versteckt, die am Anfang jeweils 1mal ausgetauscht worden sind.

Deine Einwände erscheinen mir daher recht mager, allerdings möchte ich auch nicht ausschließen, dass ich hier etwas nicht ganz verstanden habe. Falls Du mit deiner Post auf etwas anderes bestimmtes hinweisen wolltest, so möchte ich Dich bitten, etwas präziser zu werden. Nochmal vielen Dank für Deine Mühe.

Gruß,
Marc

Elderan

Hallo,
wie ein hybrides System funktioniert brauchst du mir nicht zu erklären, keine Angst

Also nehmen wir das Protokoll das du beschrieben hast und angenommen Bob ist ein Angreifer. Ich habe ausschließlich einen Angriff auf dein System beschrieben, nicht auf AES.

Alice erhält einen 128x1024 Bit Datensatz von Bob, der den verschlüsselten Sitzungsschlüssel enthält. Mittels der Paritätsprüfung extrahiert Alice daraus nun den Sitzungsschlüssel, den Bob angeblich generiert hat und verwendet dann den Sitzungsschlüssel für die weitere Kommunikation.

Anstatt das Bob nun einen zufälligen Sitzungsschlüssel generiert, diesen ordnungsgemäß verschlüsselt mittels der beiden Matrizen und an Alice sendet, nutzt dieser stattdessen einen chosen-ciphertext-attack um an Alice privaten Schlüssel zu gelangen. Ein Chosen-Ciphertext-Angriff ist ein Angriff, bei dem der Angreifer den Ciphertext frei/beliebig auswählt, Alice diesen dann entschlüsselt und das Ergebnis dem Angreifer bekannt wird.

Bob sendet einen 128x1024 Bit langen Geheimtext, der nur aus '00...0' besteht an Alice. Alice denkt, dass dies der verschlüsselte Sitzungsschlüssel von Bob ist und nutzt ihren privaten Schlüssel, um daraus den vermeintlichen Sitzungsschlüssel von Bob zu extrahieren und diesen in der weiteren Kommunikation mit Bob zu nutzen. Alice hat überhaupt keine Möglichkeit zu überprüfen, ob Bob nun den Sitzungsschlüssel ordnungsgemäßg verschlüsselt hat oder ob der Geheimtext von ihm frei erfunden wurde.

Wenn Alice nun den 128x1024 Bitstrom '00...0' entschlüsselt, wird sie das 128 Bit lange '111..1' Ergebnis erhalten, denn jede Untersumme hat gerade Parität.

Im nächsten Schritt sendet Bob nun den 128x1024 langen Bitstrom '100..0' an Alice als seinen (angeblichen verschlüsselten) Sitzungsschlüssel (neue Kommunikation zwischen Alice und Bob). Falls das 0. Bit in einer Untersumme bei Alice vorkommt, wird Alice '011...1' (128 Bits) entschlüsselt. Falls nicht, wird sie '111...1' entschlüsseln.
Da wir annehmen, dass Alice diesen Schlüssel nutzt um Bob zu antworten, kann dieser sehr leicht überprüfen ob Alice nun '011...1' oder '111...1' entschlüsselt hat und damit ob das 0. Bit in einer Prüfsumme vorkommt.

Bob geht dann weiter vor wie beschrieben.

Ich hoffe nun ist es verständlicher was ich meine.

Ansonsten entschlüssel mal '000..0', '10...0', '010...0' usw. mit deinem System und betrachte die Ergebnisse. Du wirst entweder '11...1' oder '011..1' als Ergebnis bekommen, je nachdem ob das Bit mit der 1 in einer Untersumme war. Da Alice ja dieses Ergebnis dann nutzt um Bob verschlüsselt mittels AES zu antworten, muss dieser nur überprüfen welchen Schlüssel Alice für AES verwendet hat und damit weiß er, ob das Bit in einer Untersumme ist.




Off-Topic:
AES besitzt keine (bekannten) schwachen Schlüssel. D.h., ein Schlüssel nur bestehend aus nullen ist ebenso sicher wie jeder andere Schlüssel. Und erzeugt man den AES-Sitzungsschlüssel zufällig, ist ein Schlüssel bestehend aus lauter nullen genauso wahrscheinlich wie jeder andere Schlüssel.
Aber um AES geht es mir gar nicht.

zzador

Hallo Elderan,

Also hab ich mich bei deiner letzten Post doch nicht vertan. Du gehst tatsächlich davon aus, daß Bob versucht die Sicherheit seiner eigenen Sitzung mit Alice zu knacken. Das schien mir nur äusserst nutzlos, weshalb ich diese Interpretation deines Angriffs sofort wieder verworfen hatte. Warum Bob jetzt mehrmals einen AES-Sitzungsschlüssel schickt ist mir auch schleierhaft...die beiden Matrizen (Der öffentliche Schlüssel) werden für jede Sitzung NEU generiert. Und bei JEDER Sitzung wird nur ein einziges mal ein 128 Bit-Key mit meinem Verfahren verschlüsselt und an Alice gesendet. Du sprichst jedoch davon: und dann Der Sitzungsschlüssel wird allerdings nur einmal für die jeweilige Sitzung vereinbart und für jede neue Sitzung generiert Alice einen völlig neuen öffentlichen Schlüssel in dem die Paritäten komplett andere Positionen besitzen. Daher könnte Bob nur ein einziges mal versuchen mit seinem präparierten AES-Schlüssel etwas über den privaten Schlüssel heraus zu finden, da er zum senden eines weiteren AES-Schlüssels einen neue Sitzung erbitten müsste, in der Alice jedoch einen komplett neuen öffentlichen Schlüssel generiert. Somit stände Bob dann auch hier vor dem selben Problem wie am Anfang. Nebenbei gesagt ist mir immer noch nicht ganz klar, warum Bob die Sicherheit seiner eigenen Sitzung mit Alice gefährden sollte. Nur um Informationen über den öffentlichen Schlüssel zu bekommen, der eigens für seine Sitzung generiert wurde und auch nur dafür, dass er selbst seinen AES-Schlüssel sicher an Alice übermitteln kann. Klingt paradox!

Der Grund einer asymmetrischen Verschlüsselung ist es, einen Datentransfer zwischen Alice und Bob für Dritte (Eve) geheim zu halten, ohne das Alice und Bob sich vorher getroffen haben müssen und persönlich einen Schlüssel ausgetauscht haben. Man geht also davon aus, das die Leitung zwischen Alice und Bob von Eve überwacht wird. Eve darf daher keine Möglichkeit bekommen dieses Datenstrom irgendwie entschlüsseln zu können. Diese Voraussetzung wird bisher durch mein Verfahren erfüllt, weshalb ich mich auch dem letzten Satz deiner vorletzen Post nicht anschließen kann.

Falls Du mit Deinem "Evil"-Bob jetzt auf einen "Man-In-The-Middle"-Angriff aus warst, so muss dir doch klar sein, dass es kein Verfahren gibt, welches einem "Man-In-The-Middle"-Angriff zuverlässig stand hält. Selbst DHKE und RSA sind hier nutzlos.

Gruß,
Marc