Ist diese einfache XOR-verschlüsselte Kommunikation absolut sicher?

23

Angenommen, Alice und Peter haben jeweils einen 4 GB USB-Flash-Speicherstick. Sie treffen und speichern auf beiden Sticks zwei Dateien mit den Namen alice_to_peter.key(2 GB) und peter_to_alice.key(2 GB), die zufällig erzeugte Bits enthalten. Sie treffen sich nie wieder, sondern kommunizieren elektronisch. Alice verwaltet auch eine Variable namens alice_pointerund Peter verwaltet eine Variable namens peter_pointer, die beide anfänglich auf Null gesetzt sind.

Wenn Alice eine Nachricht an Peter senden muss, tut sie Folgendes (wo nist das n-te Byte der Nachricht):

encrypted_message_to_peter[n] = message_to_peter[n] XOR alice_to_peter.key[alice_pointer + n]
encrypted_payload_to_peter = alice_pointer + encrypted_message_to_peter
alice_pointer += length(encrypted_message_to_peter)

(und für maximale Sicherheit kann der verwendete Teil des Schlüssels gelöscht werden)

Peter empfängt encrypted_payload_to_peter, liest, alice_pointerspeichert am Anfang der Nachricht und macht:

message_to_peter[n] = encrypted_message_to_peter[n] XOR alice_to_peter.key[alice_pointer + n]

Und für maximale Sicherheit löschen Sie nach dem Lesen der Nachricht auch den verwendeten Teil des Schlüssels. - BEARBEITEN: Tatsächlich verringert dieser Schritt mit diesem einfachen Algorithmus (ohne Integritätsprüfung und Authentifizierung) die Sicherheit, siehe Beitrag von Paulo Ebermann weiter unten.

Wenn Peter eine Nachricht an Alice senden muss, machen sie das Gegenteil, diesmal mit peter_to_alice.keyund peter_pointer.

Mit diesem einfachen Schema können sie jeden Tag für die nächsten 50 Jahre 2 GB / (50 * 365) = ~ 115 kB verschlüsselte Daten in beide Richtungen senden. Wenn sie mehr Daten zum Senden benötigen, könnten sie größere Schlüssel verwenden, zum Beispiel mit den heutigen 2 TB HDs (1 TB Schlüssel) wäre es möglich, 60 MB / Tag für die nächsten 50 Jahre auszutauschen! Das sind viele Daten in der Praxis. Mit der Komprimierung ist es beispielsweise mehr als eine Stunde Sprachkommunikation von hoher Qualität.

Es scheint mir, dass ein Angreifer ohne die Schlüssel keine Möglichkeit hat, die verschlüsselten Nachrichten zu lesen, denn selbst wenn er einen unendlich schnellen Computer hat, kann er mit brachialer Gewalt jede mögliche Nachricht unter die Lupe nehmen, aber dies ist eine astronomische Zahl der Nachrichten und der Angreifer weiß nicht, welche von ihnen die eigentliche Nachricht ist.

Habe ich recht? Ist dieses Kommunikationsschema wirklich absolut sicher? Und wenn es sicher ist, hat es einen eigenen Namen? XOR-Verschlüsselung ist bekannt, aber ich suche nach dem Namen dieser konkreten praktischen Anwendung mit großen Schlüsseln auf beiden Seiten? Ich erwarte demütig, dass diese Anwendung jemand vor mir erfunden hat. :-)

Hinweis: Wenn es absolut sicher ist, ist es erstaunlich, denn mit den heutigen kostengünstigen großen Speichergeräten wäre die sichere Kommunikation viel billiger als mit der teuren Quantenkryptografie, und dies hat die gleiche Sicherheit!

