Gleich zwei Vorteile auf einmal: ein neues schnelles und robustes Codierungsschema

In unserer digitalen Welt gibt es viele wichtige Daten, die wir unabhängig davon, ob sie gerade übertragen oder gespeichert werden, im Falle eines unerwarteten Verlusts oder einer Beschädigung sicher und verfügbar halten möchten. ECCs (Error Correcting Codes) sind ein wichtiges Tool für eine zuverlässige Datenübertragung oder ‐speicherung über unzuverlässige Netzwerke oder Medien und werden in der Praxis häufig verwendet – beispielsweise für die Übertragung digitaler Medien, für Mobilfunknetze und Satellitenkommunikation bis hin zu High End‐RAM, DVDs, Festplatten und Cloudspeicher.

Ein ECC verschlüsselt Daten durch das Hinzufügen von Redundanz. Die Daten werden als Nachricht betrachtet, die in Symbole zerlegt wird. Diese werden wiederum häufig durch Hinzufügen weiterer Symbole in eine noch größere Anzahl an Codesymbolen transformiert. Auch wenn einige der Codesymbole geändert oder gelöscht werden, verbleiben üblicherweise ausreichend Informationen, um sie decodieren und die Originalnachricht wiederherstellen zu können. Die meisten ECCs schützen vor einer geringen Anzahl zufälliger Fehler. Es gibt aber wichtige Anwendungen von ECCs, in denen ein Angreifer Fehler absichtlich platzieren könnte, die besonders großen Schaden anrichten.

Die meisten bekannten ECCs, die vor derartigen feindlichen Datenbeschädigungen schützen sollen, z. B. Reed‐Solomon‐Codes, sind sehr rechenintensiv und erfordern einen großen Decodierungsaufwand. Fountain‐Codes, wie LT‐[1] und Raptor[2]‐Codes, stehen am anderen Ende des Spektrums. Sie erzeugen nach Bedarf einen potenziell unbegrenzten Stream aus neuen Codesymbolen und decodieren Symbole, sobald diese verfügbar werden. Dies ermöglicht eine extrem effiziente Nachrichtencodierung und ‐wiederherstellung. Raptor‐Codes sind die modernsten Fountain‐Codes, die von IETF (RFCs 5053 und 6330) standardisiert und auch für andere Standards übernommen wurden, um breitgefächerte Anwendungsbereiche wie Multimediaservices (z. B. MBMS, DVB-H, IP-TV), Streamingmedien oder Satellitenkommunikation zu unterstützen.

All diese hervorragende Effizienz wird aber mit Qualitätseinschränkungen erkauft. LT‐ und Raptor‐Codes können nur bei zufälligen Löschungen zuverlässig arbeiten, bei denen jedes Codesymbol unabhängig und mit geringer Wahrscheinlichkeit als verloren betrachtet wird. Bei jeglicher Abweichung von dieser Betriebseinstellung, ist eine garantierte Decodierung plötzlich nicht mehr gegeben. Selbst einfache gezielte Löschungen können die Wahrscheinlichkeit erhöhen, dass heimlich Decodierungsfehler oder ‐verzögerungen verursacht werden, weil ein Angreifer die Codestruktur dazu nutzen kann, genau jene Löschungen auszuwählen, die die Nachrichtenwiederherstellung maximal stören.

In der Praxis können Löschungen problemlos erzwungen werden, beispielsweise wenn ein infizierter Router ihn passierende Symbole selektiv löscht. Lopes und Neves [3] haben kürzlich einen solchen Angriff gegen eine TFTP‐Anwendung zur Übertragung von Dateien demonstriert, welche mittels einer standardisierten Raptor‐Version codiert wurden. Sie nutzten einige anfällige Elemente des Codes, um seine Struktur vollständig vorherzusagen und besonders schädliche Löschmuster im Voraus zu berechnen. Das Alarmierende daran war, dass die ausgewählten Löschungen datenunabhängig sind und in den meisten Konfigurationen nur aus wenigen Codesymbolen bestehen. Trotzdem machen sie es beinahe unmöglich, die Nachricht wiederherzustellen. Der Angriff läuft mit der Geschwindigkeit der Datenleitung ab und ist fast nicht erkennbar, da nur wenige Symbole verloren gehen. Darüber hinaus kann er Dateiübertragungen effektiv stören, auch wenn deren Codierung authentifiziert oder verschlüsselt ist, d. h., wenn TFTP neben IPsec/ESP ausgeführt wird.

