BSI-Forum

Digitale Signatur von Bitströmen

Von Christoph Ruland und Niko Schweitzer, Institut für Nachrichtenübermittlung, Universität Siegen

Dieser Beitrag beschreibt ein Verfahren, das kontinuierliche Bitströme digital unterschreibt. Das Verfahren signiert direkt den Bitstrom und geht nicht davon aus, dass der Bitstrom in Pakete strukturiert worden ist. Bitströmen werden digitale Signaturen hinzugefügt, ohne eine Expansion des Bitstroms zu verursachen und somit zusätzliche Bandbreite zu benötigen. Dies wird möglich, da man sich auf eine implizite Authentifikation auf Grund unversehrter Daten beschränkt. Weitere wichtige Eigenschaften des in diesem Beitrag beschriebenen Verfahrens sind die Online-Fähigkeit, die ermöglicht Signaturen während des Übertragungsprozesses zu berechnen, hinzuzufügen und auf Empfängerseite wieder zu extrahieren, und die doppelte Broadcasteigenschaft aus kryptographischer und übertragungstechnischer Sicht: Die Verwendung asymmetrischer Verfahren ermöglicht den Einsatz in großen Benutzergruppen, zum Beispiel im Broadcast- und Multicastbetrieb, die selbstsynchronisierende Eigenschaft ermöglicht Empfängern, sich zu beliebigen Zeitpunkten in signierte Bitströme einzuschalten, aufzusynchronisieren und die Sicherheitsdienste zu nutzen.

1 Einleitung

Digitale Signaturen sind die Basis für eine Authentifikation des Ursprungs der Daten, auch für Datenströme. Bisher gibt es aber nur sehr wenige Veröffentlichungen über digitale Signaturen und die Authentifikation von Bit- oder Datenströmen. Die Gründe dafür liegen in der Eigenschaft der bekannten asymmetrischen kryptographischen Verfahren, die nur abgeschlossene Blöcke signieren können. Außerdem waren bisher die meisten Anwendungen, die digitale Signaturen verwenden, block- oder paketorientiert, sodass nicht die Notwendigkeit nach Bitstrom-orientierten Signaturverfahren bestand. Zudem war das Internet kaum für die Übertragung von Bitströmen geeignet, sodass auch die technischen Voraussetzungen fehlten.

Inzwischen gibt es aber ein zweifaches Interesse an Bitstrom-orientierten Signaturverfahren – aus Anwendersicht und aus Übertragungssicht: Es sollen auch die Daten von kontinuierlichen, stromorientierten, ja sogar echtzeitorientierten Anwendungen übertragen werden. Dies führt zu QoS-Anforderungen an die Übertragungsdienste, zum Beispiel für (komprimierte) Video- und Audioströme. Das Internet wird mit IPv6 in Zukunft derartige Dienste bieten. Für die Übertragung werden hauptsächlich Netze eingesetzt, die nur synchrone Bitströme übertragen. Das beste Beispiel hierfür ist die synchrone digitale Hierarchie (SDH), die heute allen breitbandigen Übertragungssystemen zugrunde liegt. Wenn die Übertragung von Datenströmen zunehmend an Bedeutung gewinnt, dann auch die Notwendigkeit des Nachweises ihres Ursprungs.

Bisherige Veröffentlichungen auf dem Gebiet der Authentifikation von Bitströmen betreffen entweder Bitströme, die zu Blöcken formatiert und zwischen denen Signaturen eingefügt werden, oder das Key Management von symmetrischen Schlüsseln, um eine broadcast- oder multicastfähige symmetrische Verschlüsselung durchzuführen.

Der bisher wichtigste Beitrag zur Signatur von digitalen Datenströmen stammt von Gennaro und Rohatgi [1]. Das dort beschriebene Verfahren enthält zwei Varianten: eine Offline-Version, bei der Signaturen im Voraus berechnet werden, und eine Online-Variante, bei der Signaturen während der Übertragung generiert werden. Das Offline-Verfahren entspricht nicht den hier angenommenen Vorstellungen von einer Bitstrom-Authentifikation, da der Empfänger den Bitstrom von Anfang an kennen muss, und dem Sender muss für die Berechnung der Signatur der gesamte Bitstrom vorliegen. Außerdem gibt es keine Möglichkeit für Empfänger, sich auf den Bitstrom aufzusynchronisieren, da zu Beginn des Bitstroms eine signierte Tabelle mit Hashwerten gesendet wird. Die Online-Variante verwendet das Prinzip von Einmal-Signaturen und leidet daher unter deren negativen Eigenschaften: es müssen zu viele Zufallszahlen und zu lange Signaturen übertragen werden. Dadurch wächst der Bandbreitebedarf um ein Vielfaches. Bei bestimmten Anwendungen, zum Beispiel dem Abrufen von MPEG-komprimierten Dateien, können diese Verfahren aber durchaus nützlich sein.

