One-Time-Pad

Das One-Time-Pad ist ein symmetrisches Verschlüsselungsverfahren, das als informationstheoretisch sicher1) bewiesen ist. Diese Eigenschaft besagt, dass die Verschlüsselung - bei korrekter Verwendung - selbst mit unendlicher Rechenleistung nicht geknackt werden kann.

Verfahren

Die Verschlüsselung und Entschlüsselung mittels One-Time-Pad ist relativ simpel. Eine Klartext-Nachricht M wird über ein exklusives Oder mit einem Schlüssel K verknüpft und erzeugt so den verschlüsselten Ciphertext C. In Kurzschreibweise bedeutet das C = M ⊕ K.

Verschlüsselung

Nun wollen wir den Text „proggen.org“ (M) verschlüsseln. Den Schlüssel K dafür wählen wir dabei komplett zufällig, er muss nichtmals aus druckbaren Zeichen bestehen. Die Byte-Werte sind deshalb als hexadezimale Zahlen angegeben.

0 1 2 3 4 5 6 7 8 9 10
M (ASCII) p r o g g e n . o r g
M (Hex) 0x70 0x72 0x6f 0x67 0x67 0x65 0x6e 0x2e 0x6f 0x72 0x67
K 0x21 0xff 0x12 0x7c 0x00 0xa9 0x30 0x54 0xb3 0x96 0xbf
=
C 0x51 0x8d 0x7d 0x1b 0x67 0xcc 0x5e 0x7a 0xdc 0xe4 0xd8

Ohne den Schlüssel zu kennen, liefert der Ciphertext C keinerlei Informationen über die Klartext-Nachricht!

Entschlüsselung

Um den Text wieder zu entschlüsseln wird das Verfahren einfach auf den Kopf gestellt, also M = C ⊕ K.

0 1 2 3 4 5 6 7 8 9 10
C 0x51 0x8d 0x7d 0x1b 0x67 0xcc 0x5e 0x7a 0xdc 0xe4 0xd8
K 0x21 0xff 0x12 0x7c 0x00 0xa9 0x30 0x54 0xb3 0x96 0xbf
=
M (Hex) 0x70 0x72 0x6f 0x67 0x67 0x65 0x6e 0x2e 0x6f 0x72 0x67
M (ASCII) p r o g g e n . o r g

Nun können wir auch zeigen wieso ein Bruteforce-Angriff nicht möglich ist. Zu jeder möglichen Klartext-Nachricht gibt es nämlich einen Schlüssel der sie aus dem Ciphertext erzeugt. Nochmals obiges Beispiel, jedoch mit falschem Schlüssel:

0 1 2 3 4 5 6 7 8 9 10
C 0x51 0x8d 0x7d 0x1b 0x67 0xcc 0x5e 0x7a 0xdc 0xe4 0xd8
K 0x21 0xff 0x4d 0x7c 0x00 0xff 0x30 0x54 0xec 0x96 0xbf
=
M (Hex) 0x70 0x72 0x30 0x67 0x67 0x33 0x6e 0x2e 0x30 0x72 0x67
M (ASCII) p r 0 g g 3 n . 0 r g

Wir haben hier also eine plausible, teilweise sogar korrekte, aber trotzdem insgesamt falsche Nachricht entschlüsselt.


Hinweis:
Die allgemeine Definition des One-Time-Pads sieht eine zeichenweise Modulo-Addition von Klartext und Schlüssel innerhalb des Alphabets vor, ähnlich wie es bei der Cäsar-Chiffre der Fall ist. Da dies bei binären Daten aber genau einem exklusiven Oder entspricht, beschränken wir uns hier auf diesen Fall.

Bedingungen

Um tatsächlich als informationstheoretisch sicher zu gelten, werden folgende Bedingungen an den Schlüssel gestellt:

  • Kryptografisch sicher
  • Wird nur ein einziges Mal verwendet
  • Ist mindestens so lang wie die zu verschlüsselnden Daten

Sobald nur eine einzige dieser Bedingungen verletzt wird, geht diese Eigenschaft verloren und Entschlüsselungs-Angriffe sind möglich!

Hier kommen wir auch zum großen Problem des One-Time-Pads: Beide Parteien müssen den verwendeten Schlüssel kennen. Dessen Übertragung stellt daher vor allem bei großen Datenmengen ein ganz neues Problem dar. Deshalb spielt das One-Time-Pad in der Praxis auch eine relativ geringe Rolle.

