Hinter den Kulissen der Verschlüsselung

Verschlüsselung nutzen wir täglich: Kaum mehr eine Webseite, Nachricht oder Mail nutzt nicht mindestens ein bisschen Verschlüsselung. Und trotzdem wissen viele nicht, wie sie funktioniert. Hier ein Blick hinter die Kulissen, mit ganz wenig Mathematik.

Aus dem Themengebiet der Verschlüsselung interessieren uns rund um die IT insbesondere drei Technologien: Symmetrische und asymmetrische Verschlüsselung, die beim Besuchen jeder HTTPS-Webseite zum Tragen kommen, sowie die sogenannte Homomorphe Verschlüsselung, in die viel Hoffnung für die Zukunft für die Cloud gesteckt wird.

Symmetrische Verschlüsselung

Die Lipizzaner: Schnell und bewährt

Symmetrische Verschlüsselungsmechanismen, auch als Symmetrisches Kyptosystem bekannt, ist seit über zwei Jahr­tau­sen­den dokumentiert und entsprechend gut erforscht. Hier trifft man auf hohe Geschwindigkeiten und es ist nicht mehr mit revolutionären Entwicklungen zu rechnen

Im einfachsten Fall, der links dargestellten Caesar-Chiffre, wird jeder Buchstabe beim Verschlüsseln (Encryption E) mit dem Buchstaben drei Positionen später im Alphabet verschlüsselt. Beim Entschlüsseln (Decryption D) wird die Operation umgekehrt.

Vor 2000 Jahren mag diese Idee bahnbrechend gewesen sein, heute ist sie trivial knackbar. Entsprechend kommen sicherere Verfahren zum Einsatz, heutzutage meist AES.

Auf modernen Prozessoren wird die Verschlüsselung und Entschlüsselung von Daten in Gigabytes pro Sekunde gemessen. Ein moderner Rechner, angeschlossen an eine Gigabit-Glasfaser, kann also problemlos seinen gesamten Netzwerkverkehr symmetrisch ver- und entschlüsseln. Dieser Mehraufwand kostet ihn dabei nur ein paar Prozent Rechenleistung.

Der Aufwand für symmetrische Verschlüsselung ist daher heute häufig vernachlässigbar. Die dahinter stehende Entwicklung hat dazu beigetragen, dass die Verschlüsselung des Netzwerkverkehrs wie beispielsweise bei HTTPS heute zum Standard geworden ist und auch Festplatten­ver­schlüsselung (Full Disk Encryption) immer beliebter wird.

Asymmetrische Verschlüsselung

Der Pferdedompteur: Organisiert und koordiniert

Symmetrische Kryptosysteme sind wahnsinnig schnell; der zur Ver- und Entschlüsselung benötigte Schlüssel ist aber derselbe, also „symmetrisch“.

Dies schränkt die Flexibilität ein und hat z.B. den Nachteil, dass man nicht sowas wie ein „Telefonbuch“ mit den Schlüsseln aller Nachrichtenempfänger veröffentlichen kann. Wenn Alice also eine Nachricht an Bob schicken möchte, könnte sie zwar Bobs Schlüssel im Telefonbuch nachschlagen und die Nachricht mit seinem Schlüssel verschlüsseln. Eine Bösewichtin, Eve, die obige Nachricht aufschnappt, könnte diese dank desselben Telefonbuchs sofort entschlüsseln.

Um den Eves dieser Welt die Arbeit zu erschweren, wurden in den 1970ern asymmetrische Kryptosysteme erfunden. Dabei wird für die Verschlüsselung ein anderer Schlüssel („öffentlicher Schlüssel“, public key) eingesetzt als für die Entschlüsselung („privater Schlüssel“, private key). Wenn nun der öffentliche Schlüssel im Telefonbuch veröffentlicht wird, beisst sich Mallory die Zähne aus, da er den privaten Schlüssel nicht kennt, den er zur Entschlüsselung aber bräuchte.