Das im Folgenden vorgestellte Verfahren hat ganz andere Eigenschaften: Unterstützung endloser Bitströme, Broadcasteigenschaft aus kryptographischer und übertragungstechnischer Sicht sowie keine Expansion des Bitstroms. Dafür muss der gebotene Sicherheitsdienst differenzierter betrachtet werden, da zwar Signaturen übertragen werden, die Authentifikation aber nur implizit erfolgt.

Man erkennt, dass es schwierig ist, Verfahren zur Bitstrom-Authentifikation zu vergleichen, und diese Schwierigkeiten werden noch größer, wenn in Zukunft weitere Beiträge zu diesem Thema veröffentlicht werden. Es ist daher sinnvoll, einen Kriterienkatalog aufzustellen, mit dessen Hilfe die Verfahren verglichen werden können. Dieser Kriterienkatalog kann von Anwendern oder Netzbetreibern gleichermaßen genutzt werden, um geeignete Verfahren auszuwählen. Eine derartige Klassifikation und Kriterien zur Beurteilung von Bitstrom-Authentifikationsverfahren werden im folgenden Kapitel eingeführt. Kapitel 3 beschreibt die Eigenschaften des neuen Verfahrens, bevor in Kapitel 4 seine technische Beschreibung folgt. Kapitel 5 schließt den Beitrag mit einer Zusammenfassung ab.

2 Klassifizierung von Bitstrom-Signaturverfahren

Da es verschiedene Verfahren für die Signatur digitaler Datenströme gibt, diese sich aber stark in ihren Eigenschaften unterscheiden, soll in diesem Kapitel eine Klassifizierung der Verfahren mithilfe von Kriterien vorgenommen werden. Vorab sei erwähnt, dass für unterschiedliche Einsatzbereiche unterschiedliche Lösungen denkbar und auch notwendig sind, zum Beispiel stellt ein MP3-Datenstrom über das Internet andere Anforderungen an ein Signaturverfahren als eine synchrone Radardatenübertragung.

Folgende Kriterien werden definiert:

Public-Key-Eigenschaft

Diese Eigenschaft wird erfüllt, wenn der Sicherheitsdienst auf einem Public-Key-Verfahren basiert, für das eine Public Key Infrastruktur existiert oder aufgebaut werden kann.

Diese Eigenschaft wird definiert, um zwischen Verfahren zu unterscheiden, die die Authentifikation auf Basis digitaler Signaturen oder symmetrischer Algorithmen unterstützen. Die Public-Key-Eigenschaft ermöglicht Rückschlüsse für den Aufwand des Key Managements in Broadcast- und Multicast-Anwendungen zu ziehen. Bei Verfahren mit der Public-Key-Eigenschaft ist kein besonderer Aufwand erforderlich, da auf herkömmliche Ansätze zum Schlüsselmanagement, beispielsweise Public Key Infrastrukturen (PKIs), zurückgegriffen werden kann. Bei Verfahren auf Basis symmetrischer Algorithmen wird das Key Management dagegen in größeren Benutzergruppen äußerst komplex.

Online-Tauglichkeit

Diese Eigenschaft ist gegeben, wenn die Ausführung der Sicherheitsmechanismen während der Übertragung möglich ist.

Die Online-Tauglichkeit ist nicht gegeben, wenn der Sender oder Empfänger den gesamten Datenstrom benötigt, um die Operationen durchzuführen. Entsprechend muss zwischen Online-Tauglichkeit beim Sender und Online-Tauglichkeit beim Empfänger unterschieden werden.

Die Online-Eigenschaft ist das wesentliche Kriterium, das Stromsignaturverfahren von "herkömmlichen" Signaturverfahren abgrenzt. Herkömmliche Signaturverfahren setzen immer die Kenntnis eines abgeschlossenen Datensatzes voraus, bevor Signaturen berechnet, beziehungsweise verifiziert werden können und sind daher nicht Online-tauglich, weder sender- noch empfängerseitig.

Selbstsynchronisationsfähigkeit

Ein Verfahren verfügt über Selbstsynchronisationsfähigkeit, wenn sich Empfänger zu beliebigen Zeitpunkten in eine laufende Übertragung einschalten und nach einer gewissen Synchronisationszeit die gebotenen Sicherheitsdienste nutzen können. Die durchschnittliche Dauer bis zur nächsten Selbstsynchronisation soll durch Systemparameter einstellbar sein.

