Apakah register shift umpan balik linier pada umumnya tidak disarankan oleh ahli kriptologi?

Katz dan Lindell menyebutkan dalam buku mereka bahwa LFSR telah mengerikan sebagai dasar untuk generator pseudorandom, dan menganjurkan bahwa mereka tidak digunakan lagi (well, mereka juga merekomendasikan agar orang menggunakan cipher blok dan bukan stream cipher). Tapi saya melihat misalnya bahwa salah satu cipher dalam portofolio estream ( Grain , yang ditargetkan untuk perangkat keras) menggunakan LFSR, sehingga pendapat bahwa LFSR tidak baik bukanlah konsensus.

Saya ingin tahu apakah ada banyak cryptologis yang membagikan pendapat Katz dan Lindell tentang LFSR (dan pada stream cipher)?

soft-question cr.crypto-security pseudorandom-generators Jay
sumber

Saya pikir pertanyaan dalam judul Anda dan pertanyaan dalam isi posting Anda bertentangan. Meskipun saya bukan seorang cryptologist, saya akan mengatakan "Ya" untuk judul dan "Tidak" untuk pertanyaan di postingan. Bisakah Anda memperbaiki pertanyaan Anda sehingga hanya memiliki satu pertanyaan yang harmonis?

Tyson Williams

Saya tidak 100% yakin apakah ini sesuai topik untuk cstheory, mungkin lebih cocok di crypto.SE .

Artem Kaznatcheev

@ Artem Kaznatcheev: Saya tidak tahu tentang crypto.SE. Saya percaya reputasi saya tidak cukup untuk memigrasi pertanyaan, tetapi saya tidak keberatan jika itu bermigrasi. (Saya kira crypto.SE bukan hanya tentang masalah implementasi)

Jay

@ Artem, IMHO, pertanyaannya adalah dalam lingkup cerita. Saya bukan ahli crypto, tetapi umumnya orang melakukan banyak hal dalam praktiknya yang tidak memiliki dasar, misalnya fungsi sederhana digunakan sebagai generator nomor psuedo-acak dalam program tetapi mereka tidak benar-benar psuedo-acak dan dapat diprediksi dengan mudah. Jay, Jika Anda ingin tahu tentang alasan mengapa Katz dan Lindell mengatakan bahwa LFSR tidak boleh digunakan karena itu adalah tempat yang tepat untuk pertanyaan itu. Di sisi lain, menanyakan apakah ada konsensus bukanlah pertanyaan yang bagus, jawabannya jelas, yaitu tidak ada. Juga pertanyaan pemungutan suara tidak konstruktif.

Kaveh

@ Jay, saya kira apa yang mereka maksud dengan tidak dipahami dengan baik adalah bahwa mereka tidak didasarkan pada kekerasan yang masuk akal atau asumsi kripto, yaitu tidak ada argumen yang kuat untuk unbreakability mereka. Anda mungkin ingin memeriksa catatan kuliah Charles Rackoff , saya ingat bahwa dia mengatakan sesuatu tentang masalah ini (tapi saya tidak yakin apakah itu ada dalam catatan kuliahnya).

Kaveh

Jawaban:

Ada banyak jenis serangan kriptanalitik: Perkiraan linier, serangan aljabar, serangan Time-memory-data-tradeoff, serangan kesalahan .

Misalnya, Anda dapat membaca survei: " Serangan Aljabar Pada Aliran Sawah (Survei) "

Abstrak : Kebanyakan stream cipher yang didasarkan pada linear feedback shift register (LFSR) rentan terhadap serangan aljabar terbaru. Dalam makalah survei ini, kami menggambarkan serangan generik: keberadaan persamaan aljabar dan serangan aljabar cepat. ...

Pada akhirnya Anda dapat menemukan referensi lain yang relevan.

Makalah lain yang baik tentang serangan kesalahan untuk stream cipher adalah: " Analisis Kesalahan Stream Cipher "

Abstrak : ... Tujuan kami dalam makalah ini adalah untuk mengembangkan teknik umum yang dapat digunakan untuk menyerang konstruksi standar cipher aliran berdasarkan LFSR, serta teknik yang lebih khusus yang dapat digunakan terhadap cipher aliran spesifik seperti RC4, LILI -128 dan SOBERt32. Sementara sebagian besar skema dapat berhasil diserang, kami menunjukkan beberapa masalah terbuka yang menarik seperti serangan pada konstruksi yang difilter FSM dan analisis kesalahan berat Hamming yang tinggi di LFSR's.

Untuk serangan pengorbanan waktu-memori-data, Anda dapat membaca: " Pengorbanan Waktu Kriptanalitik / Memori / Data untuk sandi aliran ".

Marzio De Biasi
sumber

Terima kasih! Makalah-makalah ini pasti akan bermanfaat.

Jay

Katz dan Lindell merekomendasikan agar tidak menggunakan LFSR sendiri sebagai generator pseudorandom. Namun, dimungkinkan untuk membuat generator pseudorandom menggunakan LFSR dalam hubungannya dengan mekanisme lain. (Secara khusus, PRGs berdasarkan LFSRs harus mencakup beberapa komponen non-linear.)

pengguna686
sumber