Stromchiffre von Klartext gepadded Hash

Hallo allerseits,
gleich meine erste Frage:

Ich arbeite gerade mit einem Buch zur Kryptographie und darin ist eine interessante Aufgabe gestellt:

Sei E( k, . ) eine Stromchiffre, und c= E(k, x) der Chiffretext zum Klartext x. Weiter sei H eine Hashfunktion.

Aufgabe (frei übersetzt)
Angenommen die Verschlüsselung ist wie folgt definiert:
c = E( k, x || H(x) ) und ein potentieller Angreifer kennt das Paar (x, c). Warum ist diese Methode unsicher und wie kann ein Angreifer einen alternativen Geheimtext c' berechnen, sodass der Empfänger die Nachricht erfolgreich verifiziert? (Korrektur von identifiziert in verifiziert)


Dazu stelle ich mir zunächst die Frage: Ist diese Verschlüsselung immer unsicher, egal welche Stromchiffre (ob selbstsynchron oder synchron) verwendet wird? Durch den CTR Mode lassen sich auch aus Blockchiffren Stromchiffren erzeugen. Sind dann auch diese unsicher? Ist auch das OTP dadurch unsicher?

Wenn ich einen Angriff konstruiere nehme ich an, dass ich den Schlüssel k nicht kenne, aber herausfinden möchte. Weiter würde ich voraussetzen, dass ich die verwendete Hashfunktion kenne.
Dazu dann direkt die nächste Frage: Wenn ich einen Angriff theoretisch konstruieren möchte, was darf/kann ich voraussetzen? Bzw. nach welchem Prinzip lässt sich i.A. vorgehen?



