Werden lineare Rückkopplungsschieberegister von Kryptologen generell entmutigt?

10

Katz und Lindell erwähnen in ihrem Buch, dass LFSR als Grundlage für Pseudozufallsgeneratoren schrecklich war, und befürworten, dass sie nicht mehr verwendet werden (nun, sie empfehlen auch, dass Leute Blockchiffren anstelle von Streamchiffren verwenden). Aber ich sehe zum Beispiel, dass einer der Chiffren im estream-Portfolio ( Grain , auf Hardware ausgerichtet) einen LFSR verwendet, sodass die Meinung, dass LFSRs nicht gut sind, kein Konsens ist.

Ich würde gerne wissen, ob es viele Kryptologen gibt, die Katz und Lindells Meinung zu LFSRs (und zu Stream-Chiffren) teilen.

soft-question cr.crypto-security pseudorandom-generators Jay
quelle
1
Ich denke, die Frage in Ihrem Titel und die Frage im Text Ihres Beitrags sind uneins. Obwohl ich kein Kryptologe bin, würde ich zum Titel "Ja" und zur Frage im Post-Body "Nein" sagen. Können Sie Ihre Frage so verbessern, dass sie nur eine harmonische Frage enthält?
Tyson Williams
2
Ich bin mir nicht 100% sicher, ob dies ein Thema für cstheory ist, es könnte besser für crypto.SE geeignet sein .
Artem Kaznatcheev
@Artem Kaznatcheev: Ich wusste nichts über crypto.SE. Ich glaube, mein Ruf reicht nicht aus, um die Frage zu migrieren, aber es würde mir nichts ausmachen, wenn sie migriert wäre. (Ich nehme an, bei crypto.SE geht es nicht nur um Implementierungsprobleme)
Jay
2
@Artem, IMHO, die Frage ist im theoretischen Bereich. Ich bin kein Krypto-Experte, aber im Allgemeinen machen Menschen in der Praxis viele Dinge, die keine Grundlagen haben, z. B. werden einfache Funktionen als Pseudozufallszahlengeneratoren in Programmen verwendet, aber sie sind nicht wirklich pseudozufällig und können leicht vorhergesagt werden. Jay, wenn Sie wissen möchten, warum Katz und Lindell sagen, dass LFSR nicht verwendet werden sollte, ist cstheory der richtige Ort für die Frage. Auf der anderen Seite ist die Frage, ob es einen Konsens gibt, keine gute Frage. Die Antwort liegt auf der Hand, dh es gibt keine. Auch Umfragefragen sind nicht konstruktiv.
Kaveh
1
@ Jay, ich denke, was sie bedeuten, wenn sie nicht gut verstanden werden, ist, dass sie nicht auf plausiblen Härte- oder Krypto-Annahmen beruhen, dh es gibt keine starken Argumente für ihre Unzerbrechlichkeit. Vielleicht möchten Sie die Vorlesungsunterlagen von Charles Rackoff lesen . Ich erinnere mich, dass er etwas zu diesem Thema gesagt hat (aber ich bin mir nicht sicher, ob es in seinen Vorlesungsunterlagen steht).
Kaveh

Antworten:

9

Es gibt viele Arten von kryptoanalytischen Angriffen: Lineare Approximationen, algebraische Angriffe, Time-Memory-Data-Tradeoff-Angriffe, Fehlerangriffe .

Zum Beispiel können Sie die Umfrage lesen: " Algebraische Angriffe auf Stream-Chiffren (Umfrage) "

Zusammenfassung : Die meisten Stream-Chiffren, die auf linearen Rückkopplungsschieberegistern (LFSR) basieren, sind anfällig für aktuelle algebraische Angriffe. In diesem Umfragepapier beschreiben wir generische Angriffe: Existenz algebraischer Gleichungen und schnelle algebraische Angriffe. ...

Am Ende finden Sie weitere relevante Referenzen.

Ein weiteres gutes Papier über Fehlerangriffe auf Stream-Chiffren ist: "Fehleranalyse von Stream-Chiffren "

Abstract : ... Unser Ziel in diesem Artikel ist es, allgemeine Techniken zu entwickeln, mit denen die Standardkonstruktionen von Stream-Chiffren auf Basis von LFSRs angegriffen werden können, sowie speziellere Techniken, die gegen bestimmte Stream-Chiffren wie RC4, LILI eingesetzt werden können -128 und SOBERt32. Während die meisten Schemata erfolgreich angegriffen werden können, weisen wir auf einige interessante offene Probleme hin, wie einen Angriff auf FSM-gefilterte Konstruktionen und die Analyse von Fehlern mit hohem Hamming-Gewicht in LFSRs.

Für Angriffe auf Zeit-Speicher-Daten-Kompromisse können Sie lesen: " Kryptoanalytische Zeit / Speicher / Daten-Kompromisse für Stream-Chiffren ".

Marzio De Biasi
quelle
1
Vielen Dank! Diese Papiere werden zweifellos nützlich sein.
Jay
3

Katz und Lindell rieten davon ab, LFSRs allein als Pseudozufallsgeneratoren zu verwenden. Es könnte jedoch möglich sein, einen Pseudozufallsgenerator unter Verwendung eines LFSR in Verbindung mit anderen Mechanismen zu konstruieren . (Insbesondere PRGs, die auf LFSRs basieren, müssen eine nichtlineare Komponente enthalten.)

user686
quelle