EDIT: Ich denke, dass dies in Zukunft praktischer sein wird, wenn die Speicherkosten sinken.Es kann die sichere Kommunikation für immer lösen.Heute haben Sie keine Gewissheit, ob jemand bereits ein Jahr später erfolgreich vorhandene Chiffren angreift und die oft teuren Implementierungen unsicher macht. In vielen Fällen, bevor die Kommunikation stattfindet, ist es an der Zeit, die Schlüssel zu generieren, wenn sich beide Seiten persönlich treffen. Ich denke, es ist perfekt für die militärische Kommunikation, zum Beispiel zwischen U-Booten, die HDs mit großen Schlüsseln haben können, und Militärzentralen, die HDs für jedes U-Boot haben können. Es könnte auch im Alltag praktisch sein, zum Beispiel Ihr Bankkonto zu kontrollieren, denn wenn Sie ein Konto erstellen, treffen Sie sich mit der Bank usw.

user3123061
quelle
4
Abgesehen von dem spezifischen Schema zum Koordinieren des zu verwendenden Teils des Schlüssels ist dies nur ein einmaliger Block . Bei näherer Betrachtung stellt sich jedoch heraus, dass es für 99% der Anwendungsfälle nicht wirklich nützlich ist.
10
Da es sich bei dieser Frage um die Stärke eines bestimmten Krypto-Algorithmus handelt, ist er möglicherweise besser für crypto.stackexchange.com geeignet . Um Ihre Frage dorthin zu verschieben, können Sie die Aufmerksamkeit des Moderators auf sich ziehen und eine Migration beantragen.
Bart van Ingen Schenau
12
OTPs wurden vor über einem Jahrhundert erfunden und wurden in beiden Weltkriegen als physische Blöcke aus Papier verwendet. ( en.wikipedia.org/wiki/One-time_pad ) Das Problem in der Kryptographie ist damals wie heute der Schlüsselaustausch.
Gort the Robot
6
Beachten Sie, dass Sie weiterhin das Problem der Generierung von genügend eindeutigen Schlüsseln für alle erwarteten Daten lösen müssen, bis sich die beiden Parteien wieder treffen, und dass die Schlüssel über einen GENUIN zufälligen Prozess generiert werden müssen - Pseudozufallszahlengeneratoren sind zunehmend anfällig für Analysen Sobald mehr Proben mit demselben PRNG verfügbar sind.
Keshlam
1
@keshlam. Die Erzeugung echter Quanten-Zufallszahlen wird immer billiger. Interessanter Artikel bei arxiv: Quantum Random Number Generation auf einem Mobiltelefon: arxiv.org/abs/1405.0435
user3123061

Antworten:

50

Ja, dies ist ein One-Time-Pad . Wenn das Schlüsselmaterial nie wiederverwendet wird, ist es theoretisch sicher.

Die Nachteile sind, dass Sie einen Schlüssel pro kommunizierendem Prinzipalpaar benötigen und eine sichere Methode zum Austauschen des Schlüsselmaterials vor der Kommunikation benötigen.

Vatine
quelle
52
Ich denke, es ist erwähnenswert, dass "theoretisch sicher" bedeutet, dass es sich mathematisch als unzerbrechlich erwiesen hat , vorausgesetzt, die Schlüssel sind wirklich zufällig und werden nicht wiederverwendet. Das ist so ziemlich die stärkste Garantie, die Sie in der Kryptografie erhalten können.
Michael Borgwardt
1
@MichaelBorgwardt riesiger Punkt da. In diesem Fall ist "theoretisch sicher" eigentlich besser als "praktisch sicher".
Mark
2
Beispiel: Ich habe einen 2-GB-Zufallsschlüssel, der zufällig 16 aufeinanderfolgende Bytes von 0 enthält.
Michael
@Michael Die Chancen dafür liegen bei 1 zu 10 ^ 27.
dieser
1
@Floris Meine "Berechnung": Ein Byte hat 256 mögliche Werte. Das ist einer von 256, bei dem alle Null sind. 256 ^ 16, um die Chance für 16 Bytes zu bekommen. Teilen Sie dann die Anzahl der Bytes in 2 GB durch diese Chance. Ich glaube, ich habe hier sowieso eine Division durch 16 verpasst (1024 * 1024 * 1024 * 2 * (1/16)) / (256 ^ 16). Ihr letzter Punkt macht diese Berechnung sowieso irrelevant.
dieser
32

Wie aus der Antwort von Vatine hervorgeht, handelt es sich bei Ihrem Algorithmus im Grunde genommen um ein One-Time-Pad.