Da ich x kenne, kenne ich auch H(x) (da mir die verwendete Hashfunktion vermutlich bekannt ist..) Ich könnte also nach dem Geburtstagsparadoxon 2.18 * sqrt( Hashblocklänge ) zufällige Manipulationen an dem Klartext x vornehmen, sodass dann H( x' ) = H( x ) mit der Wahrscheinlichkeit von 50% erzeugt wird.

Dann kann ich wieder " x' || H(x) " anlegen. Habe ich nun Zugriff auf die Verschlüsselungsfunktion nach obiger Aufgabenstellung?

Bevor ich jetzt noch mehr Fragen stelle, bedanke ich mich erst bei demjenigen, der sich bereits die Mühe gemacht hat, den Text zu lesen und seine Zeit bereitwillig opfert, um mir zu helfen.


Viele Grüße

Shalec hat gesagt.:

Sei E( k, . ) eine Stromchiffre, und c= E(k, x) der Chiffretext zum Klartext x. Weiter sei H eine Hashfunktion.

Aufgabe (frei übersetzt)
Angenommen die Verschlüsselung ist wie folgt definiert:
c = E( k, x || H(x) ) und ein potentieller Angreifer kennt das Paar (x, c). Warum ist diese Methode unsicher und wie kann ein Angreifer einen alternativen Geheimtext c' berechnen, sodass der Empfänger die Nachricht erfolgreich identifiziert?

Dazu stelle ich mir zunächst die Frage: Ist diese Verschlüsselung immer unsicher, egal welche Stromchiffre (ob selbstsynchron oder synchron) verwendet wird?

Zum Vergrößern anklicken....

Der Knackpunkt hierbei ist die mehrfache Nutzung des Schlüsselstroms k. Im Prinzip ist E(k,x) die Konkatenation von k_i xor x_i, d.h. jedes Bit des (möglicherweise noch zusätzlich modifizierten) Schlüsselstroms wird mit dem entsprechenden Bit vom Klartext ge'xor'ed. Einfach ausgedrückt: E(k,x)=k xor x=c.

Wenn ich einen Angriff konstruiere nehme ich an, dass ich den Schlüssel k nicht kenne, aber herausfinden möchte.

Zum Vergrößern anklicken....

Nein, die Aufgabe fragt nicht nach dem Schlüssel, sondern nach dem Klartext zu einem zweiten Chiffretext c'. D.h. sie möchte aus E(k,x')=c' das x' wissen. Nun gibt es zwei Wege:
1. Brechen des Schlüssels k und Entschlüsseln D(c',k)=x'
2. Berechnen des Klartexts x' mit Hilfe des Paars (c,x).

Tip: Versuche mal den zweiten Weg

Durch den CTR Mode lassen sich auch aus Blockchiffren Stromchiffren erzeugen. Sind dann auch diese unsicher? Ist auch das OTP dadurch unsicher?

Zum Vergrößern anklicken....

In der o.g. Definition istt k ist der Schlüsselstrom, und nicht der Schlüssel für die Blockchiffre. Allerdings lässt sich die o.g. Lösung aber auch auf solche Schlüsselströme anwenden, die eine Blockchiffre "missbrauchen". Der Beweis ist nicht schwer, das schaffst du

Dazu dann direkt die nächste Frage: Wenn ich einen Angriff theoretisch konstruieren möchte, was darf/kann ich voraussetzen? Bzw. nach welchem Prinzip lässt sich i.A. vorgehen?

Zum Vergrößern anklicken....

Geh davon aus, dass du alles, was nicht näher definiert ist, theoretisch sicher ist. D.h. du darfst nicht sagen, dass du H(x) brichst oder E(k,x) zurückrechnen kannst. Das ginge ja an der Aufgabe vorbei

Hallo und danke für die ausführliche Antwort!

SchwarzeBeere hat gesagt.:

Der Knackpunkt hierbei ist die mehrfache Nutzung des Schlüsselstroms k. Im Prinzip ist E(k,x) die Konkatenation von k_i xor x_i, d.h. jedes Bit des (möglicherweise noch zusätzlich modifizierten) Schlüsselstroms wird mit dem entsprechenden Bit vom Klartext ge'xor'ed. Einfach ausgedrückt: E(k,x)=k xor x=c.


Nein, die Aufgabe fragt nicht nach dem Schlüssel, sondern nach dem Klartext zu einem zweiten Chiffretext c'. D.h. sie möchte aus E(k,x')=c' das x' wissen. Nun gibt es zwei Wege:
1. Brechen des Schlüssels k und Entschlüsseln D(c',k)=x'
2. Berechnen des Klartexts x' mit Hilfe des Paars (c,x).

Tip: Versuche mal den zweiten Weg

Spoiler: Tip 2

Welche Informationen und Variablen liegen dir vor?

Spoiler: Tip 3

E(k,x)=c
E(k,x')=c'
c xor c' = ?

Geh davon aus, dass du alles, was nicht näher definiert ist, theoretisch sicher ist. D.h. du darfst nicht sagen, dass du H(x) brichst oder E(k,x) zurückrechnen kannst. Das ginge ja an der Aufgabe vorbei

Zum Vergrößern anklicken....

Berechne ich "c XOR c' = (x || H(x)) XOR (x' || H(x') )"
Da ich x kenne, aber H(x) nicht kenne würde das bei meine Betrachtung im Moment zu einem Problem führen. Da aber eine Stromchiffre k_i XOR x_i (Bitweise) berechnet, kann ich doch auch einfach folgendes berechnen:
c XOR c' = x XOR x', d.h. mittels c XOR x XOR x' = c' erhalte ich ein c', das zu einer gültigen Entschlüsselung führt.

Mir ist eben ein Tippfehler aufgefallen. In der Aufgabe steht am "erfolgreich identifiziert" heißen sollte es "erfolgreich verifiziert".

Muss ich mit dieser Korrektur dann nicht eine Kollision erzeugen und somit über Kenntnis der verwendeten Hashfunktion verfügen?

SchwarzeBeere hat gesagt.:

In der o.g. Definition istt k ist der Schlüsselstrom, und nicht der Schlüssel für die Blockchiffre. Allerdings lässt sich die o.g. Lösung aber auch auf solche Schlüsselströme anwenden, die eine Blockchiffre "missbrauchen". Der Beweis ist nicht schwer, das schaffst du

Spoiler: Tip

Welche Rolle spielt der Key im obigen Angriff?

Zum Vergrößern anklicken....

Im obigen Angriff spielte der Key keine Rolle. Damit wäre doch dann auch das OTP (one-time-pad) unsicher.


Aufgrund meines Tippfehlers spielt ja die Hashfunktion nun doch eine große Rolle. Was wäre denn egtl. wenn die Hashfunktion einen Key fordert?

Viele Grüße

Shalec hat gesagt.:

Muss ich mit dieser Korrektur dann nicht eine Kollision erzeugen und somit über Kenntnis der verwendeten Hashfunktion verfügen?

Zum Vergrößern anklicken....

Gemäß Kerkhoffs Prinzip musst du als Verteidiger davon ausgehen, dass einem Angreifer alle Algorithmen - jedoch nicht die genutzten Keys - bekannt sind, d.h. du kannst x = m || H(m) berechnen. Damit ist auch der obige Beweis richtig

Aufgrund meines Tippfehlers spielt ja die Hashfunktion nun doch eine große Rolle. Was wäre denn egtl. wenn die Hashfunktion einen Key fordert?

Zum Vergrößern anklicken....

Überleg mal: In diesem Fall wirst du Nachrichten entschlüsseln (m' || h(m') = x' = c xor x xor c'), aber nicht gültig verschlüsseln können, da du x' nicht konstruieren kannst. d.h. x' hängt bereits von einem k ab, das dir unbekannt ist und das du nicht vollständig eliminieren kannst: c' = c xor x xor m' xor h(m',k).

In der Praxis spielt nun die Implementation eine Rolle, denn was passiert, wenn H(m) falsch ist? Wird das Paket verworfen? Wird es trotzdem genutzt? Ist das k vielleicht fix oder wird aus einer öffentlichen Information berechnet?

SchwarzeBeere hat gesagt.:

Gemäß Kerkhoffs Prinzip musst du als Verteidiger davon ausgehen, dass einem Angreifer alle Algorithmen - jedoch nicht die genutzten Keys - bekannt sind, d.h. du kannst x = m || H(m) berechnen. Damit ist auch der obige Beweis richtig

Zum Vergrößern anklicken....

Ja, Kerkhoff's Prinzip.. total verdrängt
Theoretisch wäre ich nach dem Prinzip vor gegangen, da man ja in vielen Sprachen die genutzten Algorithmen extrahieren kann oder deren implementierte Distribution irgendwo im Internet findet. Bei selbstgeschriebenenen Codes - bestmöglich in Brainfuck - wird es dann schon schwerer, den Algorithmus zu verstehen. Aber das spielt ja keine Rolle.

Ich hatte es mir nun zunächst so gedacht: Da Stromchiffren bitweise operieren, kann c entsprechend der Bitlänge von x vom Hashwert getrennt werden. Im Prinzip: c= k XOR ( x || H(x) ) = k1 XOR x || k2 XOR H(x). Wobei k1 und k2 nur Teile des Schlüsselstroms sind. Damit kann ich dann c'_1 entsprechend oben berechnen.
Für den Rest setze ich einen Angriff im RO oder die Kenntnis über die Hashfunktion voraus. Nach dem Geburtstagsparadoxon lassen sich dann 1.18 zufällige Werte x' wählen, den Hashwert H(x') berechnen und mit H(x) vergleichen, um mit >50%er Wahrscheinlichkeit eine Kollision zu erhalten. Ist die Hashfunktion unbekannt, und man kann als aktiver Angreifer keine Informationen über die Hashfunktion sammeln, ist diese als echt zufällig vorauszusetzen. Sie ist daher, ähnlich wie das OTP, kollisionsresistent (Es gibt mehr "sinnvolle Klartexte" zum gleichen "Schlüssel" oder: Man kann nicht entscheiden, ob es sich dabei um einen Hashwert handelt).
Dann lässt sich der Geheimtext wie folgt zusammensetzen:

c' = c'_1 || ( k2 XOR H(x) ).

Ich musste dann den Schlüssel nicht kennen.
Wobei es wohl auch so ginge:
c= E( k, m || H(m) ) und c' = E( k, m' || H(m') ). Setze dann x= m || H(m) und x' = m' || H(m'), dann lässt sich obiges anwenden.
Finde nun ein m' sodass H(m') = H(m) und definiere x' := m' || H(m). Dann ist der Geheimtext verifizierbar.

