Diffie-Hellman: Der Genius-Algorithmus hinter sicherer Netzwerkkommunikation

Beginnen wir mit einem kurzen Gedankenexperiment.

Sie haben ein Netzwerk von 3 Computern, die von Alice, Bob und Charlie verwendet werden. Alle 3 Teilnehmer können Nachrichten senden, jedoch nur so, dass alle anderen Clients, die mit dem Netzwerk verbunden sind, diese lesen können. Dies ist die einzig mögliche Kommunikationsform zwischen den Teilnehmern.

Wenn Alice eine Nachricht über die Kabel sendet, erhalten sowohl Bob als auch Charlie sie. Mit anderen Worten, Alice kann keine direkte Nachricht an Bob senden, ohne dass Charlie sie ebenfalls erhält.

Aber Alice möchte eine vertrauliche Nachricht an Bob senden und möchte nicht, dass Charlie sie lesen kann.

Scheint mit diesen strengen Regeln unmöglich, oder? Das Schöne daran, dass dieses Problem 1976 von Whitfield Diffie und Martin Hellman gelöst wurde.

Dies ist eine vereinfachte Version der realen Welt, aber wir haben das gleiche Problem, wenn wir über das größte Netzwerk kommunizieren, das jemals existiert hat.

Normalerweise sind Sie nicht direkt mit dem Internet verbunden, aber Sie sind Teil eines lokalen kleineren Netzwerks namens Ethernet.

Dieses kleinere Netzwerk kann verkabelt oder drahtlos (Wi-Fi) sein, aber das Basiskonzept bleibt bestehen. Wenn Sie ein Signal über das Netzwerk senden, kann dieses Signal von allen anderen Clients gelesen werden, die mit demselben Netzwerk verbunden sind.

Sobald Sie eine Nachricht mit Ihren Kreditkarteninformationen an den Server Ihrer Bank senden, erhalten alle anderen Clients im lokalen Netzwerk die Nachricht, einschließlich des Routers. Es wird dann an den eigentlichen Server der Bank weitergeleitet. Alle anderen Clients ignorieren die Nachricht.

Was aber, wenn sich im Netzwerk ein böswilliger Client befindet, der Ihre vertraulichen Nachrichten nicht ignoriert, sondern stattdessen liest? Wie ist es möglich, dass Sie noch Geld auf Ihrem Bankkonto haben?

Verschlüsselung

An diesem Punkt ist klar, dass wir eine Art Verschlüsselung verwenden müssen, um sicherzustellen, dass die Nachricht für Alice und Bob lesbar ist, für Charlie jedoch völliger Kauderwelsch.

Das Verschlüsseln von Informationen erfolgt durch einen Verschlüsselungsalgorithmus, der einen Schlüssel (z. B. eine Zeichenfolge) verwendet und einen verschlüsselten Wert namens Chiffretext zurückgibt. Der Chiffretext ist nur eine völlig zufällig aussehende Zeichenfolge.

Es ist wichtig, dass der verschlüsselte Wert (Chiffretext) nur mit dem Originalschlüssel entschlüsselt werden kann. Dies wird als Symmetric-Key-Algorithmus bezeichnet, da Sie zum Entschlüsseln der Nachricht denselben Schlüssel benötigen, mit dem sie verschlüsselt wurde. Es gibt auch Algorithmen mit asymmetrischen Schlüsseln, die wir derzeit jedoch nicht benötigen.

Um dies leichter zu verstehen, ist hier ein in JavaScript implementierter Dummy-Verschlüsselungsalgorithmus:

function encrypt(message, key) { return message.split("").map(character => { const characterAsciiCode = character.charCodeAt(0) return String.fromCharCode(characterAsciiCode+key.length) }).join(""); }

In dieser Funktion habe ich jedes Zeichen basierend auf der Länge des angegebenen Schlüssels einem anderen Zeichen zugeordnet.

Jedes Zeichen hat eine ganzzahlige Darstellung, die als ASCII-Code bezeichnet wird. Es gibt ein Wörterbuch, das alle Zeichen mit seinem Code enthält und als ASCII-Tabelle bezeichnet wird. Also haben wir diese Ganzzahl um die Länge des Schlüssels erhöht:

Das Entschlüsseln des Chiffretextes ist ziemlich ähnlich. Anstatt zu addieren, subtrahieren wir die Schlüssellänge von jedem Zeichen im Chiffretext, sodass wir die ursprüngliche Nachricht zurückerhalten.

function decrypt(cipher, key) { return cipher.split("").map(character => { const characterAsciiCode = character.charCodeAt(0) return String.fromCharCode(characterAsciiCode-key.length) }).join(""); }

