Drei-Pass-Protokolle

Dieser Text wird eines der überarbeiteten Kapitel des Handbuchs zum Informationsschutz der Abteilung für Funktechnik und Steuerungssysteme sowie aus diesem Schulungscode der Abteilung für Informationsschutz des MIPT (GU) sein. Das vollständige Tutorial ist auf github verfügbar (siehe auch Release- Entwürfe ). Auf Habrir habe ich vor, neue "große" Stücke auszulegen, um erstens nützliche Kommentare und Beobachtungen zu sammeln und zweitens der Community mehr Überblicksmaterial zu nützlichen und interessanten Themen zu geben.

Vorherige Themen:

• Kryptografische Protokolle: Definitionen, Datensätze, Eigenschaften, Klassifizierung, Angriffe
• Schlüsselverteilungsprotokolle für symmetrische Chiffren

Wenn es einen Kommunikationskanal zwischen Alice und Bob gibt, auf den ein Angreifer nicht zugreifen kann (wenn also nur das passive Kryptoanalysemodell anwendbar ist), können Sie die zuvor in der Kryptografie mit öffentlichen Schlüsseln verwendeten Ideen auch ohne vorläufigen Austausch von geheimen Schlüsseln oder anderen Informationen verwenden. Nachdem Adi Shamir 1978 die RSA beschrieben hatte, schlug er 1980 die Verwendung von Kryptosystemen vor, die auf kommutativen Operationen beruhen, um Informationen zu übertragen, ohne zuvor geheime Schlüssel auszutauschen. Wenn wir annehmen, dass die übertragenen Informationen ein geheimer Sitzungsschlüssel sind, der von einer der Parteien generiert wurde, erhalten wir im Allgemeinen das folgende Protokoll mit drei Durchläufen.

Vorbemerkung:

• Alice und Bob sind über einen ungesicherten Kommunikationskanal verbunden, der von einem Angreifer abgehört (aber nicht geändert) werden kann.
• Jede Seite verfügt über ein Paar öffentlicher und privater Schlüssel $$$K_A$ , $$$k_A$ , $$$K_B$ , $$$k_B$ dementsprechend.
• Die Parteien haben die kommutative Verschlüsselungsfunktion ausgewählt und verwendet:
  

  $$

  $$\ begin {array} {lll} D_ {A} \ left (E_ {A} \ left (X \ right) \ right) = X & \ forall X, \ left \ {K_A, k_a \ right \}; \\ E_ {A} \ left (E_ {B} \ left (X \ right) \ right) = E_B \ left (E_A \ left (X \ right) \ right) & \ forall ~ K_A, K_B, X. \ end {array}$$

Das Protokoll besteht aus drei Durchläufen mit der Übertragung von Nachrichten (daher der Name) und einem letzten Durchlauf, bei dem Bob den Schlüssel erhält.

1. Alice wählt einen neuen Sitzungsschlüssel $$$K$
   
   $$$Alice \ to \ left \ {E_A \ left (K \ right) \ right \} \ to Bob$
2. $$$Bob \ to \ left \ {E_B \ left (E_A \ left (K \ right) \ right) \ right \} \ to Alice$
3. Alice, unter Verwendung der Kommutativität der Verschlüsselungsfunktion,
   

   $$

   $$D_A \ left (E_B \ left (E_A \ left (K \ right) \ right) \ right) = D_A \ left (E_A \ left (E_B \ left (K \ right) \ right) \ right) = E_B \ left (K \ rechts).$$
   $$$Alice \ to \ left \ {E_B \ left (K \ right) \ right \} \ to Bob$
4. Bob entschlüsselt $$$D_B \ left (E_B \ left (K \ right) \ right) = K$

Als Ergebnis erhalten die Parteien einen gemeinsamen geheimen Schlüssel. $$$K$ .

Ein gemeinsamer Nachteil all solcher Protokolle ist die fehlende Authentifizierung der Parteien. Natürlich ist dies im Fall eines passiven Kryptoanalytikers nicht erforderlich, aber im wirklichen Leben müssen Sie immer noch alle möglichen Modelle (einschließlich eines aktiven Kryptoanalytikers) berücksichtigen und Protokolle verwenden, die die gegenseitige Authentifizierung der Parteien beinhalten. Im Gegensatz zum Diffie-Hellman-Schema wird der neue Schlüssel vom Initiator der Sitzung ausgewählt, sodass der Initiator den zweiten Teilnehmer nicht mit guten Absichten zur Verwendung des veralteten Sitzungsschlüssels zwingen kann.

