24.4 Digitale Unterschriften

Ein Message-Digest, kurz MD, definiert ein Verfahren zur Erzeugung von digitalen Unterschriften für Dokumente. Der berechnende Algorithmus ist eine Einwegfunktion und liefert aus einer Botschaft beliebiger Länge einen »Fingerabdruck« in Form einer Zahl. Die Fingerabdrücke dienen dazu, veränderte Botschaften zu bemerken. Wird etwa bei einer Rechnung eine 0 angehängt, wollen wir dies erkennen können. Wir haben ähnliche Funktionen schon beim Hash-Verfahren kennen gelernt. Die meisten Klassen überschreiben die hashCode()-Methode der Oberklasse Object, die einen int (also 32 Bit) als Identifizierer liefert.

Für die Begriffe »Message-Digest« und »Fingerabdruck« gibt es weitere Synonyme: Kompressionsfunktion, Kontraktionsfunktion, kryptografische Prüfsumme (falls die Unterschrift zusätzlich verschlüsselt wird), Integritätsprüfung von Nachrichten (Message Integrity Check, MIC) oder Erkennung von Manipulationen (Manipulation Detection Code, MDC). Wird dem Fingerabdruck noch ein Schlüssel beigefügt, so fällt auch der Begriff Message Authentication Code (MAC).

24.4.1 Die MDx-Reihe

Von der Firma RSA Data Security wurden drei bekannte Verfahren mit den Bezeichnungen MD2, MD4 und MD5 entwickelt, wovon MD5 am meisten verbreitet ist. Das weit verbreitete Verschlüsselungsprogramm PGP (Pretty Good Privacy) nutzt unter anderem MD5-Signaturen. Programmiert wurde es von Ron Rivest, einem der Mitentwickler vom RSA-Public-Key-Verfahren. (Daher auch das »R«. Die Kollegen waren Adi Shamir und Leonard Adleman.) Die Verfahren sind im RFC 1319, RFC 1320 und RFC 1321 (April 1992) beschrieben. MD2 und MD4 sind ältere Versionen, haben Schwächen und sollten nicht benutzt werden. MD2 ist aus dem Jahre 1989 und MD4 von 1990. Der MD5-Algorithmus ist seit 1991 bekannt. MD5 wird als relativ sicher betrachtet (zu den Problemen gleich mehr) und produziert 128-Bit-Hash-Werte. Dies ist eine 39-stellige Dezimalzahl. Bei MD5 ist es nahezu unmöglich, die Nachricht so zu verändern, dass der Inhalt sich ändert, aber der Schlüssel gleich bleibt. Sind die Schlüssel gleich, aber die Nachricht unterschiedlich, haben wir das Problem einer Kollision. Wir haben uns mit Kollisionen schon beim Hashing beschäftigt. Da ein MD5-Hash-Wert 128 Bit lang ist, kann er 2^128 verschiedene Ausgabewerte annehmen. Zwangsläufig sind unter 2^128 + 1 verschiedenen Nachrichten mindestens zwei Texte mit gleichem Hash-Wert. Die Wahrscheinlichkeit, dass eine beliebige Nachricht den gleichen Hash-Wert wie eine vorgegebene Nachrichten hat, ist 0,000 000 000 000 000 000 000 000 000 000 000 000 029 Prozent (1/2^128). Die Wahrscheinlichkeit jedoch, dass zwei beliebig gewählte unterschiedliche Nachrichten den gleichen Hash-Wert haben, ist deutlich höher. Dieses Phänomen wird auch als Geburtstagsparadoxon bezeichnet.

Ebenso kompliziert gestaltet es sich, eine Botschaft zu generieren, die einen vorgegebenen Fingerabdruck besitzt. Doch unmöglich ist das nicht. 1994 haben Paul van Oorschot und Mike Wiener gezeigt, dass sich in weniger als einem Monat mit einem Budget von etwa zehn Millionen US-Dollar (Stand 1994) ein 128-Bit-Schlüssel knacken lässt. Die Kosten halbieren sich etwa alle 18 Monate. Im Durchschnitt tritt alle 24 Tage eine Kollision bei MD5 auf.