Diese Eigenschaft ist bei vielen Anwendungen von Stromsignaturverfahren unerlässlich: sei es auf der physikalischen Übertragungsschicht, sei es bei Multicast- und Broadcastausstrahlungen, denn nur selten erhält ein Empfänger den Datenstrom vom ersten gesendeten Bit an. Die Selbstsynchronisationsfähigkeit gilt auch bei Modifikationen von Datenströmen. Sie kann daher in Widerspruch zu Sicherheitsanforderungen stehen, wenn eine endlose Fehlerfortpflanzung bei Fehlern oder Synchronisationsverlust erwünscht wird.

Datenexpansion

Ein weiteres wichtiges Kriterium ist der Grad der Datenexpansion, der durch Stromsignaturen verursacht wird, beziehungsweise die Anforderung an die Erhöhung der Bandbreite, um einen signierten Strom mit denselben QoS-Eigenschaften des nicht signierten Datenstroms übertragen zu können.

Sicherheitsdienst

Ziel der Stromsignaturen ist es, eine Authentifikation des Ursprungs des empfangenen Datenstroms zu leisten oder zumindest zu unterstützen.

Ob dieses Kriterium von einem Verfahren erfüllt wird, lässt sich nicht immer einfach mit Ja oder Nein beurteilen. Die Authentifikation basierend auf symmetrischen Verfahren unterscheidet sich von der Aussagekraft her von einer, die auf asymmetrischen Verfahren beruht. Ein Verfahren kann die Verifikation der Signaturen beinhalten oder mit Hilfe der Signaturen nur verhindern, dass der Datenstrom unerkennbar manipuliert wird. In diesem Fall wird nur indirekt eine Authentifikation ermöglicht. Die sicherheitstechnische Bedeutung eines solchen Verfahrens, das eine Authentifikation nicht durchführt, sondern nur ermöglicht, wird anhand des folgenden Verfahrens näher erläutert. Es ist daher erforderlich, die Qualität des Sicherheitsdienstes individuell und differenziert zu erläutern.

Weitere Kriterien

Es gibt weitere Kriterien, wie Berechnungsaufwand, Speicherbedarf, Verzögerung, Auswahl und Management der Systemparameter usw. Diese können nach Bedarf hinzugefügt werden. Da diese aber hauptsächlich implementationsabhängig sind, werden sie im weiteren Verlauf dieses Beitrages nicht berücksichtigt.

3 Bewertung des neuen Verfahrens

Auch wenn das neue Verfahren noch nicht vorgestellt worden ist – dies erfolgt in Kapitel 4 –, sollen doch schon die wesentlichen Eigenschaften erläutert werden, um diese mit denen der Verfahren von Gennaro und Rohatgi [1] zu vergleichen.

Das im folgenden Kapitel dargestellte Verfahren erfüllt folgende Kriterien: Es besitzt die Public-Key-Eigenschaft, es ist Online-tauglich für Sender und Empfänger, es besitzt Selbstsynchronisationsfähigkeit und hat keine Datenexpansion. Der Sicherheitsdienst besteht in der Gewährleistung der Erkennbarkeit der Datenunversehrtheit.

Die Eigenschaften sind in Vergleich zu den beiden Verfahren von Gennaro und Rohatgi (GeRo97) in Tabelle 1 wiedergegeben. So ist ersichtlich, dass sich die Verfahren wesentlich unterscheiden und für verschiedene Anwendungsbereiche geeignet sind.

Verfahren Public-Key-Eigenschaft Online-Tauglichkeit (sender-/empfängerseitig) Selbstsynchronisationsfähigkeit Datenexpansion
GeRo97 Online ja ja/ja nein hoch
GeRo97 Offline ja nein/ja nein mittel
dieser Beitrag ja ja/ja ja keine

Tabelle 1: Klassifizierung von Bitstrom-Signaturverfahren

Der Preis, der bei dem neuen Verfahren für den Verzicht der Datenexpansion gezahlt werden muss, besteht in einem eingeschränkten Sicherheitsdienst. So kann eine Authentifikation erst in Verbindung mit weiteren Voraussetzungen, die aber meistens gegeben sind, erbracht werden.

