Quelltext der Seite 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üsselung|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.<ref>{{Literatur|Autor=Ronald L. Rivest|Titel=Chaffing and Winnowing:Confidentiality without Encryption|Sammelwerk=Cryptobyts|Verlag=RSA Laboratories|Datum=1998}}</ref> 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 (Information)|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 [[Absender|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üssel (Kryptologie)|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 [[Keyed-Hash Message Authentication Code|HMAC]]-[[Secure Hash Algorithm|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 [[Authentifikation|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 (Kryptologie)|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-Schlüsselaustausch|Diffie-Hellman-Verfahren]].

== Anwendung in der Blogosphäre ==
{{Belege fehlen}}

Aufgrund der Unzahl von [[Weblog]]s, 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 [[Steganographie#Linguistische Steganographie|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 (Informatik)|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:<br />
(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:
* <span style="color: #777;">(1, Hallo Larry, 532105)</span>
* <span style="color: #00C;">(2, wir sehen uns, 963734)</span>
* <span style="color: #777;">(3, übermorgen um, 793122)</span>
* <span style="color: #777;">(4, 16h., 891231)</span>
* <span style="color: #00C;">(5, Alice, 312265)</span>
* <span style="color: #00C;">(1, Hallo Bob, 465231)</span>
* <span style="color: #777;">(2, wir telefonieren, 2769852)</span>
* <span style="color: #00C;">(3, morgen um, 782290)</span>
* <span style="color: #00C;">(4, 12h., 344287)</span>
* <span style="color: #777;">(5, Susan, 553419)</span>

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 <math>k!^n</math> 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 <math>1 \cdot 10^{138}</math> möglichen Kombinationen, was ein richtiges Zusammensetzen der Nachricht durch Ausprobieren sämtlicher Kombinationen praktisch unmöglich machen würde.

== Weblinks ==
* [https://web.archive.org/web/20230306071104/http://people.csail.mit.edu/rivest/chaffing-980701.txt Der Originaltext von Ron Rivest]

== Einzelnachweise ==
<references />

[[Kategorie:Kryptologisches Verfahren]]