Spreu-und-Weizen-Algorithmus

Spreu-und-Weizen-Algorithmus oder Chaffing and Winnowing (englisch für „mit Spreu versetzen und Windsichten“) bezeichnet einen Algorithmus zur Geheimhaltung beim Versenden von Daten, ohne dass die Daten dabei verschlüsselt werden müssen. Das Verfahren wurde im Jahr 1998 von Ronald L. Rivest vorgestellt und stellt eine Alternative zu Steganographie und Kryptographie dar. Die grundsätzliche Idee ist, die unterteilte geheime Nachricht wie Nadeln in einem Heuhaufen aus irrelevanten, aber ähnlich aussehenden Daten zu verbergen.

Prinzipielles Verfahren auf Sender-Seite

Es besteht folgendes Szenario: Jemand möchte vertrauliche Daten über einen unsicheren Kommunikationskanal, beispielsweise das Internet, an einen Empfänger versenden. Es ist von dem verwendeten Verfahren sicherzustellen, dass ein mitlauschender Dritter keine Möglichkeit hat, Kenntnis über den Inhalt der Nachricht zu erlangen.

Schritt 1: Unterteilen der Nachricht in Pakete

Der Sender unterteilt die zu sendende Nachricht in einzelne Datenpakete. Die Datenpakete werden mit einer fortlaufenden Seriennummer versehen. Durch die Seriennummer können beim Empfänger fehlende oder doppelte Pakete identifiziert und schließlich die Nachricht rekonstruiert werden.

Schritt 2: Authentifizierung

Der Absender bestätigt die Echtheit jedes einzelnen Datenpakets mit einer Markierung, die anhand eines geheimen Schlüssels erzeugt wird, der nur Sender und Empfänger bekannt ist. Dafür fügt der Absender jedem Datenpaket einen Message Authentication Code (MAC) hinzu. Dieser Code berechnet sich aus der Seriennummer, den eigentlichen Daten und dem Schlüssel. Als Algorithmus für diese Berechnung wird beispielsweise der HMAC-SHA1-Algorithmus verwendet.

Schritt 3: Hinzufügen einer Spreu

Es werden weitere, nicht zur eigentlichen Nachricht gehörende Datenpakete hinzugemischt. An diese Pakete werden die Anforderungen gestellt, passende Seriennummern und scheinbar sinnvolle Daten zu enthalten. Es wird ein beliebiger MAC hinzugefügt.

Letztlich ist wichtig, dass der MAC für diese Pakete falsch ist. Dafür benötigt man den eigentlichen Authentifizierungsschlüssel nicht. Schritt 3 kann also von einem unbeteiligten Dritten ausgeführt werden.

Prinzipielles Verfahren auf Empfänger-Seite

Der Empfänger prüft die Authentizität jedes eintreffenden Pakets. Dafür berechnet er aus der Seriennummer, den Daten und dem ihm zur Verfügung stehenden Schlüssel seinerseits den MAC und vergleicht ihn mit dem empfangenen. Die authentischen Pakete werden gepuffert und im Anschluss auf Basis der Seriennummern zusammengesetzt.

Eigenschaften des Verfahrens

Um mit Chaffing and Winnowing eine gewisse Abhörsicherheit gewährleisten zu können, muss der Umfang der übermittelten Daten durch inhaltlich irrelevante „Spreu“ erheblich vergrößert werden. Weiterhin müssen die eigentlichen Daten (die „Botschaft“) genügend zerstückelt werden, sodass einzelne Fragmente für sich keine oder kaum Relevanz haben.

Der Authentifizierungsschlüssel ist ein geheimer Schlüssel, der nur dem Sender und dem Empfänger der Nachricht bekannt sein darf. Der Sender und der Empfänger können jederzeit einen neuen geheimen Authentifizierungsschlüssel vereinbaren, beispielsweise mit dem Diffie-Hellman-Verfahren.

Anwendung in der Blogosphäre

Aufgrund der Unzahl von Weblogs, die in vielen Fällen verwaist sind, und einem großen Kommentaraufkommen in der Blogosphäre ist der Einsatz des Spreu-und-Weizen-Algorithmus dort denkbar. Die vorhandenen, echten Kommentare entsprechen dabei der Spreu.

Sender und Empfänger verständigen sich über eine Auswahl von Blogs. Die gewählten Blogs können voneinander unabhängig sein. Diese Festlegung stellt einen symmetrischen Schlüssel dar.

Die einzubettende Nachricht wird in Teile zerlegt und in den verabredeten Blogs als Kommentar gepostet. Um zu verhindern, dass Beiträge dieser Art als Spam gelöscht werden, bietet es sich an, sie um weitere Spreu-Anteile innerhalb des Kommentars anzureichern, die den Kommentar als Meinungsäußerung plausibel erscheinen lassen. Außerdem ist die Anwendung linguistischer Steganographie zum Verschleiern der einzelnen Nachrichtenteile sinnvoll.