"Gewährleistung der Erkennbarkeit der Datenversehrtheit" bedeutet, dass kein Angreifer den Datenstrom so manipulieren kann, dass dies nicht vom Empfänger, trotz vorhandener Fehlererkennungsmechanismen, erkannt wird. Ein Angreifer kann nicht Nutzinformation und Fehlererkennungsinformation so modifizieren, dass anschließend Fehlererkennungsinformation und Nutzinformation wieder zueinander passen. Das Verfahren sorgt dafür, dass der Empfänger nach Modifikationen nur noch einen quasi-zufälligen, gestörten Datenstrom erhält. Die Störung hält bis zur nächsten Selbstsynchronisation an.

Wenn also in dem Datenstrom Informationen zur Übertragungsfehlerkennung enthalten sind und die Fehlererkennung keine Fehler erkennt, ist der Datenstrom authentisch. Wenn Fehler erkannt werden, wird der Datenstrom als gefälscht gekennzeichnet oder verworfen, bis wieder ein fehlerfreier Datenstrom geliefert wird. Zur Durchführung der eigentlichen Authentifikation wird also eine höhere Instanz vorausgesetzt, die selbst Redundanz im Datenstrom erkennt und überprüft.

Wenn im Datenstrom Redundanz vorhanden ist, wird diese durch das Signaturverfahren manipulationssicher. Wenn eine Instanz vorhanden ist, die diese Redundanz überprüft, hat diese Überprüfung denselben Wert wie die Verifikation einer digitalen Signatur. Das Ergebnis ist eine Authentifikation des empfangenen Datenstroms.

Mancher Leser wird jetzt einwenden, dass die Forderung nach einer höheren Instanz, die die Redundanzüberprüfung vornimmt, unrealistisch ist oder gar dem Schichtenprinzip des ISO-Referenzmodells widerspricht. Dem kann als Gegenbeispiel die Nutzung von Online-Kompressionsverfahren entgegengehalten werden: Auch die Dekompressionsseite kann selbst nicht erkennen, wenn sie durch Fehler außer Synchronisation geraten ist und nur noch unbrauchbaren Text liefert. Trotzdem wird keiner daran zweifeln, dass Kompressionsverfahren trotz Leitungsfehler sehr gut funktionieren und sehr nützlich sind. Voraussetzung ist dabei, dass das Gesamtsystem betrachtet wird, das auch die Zusammenarbeit verschiedener Schichten vorsieht: Die Funktion der Redundanzüberprüfung basiert auf dem Dienst der Signaturen. Der Fehlererkennungsmechanismus wird zusammen mit dem Signaturverfahren zu einem Authentifikationsmechanismus.

Bei der Beurteilung des Verfahrens muss außerdem berücksichtigt werden, dass dieser Sicherheitsdienst übertragungstechnisch nichts kostet. Daher liegt das wesentliche Anwendungsgebiet des im Folgenden beschriebenen Verfahrens in der Signatur von Bitströmen auf der physikalischen Schicht, bei der die Bandbreite durch einen synchronen Bitstrom komplett ausgeschöpft wird und nicht gesteigert werden kann. Bei der Signatur von Schicht-1-Bitströmen gibt es im Allgemeinen zumindest eine Schicht der Schichten 2–7, die in ihrem Protokoll Redundanz verwendet und überprüft, auch wenn es letzten Endes zum Beispiel der Fernsehzuschauer ist, der ein Rauschen auf dem Bildschirm sicher nicht als authentischen Film interpretieren wird.

4 Signaturverfahren für Bitströme

4.1 Einfaches blockorientiertes Verfahren

Um die Broadcast- und Multicasteigenschaft zu erreichen, wird ein Public-Key-Verfahren eingesetzt. Da bisher nur blockorientierte Public-Key-Verfahren bekannt sind, wird der Bitstrom als Folge von Blöcken aufgefasst. Jeder Block habe zunächst eine feste Länge – später wird auf eine variable Länge übergegangen. Die Folge der Blöcke sei {an}. Jeder Block ai, i ∈ N habe eine Länge von k Bits. Als Signaturverfahren wird das RSA-Verfahren [2] verwendet. Jeder Block ai wird in zwei Teilblöcke xi und yi aufgespalten (im Weiteren gilt für i immer i ∈ N).

[Abbildung 1]
Abbildung 1: Strukturierung des Bitstroms

Es ist Aufgabe der Teilblöcke yi, zusätzlich die digitalen Signaturen zu transportieren. Daher ist die Länge von yi identisch zur Länge einer Signatur, das heißt im Fall des RSA-Verfahrens gleich der Länge m des Modulus n (in Bits). Beispiel: Wenn beim RSA-Verfahren m = 1024 gewählt wird, dann beträgt die Länge von yi ebenfalls 1024. Ein Vorschlag zur Festlegung von k wird später gemacht. Es wird vorläufig angenommen, dass Sender und Empfänger die Blockgrenzen kennen, bis das Problem der Selbstsynchronisation in Kapitel 4.3 gelöst wird.