Schließlich ist hier die Dummy-Verschlüsselung in Aktion:

const message = "Hi Bob, here is a confidential message!"; const key = "password"; const cipher = encrypt(message, key); console.log("Encrypted message:", cipher); // Encrypted message: Pq(Jwj4(pmzm(q{(i(kwvnqlmv|qit(um{{iom) const decryptedMessage = decrypt(cipher, key); console.log("Decrypted message:", decryptedMessage); // Decrypted message: Hi Bob, here is a confidential message!

Wir haben ein gewisses Maß an Verschlüsselung auf die Nachricht angewendet, aber dieser Algorithmus war nur zu Demonstrationszwecken nützlich, um ein Gefühl dafür zu bekommen, wie sich Verschlüsselungsalgorithmen mit symmetrischen Schlüsseln verhalten.

Neben der schlechten Behandlung von Eckfällen und Parametertypen gibt es bei dieser Implementierung einige Probleme.

Zunächst kann jeder 8 Zeichen lange Schlüssel die Nachricht entschlüsseln, die mit dem Schlüssel "Passwort" verschlüsselt wurde. Wir möchten, dass ein Verschlüsselungsalgorithmus eine Nachricht nur entschlüsseln kann, wenn wir ihm denselben Schlüssel geben, mit dem die Nachricht verschlüsselt wurde. Ein Türschloss, das mit jedem anderen Schlüssel geöffnet werden kann, ist nicht so nützlich.

Zweitens ist die Logik zu einfach - jedes Zeichen wird in der ASCII-Tabelle um den gleichen Betrag verschoben, was zu vorhersehbar ist. Wir brauchen etwas Komplexeres, um es schwieriger zu machen, die Nachricht ohne Schlüssel herauszufinden.

Drittens gibt es keine minimale Schlüssellänge. Moderne Algorithmen arbeiten mit mindestens 128 Bit langen Schlüsseln (~ 16 Zeichen). Dies erhöht die Anzahl möglicher Schlüssel und damit die Sicherheit der Verschlüsselung erheblich.

Schließlich dauert das Ver- oder Entschlüsseln der Nachricht zu wenig. Dies ist ein Problem, da es nicht zu lange dauert, alle möglichen Schlüssel auszuprobieren und die verschlüsselte Nachricht zu knacken.

Dies geht Hand in Hand mit der Schlüssellänge: Ein Algorithmus ist sicher, wenn ich als Angreifer den Schlüssel finden möchte. Dann muss ich eine große Anzahl von Schlüsselkombinationen ausprobieren, und es dauert relativ lange, eine einzelne Kombination auszuprobieren.

Es gibt eine breite Palette symmetrischer Verschlüsselungsalgorithmen, die alle diese Ansprüche erfüllen und häufig zusammen verwendet werden, um für jede Situation ein gutes Verhältnis von Geschwindigkeit und Sicherheit zu finden.

Die beliebtesten Algorithmen mit symmetrischen Schlüsseln sind Twofish, Serpent, AES (Rijndael), Blowfish, CAST5, RC4, TDES und IDEA.

Wenn Sie mehr über Kryptographie im Allgemeinen erfahren möchten, lesen Sie diesen Vortrag.

Schlüsselaustausch

Es sieht so aus, als hätten wir den ursprünglichen Problembereich reduziert. Mit der Verschlüsselung können wir eine Nachricht erstellen, die für Parteien von Bedeutung ist, die zum Lesen der Informationen berechtigt sind, für andere jedoch nicht lesbar ist.

Wenn Alice eine vertrauliche Nachricht schreiben möchte, wählt sie einen Schlüssel aus, verschlüsselt ihre Nachricht damit und sendet den Chiffretext über die Kabel. Sowohl Bob als auch Charlie würden die verschlüsselte Nachricht erhalten, aber keiner von ihnen könnte sie ohne Alices Schlüssel interpretieren.

Die einzige Frage, die beantwortet werden muss, ist, wie Alice und Bob einen gemeinsamen Schlüssel finden können, indem sie einfach über das Netzwerk kommunizieren und Charlie daran hindern, denselben Schlüssel herauszufinden.

Wenn Alice ihren Schlüssel direkt über die Kabel sendet, würde Charlie ihn abfangen und in der Lage sein, alle Nachrichten von Alice zu entschlüsseln. Das ist also keine Lösung. Dies wird als Schlüsselaustauschproblem in der Informatik bezeichnet.

Diffie-Hellman-Schlüsselaustausch