Das Verfahren benötigt eine relativ hohe Redundanz, da themenfremde Kommentare in gut gepflegten Blogs schnell gelöscht werden. Brachliegende bzw. verwaiste Blogs bieten sich daher eher für Blog-Steganogramme an, da dort mit wenig Kommentarmoderation gerechnet werden kann. Zum Problem kann die Persistenz von Blogkommentaren werden: Abgeschickte Kommentare kann man in der Regel nicht selbst aus den Blogs entfernen. Erlangt ein Angreifer den Schlüssel, also die Blogs, in die gepostet wird, und deren Reihenfolge, so kann er die ursprüngliche Nachricht rekonstruieren.

Fälschlicherweise wird dieser Ansatz gelegentlich als Blog-Steganographie bezeichnet, obwohl er prinzipiell ohne steganographische Methoden auskommt.

Allgemeines Beispiel für den Algorithmus

Es soll folgende Nachricht geheim versandt werden:

„Hallo Bob, wir sehen uns morgen um 12h. Alice“

Nach Schritt 1 und 2 liegen folgende Pakete vor:
(alle Datenpakete haben die Form Seriennummer, Botschaft, MAC)

• (1, Hallo Bob, 465231)
• (2, wir sehen uns, 963734)
• (3, morgen um, 782290)
• (4, 12h., 344287)
• (5, Alice, 312265)

Mit Schritt 3 wird Spreu hinzugefügt:

• (1, Hallo Larry, 532105)
• (2, wir telefonieren, 2769852)
• (3, übermorgen um, 793122)
• (4, 16h., 891231)
• (5, Susan, 553419)

Auf dem Kommunikationskanal werden folgende Nachrichten übertragen:

• (1, Hallo Larry, 532105)
• (2, wir sehen uns, 963734)
• (3, übermorgen um, 793122)
• (4, 16h., 891231)
• (5, Alice, 312265)
• (1, Hallo Bob, 465231)
• (2, wir telefonieren, 2769852)
• (3, morgen um, 782290)
• (4, 12h., 344287)
• (5, Susan, 553419)

Der Empfänger wählt die Pakete mit dem korrekten MAC aus (blau dargestellt) und verwirft die übrigen Pakete (grau dargestellt). Alsdann rekonstruiert er die ursprüngliche Nachricht, indem er die Botschaften mit aufsteigender Seriennummer zusammensetzt.

Ohne Kenntnis des MAC kann in diesem Beispiel objektiv nicht entschieden werden, von wem an wen diese Nachricht geht und ob es in der Nachricht um ein Telefonat oder ein Treffen geht, sowie an welchem Tag und um welche Uhrzeit dieses stattfinden soll. Die Integrität der übermittelten Nachricht ist dadurch sichergestellt, dass sämtliche textgemäß zusammenpassende Kombinationen für sich genommen plausibel sind.

Anwendungshinweise

Entscheidend für dieses Verfahren ist, dass sich mehrere – im Idealfall eine große Anzahl von – Kombinationen ergeben, in denen die Pakete plausibel zusammengefügt werden können. Dabei ist die Integrität der zu übermittelnden Nachricht dadurch sicherzustellen, dass sämtliche Kombinationen der jeweils ähnlichen Pakete der übertragenen Information für sich genommen möglichst vollkommen plausibel zu sein scheinen.

Handelt es sich bei der Nachricht hingegen etwa um eine Datei, die sich überhaupt nur auf eine Weise wieder sinnvoll zusammensetzen lässt, ist das Verfahren nicht sicher, sofern sich die ursprüngliche Nachricht durch ein einfaches Ausprobieren der unterschiedlichen Kombinationen wiederherstellen lässt. Dieses Risiko lässt sich dadurch minimieren, dass die Nachricht in ausreichend viele und ausreichend kleine Pakete unterteilt wird und die hinzugefügte „Spreu“ so gewählt wird, dass sie grundsätzlich zu der Art der übermittelten Nachricht passt.

Wird eine Datei in n Pakete unterteilt und zu jedem „Weizen“-Paket k „Spreu“-Pakete hinzugefügt, so ergeben sich $k!^{n}$ mögliche Kombinationen, in denen die Nachricht wieder zusammengesetzt werden könnte. Für n = 100 und k = 4 ergäbe sich eine Anzahl von mehr als $1\cdot 10^{138}$ möglichen Kombinationen, was ein richtiges Zusammensetzen der Nachricht durch Ausprobieren sämtlicher Kombinationen praktisch unmöglich machen würde.

Weblinks

• Der Originaltext von Ron Rivest