Um das Grundprinzip des Verfahrens zu erläutern, wird ein einzelner Block ai, betrachtet.

H sei eine One-Way-Hashfunktion, die einen Hashwert der Länge m liefert. d sei der geheime, e der öffentliche Schlüssel und n der Modulus des RSA-Schlüsselsystems des Senders.

Der Sender berechnet nun eine Signatur für den Block ai wie folgt:

  1. zi := H(xi )
  2. bi := zi XOR yi
  3. Fallunterscheidung
    1. falls bi < n, dann
      si := bid mod n
    2. falls bi ≥ n, dann
      si := bi
      xi+1 := xi // yi // xi+1
      ("//" bedeutet Konkatenation)

Der Sender überträgt anstelle des Teilblockes yi den Teilblock si. Der Teilblock si enthält im Fall 3.1 die digitale Unterschrift verknüpft mit der Information des Blockes yi. Block yi trägt sozusagen die Unterschrift "huckepack". Es wird ausgenutzt, dass das RSA-Verfahren "Signatures with Recovery" ermöglicht.

[Abbildung 2]
Abbildung 2: Struktur des signierten Bitstroms

Es wird angenommen, dass der Empfänger die Teilböcke fehler- und manipulationsfrei empfängt. Der Empfänger führt folgende Schritte zur Verifikation beziehungsweise Rekonstruktion des Originaldatenstroms aus:

  1. zi := H(xi)
  2. Fallunterscheidung
    1. falls si < n, dann
      bi := sie mod n
      yi := bi XOR zi
    2. falls si ≥ n, dann
      bi := si
      yi := bi XOR zi
      xi+1 := xi // yi // xi+1

Bei fehler- und manipulationsfreier Übertragung hat der Empfänger wieder den ursprünglichen Teilblock yi rekonstruiert und damit den kompletten Block ai erhalten.

Falls der Teilblock xi während der Übertragung verändert worden ist, ergibt sich ein fehlerhafter Teilblock yi, ebenso wenn der Teilblock si manipuliert wurde.

Es gelingt also keinem Angreifer, die Teilblöcke xi und si zu ändern, ohne dass sich beim Empfänger ein quasi zufälliger Teilblock yi ergibt. So kann die Fehlererkennung der höheren Schichten nicht betrogen werden, indem ein Angreifer die Information und die Redundanz manipuliert, selbst wenn dieser weiß, wie die Redundanz gebildet wird.

In dem Verfahren wird die Fallunterscheidung gemacht, ob bi < n, beziehungsweise si < n ist. Dies ist durch eine Eigenschaft des RSA-Verfahrens erforderlich: Auch wenn der Input-Wert des RSA-Verfahrens dieselbe Länge wie der Modulus n hat, kann es vorkommen, dass der Input-Wert nicht kleiner als der Modulus ist. In diesem Fall kann das RSA-Verfahren nicht auf den Input-Wert angewendet werden, sondern es wird folgender Ausweg gewählt (siehe Ausführungsschritte beim Sender und Empfänger): Wenn der Input-Wert bi kleiner als n ist, wird die Unterschrift erzeugt. Der Wert des Blocks si ist dann ebenfalls kleiner als n.

Andernfalls erfolgt keine Unterschriftsberechnung und der bisher noch nicht unterschriebene Block wird dem nächsten zu unterschreibenden Block vorangestellt. Entsprechend kann der Empfänger erkennen, ob der Block unterschrieben wurde oder nicht. Durch geeignete Wahl von n ist es möglich, die Wahrscheinlichkeit, dass bi ≥ n bei gleicher Länge von bi und n ist, beliebig zu verringern. Dafür eignen sich Primzahlgenerierungsverfahren, mit denen die Primzahlen p und q so konstruiert werden können, dass n = p · q so viele führende "1"-Bits enthält, wie gewünscht.

Nun soll eine geeignete Länge k der Blöcke ai gefunden werden. k hängt von der Übertragungsrate und der Zeit ab, die für eine Signaturberechnung benötigt wird. Die Blocklänge bestimmt, wie häufig signiert wird. k entspricht der Anzahl der Bits, die übertragen werden, während der Hashwert und eine Signatur berechnet werden. Die Hashwertberechnung erfolgt immer parallel zur Übertragung, die Signaturberechnung erfolgt nach der Übertragung von k − m Bits nach der letzten Signatur.