In Bezug auf die Sicherheitseigenschaften erklären dann alle Vertreter dieser Protokollklasse nur die Schlüsselauthentifizierung (G7). Im Gegensatz zum Diffie-Hellman-Schema erfordern Drei-Pass-Protokolle nicht die Auswahl neuer „Hauptschlüssel“ für jede Protokollsitzung, weshalb weder die perfekte direkte Geheimhaltung (G9) noch die Bildung neuer Schlüssel (G10) garantiert werden kann.

Triviale Option

Geben wir ein Beispiel für ein Protokoll, das auf der XOR-Funktion basiert (bitweise Addition Modulo 2). Obwohl diese Funktion als Grundlage für die Erstellung von Systemen mit perfekter kryptografischer Stärke verwendet werden kann, ist dies für ein Protokoll mit drei Durchläufen eine schlechte Wahl.

Vor dem Starten des Protokolls haben beide Parteien ihre geheimen Schlüssel. $$$K_A$ und $$$K_B$ Darstellung zufälliger binärer Sequenzen mit einer gleichmäßigen Verteilung der Zeichen. Die Verschlüsselungsfunktion ist definiert als $$$E_i (X) = X \ oplus K_i$ wo $$$X$ diese Nachricht auch $$$K_i$ - Geheimschlüssel. Offensichtlich:

$$

$$\ forall i, j, X: E_i \ left (E_j \ left (X \ right) \ right) = X \ oplus K_j \ oplus K_i = X \ oplus K_i \ oplus K_j = E_j \ left (E_i \ left (X \ right) \ right)$$

1. Alice wählt einen neuen Sitzungsschlüssel $$$K$
   
   $$$Alice \ to \ left \ {E_A \ left (K \ right) = K \ oplus K_A \ right \} \ to Bob$