Der deutsche Kryptologe Prof. Hans Dobbertin schreibt in seinem Artikel »Cryptanalysis of MD5 Compress« (http://www.cs.ucsd.edu/users/bsy/dobbertin.ps) über das Problem der Kollisionen bei MD5. Auch bei MD4 war Dobbertin schon erfolgreich. Im Cryptobytes Journal der Firma RSA stellt er eine Methode vor, mit der innerhalb von einer Stunde zwei bis auf ein Zeichen identische Nachrichten gefunden werden konnten, die denselben Hash-Wert besitzen. Im Bulletin Nr. 4 der RSA Laboratorien vom November 1996 (http://www.rsa.com/) wird über die bisher entdeckten Schwächen von MD2, MD4 und MD5 berichtet. Obwohl es bislang nicht gelungen ist, das MD5-Verfahren generell zu brechen, wird es bei neuen Protokollen meist nicht mehr favorisiert. Dobbertin nennt als Alternativen SHA-1 und RIPEMD-160. RIPEMD ging aus dem EU-Projekt RIPE (RACE Integrity Primitives Evaluation, 1988-1992) hervor und wurde von Hans Dobbertin, Antoon Bosselaers und Bart Preneel entworfen. Es soll die Hash-Funktionen MD4 und MD5 ersetzen. Eine Beschreibung findet sich unter http://www.esat.kuleuven.ac.be/~bosselae/ripemd160.html.

24.4.2 Secure Hash Algorithm (SHA)

Das National Institute of Standards and Technology (http://www.nist.gov) entwickelte im Secure Hash Standard (SHS) den Secure Hash Algorithm (SHA) mit einem Hash-Wert von 160 Bit. Eine Beschreibung des Algorithmus ist unter http://www.itl.nist.gov/fipspubs/fip180-1.htm abgelegt. (FIPS¹ ist die Abkürzung für Federal Information Processing Standards Publication.) SHA ist im Dokument 180 (SHA) beziehungsweise 180-1 (SHA-1) definiert. Der Secure-Hash-Standard ist Teil des Digital-Signature-Standards (DSS), und dieser ist wiederum Teil des Capstone-Projekts. Dieses Projekt des US-Ministeriums definiert Standards für öffentlich verfügbare Kryptographie. Es besteht aus vier Hauptkomponenten. Dazu gehören ein symmetrischer Verschlüsselungsalgorithmus (Skipjack, auch Clipper genannt), ein Schlüsselaustauschprotokoll (bisher nicht öffentlich, ein Diffie-Hellman-Verfahren), ein Hash-Algorithmus (SHA) und ein Algorithmus für die digitale Unterschrift (DSA, die SHA benutzt). Die Auswahl der Algorithmen trifft das NIST und die NSA.

Die erste Version von SHA hatte eine undokumentierte Schwachstelle, die in einer neuen Implementierung, SHA-1, nicht mehr vorhanden ist. Wir werden SHA-1 hier kurz SHA nennen und beziehen uns damit auf die neuste Version. Im Vergleich zu MD5 generiert SHA einen Hash-Wert von 160 Bit, und Brute-force-Angriffe werden dann noch schwieriger. Bisher ist kein Angriff bekannt, der die Nutzung von SHA in Frage stellt. SHA ist etwas langsamer als MD5.

24.4.3 Mit der Security-API einen Fingerabdruck berechnen

Die Java-Cryptography-API ist eine Bibliothek zur Verschlüsselung und Authentifizierung. In der Java Cryptography Architecture (JCA) ist beschrieben, wie diese API benutzt werden kann. Einstiegspunkt für Algorithmen ist eine statische Methode getInstance(), die ein Exemplar eines konkreten kryptografischen Algorithmus liefert. Als Parameter wird ein Name für den Algorithmus übergeben, etwa »MD5« oder »SHA«. Das JCA schlägt weitere Namen vor. Sun implementiert in ihrem JDK den DSA-Algorithmus »NIST Digital Signature Algorithm« und für digitale Signaturen »MD5« und »SHA-1«. Da wir uns etwas näher mit Signaturen beschäftigt haben, soll zunächst die Klasse MessageDigest für digitale Fingerabdrücke untersucht werden.

24.4.4 Die Klasse MessageDigest

Mit der statischen Methode getInstance() bekommen wir einen Algorithmus, der eine bestimmte Berechnungsfunktion implementiert. getInstance() gibt es in zwei Ausführungen. Beiden gemeinsam ist der Name des Algorithmus als Parameter. Folgende Zeilen erzeugen ein MessageDigest-Objekt für SHA. Die zweite Variante spezifiziert den Hersteller näher:

MessageDigest digest = MessageDigest.getInstance( "SHA" );
MessageDigest digest = MessageDigest.getInstance( "SHA", "SUN" );

Ist der Algorithmus nicht bekannt, bekommen wir eine NoSuchAlgorithmException. Ein unbekannter Hersteller führt zu einer NoSuchProviderException.

Hier klicken, um das Bild zu Vergrößern

Den Fingerabdruck berechnen

Nun können wir eine Nachricht kodieren. Dazu stehen zwei Möglichkeiten bereit: Die Nachricht wird als Ganzes übergeben, oder Schritt für Schritt wird ein Teil kodiert. Die Funktionsweise erinnert sehr an die Schnittstelle java.util.zip.Checksum.

MessageDigest md = MessageDigest.getInstance( "SHA" );
md.update( "Hallo".getBytes() );

Die update()-Methode ist auch für ein einzelnes Byte definiert. Für große Dateien ist es besser, immer wieder update() auf größeren Blöcken aufzurufen, anstatt die ganze Datei auf einmal zu übergeben, da dafür die Datei vollständig im Speicher stehen müsste. Schritt für Schritt nehmen wir mit update() immer mehr von der Nachricht hinzu. Wenn wir die Eingabedatei als einen Datenstrom inputstreamMessage vorliegen haben, bietet sich Folgendes an:

byte md[] = new byte[8192];
int n = 0;
while ( (n = inputstreamMessage.read(md)) > -1 )
  messagedigest.update( md, 0, n );

Den Fingerabdruck auslesen

Nach der Sammlung lässt sich mit der Objektmethode digest() die Signatur berechnen. Sie hat eine bestimmte Länge, die wir mit getDigestLength() erfragen können. Die Länge wird in Bytes gemessen. Da digest() ein Byte-Array zurückliefert, ist der Wert von getDigestLength() mit der Länge des Arrays identisch. digest() lässt sich auch mit einem Bytefeld aufrufen. Ein einfaches SHA-Programm für den String sieht daher so aus:

MessageDigest md = MessageDigest.getInstance( "SHA" );
byte digest[] = md.digest( "abc".getBytes() );
for ( int i = 0; i < digest.length; i++ )
  System.out.print( Integer.toHexString( digest[i]&0xff) + " " );

Das Programm erzeugt die Ausgabe:

a9 99 3e 36 47 6 81 6a ba 3e 25 71 78 50 c2 6c 9c d0 d8 9d

Schon eine einfache Veränderung wirkt sich global aus. Anstatt »abc« kodieren wir jetzt »Abc« und »abd«. Einmal wird aus dem Klein- ein Großbuchstabe, und im anderen Fall nehmen wir einfach das nachfolgende Zeichen im Alphabet. Kein Byte bleibt gleich:

91 58 58 af a2 27 8f 25 52 7f 19 20 38 10 83 46 16 4b 47 f2 // Abc
cb 4c c2 8d f0 fd be e cf 9d 96 62 e2 94 b1 18 9 2a 57 35   // abd

Fingerabdrücke im Vergleich

Die folgende Applikation zeigt die generierten Fingerabdrücke für MD5 und SHA. Als zu bewertende Nachricht wird eine Datei genommen. Zu Testzwecken ist es das Java-Programm selbst.

Listing 24.4 MDGenerator.java

import java.io.*;
import java.security.*;
public class MDGenerator
{
  static byte[]messageDigest( String file, String algo ) throws Exception
  {
    MessageDigest messagedigest = MessageDigest.getInstance( algo );
    byte md[] = new byte[8192];
    FileInputStream in  = new FileInputStream( file );
    for ( int n = 0; (n = in.read(md)) > -1; )
      messagedigest.update( md, 0, n );
    return messagedigest.digest();
  }
  static void
  digestDemo( String file, String algo ) throws Exception
  {
      byte digest[] = messageDigest( file, algo );
      System.out.println( "Schlüssellänge " + algo + ": " + digest.length*8 + " Bits" );
      for ( int i = 0; i < digest.length; i++ )
      {
        String s = Integer.toHexString( digest[i] & 0xFF );
        System.out.print( (s.length() == 1 ) ? "0" + s : s );
      }
      System.out.println( "\n" );
  }
  public static void main( String args[] ) throws Exception
  {
    digestDemo( "MDGenerator.java", "SHA" );
    digestDemo( "MDGenerator.java", "MD5" );
  }
}

Das Programm produziert die folgende Ausgabe:

Schlüssellänge SHA: 160 Bits
c13248d72e57436a4952818bf3e52dddd7801899
Schlüssellänge MD5: 128 Bits
eb6876a56577ce1466657599c05ea361

24.4.5 Unix-Crypt

Das Unix-Crypt steht unter Java nicht in der Kryptographie-API zur Verfügung. Dennoch ist es manchmal sinnvoll, eine Implementierung für das Unix-Crypt nutzen zu können. Eine effiziente Nach-Implementierung findet sich zum Beispiel unter http://locutus.kingwoodcable.com/jfd/crypt.html.

¹ Ich glaube nicht, dass es eine Verwandtschaft mit Heinz Erhardts Fips gibt.