Wenn v die Übertragungsrate in Bit/s, h die Hashrate in Bit/s und st die Zeit für eine Signatur sind, dann beträgt

k = v · st · h / (h − v).

Wird noch berücksichtigt, dass m Bits nicht in die Hashwertberechnung eingehen, reduziert sich k auf

k' = v · (st · h − m) / (h − v)

Beispiel:
Bei v = 64 kBit/s, st = 20 ms, h = 640 kBit/s, m = 1024 Bit bietet sich eine Blocklänge k' > 165 Byte an.

Wird die Übertragungsrate auf 2 MBit/s erhöht, und nimmt man für die Hashrate 10 MBit/s an, so ergibt sich eine Blockgröße von k' > 6,4 KByte.

Wenn auf der Senderseite verzögerungsfrei gesendet werden soll, dann kann si erst im nächsten oder übernächsten Block untergebracht werden.

4.2 Blockorientiertes Verfahren mit Verkettung

Das in Kapitel 4.1 beschriebene Verfahren hat den Nachteil, dass von einem Angreifer ganze Blöcke im Bitstrom ausgetauscht werden können, da sie nicht miteinander verkettet sind. In diesem Kapitel wird eine Variante erläutert, die Replay- und Reordering-Angriffe erkennt, indem der Teilblock yi-1 mit in die Signatur von xi und yi eingeht. Das Prinzip der verketteten Signaturen ist in Abbildung 3 dargestellt.

