Fast Correlation Attack pada SSC2 Asadini Dwi Ajeng, Asti Meysita, Jenny Irna, Ricky Aji P. Tingkat III TK
1. Pendahuluan SSC2 adalah stream cipher yang diusulkan oleh Zhang, Carroll dan Chan. Cipher ini dirancang untuk implementasi software dan sangat cepat. Makalah ini menggambarkan kriptoanalisis secara praktis dari SSC2 yang memerlukan sekitar 225 word dari kunci stream yang diketahui (dari run 225 word) dan beberapa jam kerja pada prosesor 250 MHz dengan memori 100 MB. SSC2 didasarkan pada sebuah linear feedback shift register (LFSR) dan sebuah lagged Fibonacci Generator (LFG). Sebuah LFSR terdiri dari himpunan bit disebut state, dan sebuah fungsi yaitu linear Modulo 2. Fungsi ini memperbaharui state bit per bit. Sebuah LFG terdiri dari register yang menyimpan himpunan integer modulo N (disebut state) dan sebuah fungsi yaitu linear modulo N. Fungsi ini memperbaharui state integer per integer. Dalam SSC2, modulus adalah N = 232, dan integer yang disimpan adalah 32 bit blok disebut word. SSC2 mencapai kecepatannya dengan menggunakan operasi 32-bit. Stream berasal dari 127-bit LFSR, 17 word LFG dan sebuah multiplexer yang memilih nilai-nilai dari register LFG. 127-bit register untuk LFSR disimpan pada empat buah 32 bit word (bit ekstra dibuat menjadi 1 pada fungsi filter). Setelah state pada LFSR dan LFG dijalankan, langkahlangkah berikut diulangi untuk menghasilkan masing-masing word output: 1. 32-bit dari state LFSR diperbarui secara bersamaan. Non-linear filter (NLF) menghitung 32-bit output Ni dari empat word pada state LFSR. 2. State LFG telah diperbarui. upper 16-bit dan lower 16-bit dari LFG output diswap untuk membentuk Li. 3. Multiplexer menggunakan empat most significant bit (MSBs) dari word yang telah diperbarui untuk memilih satu dari 16 nilai pada state LFG untuk menjadi output Mi. 4. Output dari cipher adalah zi = (Li + Mi mod 232) ⊕ Ni, di mana ⊕ menunjukkan XOR.
Nilai Ni disebut output dari LFSR half cipher. Sedangkan vi = (Li + Mi mod 232) disebut output dari LFG half cipher. Hasil sebelumnya: Dalam sesi rump Crypto 2000, Rose dan Hawkes melaporkan pada korelasi antara least significant bit (LSB) output word dari SSC2. Mereka juga mencatat bahwa LFG memiliki periode kecil π = 17 . 231 . (217 – 1) ≈ 2 52. Menghitung
Memungkinkan LFSR untuk diserang secara isolasi. Korelasi pada LSB dari Zi memungkinkan seorang penyerang untuk membedakan output dari SSC2 dari random bit stream. Analisis lain oleh Hawkes dan Rose menemukan sebuah serangan terhadap half cipher LSFR dalam isolasi yang membutuhkan sekitar 382 word sebanyak 242 kali. Bleichenbacher dan Meier menemukan serangan pada seluruh cipher yaitu menemukan initial state dari LFSR menggunakan 252 word dari kunci stream yang diketahui sekitar 275 kali. Serangan memanfaatkan periode yang kecil π. Dengan cara ini, initial state dari LFG akan diketahui menggunakan 245 output yang diketahui dari LFG half cipher sekitar 2109 kali. Hasil baru. Bagian pertama dari attack pada paper ini mengeksploitasi periode kecil dari LFG dengan melakukan fast correlation attack pada stream Zi. Serangan pada bagian ini membutuhkan sekitar 225 word (dari run 252 word) dengan beberapa jam dari waktu processing pada 250 MHz Sun UltraSPARC (lihat Bagian 3). Serangan menerapkan teknikteknik sederhana yang meningkatkan akurasi dan kecepatan fast correlation attack. Setelah output dari half cipher LFSR setengah-sandi dihilangkan, serangan mengidentifikasi ketika multiplexer telah memilih word yang spesifik pada register LFG, dan menggunakan informasi ini untuk merekonstruksi initial state LFG (Bagian 4). Serangan pada bagian ini membutuhkan sekitar 15.300 output yang diketahui dari half cipher LFG (dianggap sudah diketahui dari tahap sebelumnya) dan pemrosesan kedua pada 250 MHz Sun UltraSPARC.
2. Deskripsi SSC2 LFSR half cipher. State LFSR disimpan pada 32 bit word (xi+3, xi+2, xi+1, xi). State diperbarui menjadi (xi+4, xi+3, xi+2, xi+1). Dengan menghitung
xi+4 = xi+2 ⊕ (xi+1 ≪ 31) ⊕ (xi ≫ 1), dimana ‘≪’ menunjukkan sebuah zero fill left shift dan ‘≫’ menunjukkan sebuah zero fill right shift. Pada sequence ini dikonversi ke bit stream bi, lalu bit sequence akan memenuhi rekursi linear: bi+127 = bi+63 + bi mod 2 LFSR diimplementasikan menggunakan 4 word array S[1], …, S[4] mengandung xi+3, …, xi. Pada setiap clock, LFSR menghitung A = s[2] ⊕ (S[3] ≪ 31) ⊕ (S[4] ≫ 1). Nilai di shift (S[4] ← S[3], S[3] ← S[2], S[2] ← S[1]) dan nilai S[1] diset menjadi A. Setelah LFSR diperbarui, NLF output Ni dihitung. NLF menggunakan variasi operasi: XOR, penjumlahan modular, SWAP (A), swap upper 16 bit dan lower 16 bit dari A, dan ẋi, yang menunjukkan word xi dengan LSB menjadi 1. Algoritma NLF 1. A ← xi+3 + ẋi mod 232, dengan c1 ← carry, 2. A ← SWAP (A), 3. If (c1 = 0) then A ←xi+2 + A mod 232 dengan c2 ← carry, 4. Else A ← (xi+2 ⊕ẋi) + A mod 232 with c2 ← carry, 5. Ni ← (xi+1 ⊕xi+2) + A + c2 mod 232. LFG half cipher. State LFG terdiri dari 17 word (y1+16, …, yi). State diperbarui menjadi (y1+17, …, yi+1) meggunakan rumus: yi+17 = yi+12 + yi mod 232. LFG diimplementasikan menggunakan 17 word array G[1], …, G[17]. Key schedule menginisialisasi G[1], …, G[17] menjadi nilai y16, …, y0, dan menginisialisasi dua pointer r dan s menjadi 17 dan 5 berturut-turut. State LFG diperbarui dengan menghitung G[r] + G[s] = yi+12 + yi = yi+17 mod 232,
Dan mengganti nilai G [r] (yang sebelumnya yi) dengan nilai yi+17. Nilai-nilai r dan kemudian dikurangi oleh 1 (ketika r atau s mencapai nilai 0, nilai direset ulang ke 17). Output Li ditunjukkan sebagai Li = SWAP (yi), dan output Mi ditunjukkan sebagai Mi = G [1 + (s + (yi+17 >> 28) mod 16)]. (Nilai G [r] tidak berubah menjadi yi+17 sampai Mi diperoleh). Ketika Li, Mi dan Ni telah dihitung, output SSC2 zi = ((Li + Mi mod 232) ⊕ Ni). Naikkan i dan ulangi prosesnya.
3. Serangan pada setengah sistem LFSR Serangan pada LFSR ½ sistem adalah serangan korelasi yang cepat dan maju, dengan mengeksploitasi korelasi yang diamati antara bit terkecil dari output word yang telah dipilih dan 5 bit state LFSR. Serangan ini didukung dari fakta bahwa polinomial feedback dari LFSR adalah trinomial
. Meier dan Stafelbach mengamati [9] pada tahun 1980
bahwa setiap korelasi pada LFSR kurang dari 10 tap harus dihindari. 17. 231. (217 – 1 ) adalah periode dari pembangkit bilangan
Ingat kembali bahwa
Fibonacci ½ sistem. Jika dua segment dari output stream
selain dari operasi XOR, maka
kontribusi dari LFG ½ sistem dibatalkan, dan meninggalkan aliran XOR dari dua data LFSR yang dipilih untuk dianalisis. Jika
.
menotasikan korelasi fungsi linear tiap bit
pada state S. Ditentukan
, dimana
subskrip menunjukkan bit tertentu dari word ( dengan bit 0 menjadi bit terkecil ). Kemudian, . (perhatikan bahwa korelasi tersebut tidak benar yang dijelaskan pada [1]). Secara intuisi, tiga bit pada tahap ini di-XOR dengan bit terkecil pada . Sedangkan dua bit lainnya berkontribusi dengan bit carry yang mempengaruhi bagaimana hail ini dapat diinverskan atau menyebabkan propagasi carry. Jelas bahwa sama terhadap state
berkorelasi
, namun karena fungsi state yang diperbaharui adalah linear, bit dari
juga termasukfungsi linear dari bit .
. Sehingga
menunjukkan korelasi pada
Word pada state LFSRdiperbaharui berdasarkan pada polinomial feedback bitwise, tetapi karena panjang word (32bit) memiliki kekuatan dua, word state juga melaksanakan hubungan yang berkaitan dengan kekuatan ke-32 pada polinomial feedback. Jika dua aliran stream
dan
saling bebas, maka probabilitas korelasi akan bernilai
. namun, aliran stream disini ternyata tidak saling bebas dan secara eksperimen kita harus menentukan bahwa terdapat akibat ‘second order’ dan pada prakteknya probabilitas kesalahan mendekati 0,446, lebih sedikit dari yang diperkirakan 0,46875. Perhitungan ini membuat serangan korelasi lebih efisien. Serangan pada LFSR ½ sistem yaitu dengan mengumpulkan sekitar 32.000.000 word yang mana hanya bit terkecil yang digunakan pada serangan tersebut. Proses ini memrlukan dua segmen dari output stream tunggal, yang dipisahkan oleh
. kemudian
dilakukan perhitungan korelasi cepat, untuk mencoba output stream yang benar pada jumlah input yang berbeda bervariasi antara 29.000.000 bit dan 32.000.000 bit. Secara empiris, sekitar 2/3 bagian dari percobaab ini akan berhenti dan menghasilkan output yang benar L(S), beberapa percobaan akan menghasilkan hasil yang salah, dengan melakukan sejumlah besar iterasitanpa mengoreksi nomor signifikan yaitu sisa error. Bagian di bawah ini menjelaskan bagaimana serangan korelasi singkat itu. Jika serangan tersebut menghasilkan output yang benar, maka aljabar linear digunakan untuk menghubungkan kembali kepada inisial state Sekuens dari bahwa
adalah benar. Jika
.
dapat direkonstruksi dari inisial state untuk memverifikasi tidak benar atau serangan ‘bogs down’ maka sejumlah bit
input yang berbeda akan dicoba. Komputasi korelasi single singkat ini akan berhasil dan membutuhkan sekitar 1 jam pada 250 Mhz, dan menggunakan sekitar 70MB memori. Ketika komputasi ‘bogs down’, perhitungan akan terhenti sembarang setelah 1000 round dan membutuhkan beberapa jam. Untuk himpunan output tertentu, seluruh inisial state seringkali direcovery sedikit dalam satu jam, dan tidak seperti state yang benar yang tidak akan ditemukan dalam sehari.
3.1 Meningkatkan Ketepatan dari Serangan Kecepatan Korelasi Uraian di bawah ini berlaku terutama untuk LFSRs dengan feedback beratnya rendah, khususnya di mana feedback trinomial digunakan. Sejumlah makalah telah ditulis sejak penerapan teknik heuristik untuk mempercepat atau meningkatkan akurasi teknik dasar serangan korelasi cepat. Kami terlebih
dulu menghabiskan banyak waktu meneliti beberapa teknik ini, dan variasi dalam parameter dasar, untuk memperoleh pemahaman intuitif tentang apa yang berguna dan apa yang tidak. Teknik asli perbedaan antara round dan iterasi, di mana round mulai dengan masing-masing bit yang memiliki priori error probability yang sama. Probabilitas baru dihitung untuk setiap bit yang didasarkan pada probabilitas bit yang lain yang terlibat dalam persamaan cek parity. Iterasi berikutnya melakukan perhitungan dasar yang sama berdasarkan probabilitas baru, cukup sampai bit probabilitas error telah melebihi ambang batas tertentu, atau yang telah ditetapkan jumlah iterasi yang telah terlampaui. Kami menemukan argumen yang mendukung perlakuan iterasi tidak memuaskan, karena tampaknya probabilitas baru hanya self-reinforcing. Akhirnya, kami membuat perubahanperubahan struktural pada program yang membuatnya mustahil melakukan iterasi, dan menemukan keseluruhan peningkatan akurasi. Dasar algoritma korelasi memiliki probabilitas error P sebagai parameter input; P adalah terus konstan di seluruh komputasi, dan probabilitas bit di-reset ke P pada awal masing-masing round. Dalam kenyataannya, probabilitas error menurun pada masing-masing round (pada inisial akhir), jadi pendekatan ini menghasilkan perkiraan yang tidak akurat untuk probabilitas bit. Kami menemukan bahwa sebagai probabilitas error nyata mendekati 0.5, maka nilai konstan P adalah tidak mungkin mengakibatkan serangan yang sukses. Perhitungan lebih mungkin berhasil jika P diperkirakan pada setiap putaran. Dengan diberikan P, itu sangat mudah untuk menghitung proporsi persamaan paritas cek diharapkan akan satisfied oleh data. Proses ini dapat dibalik dengan mudah juga; setelah mengamati proporsi persamaan paritas cek satisfied, mudah untuk menghitung probabilitas kesalahan P:1 ) Karena setiap putaran dimulai dengan menghitung persamaan paritas cek,itu adalah masalah sederhana untuk menghitung P setiap round. Teknik ini pada dasarnya melarang penggunaan pengulangan, dan teknik penyingkiran seperti “reset cepat ", namun demikian mempercepat serangan dan meningkatkan kemungkinan keberhasilan. Kami merasa
penting untuk memiliki kemungkinan terbesar jumlah cek paritas
persamaan untuk setiap bit pada pengoperasian algoritma, jadi kami melakukan satu kali perhitungan secara brute force untuk mencari berat rendah kelipatan dari polinomial lain dari kejelasan lain (yang dasar kekuatan polinomial). Kami menemukan beberapa dari mereka. Seperti halnya
, serangan menggunakan
dan semua kemungkinan kekuatan polinomial ini. Untuk setiap bit, paritas cek pada bit di kiri, di tengah, dan di kanan, semuanya digunakan. Untuk input 30.000.000 bit, rata-rata 200 persamaan paritas cek diterapkan pada setiap bit. Terakhir, kita membuat pengamatan yang relatif awal pada perhitungan, sebuah angka penting dari semua bit penting pada ketersediaan persamaan paritas cek. Kami menyebut ini keseluruhan bit penting. dengan percobaan kita bertekad bahwa ketika lebih dari beberapa ratus bit yang tersedia, dan jika perhitungan itu akhirnya berhasil, mereka hampir semua benar, sehingga setiap bagian dari 127 dari mereka memiliki probabilitas tinggi membentuk rangkaian bebas secara linear pada persamaan di state bit awal, yang kemudian bisa diselesaikan dengan cara yang mudah. Dengan komputasi, mengambil kesempatan awal ini untuk menghitung jawabannya adalah perbaikan kinerja penting. Pada jalan yang khas dengan input 30.000.000 bit, 5.040 fully satisfied bit yang tersedia setelah 16 round, yang semuanya ternyata benar, ketika diperlukan perhitungan penuh 64 round. Ini bukan sebagai suatu pengoptimalan besar seperti kedengarannya, karena round bisa lebih cepat seperti jumlah bit dikoreksi berkurang.
3.2 Meningkatkan kecepatan serangan Fast Correlation Pada waktu yang sama ketika melakukan analisis pada teori dasar untuk perbaikan dalam algoritma, dapat dilihat juga pada optimisasi komputasi pada algoritma. Ketika probabilitas kesalahan bit adalah sebuah variabel, maka probabilitas komputasi sangat kompleks dan membutuhkan usaha yang signifikan pada setiap bitnya, sama seperti persyaratan untuk menyimpan angka floating-point pada setiap bitnya. Ketika probabilitas kesalahan P diasumsikan sama untuk semua bit pada awal round, komputasi berkurang secara signifikan. Lebih penting lagi, kemungkinan bahwa suatu bit error dapat dinyatakan sebagai threshold dari jumlah persamaan parity check yang tidak sesuai, dengan diberikan jumlah persamaan parity check untuk bit tersebut, dan probabilitas P. Jumlah persamaan parity check yang tersedia untuk bit tertentu adalah mendekati jumlah sisi himpunan data dan meningkat hingga pusat data. Selama melewati data yang pertama, jumlah persamaan yang tersedia untuk setiap bit adalah hanya perhitungan (hal ini
secara komputasi tidak relevan dibandingkan memeriksa persamaan) dan indeks dimana jumlah tersebut berbeda dengan bit sebelumnya yang tersimpan. Maka, dibutuhkan sedikit tambahan memori untuk menghasilkan total jumlah dari parity check pada bit tertentu dalam sub bagian yang dilewati. Pada setiap round, proses pertama yang dilewati data adalah menghitung (dan menyimpan) jumlah check yang tidak sesuai untuk setiap bit. Dari total proporsi parity check yang tidak sesuai, P dihitung untuk round tersebut, dan dari hasil tersebut, nilai threshold diatas yang salah satu bit error dihitung untuk setiap persamaan parity check. Ketika P>0.4, hal tsb tepatnya benar untuk lebih dari setengah parity check yang tidak sesuai yang menyebabkan probabilitas dari bit tersebut lebih besar dari 0.5, dan bit tsb seharusnya benar. Bagaimanapun, ketika P>0.4, persamaan lain harus tidak sesuai sebelum dilakukan flipping bit secara justify. Algoritma tersebut dikatakan sukses jika sangat bergantung pada pernyataan awal. Kelulusan dilakukan melalui data dengan flipping bit yang dibutuhkan. Untuk setiap bit yang dibalik, jumlah parity check yang tidak sesuai adalah benar, tidak hanya pada bit tersebut namun juga terhadap setiap bit yang termasuk di dalam persamaan parity check tersebut. Faktor koreksi diakumulasi dalam array yang terpisah sehingga koreksi dapat dilakukan terhadap semua bit secara efektif dan berkesinambungan. Bit yang tidak memiliki parity check yang tidak sesuai ditandai. Pada round awal, pendekatan yang meningkat tidak disimpan banyak, melainkan beberapa bit dikoreksi setiap roundnya dan perhitungan yang disimpan menjadi sangat signifikan. Berdasarkan jenisnya, 50% dari seluruh perhitungan nantinya akan disimpan ketika jumlah dari seluruh bit yang sesuai mencapai panjang dari register, dan hasilnya didapatkan dari aljabar linier. Efek jaringan dari perubahan yang telah dijelaskan pada makalah ini dan bagian sebelumnya adalah faktor dari ratusan dalam waktu yang dibutuhkan untuk himpunan data sekitar 100.000 bit mencapai implementasi secara terus-menerus. Kita tidak memiliki cukup waktu untuk menemukan kecepatan pada himpunan data yang lebih besar, yang mana akan membutuhkan waktu yang sangat lama untuk dijalankan pada algoritma yang asli.
4. Attack pada LPG Half cipher Attack pada LPG half cipher ini nantinya akan menghasilkan nilai initial state iv = (y16, ..., y0) dari output vi = Li + Mi mod 232 = zi Ni. Kebanyakan analisis dilakukan didasarkan pada pembagian 32-bit words menjadi dua blok 16-bit a = aH||aL. Berikut ini persamaan yang digunakan :
yLi yLi 12 yLi 17 0 mod 216 yH i yH i 12 yH i 17 0 mod 216
dimana fi {0,1}, yang menotasikan ibit carry untuk upper half pada (yi + y1+12). Nilai i ( yi 17 28) memilih Mi dari yi, ....., yi+16 : M i G[1 (s i mod 16)] .Lalu nilai untuk i sedemikian sehingga M i yi i merupakan multiplexor difference. Dan perlu dicatat bahwa i dituliskan dalam bentuk heksa dan i dituliskan dalam bentuk desimal. Suatu word dipilih berdasarkan nilai i dan s, dimana s berhubungan langsung dengan nilai def
dari i i mod 17. Sebagai contoh, jika i =0, maka i = 12, jika i bukan elemen {4,5}, dalam hal ini i = 11. Attack ini mengeksploitasi suatu sifat dari output (vi , vi+12) dengan
i = i 12 = 12. Jika sifat tadi terpenuhi maka (vi , vi+12) disebut good pair, sementara yang lainnya disebut bad pairs. Jika (vi , vi+12) merupakan good pair maka Mi = yi+12 dan Mi+12 =yi+24, sehingga
dimana gi {0,1} merupakan bit carry dari lower half pada upper half dalam penjumlahan vi= Mi + Li. Misalkan diberikan sebuah good pair, (yLi+24 – yLi) bisa diperoleh dari (vLi+12 – vHi) dengan menduga gi. Karena setiap 16-bit half word yLi adalah suatu fungsi linier (mod def
216) dari ivL ( yL16 ,...., yL0 ) dan juga dari (yLi+24 – yLi).
Nilai (yLi+24 – yLi) akan
merupakan bebas linier jika persamaan linier untuk (yLi+24 – yLi) bersifat bebas linier. Jika seorang attacker mengetahui sebuah himpunan dari 17 nilai – nilai (yLi+24 – yLi) yang bebas linier maka nilai ivL dapat ditentukan dengan cara menyelesaikan sistem persamaan linier. Sekarang, nilai ivL telah diperoleh, maka nilai yLi pun dapat dihitung. Untuk setiap 17 good pairs tersebut, nilai yLi+12 mengizinkan yHi vLi – yLi+12 mod 216 untuk dihitung. Perhitungan yLi menyelesaikan word yi = yHi||yLi. Ketujuhbelas persamaan yi juga akan bebas linier, sehingga sistem ini dapat dipecahkan untuk mencari initial state dan attack ini selesai. Tinggal dua permasalahan lagi, yaitu menduga 17 bit carry gi dan mengidentifikasi good pairs. Attack ini pasti akan mencoba berbagai kombinasi nilai-nilai gi sebelum bit carry ditemukan. Akan tetapi, attack ini menghindari mencoba semua 217 kombinasi dengan cara menghitung suatu prediksi pi dengan tepat untuk nilai gi. Jika vLi < 215 maka ini lebih tepatnya bahwa penjumlahan (yHi + yLi+12 mod 216) yang dihasilkan pada sebuah bit carry, sehingga attack memasang nilai pi = 1. Atau, attack memasang nilai pi = 0. Ketimbang menduga nilai gi, ketujuhbelas eror ei = pi gi diduga, mulai dari tidak ada eror, kemudian sebuah eror, dua eror, dan seterusnya. Jika semua pasangan merupakan good pair maka akan hanya terdapat sejumlah kecil erornya. Pada saat memilih 17 nilai (yLi+24 – yLi) yang bebas linier, attack memberikan pilihan nilai dengan prediksi yang akurat dimana memiliki eror yang lebih
sedikit, dan attack akan menjadi lebih cepat. Keakuratan memprediksi P(pi = gi)tergantung pada vLi :
Seperti yang ditunjukkan di bawah, attack ini mempunyai probabilitas yang kecil untuk memilih satu atau lebih bad pairs. Jika initial state yang tepat tidak ditemukan sementara jumlah erornya kecil, maka hal ini menendakan bahwa salah satu pasangannya merupakan bad pair, sehingga kita harus memilih himpunan 17 nilai-nilai (yLi+24 – yLi) yang bebas linier. Terdapat 16 kemungkinan nilai i , sehingga kita mengharapkan good pairs muncul rata-rata setiap 162 = 256 word. Permasalahannya adalah pada mengidentifikasi good pairs. Adapun triknya untuk mengindentifikasi triples (vi, vi+12, vi+17) dengan i = i +12 = i +17 = 12. Attacker memulainya dengan mengidentifikasi triples tersebut dengan
Ketika triples tersebut dapat ditunjukkan memenuhi
i = i +12 = i +17 = 12, dengan
probabilitas mendekati satu. Triples tersebut dikatakan valid karena i = i +12 (= i +17 ) dengan probabilitas mendekati satu. Perlu dicatat bahwa i , i +12, dan i +17
harus
memenuhi hubungan berikut :
dikarenakan perulangan kondisi yi+17 = yi+12 + yi mod 232 (carry {0,1}). Akibatnya, kemungkinan kombinasi untuk ( i , i +12, i +17) yang menghasilkan suatu triple valid dibatasi sebagai berikut :
Sebuah triple valid yang berkorespondensi pada sebuah good pair juga dapat disebut sebagai good pair, selain itu triple dikatakan sebagai bad pair. Jika i = 4, maka semua triple valid adalah good pair. Kemudian jika i {5,10}, maka semua kemungkinan triple valid merupakan bad pair sehingga triple-triple tersebut diabaikan. Pada dasarnya, tidak ada
metode yang efisien untuk membedakan antara kasus kondisi ketika ( i , i +12, i +17) = (0,F,0) dan ( i , i +12, i +17) = (1,0,1), sehingga attack juga mengabaikan triple-triple dengan i = 9. Jika i {4, 5, 9, 10}, maka sebuah triple valid mirip good pair maupun bad pair. Mirip good pair ketika ( i , i +12, i +17) = (0, 0, 0) dan mirip bad pair ketika ( i , i +12, i +17) = (F, F, F). Kedua kasus kondisi di atas mempunyai distribusi yang def
berbeda untuk eHi, vLi dan
vi (vHi 12 vLi mod 216 ) 12 keempat MSBs dari
(vHi 12 vLi mod 216 ) .
Attack ini menghilangkan triple-triple dengan i {4, 5, 9, 10}, jika vi {0, 1, F}, atau eHi {0,1} atau jika vLi < 215 dan eHi = 0. Berikut ini, 0,84 dari good triples yang tersisa, sementara itu hanya 0,024 bad triples yang tersisa. Dengan demikian 0,024/0,84 = 0,028 dari bad triples yang tersisa. Berikut ini algoritma dari LFG Half cipher attack : 1. Cari sebuah himpunan triple-triple valid dengan i {5, 9, 10}. Untuk i 4 , hilangkan triple-triple jika vieHi {0,1} atau jika eHi = 0 dan vLi < 215. Himpunan pi = 1 jika vLi < 215, atau jika pi =0. 2. Berdasarkan triple-triple di atas, temukan 17 nilai (yLi+24 – yLi) bebas linier untuk P(pi = gi) = 1. 3. Tebak nilai eror ei. Jika jumlah eror besar, maka kembali ke langkah kedua. 4. Hitung ivL dari ( yLi 24 yLi ) vLi 12 vHi ( pi ei ) mod 216 5. Hitung nilai yH i vLi yLi 12 mod 216 , untuk memperoleh yi. 6. Hitung semua state iv dari yi. Kembali ke tahap 3 jika iv menghasilkan output yang salah. Kesimpulan Berdasarkan penjelasan mengenai attack di atas, maka dapat disimpulkan bahwa secara komputasi mudah dilakukan, dengan diberikan sejumlah key-stream yang cocok. Sehingga dengan adanya attack ini, mengindikasikan bahwa SSC2 tidak cukup aman sebagai syarat untuk penyandian modern.
