Pertanyaan saya agak umum, jadi saya mengarang cerita yang bagus untuk membenarkannya. Bersabarlah jika tidak realistis ;-)
Cerita
Tn. X, kepala departemen keamanan komputer di sebuah perusahaan besar, agak paranoid: ia mengharuskan semua karyawan mengganti kata sandi sekali sebulan, untuk meminimalkan risiko pencurian identitas atau informasi. Selain itu, ia tidak percaya karyawan dapat membuat kata sandi yang aman.
Karena itu, setiap bulan, ia menghasilkan kata sandi baru menggunakan perangkat lunak yang ia tulis, dan memberikannya kepada karyawan sehingga mereka dapat masuk kembali. Tapi selain paranoid, Tn. X juga agak malas: kata sandi yang dihasilkannya mengikuti semua pola, dan algoritma yang digunakan untuk memungkinkan orang masuk hanya memeriksa bahwa kata sandi "terlihat oke" sesuai dengan aturan itu, dan bahwa itu tidak ada dalam "daftar kedaluwarsa".
Sayangnya, perilakunya yang sombong membuat banyak orang pahit, dan salah satu dari mereka, Tuan Y, memutuskan untuk membuktikan kepadanya bahwa ia dapat memecahkan kata sandi. Jadi, suatu malam, ia mengumpulkan beberapa dari mereka, dan mulai mencoba merancang algoritma pembelajaran untuk menghasilkan kata sandi yang valid, menggunakan komputer pribadinya untuk memverifikasinya.
Pertanyaan
Peramalan yang digunakan oleh Tn. Y agak aneh, karena ia mengatakan "kebenaran, tetapi bukan seluruh kebenaran" (karena itu kata sifat "pendiam"). Lebih tepatnya: Tn Y akan tahu bahwa password berlaku ketika komputer menerimanya, tetapi ketika password ditolak, Mr Y tidak akan tahu apakah atau tidak itu bisa saja berlaku: password dapat ditolak karena tidak sesuai dengan beberapa pola, tetapi mungkin juga ditolak karena dulu valid tetapi tidak lagi, menurut "perubahan sebulan sekali" Mr. X.
Jadi, akankah Tuan Y dapat menemukan apa pun dalam situasi itu? Atau bisakah kita mengklaim / membuktikan bahwa kata sandi X secara inheren tidak dapat diprediksi (seperti yang didefinisikan dalam pengaturan pembelajaran PAC, tetapi mungkin konsep ini ada dalam kerangka kerja lain)?
sumber
Sulitnya rekayasa balik algoritma tampaknya tergantung pada seberapa banyak ruang tombol telah berakhir.
Katakanlah algoritma Tn. X sangat terbatas, sehingga hanya ada (katakan) hanya 10.000 kunci yang berpotensi valid. Jika Tn. X baru-baru ini memulai perusahaan ini, maka ada sangat sedikit kunci kadaluarsa - dan karenanya hanya sedikit "negatif palsu" - maka rekayasa ulang algoritme mungkin relatif mudah. Jika Tn. X telah kedaluwarsa 9.000 dari kunci yang berpotensi sah, dan kami memiliki 9 dari 10 "false negative", maka rekayasa ulang algoritme tampaknya jauh lebih sulit. Dan, tentu saja, jika Tn. X telah kedaluwarsa setiap kunci yang berpotensi sah kecuali yang Tn. Y dan rekan-rekannya sudah ketahui, maka "peramal pendiam" akan memberinya nol informasi baru.
sumber
Tampaknya hanya banyak kata sandi yang valid yang dapat digunakan. Jika bahasa kata sandi terbatas, maka tidak ada harapan (seperti dalam kasus ini, semua kata sandi yang valid dapat digunakan, dalam hal ini oracle selalu mengembalikan FALSE).
sumber