Das erste öffentlich bekannte asymmetrische Kryptosystem und auch eines der bekanntesten ist das RSA-Verfahren, benannt nach den Initialen der Entdecker.

Wer sich noch an das Potenzrechnen erinnern mag, weiss, dass man mit diesen Potenzen auch vielfältig rechnen kann, insbesondere ein- und ausklammern. Schauen wir uns das an einem Beispiel an, das genau diese Anwendung erläutert. (Wen die Mathematik nicht interessiert, kann sie auch überlesen.)

Unser Bösewicht heisst diesmal Mallory, weil er nicht nur wie Eve zuhören kann, sondern die Nachricht auf ihrem Weg von Alice zu Bob auch verändern kann (Man-in-the-Middle-Angriff). Per Zufall hat Mallory erfahren, dass ein spezifisches Chiffrat C den Betrag repräsentiert, der auf sein Konto überwiesen werden soll und dass dieses Chiffrat nach der obigen „Lehrbuchmethode“ erzeugt wurde. Er kennt auch den öffentlichen Schlüssel des Empfängers Bob. Er kennt aber nicht den genauen Betrag, findet aber, der doppelte Betrag sei seiner Cleverness definitiv angemessener. Wie verdoppelt Mallory nun diesen geheimen Betrag?

Mallory weiss, dass dieses bestehende Chiffrat C, wie im Kasten beschrieben, als M^e mod N berechnet wurde, wobei M eben der zu überweisende Betrag ist. Er möchte aber dieses Chiffrat C durch eine Ersatzchiffrat C‘ ersetzen, welches sich aus dem doppelten von M errechnet, also (2M)^e mod N. Durch Ausklammern erhalten wir (2M)^e mod N = 2^eM^emod N = (2^emod N)*(M^emod N).

Grob gesagt bedeutet das, dass wir ohne Probleme jede Nachricht an Bob mit (2^emod N) multiplizieren können und Bob nachher glaubt, der doppelte Wert sei in der Nachricht gewesen.

Diese sogenannte „Formbarkeit“ (malleability) ist — wie in diesem Beispiel — meist unerwünscht. Deshalb werden RSA-Nachrichten meist nicht so direkt und ungeschützt verschickt, sondern sie sind eingebettet in weitere Sicherheitsmassnahmen wie beispielsweise digitale Signaturen, mit denen Veränderungen bei der Übermittlung erkannt werden können.

Digitale Signatur

