Czy kryptologowie odradzają rejestrom przesuwnym liniowe sprzężenie zwrotne?

10

Katz i Lindell wspominają w swojej książce, że LFSR są okropne jako podstawa dla generatorów pseudolosowych i zalecają, aby nie były już używane (cóż, zalecają również, aby ludzie używali szyfrów blokowych zamiast szyfrów strumieniowych). Widzę jednak na przykład, że jeden z szyfrów w portfolio estream ( ziarno , ukierunkowane na sprzęt) korzysta z LFSR, więc opinia, że ​​LFSR nie są dobre, nie jest zgodna.

Chciałbym wiedzieć, czy wielu kryptologów podziela zdanie Katza i Lindella na temat LFSR (i szyfrów strumieniowych)?

soft-question cr.crypto-security pseudorandom-generators Sójka
źródło
1
Myślę, że pytanie w twoim tytule i pytanie w treści twojego postu są sprzeczne. Chociaż nie jestem kryptologiem, powiedziałbym „tak” w tytule i „nie” w pytaniu w treści postu. Czy możesz poprawić swoje pytanie, tak aby zawierało tylko jedno harmonijne pytanie?
Tyson Williams,
2
Nie jestem w 100% pewien, czy jest to temat na cstheory, może lepiej pasować do crypto.SE .
Artem Kaznatcheev
@Artem Kaznatcheev: Nie wiedziałem o crypto.SE. Uważam, że moja reputacja nie wystarczy do migracji pytania, ale nie miałbym nic przeciwko, gdyby migrował. (Przypuszczam, że crypto.SE to nie tylko problemy z implementacją)
Jay
2
@Artem, IMHO, pytanie jest w zakresie cstheory. Nie jestem ekspertem od kryptografii, ale generalnie ludzie robią wiele rzeczy w praktyce, które nie mają podstaw, np. Proste funkcje są używane jako generatory liczb losowych psuedo w programach, ale tak naprawdę nie są losowe losowe i można je łatwo przewidzieć. Jay, jeśli chcesz dowiedzieć się, dlaczego Katz i Lindell twierdzą, że LFSR nie powinien być używany, cstheory jest właściwym miejscem na pytanie. Z drugiej strony pytanie, czy istnieje konsensus, nie jest dobrym pytaniem, odpowiedź jest oczywista, tzn. Nie ma. Również pytania ankietowe nie są konstruktywne.
Kaveh
1
@Jay, chyba nie rozumieją, że nie są oparte na prawdopodobnej twardości lub założeniach kryptograficznych, tj. Nie ma silnych argumentów za ich niezłomnością. Możesz sprawdzić notatki z wykładów Charlesa Rackoffa , pamiętam, że powiedział coś na ten temat (ale nie jestem pewien, czy jest to w jego notatkach z wykładów).
Kaveh

Odpowiedzi:

9

Istnieje wiele rodzajów ataków kryptoanalitycznych: aproksymacje liniowe, ataki algebraiczne, ataki wymiany danych czas-pamięć-dane, ataki błędów .

Na przykład możesz przeczytać ankietę: „ Algebraiczne ataki na szyfry strumieniowe (ankieta) ”

Streszczenie : Większość szyfrów strumieniowych opartych na rejestrach przesuwnych z liniowym sprzężeniem zwrotnym (LFSR) jest podatna na niedawne ataki algebraiczne. W tym artykule przeglądowym opisujemy ataki ogólne: istnienie równań algebraicznych i szybkie ataki algebraiczne. ...

Na końcu można znaleźć inne odpowiednie referencje.

Kolejny dobry artykuł na temat ataków błędów na szyfry strumieniowe to: „ Analiza błędów szyfrów strumieniowych ”

Streszczenie : ... Naszym celem w tym artykule jest opracowanie ogólnych technik, które można wykorzystać do ataku na standardowe konstrukcje szyfrów strumieniowych opartych na LFSR, a także bardziej wyspecjalizowanych technik, które można zastosować przeciwko konkretnym szyfrom strumieniowym, takim jak RC4, LILI -128 i SOBERt32. Chociaż większość schematów można skutecznie zaatakować, zwracamy uwagę na kilka interesujących otwartych problemów, takich jak atak na konstrukcje filtrowane FSM i analiza błędów wysokiej masy Hamminga w LFSR.

W przypadku ataków na kompromis między pamięcią czasową a danymi możesz przeczytać: „ Kompromis czas kryptoanalityczny / pamięć / dane dla szyfrów strumieniowych ”.

Marzio De Biasi
źródło
1
Dziękuję Ci! Dokumenty te bez wątpienia będą przydatne.
Jay
3

Katz i Lindell odradzali samodzielne używanie LFSR jako generatorów pseudolosowych. Jednak może być możliwe zbudowanie generatora pseudolosowego przy użyciu LFSR w połączeniu z innymi mechanizmami. (W szczególności PRG oparte na LFSR muszą zawierać pewien składnik nieliniowy.)

użytkownik686
źródło