Um jedoch einen Ihrer Notizen zu kommentieren:

Hinweis: Wenn es absolut sicher ist, dann ist es erstaunlich, denn mit den heutigen kostengünstigen großen Speichern ist es praktisch viel preiswerter und sicherer als die teure Quantenkryptographie und mit der gleichen Sicherheit!

Meine Antwort ist nein, es ist nicht erstaunlich. Der Teufel steckt immer im Detail und der Teufel hier im Schlüsselaustausch. Ihre Methode hängt von einem einwandfreien Schlüsselaustausch von Angesicht zu Angesicht ab. Ich kann es mir nicht leisten, James Bond jedes Mal, wenn ich etwas kaufen oder andere sichere Verbindungen haben möchte, mit einer 4-GB-Flash-Disk an jeden Händler im Internet zu schicken.

Und schließlich ist der XOR-Aspekt Ihres Algorithmus nicht wichtig. Eine einfache Ersetzungs-Chiffre ist mit einem OTP in Ordnung. Die Stärke des OTP ist, dass der Schlüssel niemals wiederverwendet wird und dass James Bond die Schlüssel für beide Parteien fehlerfrei austauscht (dh vorheriger sicherer Schlüsselaustausch).

Whatsisname
quelle
13
Das andere an einem OTP ist, dass der Schlüssel (mindestens) so lang ist wie die zu verschlüsselnde Nachricht und eine Zufallszahlenquelle von sehr hoher Qualität benötigt.
Donal Fellows
Viele Verschlüsselungsalgorithmen wandeln einen Schlüssel irgendwie in einen Datenstrom um, der nicht von zufälligen Daten zu unterscheiden ist, und verwenden diese Daten dann als einmaliges Pad. Aus der Sicht eines Angreifers gibt es keinen Unterschied zwischen Daten, die wirklich zufällig sind, und Daten, die nicht von zufälligen Daten unterschieden werden können (per Definition; wenn Sie einen Unterschied festgestellt haben, war dies nicht ununterscheidbar). Theoretisch ist dies also genauso sicher wie OTP . Wenn wir sagen, dass Daten nicht von echten Zufallsdaten zu unterscheiden sind, gibt es natürlich in der Regel eine Reihe von Einschränkungen. Diese Erklärung ist natürlich eine grobe Übervereinfachung.
Brian
21

Während das One-Time-Pad eine unbedingte (mathematisch nachgewiesene) Datenschutzgarantie gegen einen Angreifer bietet, der nur Nachrichten lesen kann, weist es einige Schwächen auf.

  • Ein abfangender Angreifer, der den Klartext richtig errät, kann den Chiffretext beliebig manipulieren (mit der gleichen Länge).

  • Wenn ein Angreifer eine Nachricht (oder einen Teil davon) einfügt oder löscht, sind die Zeiger von Alice und Bob nicht mehr synchron und jede zukünftige Kommunikation ist unterbrochen.

    Update: Dies setzt voraus, dass beide Parteien beide Zeiger verfolgen. Wenn Sie den aktuellen Zeigerwert senden, sind Sie anfällig für Two-Time-Pad-Angriffe (wenn Sie zulassen, dass derselbe Bereich von Schlüsseln mehrmals verwendet wird) oder für DOS-Angriffe (wenn Sie nicht den gleichen Bereich von Schlüsseln zulassen) mehrmals verwendet werden (z. B. durch Löschen).

Beide Probleme werden durch fehlende Integrität und fehlenden Authentifizierungsschutz verursacht - Sie haben eine perfekte Verschlüsselung, aber keinen MAC.

Fügen Sie Ihrem One-Time-Pad-Protokoll einen MAC hinzu, um es tatsächlich sicher zu machen. Jede Nachricht sollte eine "Prüfsumme" erhalten, die sicherstellt, dass sie tatsächlich vom vermeintlichen Absender gesendet und dazwischen nicht geändert wurde. Außerdem sollten Sie eine Sequenznummer senden, damit der Empfänger weiß, welcher Teil des Schlüssels verwendet werden soll, wenn eine vorherige Nachricht verloren gegangen ist (oder um die Nachricht abzulehnen, wenn sie dupliziert wurde) - schließen Sie dies in die Prüfsummenberechnung ein.