Etliche asymmetrische Kryptosysteme, so auch RSA, haben noch einen weiteren Trick im Köcher: Wenn man sie „falsch herum“ einsetzt, also die Verschlüsselung statt mit dem öffentlichen mit dem privaten Schlüssel durchführt, ist das Resultat eine digitale Signatur. Da sie den privaten Schlüssel voraussetzt, bestätigt sie den Besitz des privaten Schlüssels (und — wenn dieser Schlüssel mit einer Identität verknüpft ist — auch die Identität des Signierers.

Durch die zweite „falsche“ Kombination (Entschlüsselungsfunktion gepaart mit öffentlichem statt privatem Schlüssel) lässt sich die Signatur von jedem Überprüfen, der Zugriff auf das Telefonbuch hat.

(In der Praxis ist übrigens meist nicht die Verschlüsselung selbst das Komplizierte, sondern das sichere Führen und vertrauenswürdige Verteilen des „Telefonbuchs“, das sogenannte Schlüsselmanagement. Anders gesagt: Die Arbeitspferde zu koordinieren, das ist das Schwierige und die Hauptaufgabe des Dompteurs.)

Homomorphe Verschlüsselung

Der Schlangenmensch: Flexibel, aber langsam.

Die Daten einfach nur verschlüsselt auf dem Cloudlaufwerk liegen zu lassen, das ist—wie eingangs gesagt—Schnee von gestern. Clouddienste nutzen wir heute viel häufiger um auch Daten zu bearbeiten. Ach, wie schön wäre es doch, wenn wir die Vorteile von Cloud Computing sorglos geniessen könnten, ohne dass der Cloudprovider unsere Daten im Klartext sehen könnte.

Genau das verspricht die Homomorphe Verschlüsselung (homomorphic encryption): (Fast) beliebige Operationen auf den verschlüsselten Daten ausführen zu können, ohne sie zwischendurch entschlüsseln zu müssen.

Einen einfachen Fall von Homomorpher Verschlüsselung haben wir oben bei der RSA-Lohnverdopplung schon gesehen: Bei (ungesicherten) „Lehrbuch“-RSA können mit dem gleichen öffentlichen Schlüssel codierte Werte miteinander multipliziert werden, ohne dass sie entschlüsselt werden können oder dass man die Werte kennen muss. Leider lässt sich das nicht auf weitere Operationen (Addition, Vergleiche auf grösser/kleiner, …) erweitern.

Es wäre schön, wenn man verschiedene Operationen auf die verschlüsselten Daten anwenden könnte. Und natürlich auch, beliebige dieser Operationen in beliebiger Reihenfolge und Tiefe hintereinander anwenden zu können. Das sind die Eigenschaften von Voll-Homomorphen Verschlüsselungssystemen (Fully Homomorphic Encryption oder kurz FHE).

Beispiel-FHE

Hier einige Beispiele mit der beliebten Microsoft-SEAL-Bibliothek für FHE. Diese bietet drei verschiedene Kryptosysteme an, BFV, BGV und CKKS, die unterschiedliche Eigenschaften und damit Einsatzgebiete haben. Hier die Schlüsselgrössen und Beispielberechnungen für CKKS, welches sehr gerne für Machine Learning eingesetzt wird:

+---------------------------------------------------------+
| The following examples should be executed while reading |
| comments in associated files in native/examples/.       |
+---------------------------------------------------------+
| Examples                   | Source Files               |
+----------------------------+----------------------------+
| 1. BFV Basics              | 1_bfv_basics.cpp           |
| 2. Encoders                | 2_encoders.cpp             |
| 3. Levels                  | 3_levels.cpp               |
| 4. BGV Basics              | 4_bgv_basics.cpp           |
| 5. CKKS Basics             | 5_ckks_basics.cpp          |
| 6. Rotation                | 6_rotation.cpp             |
| 7. Serialization           | 7_serialization.cpp        |
| 8. Performance Test        | 8_performance.cpp          |
+----------------------------+----------------------------+
[    139 MB] Total allocation from the memory pool

> Run example (1 ~ 8) or exit (0): 7

+----------------------------------------+
|         Example: Serialization         |
+----------------------------------------+
Line 124 --> EncryptionParameters: wrote 81 bytes
Line 176 --> EncryptionParameters: data size upper bound (compr_mode_type::none): 129
             EncryptionParameters: data size upper bound (compression): 192
Line 204 --> EncryptionParameters: parms == parms2: true
Line 270 --> Serializable<RelinKeys>: wrote 309254 bytes
             RelinKeys wrote 620711 bytes
Line 314 --> Serializable<Ciphertext> (public-key): wrote 191722 bytes
             Serializable<Ciphertext> (seeded secret-key): wrote 95228 bytes
Line 378 --> Ciphertext (secret-key): wrote 117913 bytes
Line 407 --> Decrypt the loaded ciphertext
    + Expected result: (4096)

    [ 10.3500000, 10.3500000, 10.3500000, ..., 10.3500000, 10.3500000, 10.3500000 ]

    + Computed result ...... Correct.

    [ 10.3499969, 10.3499983, 10.3500004, ..., 10.3499974, 10.3500070, 10.3499935 ]

Line 453 --> Size written to stream: 63 bytes
             Size indicated in SEALHeader: 63 bytes

• Die verwendeten Schlüssel sind 310 bzw. 620 Kilobytes gross.
• 4096 Zahlen belegen nicht die üblichen rund 16 kByte, sondern rund 12 mal mehr (in einem Sondermodus mit reduzierten Möglichkeiten nur 6x so gross)
• Keine der als „korrekt“ bezeichneten Resultate stimmt vollständig mit den korrekten Resultat der Multiplikation 2.3*4.5 überein. (Was für den Anwendungszweck wahrscheinlich meist ausreicht.)

Geschwindigkeitstests findet man im Untermenü 8. Testen wir alle verfügbaren Systeme mit den Standardeinstellungen. Zuerst BFV:

+-------------------------------------------+
|         Example: Performance Test         |
+-------------------------------------------+

Select a scheme (and optionally poly_modulus_degree):
  1. BFV with default degrees
  2. BFV with a custom degree
  3. CKKS with default degrees
  4. CKKS with a custom degree
  5. BGV with default degrees
  6. BGV with a custom degree
  0. Back to main menu

> Run performance test (1 ~ 6) or go back (0): 1

+--------------------------------------------------------------------------+
|         BFV Performance Test with Degrees: 4096, 8192, and 16384         |
+--------------------------------------------------------------------------+
/
| Encryption parameters :
|   scheme: BFV
|   poly_modulus_degree: 4096
|   coeff_modulus size: 109 (36 + 36 + 37) bits
|   plain_modulus: 786433
\

Generating secret/public keys: Done
Generating relinearization keys: Done [1546 microseconds]
Generating Galois keys: Done [32339 microseconds]
Running tests .......... Done

Average batch: 45 microseconds
Average unbatch: 54 microseconds
Average encrypt: 989 microseconds
Average decrypt: 278 microseconds
Average add: 12 microseconds
Average multiply: 2698 microseconds
Average multiply plain: 433 microseconds
Average square: 1971 microseconds
Average relinearize: 593 microseconds
Average rotate rows one step: 600 microseconds
Average rotate rows random: 2185 microseconds
Average rotate columns: 585 microseconds
Average serialize ciphertext: 11 microseconds
Average compressed (ZLIB) serialize ciphertext: 10236 microseconds
Average compressed (Zstandard) serialize ciphertext: 1166 microseconds

[...]

• Eine einzelne Addition im schnellsten Modus dauert 12µs. In derselben Zeit macht derselbe Rechner einige 10’000 „normale“ Additionen. (Die langsamste Variante in den Tests ist nochmals 20x langsamer, 244µs.)
• Ein einzelne Multiplikation im schnellsten Modus dauert je nach Weiterverwendung 433 bis 2698µs. Derselbe Rechner schafft in derselben Zeit über eine Million „normale“ Multiplikationen. (Auch hier ist der langsamste der Beispieltests nochmals 20x langsamer.)

Bei CKKS und BGV lasse ich den Output weg. Die Erkenntnisse daraus in Kürze:

• BGV ist etwa gleich schnell wie BFV, die vollständige Multiplikation ist aber schneller: nur noch etwa doppelt so langsam wie die „nackte“ (plain) Multiplikation.
• Die Addition bei CKKS ist gleich schnell wie bei den BFV und BGV. Die Multiplikation braucht aber nur 4 bis 8 Mal so lange wie eine Addition, also „nur“ noch ein paar 100’000x langsamer als die „normale“ Multiplikation. (Diesen relativen Geschwindigkeitsvorteil gegenüber den anderen FHEs handeln wir uns mit den oben genannten Ungenauigkeiten eiin.)

Der Aufwand für Schlüsselerzeugung, -übertragung, Speicherplatz und Rechenaufwand ist also ein Vielfaches höher, für gewisse Operationen mehrere hunderttausend Mal. Dies wird sich sicher in den nächsten Jahren noch weiter verbessern. Trotzdem ist anzunehmen, dass FHE nicht als Allerweltslösung taugen wird sondern nur selektiv sinnvoll eingesetzt werden wird.