Home
 

Kryptographie -- Multimedia Security, MPEG

Einleitung

Am 15. und 16. Jannuar 1999 fand das Proseminar Kryptographie des WS 1998/99 statt. Dies sind die Unterlagen zum 4. Teil der Gruppe "Multimedia Security"; dabei geht es um MPEG Security.

Das Referat wurde in 4 Teile aufgeteilt, wobei Teil 4 von mir stammt. Hier sind Teil1, Teil 2 und Teil 3 zu finden.

Die Folien zum Vortrag stehen zum Download bereit: Folien - PS (182k) oder Folien - PS, gzip'ed (55k).

MPEG Überblick

Dieser Abschnitt bietet eine kleine Einführung in MPEG-2, jenes Datenformat welches wir im folgenden verschlüsseln wollen. Jeder der dieses Format bereits kennt kann diesen Abschnitt getrost überspringen; er wird nichts neues bieten.

MPEG-2 liegt ein Schichtenmodell zugrunde, von der obersten Schicht - dem Video - bis hinunter zu einem Block - einem 8x8 Pixel großem Bildteil. Dieses sieht wie folgt aus:

Codierung eines MPEG-2 Videos
  • Ein MPEG-Video besteht aus vielen Gruppen von Bildern (group of pictures, GOP).
  • Eine GOP besteht aus einer Reihe von I, P und B Frames. Ein I-frame (intra-coded) ist ein vollstöndiges Bild, codiert im JPEG Format. Ein P-frame (predictive-coded) stellt eine Bewegung im letzten Frame dar; dies kann durch einen Bewegungsvektor eines Blocks mit Fehleranpassung geschehen oder durch vollständige Neucodierung eines Blocks (analog zu I-frames). Als Referenz kann ein vorhergehender I oder P-frame dienen. B-frames (bidirectional predictive-coded) ist ähnlich zu P-frames, jedoch kann als Referenz auch ein zukünftiger I oder P-frame dienen. B-frames bieten die beste Kompression, I-frames die schlechteste.
  • Ein Frame besteht aus 16x16 Pixel großen Macroblöcken.
  • Ein Macroblock besteht aus 8x8 Pixel großen Blöcken: 4 Luminanz-Planes (Grauwerte, Y) und 2 Chrominanz (Farbwerte, Cr und Cb).

Ein Block (8x8 Pixel) wird dann auf folgende weise codiert:

Codierung eines Macroblocks
Discrete Cosine Transform (DCT)
Als Ergebnis erhält man eine 8x8 Matrix. Diese liefert eine gute Aproximation von Zeilen selbst wenn man nur wenige ausgewählte Koeffizienten zur Verfügung hat. Die Werte werden DC und A1 bis A63 genannt. Deren Reihenfolge ist durch das Zig-zag Muster festgelegt.
Quantization (Quant)
Durch das Quantifizieren werden die Matrizenwerte auf bestimmte festgelegte werde reduziert. Dadurch werden weniger Bits für die Darstellung benötigt, es entstehen dabei jedoch Rundungsfehler und bilden die Hauptquelle für Qualitätsverluste.
Zig-zag Scan (Zig-zag)
Hierbei wird die 8x8 Matrix auf einen 1x64 Vector abgebildet. Grund dafür ist das die Werte in der linken oberen Ecke der Matrix groß sind, rechts unten jedoch klein, im Idealfall sogar Null. Dies ermöglicht eine bessere RLE, die gleich beschrieben wird.
Zig-zag Scan Muster

Zig-zag Scan Muster
Run Length Encoding (RLE)
Im Vector befinden sich nun viele Nullen, hauptsächlich an dessen Ende. Daher wird der Vector dargestellt als (skip, value) Paare. skip gibt die Anzahl der folgenden Nullen, value den nächsten Wert (ungleich Null) an.
Huffman Coding
Möglichst optimale Darstellung der Restdaten. (Länge eines Datums proportional zu dessen Auftrittswahrscheinlichkeit).

Eigenschaften für Verschlüsselung

Im folgenden werden einige wesentliche Eigenschaften aufgeführt, die für die Verschlüsselung nützlich sind.

  • In einem MPEG-2 Datenstrom gibt es eine gleichmäßige Frequenzverteilung (frequency distribution) von Byte-Werten, d.h. jeder mögliche Bytewert tritt im Datenstrom ca. gleich oft auf.
  • Jede Nachbarschaft von Byte-Werten (256x256 Werte, frequency distribution of diagrams) ist möglich.
  • Als Schlußfolgerung ergibt sich, daß Perioden in einem MPEG-2 Datenstrom kaum auftreten. Für Bereiche von 1/16 Frame kann dies praktisch ausgeschlossen werden.

Eigenschaften für das Brechen

Nun folgt eine wesentliche Eigenschaften für das Brechen.

  • Nach der Quantifizierung (Quant) befinden sich alle großen Werte in der linken oberen Ecke, der größte oft ganz links oben. Dadurch ergibt sich die Chance ein Bild zu erraten wenn man eine Permutation der Daten kennt.