In diesem Fall berechnet der Sender:

  1. zi := H(yi-1 // xi)
  2. bi := zi XOR yi
  3. 3 Fallunterscheidung
    1. falls bi < n, dann
      si := bid mod n
    2. falls bi ≥ n, dann
      si := bi
      yi := yi-1 // xi // yi

Gesendet wird wieder xi // si anstelle von xi // yi.

[Abbildung 3]
Abbildung 3: Verkettete Signaturen

Auf die Darstellung der Berechnungsschritte auf der Empfangsseite soll hier verzichtet werden. Sie erfolgen entsprechend der Senderseite, beziehungsweise der Empfängerseite von Kapitel 4.1.

Falls der Teilblock xi während der Übertragung verändert worden ist, ergibt sich beim Empfänger ein fehlerhafter Teilblock yi, ebenso wenn der Teilblock si manipuliert worden ist. Als Folge einer Manipulation ist daher auf jeden Fall yi fehlerhaft. Da yi in die folgende Signatur eingeht, wird auch die Rekonstruktion von yi+1 und allen folgenden Teilblöcken yi+j (j ∈ N) falsch sein. Somit ergibt sich eine endlose Fehlerfortpflanzung über alle Signaturblöcke, die die Erkennung von Reordering- und Replay-Angriffen ermöglicht.

4.3 Verfahren mit Selbstsynchronisation

Jetzt soll das Problem der Selbstsynchronisation gelöst werden: Wie kann ein Empfänger erkennen, wo sich Anfang und Ende der Blöcke ai befinden, wenn er sich in eine laufende Übertragung einschaltet? Dazu wird das Prinzip der statistischen Selbstsynchronisation verwendet. Da die Synchronisation nicht in regelmäßigen, sondern in statistisch verteilten Abständen erfolgt, erhalten die Blöcke ai eine variable Länge (siehe Abbildung 4).

Die statistische Selbstsynchronisation ist von der Bitstromverschlüsselung her bekannt [3]: Zwischen Sender und Empfänger wird ein bestimmtes Bitmuster verabredet. Immer wenn dieses Bitmuster im übertragenen Datenstrom auftritt, wird eine Synchronisationsphase ausgelöst. Da es sich im Fall der Bitstromverschlüsselung bei dem übertragenen Text um Schlüsseltext handelt, ist gewährleistet, dass das Bitmuster mit einer bestimmten Wahrscheinlichkeit im übertragenen Text auftritt.

Wenn das Prinzip der statistischen Selbstsynchronisation zum Signieren von Bitströmen angewendet werden soll, ergibt sich die Schwierigkeit, dass das verabredete Bitmuster eventuell nie oder sehr häufig auftritt, da hauptsächlich Klartext übertragen wird. Das Signaturverfahren und die Selbstsynchronisation sollen aber von dem Kontext der Anwendung unabhängig sein.

Man könnte nur die Teilblöcke si des übertragenen Datenstroms, die die Signatur enthalten, für eine statistische Selbstsynchronisation nutzen. Das Problem ist, dass ein Empfänger nicht weiß, wo die Teilblöcke si liegen. Daher muss sich der gesamte Bitstrom zum Suchen des verabredeten Bitmusters eignen. Um das zu erreichen, wird der gesamte Bitstrom gescrambelt. Der Scrambler sorgt dafür, dass jedes Bitmuster statistisch gleichverteilt im übertragenen Bitstrom auftritt. In diesem gescrambelten Bitstrom wird dann nach dem Bitmuster gesucht, das die Synchronisation auslöst, das heißt die Struktur des Bitstroms bestimmt.

Bei einem Scrambler handelt es sich um ein linear-rückgekoppeltes Schieberegister mit einer maximalen Periode (MLSFR). Scrambler sind in nachrichtentechnischen Geräten weit verbreitet. Zum statistischen Verhalten von maximalen linear-rückgekoppelten Schieberegistern siehe [4].

Um den Scrambler für die statistische Selbstsynchronisation einzusetzen, wird die Länge des MLSFR in Abhängigkeit von der Länge des verabredeten Bitmusters gewählt. Dadurch kann man festlegen, wie häufig im Mittel das Bitmuster auftritt, das heißt wie häufig synchronisiert wird. Scrambler und Descrambler selbst arbeiten ebenfalls selbstsynchronisierend, wobei die Synchronisationsdauer der Länge des Schieberegisters entspricht.

Das zwischen Sender und Empfänger verabredete Bitmuster sei c. Sobald der Sender im gescrambelten Bitstroms das verabredete Bitmuster c erkennt, berechnet er die Signatur. Dafür benötigt er weniger als eine bestimmte Zeit. Diese Zeit entspricht der Übertragungszeit von t Bits. Genau nach w Bits (w > t) nach dem letzten Bit des Bitmusters wird die Signatur gesendet. w ist ein Systemparameter.

Ab dem ersten Bit, das nicht mehr in die Unterschriftsberechnung eingegangen ist, wird der nächste Hashwert (parallel zur Übertragung) solange berechnet, bis das Bitmuster c im übertragenen Bitstrom wieder auftritt und die nächste Signatur berechnet wird.

Da jedes Auftreten des verabredeten Bitmusters eine digitale Signatur auslöst, darf keine neue Synchronisation angestoßen werden, solange noch eine digitale Signatur berechnet wird und die letzte Synchronisationsphase noch nicht abgeschlossen ist. Daher wird die Bitmustererkennung nach dem Start einer Synchronisation für eine festgelegte Anzahl von u Bits gesperrt, u ≥ w + m.

Durch geschicktes Wählen der Länge des Bitmusters c und des Scramblers in Abhängigkeit von Übertragungsgeschwindigkeit und benötigter Zeit für die Hashwert- und Signaturberechnung, kann der durchschnittliche Abstand zwischen den Synchronisationsphasen eingestellt werden. Dies kann auch unter Sicherheitsgesichtspunkten erfolgen, wenn eine längere Fehlerfortpflanzung gewünscht wird.

Nun zum Ablauf der selbstsynchronisierenden Bitstrom-Signatur: Der Block ai besteht aus einem Teilblock xi,1 der Länge w Bit, dem Teilblock yi der Länge m Bit, sowie einem Teilblock xi,2 mit einer variablen Länge (siehe Abbildung 4).

Der Sender berechnet nun die Signatur si für den Block ai wie folgt:

  1. zi := H(xi,1 // xi,2)
  2. bi := zi XOR yi+1
  3. Fallunterscheidung
    1. falls bi < n, dann
      si := bid mod n
    2. falls bi ≥ n, dann
      si := bi
      xi+1,1 := xi,1 // xi,2 // xi+1,1 // yi

Diese Konkatenation berücksichtigt, dass zum Zeitpunkt der Fallunterscheidung H(xi,1 // xi,2 // xi+1,1) bereits berechnet worden ist.

Der Sender überträgt anstelle des Blockes ai+1 die gescrambelten Teilblöcke xi+1,1, si und xi+1,2. Die Teilblöcke {si} enthalten somit die digitale Unterschrift über die Teilblöcke xi,1 und xi,2. Sie befinden sich aber auf dem Territorium des nächsten Blockes ai+1, da die Signatur erst verzögert zur Verfügung steht.

[Abbildung 4]
Abbildung 4: Struktur des Datenstroms mit Signatur und Scrambling

Es wird wiederum angenommen, dass der Empfänger den gescrambelten Bitstrom fehler- und manipulationsfrei empfängt.

Um die Struktur des Datenstroms und die Lage der Signaturblöcke Teilblöcke si zu erkennen, untersucht der Empfänger den empfangenen, gescrambelten Bitstrom und wartet, bis das verabredete Bitmuster c aufgetreten ist. Die Erkennung des Bitmusters wird für u Bits abgeschaltet. Jetzt betrachtet er den descrambelten Bitstrom. Mit dem Erkennen des Bitmusters ist die Anfangsblockgrenze von xi,1 identifiziert worden. Auf die Darstellung der folgenden Einzelschritte zur Herstellung des Teilblockes yi soll hier verzichtet werden, sie laufen entsprechend denen des Senders, beziehungsweise wie in Kapitel 4.1 beschrieben ab.

Auch die Beschreibung einiger Details, zum Beispiel des Verhaltens, wenn der Empfänger das Bitmuster c erkennt, während der Sender die Bitmustererkennung abgeschaltet hatte, würde über diesen Beitrag hinausgehen und ist nur für Implementationen erforderlich, aber nicht für das Verständnis.

Bei fehler- und manipulationsfreier Übertragung kann der Empfänger den ursprünglichen Teilblock yi+1 rekonstruieren.

Falls einer der Teilblöcke xi,1 und xi,2 während der Übertragung verändert worden ist, ergibt sich ein fehlerhafter Teilblock yi+1, ebenso, wenn der Teilblock si manipuliert wurde.

Es gelingt also keinem Angreifer, die Teilblöcke xi,1, xi,2 und si so zu ändern, ohne dass sich beim Empfänger ein Teilblock yi+1 ergibt, dessen Inhalt vom Angreifer nicht vorherbestimmt werden kann.

Auf eine anhaltende Fehlerfortpflanzung wird zugunsten der Selbstsynchronisation verzichtet. Über eine geeignete Wahl von Systemparametern kann die Fehlerfortpflanzungsphase jedoch verlängert werden. Generell schließen sich aber eine lange Fehlerfortpflanzung und eine schnelle Selbstsynchronisation gegenseitig aus.

5 Zusammenfassung und Ausblick

Es wurde ein Verfahren zur digitalen Signatur von Bitströmen vorgestellt, das die in Tabelle 1 angegebenen Eigenschaften hat. Es kann online ausgeführt werden, ist sowohl aus kryptographischer Sicht (Public-Key-Verfahren) als auch aus übertragungstechnischer Sicht (Point-to-Multipoint-Konfigurationen) Broadcast-tauglich und anwendungsunabhängig, Die Authentifikation erfolgt in Verbindung mit höheren Schichten, da das Verfahren nur die digitalen Signaturen bereitstellt, aber nicht den Soll/Ist-Vergleich der signierten Redundanz durchführt.

Die Signaturen werden Teilen des Bitstroms im Huckepack-Verfahren aufgeladen. In der Nachrichtentechnik würde man sagen: Die Signaturen werden moduliert, wobei der Bitstrom die Funktion des Trägers übernimmt.

Die Funktionsfähigkeit des Verfahrens wurde in Testimplementationen mit verschiedenen Anwendungsszenarios nachgewiesen. Weitere Arbeiten werden sich darauf konzentrieren, auf Basis dieser Grundideen eine Theorie der Modulation von digitalen Signaturen, beziehungsweise einer asymmetrischen Codemodulation weiterzuentwickeln. Darüber hinaus muss der Zusammenhang zwischen den zahlreichen Systemparametern analytisch und simulativ untersucht werden, um ihre Abhängigkeiten festzustellen und optimale Systemeinstellungen für das Verfahren vornehmen zu können.

Literatur

[1]
R. Gennaro, P. Rohatgi, How to Sign Digital Streams, in: Advances in Cryptology – Crypto 97, Springer 1998, S. 180–197
[2]
R. Rivest, A. Shamir, L. Adleman, A Method for obtaining Digital Signatures and Public-Key Cryptosystems, Comm. ACM 21 (1978), S. 120–126
[3]
O. Jung, C. Ruland, Encryption with statistical self-synchronization in Synchronous Broadband Networks, in: Cryptographic Hardware and Embedded Systems, CHES 99, Springer 1999, S. 340–352
[4]
A. J. Menezes, P. C. van Oorschot, S. A. Vanstone, Handbook of Applied Cryptography, CRC Press, Boca Raton, USA, 1997
 
Die Beiträge zum 7. Deutschen IT-Sicherheitskongress des BSI 2001 sind erschienen im Tagungsband "2001 – Odyssee im Cyberspace? Sicherheit im Internet", 489 S., 96 DM, SecuMedia-Verlag, Ingelheim,
ISBN 3-922746-36-5

© SecuMedia-Verlags-GmbH, D-55205 Ingelheim,
KES 3/2001, Seite 31