2. $$$Bob \ to \ left \ {E_B \ left (E_A \ left (K \ right) \ right) = K \ oplus K_A \ oplus K_B \ right \} \ to Alice$
3. Alice, unter Verwendung der Kommutativität der Verschlüsselungsfunktion,
   

   $$

   $$D_A \ left (E_B \ left (E_A \ left (K \ right) \ right) = K \ oplus K_A \ oplus K_B \ oplus K_A = K \ oplus K_B = E_B \ left (K \ right).$$
   $$$Alice \ to \ left \ {E_B \ left (K \ right) = K \ oplus K_B \ right \} \ to Bob$
4. Bob entschlüsselt $$$D_B \ left (E_B \ left (K \ right) \ right) = K \ oplus K_B \ oplus K_B = K$

Am Ende der Protokollsitzung kennen Alice und Bob den gemeinsamen Sitzungsschlüssel $$$K$ .

Die vorgeschlagene Wahl der kommutativen Verschlüsselungsfunktion zur Geheimhaltung ist erfolglos, da es Situationen gibt, in denen ein Kryptoanalytiker den Schlüssel bestimmen kann $$$K$ . Angenommen, ein Kryptoanalytiker hat alle drei Nachrichten abgefangen:

$$

$$K \ oplus K_A, ~~ K \ oplus K_A \ oplus K_B, ~~ K \ oplus K_B.$$

Modulo 2 Addition aller drei Meldungen ergibt den Schlüssel $$$K$ . Daher wird ein solches Verschlüsselungssystem nicht verwendet.

Jetzt präsentieren wir das Protokoll für die zuverlässige Übertragung des geheimen Schlüssels, basierend auf der exponentiellen (kommutativen) Verschlüsselungsfunktion. Die Stabilität dieses Protokolls hängt mit der Schwierigkeit der Aufgabe zusammen, den diskreten Logarithmus für bekannte Werte zu berechnen $$$y, g, p$ finden $$$x$ aus der Gleichung $$$y = g ^ x \ bmod p$ .

Shamirs Keyless-Protokoll

Die Parteien einigen sich vorläufig auf eine große Spitze $$$p \ sim 2 ^ {1024}$ . Jede der Parteien wählt einen geheimen Schlüssel. $$$a$ und $$$b$ . Diese Schlüssel sind kleiner und gegenseitig einfach. $$$p-1$ . Auch die Parteien bereiteten sich nach einer besonderen Anzahl vor $$$a '$ und $$$b '$ Damit können sie eine mit ihrem Schlüssel verschlüsselte Nachricht entschlüsseln:

$$

$$\ begin {array} {l} a '= a {-1} \ mod (p-1), \\ a \ times a' = 1 \ mod (p-1), \\ \ forall X: (X ^ a) ^ {a '} = X. \\ \ end {array}$$

Der letzte Ausdruck ist wahr durch die Folgerung aus Fermats kleinem Theorem \ index {theorem! Die Farm ist klein. Ver- und Entschlüsselungsvorgänge sind wie folgt definiert:

$$

$$\ begin {array} {lll} \ forall M <p: & C = E (M) = M ^ {a} & \ mod p, \\ & D (C) = C ^ {a '} & \ mod p, \\ & D_A (E_A (M)) = M ^ {aa '} = M & \ mod p. \\ \ end {array}$$

1. Alice wählt einen neuen Sitzungsschlüssel $$$K <p$
   
   $$$Alice \ to \ left \ {E_A \ left (K \ right) = K ^ a \ bmod p \ right \} \ to Bob$
2. $$$Bob \ nach \ links \ {E_B \ links (E_A \ links (K \ rechts) \ rechts) = K ^ {ab} \ bmod p \ rechts \} \ nach Alice$
3. Alice, unter Verwendung der Kommutativität der Verschlüsselungsfunktion,
   

   $$

   $$D_A \ left (E_B \ left (E_A \ left (K \ right) \ right) \ right) = K ^ {aba '} = K ^ b = E_B \ left (K \ right) \ mod p.$$
   
   $$$Alice \ to \ left \ {E_B \ left (K \ right) = K ^ b \ right \} \ to Bob$
4. Bob entschlüsselt $$$D_B \ left (E_B \ left (K \ right) \ right) = K ^ {bb '} \ bmod p = K$

Am Ende der Protokollsitzung kennen Alice und Bob den gemeinsamen Sitzungsschlüssel $$$K$ .

Angenommen, ein Kryptoanalytiker hat drei Nachrichten abgefangen:

$$

$$\ begin {array} {l} y_1 = K ^ a \ bmod p, \\ y_2 = K ^ {ab} \ bmod p, \\ y_3 = K ^ b \ bmod p. \\ \ end {array}$$

Den Schlüssel finden $$$K$ muss ein Kryptoanalytiker ein System dieser drei Gleichungen lösen, das einen sehr großen Rechenaufwand aufweist, der aus praktischer Sicht nicht akzeptabel ist, wenn alle drei $$$a, b, ab$ ziemlich groß. Nimm das an $$$a$ (oder $$$b$ ) ist nicht genug. Dann Berechnung aufeinanderfolgender Abschlüsse $$$y_3$ (oder $$$y_1$ ) gefunden werden $$$a$ (oder $$$b$ ) und vergleicht das Ergebnis mit $$$y_2$ . Wissen $$$a$ leicht zu finden $$$a ^ {- 1} \ bmod (p-1)$ und $$$K = (y_1) ^ {a ^ {- 1}} \ bmod p$ .

Massey-Omura-Kryptosystem

Im Jahr 1982 meldeten James Massey und Jim Omura ein Patent an (James Massey, Jim K. Omura) und verbesserten (ihrer Meinung nach) das schlüssellose Protokoll von Shamir. Als Verschlüsselungsoperation statt Exponentiation in einer multiplikativen Gruppe $$$\ mathbb {Z} _p ^ *$ Sie schlugen vor, Exponentiation im Galois-Feld zu verwenden $$$\ mathbb {GF} {2 ^ n}$ . Geheimschlüssel jeder Party (für Alice - $$$a$ ) müssen die Bedingungen erfüllen:

$$

$$\ begin {array} {l} ein \ in \ mathbb {GF} {2 ^ n}, \\ gfd \ left (a, x ^ {n-1} + x ^ {n-2} + ... + x + 1 \ right) = 1. \\ \ end {array}$$

Ansonsten sieht das Protokoll ähnlich aus.

Nachwort

Der Autor ist für sachliche und sonstige Kommentare zum Text dankbar.