Dieser coole Algorithmus bietet eine Möglichkeit, einen gemeinsamen Schlüssel zwischen zwei Personen so zu generieren, dass der Schlüssel durch Beobachtung der Kommunikation nicht gesehen werden kann.

Als ersten Schritt werden wir sagen, dass es eine riesige Primzahl gibt, die allen Teilnehmern bekannt ist, nämlich öffentliche Informationen. Wir nennen es "p" oder Modul .

There is also another public number called "g" or base,which is less than p.

Don't worry about how these numbers are generated. For the sake of simplicity let's just say Alice picks a very big prime number (p) and a number which is considerably less than p. She then sends them through the wires without any encryption, so all participants will know these numbers.

Example: To understand this through an example, we'll use small numbers. Let's say p=23 and g=5.

As a second step both Alice (a) and Bob (b) will pick a secret number, which they won't tell anybody, it's just locally living in their computers.

Example:Let's say Alice picked 4 (a=4), and Bob picked 3 (b=3).

As a next step, they will do some math on their secret numbers, they will calculate:

  1. the base (g) in the power of their secret number,
  2. and take the calculated number's modulo to p.
  3. Call the result A (for Alice) and B (for Bob).

Modulo is a simple mathematical statement, and we use it to find the remainder after dividing one number by another. Here is an example: 23 mod 4 = 3, because 23/4 is 5 and 3 remains.

Maybe it's easier to see all of this in code:

// base const g = 5; // modulus const p = 23; // Alice's randomly picked number const a = 4; // Alice's calculated value const A = Math.pow(g, a)%p; // Do the same for Bob const b = 3; const B = Math.pow(g, b)%p; console.log("Alice's calculated value (A):", A); // Alice's calculated value (A): 4 console.log("Bob's calculated value (B):", B); // Bob's calculated value (B): 10

Now both Alice and Bob will send their calculated values (A, B) through the network, so all participants will know them.

As a last step Alice and Bob will take each other's calculated values and do the following:

  1. Alice will take Bob's calculated value (B) in the power of his secret number (a),
  2. and calculate this number's modulo to p and will call the result s (secret).
  3. Bob will do the same but with Alice's calculated value (A), and his secret number (b).

At this point, they successfully generated a common secret (s), even if it's hard to see right now. We will explore this in more detail in a second.

In code:

// Alice calculate the common secret const secretOfAlice = Math.pow(B, a)%p; console.log("Alice's calculated secret:", secretOfAlice); // Alice's calculated secret: 18 // Bob will calculate const secretOfBob = Math.pow(A, b)%p; console.log("Bob's calculated secret:", secretOfBob); // Bob's calculated secret: 18

As you can see both Alice and Bob got the number 18, which they can use as a key to encrypt messages. It seems magic at this point, but it's just some math.

Let's see why they got the same number by splitting up the calculations into elementary pieces:

In the last step, we used a modulo arithmetic identity and its distributive properties to simplify nested modulo statements.

So Alice and Bob have the same key, but let's see what Charlie saw from all of this. We know that p and g are public numbers, available for everyone.

We also know that Alice and Bob sent their calculated values (A, B) through the network, so that can be also caught by Charlie.

Charlie knows almost all parameters of this equation, just a and b remain hidden. To stay with the example, if he knows that A is 4 and p is 23, g to the power of a can be 4, 27, 50, 73, ... and infinite other numbers which result in 4 in the modulo space.

He also knows that only the subset of these numbers are possible options because not all numbers are an exponent of 5 (g), but this is still an infinite number of options to try.

This doesn't seem too secure with small numbers. But at the beginning I said that p is a really large number, often 2000 or 4000 bits long. This makes it almost impossible to guess the value of a or b in the real world.

The common key Alice and Bob both possess only can be generated by knowing a or b, besides the information that traveled through the network.

If you're more visual, here is a great diagram shows this whole process by mixing buckets of paint instead of numbers.

Here p and g shared constants represented by the yellow "Common paint". Secret numbers of Alice and Bob (a, b) is "Secret colours", and "Common secret" is what we called s.

This is a great analogy because it's representing the irreversibility of the modulo operation. As mixed paints can't be unmixed to their original components, the result of a modulo operation can't be reversed.

Summary

Now the original problem can be solved by encrypting messages using a shared key, which was exchanged with the Diffie-Hellman algorithm.

With this Alice and Bob can communicate securely, and Charlie cannot read their messages even if he is part of the same network.

Thanks for reading this far! I hope you got some value from this post and understood some parts of this interesting communication flow.

If it was hard to follow the math of this explanation, here is a great video to help you understand the algorithm without math, from a higher level.

If you liked this post, you may want to follow me on Twitter to find some more exciting resources about programming and software development.