Entschlüsselungs-Angriffe

Wird auch nur eine Bedingung des One-Time-Pads verletzt, entstehen verschiedene Angriffsmöglichkeiten den Klartext herauszufinden.

Pseudo-Zufallszahlen

Pseudo-Zufallszahlengeneratoren wechseln auf Basis eines Seeds ihren internen Zustand und produzieren aufgrund eines deterministischen Berechnungsverfahren „Zufallszahlen“. Kann man den internen Zustand des Zufallszahlengenerators zurückrechnen, können alle folgenden Zufallszahlen - und damit der restliche Schlüssel - ebenfalls deterministisch berechnet werden. Auch wenn die Zahl der möglichen Werte für den Seed theoretisch sehr groß ist, kann man diese in vielen Fällen stark einschränken.

Beispiel:
Geht man von einem 64-bit Unix-Timestamp als Seed aus, können die möglichen Werte von 264 (18.446.744.073.709.551.616) auf ca. 235 (31.536.000.000) eingeschränkt werden, sofern man das korrekte Jahr errät. Noch immer eine schwierige, jedoch lösbare Aufgabe für moderne Rechner.

Folgendes Programm nimmt den aktuellen Timestamp als Seed, um den per Kommandozeilenparameter übergebenen Text zu verschlüsseln und in hexadezimaler Form auszugeben:

// gcc -o otp_rand otp_rand.c -Wall -std=c99
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
 
int main( int argc, char *argv[] )
{
    if( argc != 2 )
    {
        printf("Usage: %s plaintext\n", argv[0] );
        return 1;
    }
 
    unsigned int seed = time( NULL );
    srand( seed );
    printf( "Seed: %u\n", seed );
    printf( "Ciphertext: " );
    for( int i = 0; argv[1][i] != '\0'; i++ )
        printf( "%02x", argv[1][i] ^ ( rand() & 0xff ) );
    printf( "\n" );
 
    return 0;
}

Nun werden wir versuchen einen mit diesem Programm verschlüsselten Text zu entschlüsseln. Dabei verwenden wir folgenden Aufruf als Eingabe:

$ ./otp_rand "Never use insecure random number generators!"
Seed: 1408487231
Ciphertext: 8132948028a5d6d49a3f3d0229531f6b2f113f50a36105c4e155b8dd984412b65d3eccb9bb3f1fa903a139e7

Um den Text zu entschlüsseln, muss mit einem angenommenen Seed der komplette Text erfolgreich entschlüsselt werden können. Der Text wird als erfolgreich entschlüsselt angesehen, wenn alle entschlüsselten Zeichen im Alphabet der Eingabenachrichten liegen. In diesem Beispiel wählen wir eine relativ lockere Bedingung, nämlich alle druckbaren Zeichen. Die Funktion isprint() erweist sich bei dieser Prüfung als sehr hilfreich.

// gcc -o otp_prngcrack otp_prngcrack.c -Wall -std=c99
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
 
int main( int argc, char *argv[] )
{
    if( argc != 4 )
    {
        printf("Usage: %s ciphertext beginTime endTime\n", argv[0] );
        return 1;
    }
 
    if( strlen( argv[1] ) % 2 != 0 )
    {
        printf( "Ciphertext has invalid length\n" );
        return 1;
    }
 
    const int length = strlen( argv[1] ) / 2;
    char decoded[length];
    for( int i = 0; i < length; i++ )
    {
        unsigned int byte;
        if( sscanf( argv[1] + 2 * i, "%02x", &byte ) != 1 )
        {
            printf( "Error parsing ciphertext\n" );
            return 1;
        }
        decoded[i] = byte & 0xff;
    }
 
    unsigned int beginTime, endTime;
    if( sscanf( argv[2], "%d", &beginTime ) != 1 )
    {
        printf( "Error parsing begin time\n" );
        return 1;
    }
    if( sscanf( argv[3], "%d", &endTime ) != 1 )
    {
        printf( "Error parsing end time\n" );
        return 1;
    }
    if( beginTime > endTime )
    {
        printf( "Begin time must not be greater than end time\n" );
        return 1;
    }
 
    for( unsigned int i = beginTime; i <= endTime; i++ )
    {
        int valid = 1;
        char decrypted[length + 1];
        decrypted[length] = '\0';
        srand( i );
        for( int j = 0; j < length; j++ )
        {
            char c = decoded[j] ^ ( rand() & 0xff );
            if( !isprint( c ) )
            {
                valid = 0;
                break;
            }
            decrypted[j] = c;
        }
        if( valid )
            printf( "[%d]: %s\n", i, decrypted );
    }
 
    return 0;
}