5 Algorithmen

Naive Algorithm

Dabei kommen bekannte Verschlüsselungsalgorithmen zu Einsatz. Auf die Besonderheit von MPEG-2 wird keine Rücksicht genommen.

Sicherheit
So sicher wie das verwendete Verfahren, also relativ hoch.
Geschwindigkeit
Langsam, da blind alles verschlüsselt wird.
Datenstromgröße
Keine änderung.

Pure Permutation Algorithm

Dabei wird der Datenstrom aus der MPEG-2 Codierung mittels eines Permutationsschlüssels permutiert. Diese Methode ist jedoch anfällig für die known-plaintext Attacke, da man nur den Plaintext mit dem Ciphertext vergleichen muß. Aufgrund der gleichmäßigen Verteilung der Daten im Strom sollte 1 I-frame zum Brechen genügen; dieser kann z.B. aus einem bekannten Firmenlogo stammen. Die gleichmäßige Verteilung spielt deshalb eine Rolle, weil man z.B. bei 3 Nullen nicht sagen kann wie die richtige Reihenfolge lautet; durch die gleichmäßige Verteilung ist ein wiederholtes auftreten dieser Alle-3-Stellen-Gleich Kombination recht unwahrscheinlich.

Sicherheit
Wenig sicher.
Geschwindigkeit
Sehr schnell.
Datenstromgröße
Keine änderung.

Zig-Zag Permutation Algorithm

Das bekannte Zig-zag Muster wird hierbei durch eine Permutation verändert. Diese Methode ist anfällig für die known-plaintext Attacke und die ciphertext-only Attacke. Bei der known-plaintext Attacke kann durch einfachen Vergleich die Permutation gefunden werden. Die ciphertext-only Attacke ist auch erfolgreich, da sich die großen Werte (DC und unteren ACs) in der linken oberen Ecke sammeln. Ein richtiges Raten der ersten fünf Werte liefert schon ein brauchbares Bild.

Es gibt noch zwei Erweiterungen, die jedoch auch wenig brauchbar sind.

  • Es wird eine Binary coin flipping sequence und 2 Permutationsschlüssel verwendet. Die "Münze" entscheidet welcher Schlüssel für einen Block verwendet wird. Dies hilft nicht wesentlich, da sich die großen Werte in der linken oberen Ecke befinden; beim falschen Schlüssel sind sie irgenwie verteilt. Im Endeffekt verdoppelt man nur den benötigten Rechenaufwand für das Brechen.
  • Alternativ kann man die kritischen DC-Werte aus 8 Blöcken sammeln, mit z.B. DES verschlösseln und getrennt übertragen. Dies entspricht im wesentlichen SECMPEG 2nd level welches später beschrieben wird.
Sicherheit
Unsicher.
Geschwindigkeit
Sehr schnell.
Datenstromgröße
Großer (über 30%) Zuwachs, da durch die Permutation die RLE der großen Nuller-Blöcke behindert wird.

Selective Algorithm

Dies sind alle Algorithmen, die sich der MPEG-2 Layer Struktur bedienen um nur gewisse, ausgewählte Teile zu verschlüsseln. Basis hierfür ist, daß ein Datenstrom nutzlos ist wenn die I-frames fehlen; daher werden nur diese verschlüsselt, der Rest (P, B-frames) ist dann unbrauchbar. Dieser an sich brauchbare Ansatz bietet einige Probleme: Zum einen können I-frames Teile in P- und B-frames eingebettet sein und so zu sichtbaren Teilen führen. Abgesehen davon kann man bei Videos, wo sich der Hintergrund relativ wenig ändert auch ohne I-frames gewisse Bewegungen erkennen. Die Sicherheit dieses Verfahrens kann durch übermäßige Verwendung von I-frames gesteigert werden, da so mehr Bildteile verschlüsselt übertragen werden. Jedoch steigt so auch die Größe des Datenstroms unnötig an.

SECMPEG nutzt die oben beschriebene Basis. Für die Verschlüsselungsteile wird DES oder RSA verwendet. Es erfolgt eine Einteilung in 4 Sicherheitsebenen:

  1. Header verschlüsseln.
  2. Header, DC und die ersten ACs verschlüsseln.
  3. Alle I-frames, auch die in B- und P-frames eingebetteten, verschlüsseln.
  4. Alles verschlüsseln (siehe Naive Algorithm).

Nachteil von SECMPEG ist daß es nicht kompatibel ist zu MPEG-2, d.h. man braucht eigene encoder/decoder Einheiten.

Sicherheit
Je nach Sicherheitsstufe; i.A. relativ sicher.
Geschwindigkeit
Schnell.
Datenstromgröße
Keine änderung.

Video Encyrption Algorithm (VEA)

Der Algorithmus basiert auf folgender Grundidee: Sei a1a2a3...a2n-1a2n ein Teil des MPEG-2 Datenstroms. Dieser wird in 2 Listen aufgeteilt: Odd List, Even List. Diese Listen werden dann Xored.