Vor Kurzem haben wir eine Lösung für das obige Problem entwickelt. In Zusammenarbeit mit Ari Juels, James Kelley und Roberto Tamassia haben wir gezeigt, dass die Entwicklung eines für Kryptografie optimierten Codierungsschemas möglich ist, das sowohl in der Praxis effizient, als auch vor gezielten Fehlern immun ist. Unsere Lösung namens Falcon‐Codes [4]ist eine Klasse authentifizierter ECCs, die auf LT‐Codes basieren und die Lösung für gleich zwei Probleme bieten. In fast allen Fällen können sie feindliche Symbolbeschädigungen korrigieren und die Hauptfunktionen standardmäßiger LT‐Codes bewahren, also die schnelle Erzeugung einer „Fontäne“ von Codesymbolen und eine schnelle Wiederherstellung von Nachrichten, solange eine ausreichende Anzahl an Symbolen intakt bleibt.

Das neue Design verbessert LT‐Codes auf zwei entscheidende Weisen: Es wird ein geheimer Schlüssel für die Datencodierung und Nachrichtenwiederherstellung verwendet und die Codestruktur wird vollständig mithilfe einer einfachen Kombination aus einem starken Zufallszahlengenerator (der die Codierung zufällig festlegt und eine Vorhersage nicht zulässt), optional mit einem sicheren Verschlüsselungsverfahren (das Symbole verschlüsselt und Verluste nicht zulässt), sowie einem fälschungssicheren MAC (der Symbole authentifiziert und die Fehlerfortpflanzung unterbindet) geschützt. Sorgfältig kombiniert mit Daten‐Striping bietet die neue Codierung skalierbare Varianten, die beispielsweise mehrere Gigabyte große Nachrichten verarbeiten können. Durch die überlegte Verwendung von Kryptografie auf der entscheidenden LT‐Codierungsebene empfehlen sich Falcon‐Codes auch als sichere Erweiterungen für Raptor‐Codes, die eine hohe Effizienz erreichen, beispielsweise mit Durchsatzgeschwindigkeiten von 300 MB/s. Praktischerweise können Falcon‐Codes auch beliebige Sicherheitsfunktionen nutzen, die vom Kommunikationskanal bereitgestellt werden (z. B. Tunneling per SSH oder IPsec), um den erforderlichen Overhead weiter einzuschränken.

Insgesamt betrachtet ist die schnelle, umgehende Erzeugung von Codesymbolen, die bei vorhandenen beschränkten bösartigen Beschädigungen eine schnelle Nachrichtenwiederherstellung gewährleistet, eine attraktive Eigenschaft, die Falcon‐Codes für viele praktische Szenarios geeignet macht. Sie bieten einen erheblich besseren Schutz als LT‐/Raptor‐Codes und verursachen trotzdem nur einen geringen Overhead, sodass sie praktisch bleiben. Falcon‐Codes können insbesondere Raptor‐Codes nachweislich gegen gezielte Löschangriffe von Lopes und Neves verstärken. Sie bieten zudem vergleichbaren Schutz wie vorhandene angriffstolerante Codes wie Reed-Solomon, sind aber effizienter. Vor allem, wenn sie als nicht hundertprozentiger Ersatz für einen speziell entwickelten Code eingesetzt werden, der im Sicherheitsprotokoll für Cloudspeicher von Shi et al. [5]verwendet wird, führen Falcon‐Codes zu einer Beschleunigung um 35 %. Aufgrund ihres Designs bieten Falcon‐Codes das Beste zweier Welten: Sicherheit und Effizienz.

[1] M. Luby: LT Codes. IEEE Symposium on Foundations of Computer Science 2002: 271.

[2] A. Shokrollahi: Raptor codes. IEEE Transactions on Information Theory 52(6): 2551-2567, 2006.

[3] J. Lopes, N. Neves: Stopping a Rapid Tornado with a Puff. IEEE Symposium on Security and Privacy 2014: 509-523.

[4] A. Juels, J. Kelley, R. Tamassia, N. Triandopoulos: Falcon Codes: Fast, Authenticated LT Codes (Or: Making Rapid Tornadoes Unstoppable). ACM Conference on Computer and Communications Security 2015: 1032-1047.

[5] E. Shi, E. Stefanov, C. Papamanthou: Practical Dynamic Proofs of Retrievability. ACM Conference on Computer and Communications Security 2013: 325-336.

No Comments