Die Parameter des Aufrufs sind einfach der bekannte Ciphertext, sowie Beginn- und End-Timestamp des vermuteten Seed-Jahres.
Wissen wir nun, dass der Text im Jahr 2014 verschlüsselt wurde, kann dieser mit dem entsprechenden Aufruf in kurzer Zeit entschlüsselt werden:

$ ./otp_prngcrack 8132948028a5d6d49a3f3d0229531f6b2f113f50a36105c4e155b8dd984412b65d3eccb9bb3f1fa903a139e7 1388534400 1420070399
[1408487231]: Never use insecure random number generators!



Moderne Programmiersprachen bieten oft Klassen oder Bibliotheken zur Generierung von kryptografisch sicheren Zufallszahlen, wie etwa random_device in C++11 oder java.security.SecureRandom in Java. Bei der Implementierung von sicherheitskritischen Anwendungen sollte man sich aber auf jeden Fall über die interne Funktionsweise des Generators informieren.

Key-Wiederverwendung für mehrere Nachrichten (n-Time-Pad)

Wird der gleiche Schlüssel mehrere (n) Male für verschiedene, voneinander unabhängige, Nachrichten verwendet, spricht man von einem n-Time-Pad. Nun stellen wir die Gleichungen für die Verschlüsselung von 2 Nachrichten mit dem selben Schlüssel auf:
C1 = M1 ⊕ K
C2 = M2 ⊕ K

Kombiniert man nun die beiden verschlüsselten Texte mit XOR:
C1 ⊕ C2
erhält man als Formel:
(M1 ⊕ K) ⊕ (M2 ⊕ K)
Da das exklusive Oder kommutativ ist, kann die Gleichung folgendermaßen umgeformt werden:
(K ⊕ K) ⊕ (M1 ⊕ M2)
Jede beliebige Zahl die über ein exklusives Oder mit sich selbst verbunden wird ergibt 0 (x ⊕ x = 0), daher:
(0) ⊕ (M1 ⊕ M2)
Nach kurzer Überlegung erkennt man auch, dass jede beliebige Zahl die über ein exklusives Oder mit 0 verbunden ist, wieder die gleiche Zahl ergibt (x ⊕ 0 = x), also bleibt:
M1 ⊕ M2

Der geheime Schlüssel ist komplett aus der Gleichung verschwunden!
Errät man nun einen Teil einer Klartext-Nachricht, kann durch ein weiteres exklusives Oder und den gleichen Rechenregeln wie zuvor die jeweils andere ebenfalls teilweise entschlüsselt werden:
(M1 ⊕ M2) ⊕ M1
Löst man obige Gleichung auf, bleibt die entschlüsselte Nachricht M2 übrig. Erhält man für M2 plausiblen Inhalt, weist dies auf einen korrekten Versuch hin. Hat man mehrere Nachrichten zur Entschlüsselung bzw. Validierung, erleichtert dies den Vorgang natürlich enorm.

Um das n-Time-Pad zu knacken geht man also folgendermaßen vor:

  • Ciphertexte über ein exklusives Oder miteinander verbinden
  • Inhalt der Nachrichten raten
  • Validierung über den berechneten Inhalt der jeweils anderen Nachrichten

Je größer die entschlüsselten Teile der Nachrichten, desto leichter fällt es natürlich auf den restlichen Inhalt zu schließen.

Tipp zum Erraten des Inhalts:
Bei komplett unbekannten Inhalt kann das Raten sehr mühsam sein. Abhilfe schaffen allgemeine Wörter wie z.B. „ und “ und „ oder “ bzw. in Englisch „ and “ und vor allem „ the “. Die Leerzeichen vor und nach den Wörtern sind beabsichtigt und liefern den Inhalt der anderen Nachrichten an diesen Stellen „gratis“ mit!

Frequenzanalyse

Bei genügend großen n kann auch eine Frequenzanalyse angewendet werden, bei der über die Häufigkeit der Hex-Bytes an einer Stelle und der Häufigkeit von Buchstaben in einer Sprache auf den Inhalt geschlossen wird.