SchwarzeBeere hat gesagt.:

Überleg mal: In diesem Fall wirst du Nachrichten entschlüsseln (m' || h(m') = x' = c xor x xor c'), aber nicht gültig verschlüsseln können, da du x' nicht konstruieren kannst. d.h. x' hängt bereits von einem k ab, das dir unbekannt ist und das du nicht vollständig eliminieren kannst: c' = c xor x xor m' xor h(m',k).

Zum Vergrößern anklicken....

Ohne den verwendeten Key für die Hashfunktion lässt sich folglich auch keine Kollision für den gegebenen Hashwert berechnen. Daher sind dann diese Verfahren, wie z.B: E( k, X || H_k2 (x) ) "sicher"?

Bei einer Stromchiffre (oder CTR-Mode) wird die Chiffre durch ein einfaches Xor des Plaintext mit dem Bitstrom des Algorithmus gebildet. Wenn der Angreifer den Plaintext kennt, kann er ohne Kenntnis des Schlüssels jeden beliebigen (gleich langen) "verschlüsselten" Alternativtext aus dem Ciphertext erzeugen. Er muss nur einfach den Xor von bekanntem Plaintext und gewünschtem Plaintext per Xor mit dem bekannten Ciphertext überlagern. Da bei Deiner Konstruktion der direkte Hash und nicht ein HMaC oder was Ähnliches verwendet wird, wird durch den angehängten Hash keinerlei Integritätsschutz erreicht, denn der Hash kann ebenso wie die Nachricht beliebig geändert werden. Das Beispiel aus der Aufgabe hat also keinen Integritätsschutz. (Ich konnte ehrlich gesagt eure bisherige Diskussion im Hinblick auf die Aufgabenstellung nicht wirklich verstehen.)