Hier würde ein gewöhnlicher MAC-Algorithmus funktionieren, aber ich nehme an, Sie möchten einen einmaligen Polynom-MAC verwenden, um die passende Sicherheit für Ihr One-Time-Pad zu erhalten. (Nehmen Sie den MAC-Schlüssel von den Bits vor oder nach Ihrem Verschlüsselungsschlüssel, dh verwenden Sie nicht einen Schlüssel für beide Ziele.)

Paŭlo Ebermann
quelle
Wenn ein Angreifer eine Nachricht (oder einen Teil davon) einfügt oder löscht, sind die Zeiger von Alice und Bob nicht mehr synchron und jede zukünftige Kommunikation ist unterbrochen. Zeiger sind unabhängig und müssen nicht synchronisiert sein, sodass die zukünftige Kommunikation nicht unterbrochen wird, wenn die Nachricht verloren geht (der tatsächliche Versatz des zum Verschlüsseln der Nachricht verwendeten Schlüssels wird mit dieser Nachricht gesendet). Aber Sie haben teilweise Recht: "Nicht synchron" ist ein Teil des Schlüssels auf der Empfangsseite, der nicht gelöscht wird, weil gelöschte Nachrichten nicht empfangen werden (der verwendete Teil wird mit der nächsten empfangenen Nachricht gelöscht).
user3123061
Aber Sie haben Recht. Präsentiert einfache Algorithmus Miss Integrität und Authentifizierung. Die praktische Umsetzung muss robuster sein.
user3123061
@ user3123061 Ich würde Integrität und Authentifizierung nicht einfach abschütteln, wenn ich Sie wäre. Die Technik des adaptiven ausgewählten Chiffretext-Angriffs nutzt einen fehlenden Integritätsschutz aus, um die Vertraulichkeit zu brechen . Ich würde sogar sagen, dass der klassische One-Time-Pad (den Sie neu erfunden haben) trotz seiner offensichtlichen mathematischen Solidität nur wegen dieses Angriffs absolut unsicher ist.
zwol
2
Adaptive Chiffretext-Angriffe sind eine ziemlich schlechte Wahl für Angriffe gegen von Menschen überprüfte OTPs. OOS wird bemerkt und Ihr Angreifer wird ziemlich schnell gestoßen. Nur wenn der Empfänger maschinell bearbeitet wird und eine Antwort liefert, ist dieser Angriff überhaupt von Vorteil.
Joshua
@Zack Es gibt viele Probleme mit OTPs, aber keines bedroht die Vertraulichkeit. Beachten Sie, dass selbst wenn Sie den Plantext + Schlüssel der vorherigen Nachricht genau erraten, die nächste Nachricht mit einem völlig neuen, unabhängigen Schlüssel (auch von beträchtlicher Größe) verschlüsselt wird. Es gibt nichts zu über mehrere Interaktionen anzupassen.
4

Eigentlich ist es nicht ganz sicher. Was Ihr Protokoll verliert, ist die LÄNGE der übermittelten Nachricht.

Wenn der Spion zum Beispiel weiß, dass Sie mit "Ja" oder "Nein" antworten und die Länge = 2 sehen, kann er daraus schließen, dass es "Nein" ist.

Es ist tatsächlich erstaunlich, wie viel nur aus bekannten Längen abgeleitet werden kann, wenn man den Kontext erraten kann.

w.pasman
quelle
3
Dies ist jedoch recht einfach zu beheben, da Sie die Nachricht mit zufälligem Junk auffüllen können. Die Nachrichtenlänge ist also ein Vielfaches einer festen Blockgröße - beispielsweise 256 Zeichen. Das würde eine einfache Ja-Nein-Analyse zunichte machen und den OTP schneller verbrauchen.
Peter Bagnall
In der Tat - da Sie in den nächsten 50 Jahren ~ 115 KB täglich senden können , können Sie davon ausgehen, dass jeder Block mindestens 20 KB groß ist, was bedeutet, dass die Länge nicht so wichtig ist.
Apnorton