Key-Wiederverwendung innerhalb einer Nachricht (Vigenère-Cipher)

Ist der zu verschlüsselnde Text länger als der Schlüssel selbst und wird der Schlüssel dann wieder von Beginn verwendet, degeneriert das One-Time-Pad zur Vigenère-Cipher mit all ihren Schwächen und praktisch den gleichen Angriffsmöglichkeiten wie das n-Time-Pad.

Fehlende Datenintegrität

Obige Angriffe zielen darauf ab die Klartext-Nachricht zu erhalten. Dies ist bei korrekter Verwendung des One-Time-Pads zwar unmöglich, allerdings kann die verschlüsselte Nachricht dennoch manipuliert werden.
Wie schon anfangs bei der Entschlüsselung mit falschem Schlüssel demonstriert, bietet das One-Time-Pad keinerlei Datenintegrität. Gelingt es einem Angreifer eine verschlüsselte Nachricht abzufangen, kann er sie verändern und an den ursprünglichen Empfänger weiterleiten, ohne den genauen Inhalt zu kennen.

Beispiel:
Wir stellen uns ein stark vereinfachtes Protokoll für Banküberweisungen vor, das lediglich aus den Namen von Absender und Empfänger, sowie den übermittelten Betrag besteht:

F:[Sender];T:[Empfänger];A:[Betrag]

Eine 1234€ Überweisung von Alice an Bob würde also folgendermaßen aussehen:

F:Alice;T:Bob;A:1234

Bevor der Datensatz an die Bank geschickt wird, verknüpft der Absender ihn mit einem mit der Bank vereinbarten Schlüssel:

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
M (ASCII) F : A l i c e ; T : B o b ; A : 1 2 3 4
M (Hex) 0x46 0x3a 0x41 0x6c 0x69 0x63 0x65 0x3b 0x54 0x3a 0x42 0x6f 0x62 0x3b 0x41 0x3a 0x31 0x32 0x33 0x34
K 0x53 0x02 0x77 0x2f 0x36 0x63 0x87 0x54 0xb3 0x96 0xbf 0x9a 0xdc 0x00 0x07 0x49 0x0a 0xb8 0x26 0x51
=
C 0x15 0x38 0x36 0x43 0x5f 0x00 0xe2 0x6f 0xe7 0xac 0xfd 0xf5 0xbe 0x3b 0x46 0x73 0x3b 0x8a 0x15 0x65

Schafft es ein Angreifer diese Nachricht abzufangen, kann diese - bei korrekter Verwendung des One-Time-Pads - zwar nicht entschlüsselt, aber trotzdem unbemerkt manipuliert werden. Der Angreifer kennt dden genauen Inhalt der Nachricht zwar nicht, das Protokoll sieht jedoch den Überweisungsbetrag am Ende der Nachricht vor. In diesem Beispiel ändert der Angreifer nun Byte 16 wie gezeigt auf den Wert 0x33.

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
C 0x15 0x38 0x36 0x43 0x5f 0x00 0xe2 0x6f 0xe7 0xac 0xfd 0xf5 0xbe 0x3b 0x46 0x73 0x33 0x8a 0x15 0x65

Wird dieser manipulierte Ciphertext vom Angreifer an die Bank weitergeleitet und entschlüsselt, sieht das Ergebnis folgendermaßen aus:

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
C 0x15 0x38 0x36 0x43 0x5f 0x00 0xe2 0x6f 0xe7 0xac 0xfd 0xf5 0xbe 0x3b 0x46 0x73 0x33 0x8a 0x15 0x65
K 0x53 0x02 0x77 0x2f 0x36 0x63 0x87 0x54 0xb3 0x96 0xbf 0x9a 0xdc 0x00 0x07 0x49 0x0a 0xb8 0x26 0x51
=
M (Hex) 0x46 0x3a 0x41 0x6c 0x69 0x63 0x65 0x3b 0x54 0x3a 0x42 0x6f 0x62 0x3b 0x41 0x3a 0x39 0x32 0x33 0x34
M (ASCII) F : A l i c e ; T : B o b ; A : 9 2 3 4

Ohne den Schlüssel zu kennen, wurde der Betrag vom Angreifer von 1234€ auf 9234€ geändert. Die Bank hat auch keine Möglichkeit diese Manipulation festzustellen.

1)
In Englisch verwendet man für diese Eigenschaft gern den Ausdruck „perfect secrecy“.