Kombination von Odd und Even List
a1 a3 ... a2n-1
Xor a2 a4 ... a2n
=> c1 c2 ... cn

Dann wählt man eine Verschlüsselungsfunktion E (z.B. DES) um a2a4...a2n zu verschlüsseln. Der resultierende Ciphertext hat die Form c1c2...cnE(a2a4...a2n). D.h. man verwendet den halben Strom als one-time pad. Dies ist möglich, da es in einem MPEG-2 Datenstrom kaum sich wiederholende Muster gibt (siehe Verschlüsselungseigenschaften).

Es gibt einige Erweiterungen um diesen Algorithmus noch sicherer zu machen.

KeyM
Einführung eines 128-bit Schlüssels, der die Odd-Even-List Zuordnung permutiert. Eine 1 steht für "Byte in Odd List geben", eine 0 für "Byte in Even List geben". Eine Randbedingung ist, das der Schlüssel aus 64 Einsen und 64 Nullen besteht.
Keyi, i Element aus {1, ..., 8}
Nur 1/16 eines Frames gilt als Muster-wiederholungsfrei. Dies kann folgendermaßen aus 1/2 Frame ausgedeht werden: Keyi ist eine zufällige Permutation von (1, ..., 32}. Jeweils 32 Byte der Even List werden der Reihe nach mit Keyi permutiert, die nächsten 32 mit Keyi+1, usw.
KeyF
Ist ein 64-bit Schlüssel, der eine zufällige Permutation von (1, ..., 16) enthält, wobei jede Zahl durch 4 Bit dargestellt wird (16*4 = 64 Bit). Mit diesem Schlüssel werden dann KeyM und die Keyis bei jedem Frame verändert (genaue Methode ist auch mir unbekannt, im Bericht [C&G22] steht dazu nur "...apply KeyF to KeyM repeatedly and to the Keyi's...").
KeyE
Der Schlüssel für die Funktion E. KeyE wird über einen sicheren Kanal oder ein public-key Verfahren übertragen. Man kann KeyE auch zum Verschlüsseln der anderen Schlüssel (KeyM, Keyi's, KeyF) verwenden oder diese auch über einen sicheren Kanal oder ein public-key Verfahren übertragen.
Sicherheit
Sehr sicher, besonders mit den Erweiterungen.
Geschwindigkeit
Schnell.
Datenstromgröße
Keine änderung.

Einsatzgebiete

Bei Video Verschlüsselung gibt es nicht nur ein Tradeoff bzgl. Sicherheit und Geschwindigkeit, es gibt da noch eine weitere Komponente: Das Einsatzgebiet.

Selective Algorithms kann man gut bei pay-per-view, video-on-demand und ähnlichen Anwendungen einsetzen. überall wo SSMC (Single Server Multiple Client) im Spiel sind. Dabei kann man über 90%, bis 99%, unverschlüsselt übertragen (P, B-frames), der Rest (I-frames) muß pro Zuseher verschlüsselt werden, weil entweder jeder Zuseher einen eigenen Schlüssel hat oder weil jeder Zuseher ein Video mit persönlichem Watermark erhält, um anonyme Raubkopien zu erschweren (insbesondere deren Verkauf).

Daher: Unverschlüsseltes multicasten, Verschlüsseltes singlecasten.

Dieses Einsatzgebiet muß nicht unbedingt hochsicher sein, die Video Durchsatzrate muß jedoch sehr hoch sein. Ein Video in VHS Qualität benötigt ca. 1,5MBit/sec. Bei hunderten bis tausenden Clients dürfte diese Datenmenge bei Vollverschlüsselung kaum bewältigbar sein.

Anders bei Videokonferenzen und ähnlichem. Dort überwiegt die Sicherheitsanforderung, Geschwindigkeit ist durch die wenigen beteiligten Personen eher kein Problem. Daher bietet sich eine Vollverschlüsselung mit einem der anderen Verfahren an.

Quellen

[C&G22]
COMPUTER & GRAPHICS, Volume 22, November 4, July/August 1998.
[M2TUT]
MPEG-2: the basics Einführung in MPEG-2.
[JSAC1]
Run-Time Performance Evaluation of A Secure MPEG system Supporting both Selective Watermarking and Encryption. S.F. Wu, T.L. Wu
[JSAC2]
NCSU SHANG: Secure MPEG, Implementierung von [JSAC1].
[SHANG1]
Selective Encryption and Watermarking of MPEG Video. T.L. Wu, S.F. Wu
[ISOC96]
An Empirical Study of Secure MPEG Video Transmissions. Iskender Agi and Li Gon
[VEA98]
ACM Multimedia 98 - Electronic Proceedings, A Fast MPEG Video Encryption Algorithm. Changgui Shi & Bharat Bhargava
[MPG]
MPEG . ORG - MPEG Pointers and Resources
[SECMPG]
SECMPEG -- Secure MPEG