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örenden 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 Nachrichtteile 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 selber 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 morgen um, 782290)
• (3, 12h., 344287)
• (4, Alice 312265)

Mit Schritt 3 wird Spreu hinzugefügt:

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

Auf dem Kommunikationskanal werden folgende Nachrichten übertragen:

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

Weblinks

• Der Originaltext von Ron Rivest