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

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.

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.

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

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

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:

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.

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.

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

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 2⁶⁴ (18.446.744.073.709.551.616) auf ca. 2³⁵ (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.

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:
C₁ = M₁ ⊕ K
C₂ = M₂ ⊕ K

Kombiniert man nun die beiden verschlüsselten Texte mit XOR:
C₁ ⊕ C₂
erhält man als Formel:
(M₁ ⊕ K) ⊕ (M₂ ⊕ K)
Da das exklusive Oder kommutativ ist, kann die Gleichung folgendermaßen umgeformt werden:
(K ⊕ K) ⊕ (M₁ ⊕ M₂)
Jede beliebige Zahl die über ein exklusives Oder mit sich selbst verbunden wird ergibt 0 (x ⊕ x = 0), daher:
(0) ⊕ (M₁ ⊕ M₂)
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:
M₁ ⊕ M₂

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:
(M₁ ⊕ M₂) ⊕ M₁
Löst man obige Gleichung auf, bleibt die entschlüsselte Nachricht M₂ übrig. Erhält man für M₂ 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!

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.

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.

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

Nun wird der Datensatz mit einem zufälligen Schlüssel verknüpft: