Paritätsangriff auf Blockchiffre
Mein Missverständnis dreht sich alles um den Paritätsangriff, der in "Cryptography Engineering von Ferguson, Schneier und Kohno" erwähnt wird.
Die meisten modernen Blockchiffren haben eine 128-Bit-Blockgröße, arbeiten jedoch mit 32-Bit-Wörtern. Sie bauen die Verschlüsselungsfunktion aus vielen 32-Bit-Operationen auf. Dies hat sich als sehr erfolgreiche Methode erwiesen, hat jedoch einen Nebeneffekt. Es ist ziemlich schwierig, aus kleinen Operationen eine ungerade Permutation zu erstellen. Infolgedessen erzeugen praktisch alle Blockchiffren nur gleichmäßige Permutationen.
Ich weiß immer noch nicht, inwieweit ein Paritätsangriff hilfreich sein wird. Warum haben nur ideale Chiffren ungerade Permutationen? Kann jemand ein Beispiel dafür geben, warum ungerade Permutationen mehr Operationen benötigen und warum es schwierig ist zu realisieren, dass die aktuelle Hardware nur 32-Bit-Operationen ausführen kann?
Ich bin nicht durch einen anderen Thread in diesem Forum genau zu dieser Frage schlau geworden.
Antworten
Bei einer Blockverschlüsselung mit großer Blockgröße wird der Text in der Frage als Zitat angezeigt
Die meisten modernen Blockchiffren haben eine 128-Bit-Blockgröße, arbeiten jedoch mit 32-Bit-Wörtern. Sie bauen die Verschlüsselungsfunktion aus vielen 32-Bit-Operationen auf. Dies hat sich als sehr erfolgreiche Methode erwiesen, hat jedoch einen Nebeneffekt. Es ist ziemlich schwierig, aus kleinen Operationen eine ungerade Permutation zu erstellen. Infolgedessen erzeugen praktisch alle Blockchiffren nur gleichmäßige Permutationen.
handelt von einem rein theoretischen Angriff. Das Buch ist in Kapitel 3 erkennt es:
Dieser Angriff hat keinerlei praktische Bedeutung.
Dies liegt daran, dass die Parität der Permutation bekannt ist, die von einer ansonsten idealen Blockverschlüsselung mit a implementiert wird$b$-Bit-Block und einige feste Schlüssel helfen Gegnern erst, nachdem sie erhalten haben $2^b-2$Klartext / Chiffretext-Paare: Die letzten beiden Klartext / Chiffretext-Paare werden durch diese Parität aufgedeckt. Vor diesem Schwellenwert kommt aus dieser einen Information nichts Umsetzbares.
Zum Beispiel mit $b=3$Nachdem ein Gegner Klartext / Chiffretext-Paare 0/ 1, 1/ 6, 2/ 5, 3/ 0, 4/ 2, 5/ erhalten hat 7, die wir uns vorstellen können,
0 1 2 3 4 5 6 7
1 6 5 0 2 7 ? ?
und wenn bekannt ist, dass die Permutation gerade ist, kann der Gegner bestimmen¹, dass die verbleibenden Paare 6/ 3, 7/ 4( eher als 6/ 4, 7/ 3). Aber bevor der Gegner das Paar erhalten 5/ 7, wohl wissend , dass die Permutation wurde auch keine Hilfe war , um vorherzusagen , ob 5Karten 3, 4oder 7.
Selbst wenn bekannt ist, dass eine 128-Bit-Blockverschlüsselung eine gerade Permutation für einen Schlüssel implementiert, ist dies keine ausnutzbare Schwäche. Es erlaubt zwar, einen theoretischen Unterscheidungsmerkmal von einer idealen Chiffre zu erstellen, jedoch erst nach so vielen Abfragen ($2^{128}-1$) auf die Verschlüsselung oder Entschlüsselung oracle², die nicht als Angriff auf übliche oder vernünftige Sicherheitsdefinitionen gilt.
Der zitierte Text übertreibt etwas die Schwierigkeit, aus kleinen Operationen eine ungerade Permutation aufzubauen; siehe diese Kommentare von poncho :
Der Standardtrick für Feistel-Chiffren mit kleinen Blöcken besteht darin, in jeder Runde anstelle von xor eine modulare Addition zu verwenden. Auf diese Weise hat die Runde und damit die Permutation eine Wahrscheinlichkeit von 0,5, ungerade zu sein. (…) Wenn die beiden Hälften des Feistel-Zustands sind$a, b$, dann das Update $a\gets a+F(k,b)$kann seltsam sein; in der Tat wird es sein, wenn eine ungerade Zahl der$F(k,b)$ Werte sind ungerade (fest $k$über alle möglichen Werte von $b$).
¹ Beweis: Der Übergang von 01234567nach 16502734kann mit einer geraden Anzahl von Permutationen erfolgen, z. B. 01234567→ 10234567→ 16234507→ 16534207→ 16504237→ 16502437→ 16502734.
² Der Herausforderer wählt zufällig eine ideale zufällige Chiffre oder sogar eine zufällige Chiffre, der Unterscheidungsmerkmal versucht, diese Wahl zu erraten. Es braucht$2^{128}-1$Abfragen, um festzustellen, ob die Verschlüsselung gerade oder ungerade ist, ob ungerade 'ideal' ausgibt, andernfalls 'gerade' ausgibt. Es gelingt mit Wahrscheinlichkeit$3/4$.