-
TECHNISCHES
GEBIET
-
Die
Erfindung betrifft die Datenverschlüsselung und bezieht sich insbesondere
auf das Verschlüsseln von
Teilen zusammengesetzter Daten, im einzelnen von kodierten Audio-
oder Videodaten.
-
STAND DER
TECHNIK
-
Datenverschlüsselung
wird angewandt, um Informationen sicher über einen unsicheren Kanal
zu übertragen.
Auf die Information wird eine mathematische Transformation so angewandt,
daß es
sehr schwierig ist, die Transformation ungeschehen zu machen. Ein
Schlüssel,
bei dem es sich um nicht mehr als eine große Zahl handelt, steuert den
Verschlüsselungs-
und Entschlüsselungsalgorithmus.
Ein symmetrischer Schlüsselalgorithmus
benutzt den gleichen Schlüssel
zum Verschlüsseln
und Entschlüsseln
der Daten. Ein asymmetrischer Schlüsselalgorithmus benutzt zwei
verschiedene, aber verwandte Schlüssel, von denen einer zum Verschlüsseln und
der andere zum Entschlüsseln
der Daten benutzt wird.
-
Algorithmen
zur Datenverschlüsselung
sind rechnerisch eher aufwendig, besonders bei Universalprozessoren,
die Wörter
statt einzelne Bits bearbeiten. Der gegenwärtige Standardalgorithmus DES
funktioniert auf diese Weise. Allgemein gesagt ist es so, daß der Algorithmus
rechnerisch um so aufwendiger ist, je größer die Größe des Schlüssels ist.
-
Ein
sicherer Verschlüsselungsalgorithmus
geht davon aus, daß ein
Angreifer alles über
das System außer
den Schlüssel
kennt, der zum Entschlüsseln
der gestohlenen Information nötig
ist. Unter ideellen Bedingungen wäre die einzig erfolgreiche
Attacke eine erschöpfende
Schlüsselsuche,
bei der der Angreifer jeden möglichen
Schlüssel
auf den gesamten Satz verschlüsselter
Daten anwenden und dann das entschlüsselte Ergebnis analysieren
muß, um
zu sehen, ob es empfindlich war. Wenn das der einzig mögliche Angriff
ist, kann man in der Praxis das System dadurch sicher machen, daß man eine
ausreichend große
Schlüsselgröße wählt (d.
h., daß die
zum Prüfen
jedes möglichen
Schlüssels
erforderliche Zeit es praktisch undurchführbar machte).
-
In
vielen Systemen läßt sich
eine bedeutsame Schwäche
ausnutzen, um die für
die Durchführung
einer erschöpfenden
Schlüsselsuche
erforderliche Zeit zu verkürzen.
Diese Schwäche
tritt auf, wenn man von entschlüsselten
Daten weiß,
daß sie
erkennbare Information enthalten. Wüßte man beispielsweise, daß die verschlüsselten
Daten englischer Text waren, dann könnte man anhand von Statistiken
aus den entschlüsselten
Daten ermitteln, ob etwas gefunden wurde, das der englischen Sprache
nahekommt. Das würde
auf einen potentiellen Schlüssel
hindeuten. Wenn man wüßte, daß bestimmte
Wörter
innerhalb des entschlüsselten
Textes existieren, wäre
es sogar noch einfacher, potentielle Schlüssel zu finden.
-
Darüber hinaus
kann es möglich
sein, eine wirksamere, erschöpfende
Schlüsselsuche
durchzuführen, wenn
die verschlüsselten
Daten interne gegenseitige Abhängigkeiten
enthalten. Wenn die zu verschlüsselnden
Daten ein Bitstrom sind und die spezifischen Werte bestimmter Bitstromelemente
das Vorhandensein oder die Größe anschließender Bitstromelemente
bestimmen, können
diese gegenseitigen Abhängigkeiten
von einem Angreifer ausgenutzt werden. Es sei zum Beispiel angenommen,
daß eine
Bitstromsyntax auf Rahmenbasis, von der die Gesamtrahmengröße bekannt
ist und für
die ein oder mehr Parameter auf der Basis des Wertes anderer Parameter
wahlweise eingeschlossen sind. Dann könnte ein Angreifer, der eine
erschöpfende Schlüsselsuche
vornimmt, herausfinden, daß der
entschlüsselte
Bitstrom für
eine bestimmte Gruppe von Schlüsseln
den Einschluß dieser
wahlweisen Parameter anzeigt, und infolgedessen ist die Rahmengröße länger als
sie sein sollte (dies wird als ein Überlauf bezeichnet). Ein solcher
entschlüsselter
Bitstrom ist ein "unzulässiger" Bitstrom, der die
Syntax des Bitstroms verletzt. In diesem Fall kann der Angreifer
darauf schließen, daß der richtige
Schlüssel
für die
Verschlüsselung
nicht in dieser Gruppe enthalten ist, wodurch beträchtlich viel
Zeit bis zur Vollendung der erschöpfenden Suche gespart werden
könnte. Ähnliche
Fälle gibt
es bei Zuständen
des Unterlaufs, bei denen die entschlüsselte Syntax nicht genügend der
im Rahmen verfügbaren
Bits benutzt, um einen zulässigen
Bitstrom zu bilden. Und wenn schließlich einer oder mehr der Parameter
in einem Bitstrom daran gehindert sind, bestimmte Werte anzunehmen,
kann das Auftreten dieser Werte einem Angreifer helfen, Schlüssel auszuschließen (das
nennt man Zustand eines unzulässigen
Wertes, und dies ist ein weiteres Beispiel für einen unzulässigen Bitstrom,
der die Syntax des Bitstroms verletzt).
-
Eine
Möglichkeit,
um das System gegen Angriffe robuster zu machen, besteht darin,
die Daten vor ihrer Verschlüsselung
einem Hash-Vorgang zu unterziehen. Mit einer Hash-Funktion werden
die Daten randomisiert, so daß Statistiken
und Schlüsselwörter als
Hilfe bei einem Angriff nicht benutzt werden können. Bei diesem Verfahren
gibt es aber einige Probleme. Es muß angenommen werden, daß der Angreifer
die Hash-Funktion kennt und sie ungeschehen machen kann. Außerdem erfordert
die Hash-Funktion mehr Verarbeitungsleistung, was die Rechenkosten
weiter erhöht.
-
Es
gibt viele Datenreduktionssysteme, die Eingabedaten, beispielsweise
Audio- und Videodaten im Block verarbeiten. Mit diesen Systemen
werden die komprimierten Daten insgesamt in einer vorherbestimmten Weise
strukturiert. Die Daten werden in Blöcke oder Rahmen unterteilt,
die über
eine gewisse Zeit hinweg unabhängig
dekodierbar sind. Die Rahmen können
sowohl aus fester Information (d. h. von Rahmen zu Rahmen unveränderlich)
als auch aus veränderlicher
Information bestehen (d. h. sie ändert
sich von Rahmen zu Rahmen). All diese Daten in den Rahmen direkt
zu verschlüsseln
führt zu
den oben genannten Schwierigkeiten, beispielsweise die große Menge
erforderlicher Verarbeitung, sowie die Sicherheitsprobleme mit bekannten Schlüsselwörtern, die
einem Angreifer helfen könnten,
den Schlüssel
zu ermitteln. Innerhalb der festen Information enthaltene Schlüsselwörter, beispielsweise
Synchronisierwörter,
die Datentransfergeschwindigkeit und sonstige Metadaten ändern sich
weniger oder überhaupt
nicht von Rahmen zu Rahmen und könnten
von einem Angreifer dazu herangezogen werden, einen Angriff zu planen,
für den
weniger Arbeit als eine erschöpfende
Schlüsselsuche
erforderlich wäre.
-
Im
US-Patent 5 636 279 ist ein Verwürfelungsgerät offenbart,
mit dem Daten, einschließlich
eines Code von veränderlicher
Länge verwürfelt werden.
Im Fall eines Ausführungsbeispiels
empfängt
das Verwürfelungsgerät als Eingabesignal
ein MPEG-kodiertes Videosignal. Das Eingabesignal wird einer Code-Erkennungseinheit
zugeführt,
die ein Codebuch zum Reproduzieren jedes Codes hat, um den Inhalt
sämtlicher
Daten im Eingabesignal zu lesen. Auf der Grundlage des Ausgabesignals
des Code-Erkennungsgeräts
werden ausgewählte
Teile des Eingabesignals verwürfelt.
Der Bedarf an einer Code-Erkennungseinheit zum Dekodieren des empfangenen
Bitstroms vor dem Verwürfeln
macht dieses bekannte Gerät
kompliziert und teuer.
-
Es
ist bekannt, einen veränderlichen
Informationsteil eines Rahmens vor dem Zusammensetzen des Ausgabebitstroms
durch einen Kodierer zu verschlüsseln
(deutsches Patent
DE
199 07 964 C1 , US-Patent
5 636 279). Dieser Ansatz hat aber mehrere Nachteile. Er ist kompliziert,
denn die Verschlüsselung
muß innerhalb
des Kodierers statt am zusammengesetzten Bitstrom vorgenommen werden.
Diese Kompliziertheit macht ihn unpraktisch für Fälle, in denen mehrere Exemplare
eines Bitstroms, jeweils mit einem anderen Schlüssel verschlüsselt, an
mehrere Benutzer gesandt werden müssen. Wenn darüber hinaus
die Verschlüsselung
auf Daten innerhalb eines Kodierers vor der Entropiekodierung, beispielsweise
der Huffman-Kodierung angewandt wird, geht der Kodiervorteil des
Entropiekodierers durch die Verschlüsselung verloren (es besteht
die Tendenz, daß die
Daten durch die Verschlüsselung "geweißelt" werden, was weniger
redundante Stellen in den Daten übrig
läßt, die
durch Entropiekodieren reduziert werden müssen). Folglich besteht weiterhin
Bedarf an einem verbesserten Datenverschlüsselungsverfahren.
-
OFFENBARUNG
DER ERFINDUNG
-
Gemäß einem
ersten Aspekt der vorliegenden Erfindung wird dieser Bedarf durch
ein Verfahren zum Verschlüsseln
eines kodierten Bitstroms erfüllt,
der von einem Audio- oder Videokodierer zusammengesetzt ist, wobei
der zusammengesetzte, kodierte Bitstrom eine Syntax hat. In dem
zusammengesetzten, kodierten Bitstrom werden Daten ausgewählt, die
weniger ausmachen als sämtliche
Daten im Bitstrom und die, wenn sie verschlüsselt würden, zu einem teilweise verschlüsselten
Bitstrom führen
würden,
der die Syntax des zusammengesetzten kodierten Bitstroms nicht verletzt
und hätte
zur Folge, daß aus
einem nicht entschlüsselten
Dekodieren des teilweise verschlüsselten
Bitstroms wiedergegebene Audio- oder Videodaten eine verschlechterte
Qualität
hätten.
Die ausgewählten
Daten in dem zusammengesetzten, kodierten Bitstrom werden verschlüsselt, um
den teilweise verschlüsselten
Bitstrom zu ergeben. Die Syntax ist eine Abwandlung der normalen
Syntax des Kodierers für
den zusammengesetzten, kodierten Bitstrom, wenn der teilweise verschlüsselte Bitstrom die
normale Syntax des zusammengesetzten, kodierten Bitstroms verletzen
würde,
wobei die normale Syntax so abgewandelt ist, daß, wenn die ausgewählten Daten
verschlüsselt
sind, der resultierende teilverschlüsselte, modifizierte Bitstrom
die modifizierte Syntax des zusammengesetzten, kodierten Bitstroms
nicht verletzt.
-
Für Systemsicherheit
ist es nicht unbedingt erforderlich, daß ein Angreifer daran gehindert
ist, gewisse Kenntnis über
die Daten zu erlangen, die geschützt
werden sollen. Selbst wenn einige der Bitstromelemente klar sichtbar
sind, kann es, wenn ein genügend
großer
Teil des Bitstroms verschlüsselt
ist, unmöglich
sein, die Daten sinnvoll zu benutzen, ohne sie richtig zu entschlüsseln. Zum
Beispiel können
Audiodaten nutzlos sein, wenn sie unverständlich oder von schlechter
Qualität
sind, selbst wenn der Angreifer einen Teil der im Bitstrom mitgeführten, zugehörigen Metadaten
sehen kann.
-
Gemäß der vorliegenden
Erfindung wird die Sicherheit dadurch verbessert, daß nur ein
Teil eines zusammengesetzten Bitstroms statt alles verschlüsselt wird.
Es wird nicht bevorzugt, Elemente in einem zusammengesetzten Bitstrom
zu verschlüsseln,
deren Werte bekannt oder statistisch wahrscheinlich sind. Bevorzugt wird
die Verschlüsselung
derjenigen Elemente, die die höchste
Entropie im zusammengesetzten Bitstrom haben. Wenn der Kodierer
zum Beispiel einen Entropiekodieralgorithmus anwendet, wird vorzugsweise
mindestens ein Teil des entropiekodierten Datenanteils des zusammengesetzten
Bitstroms, zum Beispiel mindestens ein Teil des Bitstromdatenanteils
verschlüsselt,
der Huffman kodiert, arithmetisch kodiert oder verstärkungsadaptiv
kodiert ist (GAQ). Wenn der Kodierer einen Entropiekodieralgorithmus
verwendet, ist es vorzuziehen, mindestens einen Teil der Bitstromanteile
mit höchster
Entropie zu verschlüsseln
(zum Beispiel derjenigen Anteile, die sich nicht wiederholen und
am wenigsten vorhersagbar sind). Die Verschlüsselung eines oder mehrerer
Elemente in einem zusammengesetzten Bitstrom, die dazu führen könnte, daß der resultierende,
teilweise verschlüsselte
Bitstrom die Syntax des zusammengesetzten Bitstroms verletzt (d.
h. einen unzulässigen
Bitstrom hervorbringt, indem beispielsweise ein Überlauf, Unterlauf oder unzulässige Wertbedingungen
verursacht werden) wird nicht bevorzugt.
-
Um Überlauf-
oder Unterlaufbedingungen zu vermeiden, wenn die entropiekodierten
Datenanteile in den zusammengesetzten Bitströmen, die von gewissen Arten
von Kodierern erzeugt werden (zum Beispiel Kodierern, die mit verstärkungsadaptiver
Quantisierung arbeiten) verschlüsselt
werden, kann es sich als notwendig erweisen, die Syntax des Bitstroms
eines Kodierers abzuwandeln, damit im zusammengesetzten Bitstrom die
Daten neu angeordnet werden können.
-
Was
andere Kodierer des Entropietyps betrifft (zum Beispiel Kodierer,
die mit Huffman-Kodierung oder arithmetischer Kodierung arbeiten),
kann es zum Vermeiden von Überlauf-
oder Unterlaufbedingungen nötig sein,
die Syntax des Kodierers abzuwandeln, damit Fülldaten hinzugefügt werden
können,
indem sie zum Beispiel an das Ende des Rahmens oder Blocks angehängt werden,
in dem ein solcher Überlauf
oder Unterlauf auftritt.
-
Abgesehen
vom Verbessern der Sicherheit wird mit der vorliegenden Erfindung
die Rechenkomplexität
insgesamt verringert, da weniger Datenwörter verschlüsselt und
anschließend
entschlüsselt
werden. Die Rechenkomplexität
wird auch deshalb verringert, weil die Verschlüsselung unmittelbar an einem
zusammengesetzten Bitstrom vorgenommen wird (an der multiplexierten
Bitstromausgabe eines Kodierers). Damit wird die zusätzliche
Kompliziertheit vermieden, daß ein
Kodierer oder Dekodierer am Verschlüsselungsprozeß beteiligt
ist. Ein Vorteil des Verschlüsselns
eines zusammengesetzten Bitstroms (an dem kein Kodierer oder Dekodierer
beteiligt ist) besteht darin, daß getrennt verschlüsselte Bitströme für verschiedene
Märkte
und/oder Ziele vorbereitet werden können.
-
Das
Verschlüsseln
großer
Datenmengen ist rechnerisch aufwendig. Es wäre nützlich, wenn man Daten mit
geringen Rechenkosten an der Verteilerstelle verschlüsseln könnte. Damit
wäre sichergestellt,
daß jederzeit
Daten für
eine begrenzte Anzahl von Endnutzern personalisiert werden könnten. Beispielsweise
wird in einem Video-Abrufsystem (VOD) eine große Menge Daten verschlüsselt und über ein
Netz verteilt. Wenn dieser Inhalt in verschlüsseltem Format gespeichert
wird, bleibt der Schlüssel
gleich zum Entschlüsseln
des Materials. Sobald ein Benutzer einen Schlüssel für die Entschlüsselung
erwirbt, hätte
er immer Zugang zu dem Material. Wenn eine Verschlüsselung
an der Verteilerstelle möglich
wäre, gäbe es eine
bessere Kontrolle über den
Inhalt. Das ist gemäß der vorliegenden
Erfindung möglich,
weil die Verschlüsselung
an einem zusammengesetzten Bitstrom vorgenommen wird, statt während des
Kodierverfahrens vor dem Zusammensetzen des kodierten Bitstroms.
-
Die
vorliegende Erfindung beschreibt, wie die Verschlüsselung
von einem Komprimierungssystem auf eine Weise getrennt werden kann,
die die Rechenkosten für
die Sicherheit senkt. Außerdem
wird ein Verteilungsmodell gestützt,
in dem dies anwendbar ist, um die an Endnutzer übertragenen Daten zu schützen.
-
BESCHREIBUNG
DER ZEICHNUNGEN
-
1 ist
ein konzeptuelles Blockdiagramm und zeigt insgesamt, wie Verschlüsselung
gemäß Aspekten
der vorliegenden Erfindung angewandt wird.
-
2 ist
ein konzeptuelles Blockdiagramm und zeigt insgesamt wie Entschlüsselung
gemäß Aspekten
der vorliegenden Erfindung angewandt wird.
-
3 ist
ein idealisiertes Diagramm (nicht maßstabsgerecht) und zeigt das
Format eines mit einem Transformationskodierer erzeugten typischen,
kodieren Audiorahmens, in dem die Audiodaten durch Exponenten und
quantisierte Mantissen dargestellt sind.
-
4 ist
ein konzeptuelles Blockdiagramm und zeigt insgesamt, wie Verschlüsselung
gemäß Aspekten
der vorliegenden Erfindung angewandt wird, wobei die Bitstromsyntax
modifiziert wird.
-
5 ist
ein konzeptuelles Blockdiagramm und zeigt insgesamt, wie Entschlüsselung
gemäß Aspekten
der vorliegenden Erfindung angewandt wird, wobei die Bitstromsyntax
modifiziert wird.
-
BESTE ART
UND WEISE ZUM AUSFÜHREN
DER ERFINDUNG
-
1 ist
ein konzeptuelles Blockdiagramm und zeigt insgesamt, wie Verschlüsselung
gemäß Aspekten
der vorliegenden Erfindung angewandt wird. Ein Audio- oder Videosignal
wird einer Audio- oder
Videokodierfunktion oder einem solchen Verfahren 2 zugeführt, dessen
Ausgabe an eine Multiplexerfunktion bzw. ein solches Verfahren 4 weitergegeben
wird, um einen kodierten Bitstrom gemäß einer Syntax zusammenzusetzen.
Die Multiplexerfunktion oder das Verfahren ist üblicherweise Teil der Kodierfunktion
oder des Verfahrens, ist aber hier zum Zweck der Erläuterung
getrennt gezeigt. Der zusammengesetzte, kodierte Bitstrom wird dann durch
eine Verschlüsselungsfunktion
oder ein solches Verfahren 6 verschlüsselt, wozu ein Schlüssel benutzt wird,
wie schon gesagt. Die Auswahl eines bestimmten Verschlüsselungsverfahrens
hat für
die Erfindung keine kritische Bedeutung. Ausgabe der Verschlüssefungsfunktion
oder des Verfahrens ist ein geschützter Bitstrom. In dem geschützten Bitstrom
sind weniger als sämtliche
Daten im Bitstrom verschlüsselt,
der teilweise verschlüsselte
Bitstrom verletzt nicht die Syntax des zusammengesetzten, kodierten
Bitstroms vom Multiplexer 4 und würde wiedergegebene Audio- oder
Videodaten, die aus einem nicht entschlüsselten Dekodieren des teilweise
verschlüsselten
Bitstroms resultieren, in verschlechterter Qualität ergeben.
Der Grad der Verschlechterung hängt
mindestens davon ab, wie viel des Bitstroms verschlüsselt ist,
sowie von der angewandten Verschlüsselung. Ein akzeptables Niveau
an Qualitätsverschlechterung
kann vom Benutzer bestimmt werden.
-
2 ist
ein konzeptuelles Blockdiagramm und zeigt insgesamt, wie Entschlüsselung
gemäß Aspekten
der vorliegenden Erfindung angewandt wird. Der geschützte Bitstrom
wird einer Entschlüsselungsfunktion oder
einem entsprechenden Verfahren 8 zugeführt, welches den gleichen Schlüssel empfängt, der
auch von der Verschlüsselungsfunktion
oder dem Verfahren 6 zum Verschlüsseln des geschützten Bitstroms
angewandt wird. Der entschlüsselte
Bitstrom wird dann von einer Demultiplexerfunktion oder einem solchen
Verfahren 10 demultiplexiert und einer Audio- oder Videodekodierfunktion
oder einem solchen Verfahren 12 zugeführt, mit dem ein dekodiertes
Audio- oder Videosignal erhalten wird. Bei Fehlen eines richtigen
Schlüssels,
der auf die Entschlüsselungsfunktion
oder das Verfahren 8 angewandt wird, hat das wiedergegebene
Audio- oder Videosignal eine verschlechterte Qualität.
-
Aspekte
der Erfindung gelten sowohl für
Audio- als auch Videokodierer und Dekodierer, insbesondere perzeptuelle
Kodierer und Dekodierer, in denen Audio- oder Videosignale der Zeitdomäne in die
Frequenzdomäne übertragen
und Frequenzkoeffizienten unter Verwendung perzeptueller Modelle
quantisiert werden, um die Datenmenge in der Ausgabe des Kodierers
zu verringern. Ein großer
Anteil der Daten in einem perzeptuellen Audio- oder Videokomprimiersystem
sind entropiekodierte Daten. Diese Daten treten im allgemeinen am gleichen
Ort in den kodierten Rahmen mit der Rahmenrate des Komprimierungssystems
auf. Gemäß der vorliegenden
Erfindung kann zum Beispiel ein Distributionsserver (ein Server,
der Audio- oder Videoinhalt an mehrere Benutzer verteilt) nur einen
kleinen Anteil der Daten an einem festen Ort in Rahmen verschlüsseln, während er
zusammengesetzte Bitströme übermittelt.
Damit wäre
es nicht mehr nötig,
daß der
Server den Bitstrom syntaktisch analysiert (den Bitstrom teilweise
dekodiert, um Anteile hoher Entropie des Bitstroms zu identifizieren)
und spezifische Teile der Daten verschlüsselt oder den Bitstrom dekodiert
verschlüsselt
und neu kodiert.
-
Wenn
man Systeme zur Audiodatenreduzierung betrachtet, beispielsweise
MPEG-AAC, Dolby E oder Videoreduzierungssysteme, wie MPEG-1, 2 und
4, so enthalten diese alle eine Art von Entropiekodierer als Teil
des Komprimierungsalgorithmus ("Dolby" ist ein Warenzeichen
der Dolby Laboratories Licensing Corporation). Ein Entropiekodierer
reduziert die Datengröße dadurch,
daß er
Redundantes aus dem Datensatz entfernt. Der entropiekodierte Datensatz
hat eine "geweißelte" Charakteristik,
weil durch die Bearbeitung die Wahrscheinlichkeitsdichtefunktion
(PDF) abgeflacht wird. Dieser Datensatz ist für die Verschlüsselung
optimal, da aus ihm auf sehr wenig Information geschlossen werden
kann. Der Entropiekodierer erzeugt eine Ausgabe, die der eines Hash-Datensatzes ähnlich ist.
-
Interessant
sind auch andere Systeme zur Reduzierung von Audio- und Videodaten,
beispielsweise das Audiosystem Dolby AC3, bei denen keine Entropiekodierung
als Teil des Komprimierungsalgorithmus angewandt wird, die aber
trotzdem Bitströme
generieren, die Anteile haben, in denen die Entropie höher ist
(zum Beispiel die quantisierten Mantissen der Frequenzkoeffizienten)
als in anderen Anteilen (zum Beispiel Synchronisierwörter, Bitstrominformation
und dergleichen).
-
In
solchen Audio- und Videodatenreduzierungssystemen, die mit Entropiekodierung
oder anderen Arten von Kodierung arbeiten, bei denen Bitstromanteile
hoher Entropie erzeugt werden, identifiziert die Syntax des Kodieralgorithmus
diejenigen Bereiche des zusammengesetzten Datenstroms, die entropiekodiert
sind oder hohe Entropie haben. Üblicherweise
gehören
zu entropiekodierten Bereichen oder Bereichen mit hoher Entropie
Skalenfaktoren, Exponenten und quantifizierte Koeffizienten. Die
entropiekodierten Daten oder Daten mit hoher Entropie machen üblicherweise
einen großen
Prozentsatz des zusammengesetzten Bitstroms aus und befinden sich
häufig
am Ende eines Rahmens. Da solche entropiekodierten Bereiche oder
Bereiche mit hoher Entropie sich meistens in jedem Rahmen an der
gleichen Stelle befinden, lassen sie sich zum Verschlüsseln und
Entschlüsseln
ohne weiteres auffinden, so daß das
komplizierte syntaktische Analysieren oder Dekodieren des Bitstroms,
um alles oder einen Teil desselben zu verschlüsseln, vermieden wird.
-
3 ist
ein idealisiertes Diagramm (nicht maßstabsgerecht) und zeigt das
Format eines typischen kodierten Audiorahmens, der mit einem Transformationskodierer
erzeugt wurde, wobei die Audiodaten durch Exponenten und quantisierte
Mantissen wiedergegeben sind (zum Beispiel Dolby AC3, näher beschrieben
in der Veröffentlichung
Digital Audio Compression (AC-3) Standard. Genehmigt am 10. November
1994 (Rev 1) Annex A hinzugefügt
am 12. April 1995. (Rev 2) 13 corrigendum hinzugefügt am 24.
Mai 1995. (Rev 3) Annex B und C hinzugefügt am 20. Dezember 1995). Bei
diesem Beispiel hat jeder Rahmen eine gleichbleibende Länge (die
gleiche Anzahl Bits). Typischerweise beginnt jeder Rahmen mit einigen
Synchronisierbits, gefolgt von Bitstrominformation (BSI), Exponenten
und quantisierten Mantissen. Die Daten mit der höchsten Entropie sind quantisierte
Mantissen am Ende des Rahmens. Die quantisierten Mantissen oder
ein Teil der quantisierten Mantissen (wie gezeigt) sind vorzugsweise
verschlüsselt.
Wenn das gemacht wird, erhält
man eine wesentliche Verschlechterung des dekodierten Bitstroms,
wenn der Bitstrom nicht ordnungsgemäß entschlüsselt wird. Eine weniger starke
Verschlechterung ergibt sich, wenn die Exponenten oder ein Teil
derselben verschlüsselt werden
(die Exponenten haben eine niedrigere Entropie als die quantisierten
Mantissen). Es ist unerwünscht, das
Synchronisierwort oder die BSI-Bits zu verschlüsseln, weil sie sich von Rahmen
zu Rahmen wiederholen oder vorhersagbar sind, und eine solche Verschlüsselung
einem Angreifer nur helfen würde.
-
Um
die größtmögliche Sicherheit
zu erhalten, sollte der teilweise verschlüsselte Bitstrom Idealerweise die
Syntax des Kodierers nicht verletzen, sollte aber, wenn dekodiert,
zu einer Ausgabe verschlechterter Qualität führen. Wenn der Bitstrom die
Syntax des Kodierers verletzt, wird ein Angriff vereinfacht, denn
der Angreifer braucht nur einen Schlüssel zu finden, der die Bitstromsyntax
zulässig
macht. Ist jedoch die Bitstromsyntax zulässig, ist ein Angriff schwieriger,
denn der Angreifer braucht nur einen Schlüssel zu finden, der die Audio- oder
Videoqualität
wiederherstellt, eine viel komplexere Aufgabe und noch dazu eine,
die unter Umständen schwer
zu automatisieren ist.
-
Einen
Teil eines von einigen Kodierern erzeugten Rahmens oder einen solchen
ganzen Rahmen zu verschlüsseln
kann zu einem unzulässigen
Bitstrom führen,
einem Bitstrom, der die Syntax des Kodierers verletzt. Ein derartiger
Bitstrom wäre
nicht von einem Dekodierer "dekodierbar", der einen Bitstrom
entsprechend der Kodierersyntax erwartet, womit die Aufgabe eines
Angreifers vereinfacht wäre,
wie gerade erwähnt.
Zum Beispiel enthalten einige entropiekodierte Daten (zum Beispiel
Huffman-kodierte Daten) Rückwärtsabhängigkeiten,
die durch Verschlüsselung
aufgebrochen werden. Derartige zerstörte Abhängigkeiten haben zur Folge, daß der Dekodieralgorithmus
mit dem Dekodieren des Rahmens vor dem Ende des Rahmens aufhört oder
mit dem Dekodieren über
das Ende des Rahmens hinaus fortfährt. Das sind dann Überlauf-
und Unterlaufbedingungen, die einem Angreifer den Hinweis geben
würden,
daß nicht
der richtige Schlüssel
benutzt wurde, was einen Angriff wesentlich vereinfachen würde. Das
System ist sicherer, wenn der Angreifer gezwungen wird, andere Mittel
heranzuziehen, um festzustellen, ob der richtige Schlüssel vorliegt,
beispielsweise, nach einem Schlüssel
zu suchen, der verschlechterte Audio- oder Videodaten wiederherstellt.
-
Um
das Problem der Verschlüsselung
entropiekodierter Daten zu überwinden,
ist eine Abwandlung der Bitstromdaten nötig, zum Beispiel eine Bitstromneuanordnung
oder das Hinzufügen
von Fülldaten,
und damit eine Modifizierung der Bitstromsyntax. 4 zeigt
insgesamt, wie das erreicht werden kann. Ein Audio- oder Videosignal
wird einer Standardfunktion oder einem Standardverfahren 14 eines
Kodierers der Entropieart unterzogen. Der von der Kodierfunktion
oder dem Verfahren 14 hervorgebrachte, zusammengesetzte,
kodierte Bitstrom wird einer Syntaxmodifizierfunktion oder einem
solchen Verfahren 16 zugeleitet. Der Bitstrom wird dann
von einer Verschlüsselungsfunktion
oder einem solchen Verfahren 18 in Übereinstimmung mit einem angewandten
Schlüssel
unterzogen, um den Bitstrom zu modifizieren. Damit entspricht der
modifizierte Bitstrom der modifizierten Syntax, um den geschützten Bitstrom
zu erzeugen. In der Praxis können
die Funktionen, nämlich
Syntaxmodifizierfunktion oder Verfahren 16 und Verschlüsselungsfunktion
oder Verfahren 18 in enger Beziehung zueinander stehen.
Sie sind lediglich zum Zweck der Erläuterung als getrennte Funktionen gezeigt.
Wie aus 5 hervorgeht, wird der geschützte Bitstrom
einer Entschlüsselungsfunktion
oder einem solchen Verfahren 20 unterzogen, welches den
gleichen Schlüssel
erhält,
wie die Verschlüsselungsfunktion oder
das Verfahren 18. Die Entschlüsselungsfunktion oder das Verfahren 20 stellt
auch den modifizierten Bitstrom in seinem nicht modifizierten Zustand
wieder her (wie er vom Entropiekodierer 14 erzeugt wurde).
Eine Syntaxwiederherstellungsfunktion oder ein solches Verfahren 22 stellt
die ursprüngliche
Syntax des durch die Entropiekodierfunktion oder das entsprechende
Verfahren 14 erzeugten Bitstroms wieder her. Wie im Fall
der Funktionen 16 und 18 gemäß 3 können in
der Praxis die Funktionen, nämlich
die Entschlüsselungsfunktion
oder das Verfahren 20 und die Syntaxwiederherstellungsfunktion
oder das Verfahren 22 in enger Beziehung zueinander stehen
oder miteinander kombiniert sein und sind hier nur zum Zweck der
Erläuterung
als getrennte Funktionen gezeigt. Der wiederhergestellte Bitstrom
mit seiner ursprünglichen
Syntax wird einer Standardfunktion bzw. einem Verfahren 24 einer
Entropiedekodierung unterzogen, womit ein dekodiertes Audio- oder
Videosignal erhalten wird.
-
Huffman-Kodierung
-
Die
Huffman-Kodierung ist ein Beispiel einer Entropiekodierung, die
nicht auf konventionelle Weise verschlüsselt werden kann, ohne die
Zulässigkeit
des resultierenden Bitstroms zu beeinflussen. Diese Art der Entropiekodierung
bringt einmalig dekodierbare Symbole auf der Grundlage der Wahrscheinlichkeiten
des Auftretens jedes Symbols hervor. Die folgende Tabelle zeigt
einen Beispielsatz von Symbolen, Wahrscheinlichkeiten für die Symbole
und zwei Sätze
möglicher
Huffman-Codes. Es sei darauf hingewiesen, daß jede beliebige Kombination
von Codewörtern
einmalig dekodierbar ist.
-
-
Bei
praktischen Verwirklichungen der Huffman-Kodierung sind mehrere
Sätze im
voraus berechneter Huffman-Codes im Kodierer und Dekodierer festgelegt,
so daß diese
Codebücher
in den komprimierten Bitstrom nicht eingeschlossen zu werden brauchen.
Der Kodierer wählt
das Codebuch aus, das die größte Kodierverstärkung bietet.
Die Schwierigkeit bei der herkömmlichen
Verschlüsselung
der Huffman-Daten besteht darin, daß die verschlüsselten
Daten sich nicht ordnungsgemäß dekodieren
(assen (d. h. das Ergebnis ist ein unzulässiger Bitstrom), so daß sie einem
Angreifer nützliche
Information bieten.
-
Das
folgende Beispiel zeigt in der zweiten Zeile der Tabelle die kodierte
Ausgabe der Huffman-kodierten
Symbole 0, 1, 2, 3, 4 unter Verwendung des Codewort 1 aus der obigen
Tabelle. Aus Gründen
der Klarheit ist in diesem Beispiel zwischen jedem der kodierten
Symbole in Zeile 2 ein Zwischenraum gezeigt. Zeile 3 zeigt die kodierte
Ausgabe ohne Zwischenräume.
Eine einfache Verschlüsselungstechnik,
nämlich
die Umkehr jedes Bits, ist auf die Daten angewandt und die entsprechende
Ausgabe in der vierten Zeile der Tabelle zu sehen. Zeile 5 zeigt
die verschlüsselten
Daten mit umgedrehten Bits, die aber syntaktisch analysiert und
in Gruppen von Codewörtern
des Codewortsatzes 1 in Abständen
voneinander zu sehen sind. Die letzte Zeile zeigt die ausgegebenen
Symbole entsprechend jedem Codewort in der fünften Zeile. Der Code "01" ergibt also eine Ausgabe von "1", und Codewort "1" ergibt
eine Ausgabe von "0".
-
-
Ein
Angreifer, der die Anzahl der Eingabesymbole kennt (es wird davon
ausgegangen, daß ein
Angreifer diese Kenntnis hätte),
der aber nicht den richtigen Schlüssel zum Entschlüsseln hat,
würde die
unrichtigen, dekodierten Ausgabesymbole erhalten, die in Zeile 6
gezeigt sind. Der Angreifer würde
merken, daß es
nicht zugeordnete, verschlüsselte
Ausgabesymbole gibt (Zeile 5), würde
aber vermutlich annehmen, daß der
Huffman-kodierten Ausgabe (Zeile 3) vor dem Verschlüsseln Bits
zum Auffüllen
hinzugefügt
worden seien. Ein Angreifer, der ein Auffüllen vermutet, erhielte also
die in Zeile 7 gezeigten dekodierten Ausgabesymbole, (obwohl der
Angreifer wahrscheinlich diese erweiterte Ausgabe nicht beachten
würde,
wenn er annahm, daß ein
Auffüllen
stattgefunden hatte und wußte,
daß es
nur fünf
Symbole geben sollte. Aber bei diesem Beispiel wurden der Huffman-kodierten Ausgabe
in Zeile 3 keine willkürlichen
Bits zum Auffüllen
hinzugefügt.
Wenn solche Auffüllbits
hinzugefügt
worden wären,
hätte es
sogar noch mehr zusätzliche
dekodierte Ausgabesignale gegeben. Auf jeden Fall findet der Angreifer
einen unzulässigen
Bitstrom, erhält
aber keinerlei Information, die für den Angriff nützlich ist.
Wie aber weiter unten noch erklärt
wird, ist es wünschenswert,
der Huffman-kodierten Ausgabe Bits zum Auffüllen hinzuzufügen, um
einen Angriff noch schwieriger zu machen, wenn es bei fehlenden Auffüllbits zu
einem Unterlauf käme.
-
Beim
vorhergehenden Beispiel und beim folgenden Beispiel ... sind die
externen Bits am Ende der verschlüsselten Ausgaben (die in den
dekodierten Symbolen das "?" ergeben) unbeachtlich,
denn in praktischen Systemen wird bei einem Bitzuteilungsprozeß selten
genau zugeteilt, so daß es
immer einige übrigbleibende Bits
gibt.
-
Das
folgende Beispiel zeigt, daß das
Hinzufügen
von Auffüllbits
im Fall von Unterlaufbedingungen Schutz gegen Angreifer bietet.
-
-
In
diesem Beispiel für
Unterlauf sind willkürliche
Bits "1010" der verschlüsselten
Ausgabe hinzugefügt. Infolgedessen
gibt es sechs Eingabesymbole und sechs Ausgabesymbole (ohne Auffüllung hätte es nur
vier Ausgabesymbole gegeben). Die vier-Bit Auffüllung verhindert also einen
Unterlauf, der einem Angreifer nützliche
Information gegeben hätte.
-
Verstärkungsadaptive
Quantisierung
-
Verstärkungsadaptive
Quantisierung ist eine Art von Entropiekodierung; unterschiedlich
von der Huffman-Entropiekodierung, die die veränderliche Codewortlänge auf
zwei unterschiedliche Zustände
begrenzt. Verstärkungsadaptive
Quantisierung ist im US-Patent 6 246 345 von Davidson, Grant; Robinson,
Charles; Truman, Michael, "Using
Gain Adaptive Quantization and Non-Uniform Symbol Lengths for Improved
Audio Coding" beschrieben;
dieses Patent wird in seiner Gesamtheit durch diesen Hinweis hier
eingeschlossen.
-
Verstärkungsadaptive
Quantisierung teilt einen Satz Zahlen in zwei Gruppen. Eine Gruppe
enthält
kleinere Zahlen, die weniger Stellen brauchen, um die gewünschte Auflösung auszudrücken, während die
andere Gruppe die restlichen größeren Zahlen
enthält.
Dekodierungseffizienz leitet sich aus der Tatsache ab, daß die kleineren
Zahlen häufiger
auftreten, was zu einer schiefen Verteilung führt.
-
Es
gibt verschiedene Möglichkeiten,
wie diese Art von Daten zu einem Ausgabestrom formatiert werden
können.
Eine Möglichkeit
sieht vor, jedes Element der Reihe nach in den Strom einzusetzen.
Insgesamt stammen die Elemente aus dem kleinen Satz, so daß ein Steuercode
benutzt wird, um das Vorhandensein eines Elements aus dem großen Satz
anzuzeigen. Der folgende Beispielsstrom zeigt eine gemischte Gruppe aus
kleinen (S) und großen
(L) Zahlen mit Steuercodes (E):
SSSSELSSELSSSS
-
S-Zahlen
und E-Zahlen enthalten die gleiche Anzahl Bits (für ein bestimmtes
perzeptuelles Modell der Bitzuteilung), sind aber anhand ihrer Bitmuster
zu unterscheiden. Es gibt eine feste Anzahl S- der Bitzuteilung), sind aber anhand
ihrer Bitmuster zu unterscheiden. Es gibt eine feste Anzahl S- und E-Zahlen – eine für jeden Frequenzkoeffizienten
(der verstärkungsadaptive
Quantisierung anwendende Kodierer ist ein Transformationskodierer,
bei dem die Frequenzkoeffizienten quantisiert sind). Auch wenn die
L-Zahlen alle die gleiche Länge
haben (für
ein bestimmtes perzeptuelles Modell der Bitruteilung), gibt es eine
veränderliche
Anzahl L-Zahlen, was zu einer veränderlichen Bitstromlänge führt und
folglich zu einem unzulässigen
Bitstrom, wenn der Strom verschlüsselt
wird (d. h. eine Unterlaufbedingung). Eine Möglichkeit, dieses Problem zu überwinden,
besteht darin, den Datenstrom so neu zu ordnen, daß die größeren Zahlen
(L) ans Ende des Stroms gestellt werden:
SSSSESSESSSS LL
-
In
diesem umarrangierten Datenstrombeispiel gibt es zwei Gruppen von
Codewörtern – die kleinen Zahlen
und Steuercodes sind eine, und die großen Zahlen eine weitere. Jede
Gruppe enthält
innere Elemente, die die gleiche Länge haben. Nur die Gruppe der
großen
Zahlen kann verschlüsselt
werden, ohne daß es
zu dem oben genannten Kodierproblem veränderlicher Länge kommt.
Der erste Satz kleiner Zahlen und Steuercodes enthält nützliche
Information für
einen Angreifer, denn die Anzahl der Steuercodes gibt einen Hinweis auf
die Anzahl von Elementen in der großen Gruppe. Eine einen Unterlauf
verursachende, unzulässige
Syntax könnte
auftreten, wenn der verschlüsselte
Satz kleiner Zahlen und Steuercodes ohne den richtigen Schlüssel dekodiert
wird. Nur den großen
Satz zu verschlüsseln,
würde die
Qualität
des Ausgabesignals ohne den richtigen Schlüssel stark beeinträchtigen.
Mit einer anderen möglichen
Umordnung werden die Steuercodes aus der kleinen Gruppe entfernt.
Diese Codes werden dann in noch eine andere Gruppe gegeben, um den
richtigen Ort einer großen
Zahl anzuzeigen. Dann wäre
es möglich,
die kleine Gruppe ohne feste Codes (Steuercodes) zu verschlüsseln. Allerdings
hätte dies
den Nachteil, daß die
Bitstromsyntax in der in 3 und 4 gezeigten
Art abgewandelt werden müßte, wie
oben beschrieben. Ausgehend von dem letzten obigen Beispiel zeigt beispielsweise
das "5te" Element und das "8te" Element die Positionen
in den S-Codewörtern,
an denen die L-Codewörter
angeordnet werden sollten.
5te 8te SSSSSSSSSS LL
-
Es
sollte klar sein, daß die
Verwirklichung weiterer Abänderungen
und Abwandlungen der Erfindung und ihrer verschiedenen Aspekte für den Fachmann
auf der Hand liegen, und daß die
Erfindung nicht durch diese speziellen, beschriebenen Beispiele
beschränkt
ist. Daher wird erwogen, mit der vorliegenden Erfindung jegliche
und alle Abwandlungen, Änderungen
oder Äquivalente
abzudecken, die in den wahren Sinn und Umfang der hier offenbarten
und beanspruchten grundlegenden Prinzipien fallen.
-
Die
vorliegende Erfindung und ihre verschiedenen Aspekte können als
Softwarefunktionen verwirklicht werden, die in digitalen Signalprozessoren,
programmierten digitalen Universalrechnern und/oder speziellen digitalen
Rechnern ausgeführt
werden. Schnittstellen zwischen analogen und digitalen Signalströmen können in
geeigneter Hardware und/oder Firmware verwirklicht werden.
