Correlation Attack Pada Geffe Generator

Correlation Attack pada Geffe Generator

LFSR Stream Cipher

Ada beberapa kondisi yang disyaratkan dalam pembangunan stream cipher berdasarkan LFSR. Dantaranya adalah hasil dari keystream-nya memiliki periode yang panjang, memiliki kompleksitas linier yang besar, dan memenuhi property statistik. Hal ini disebut dengan generator yang digunakan memenuhi cryptographically secure. Pembuktian matematika dari pembangkit bilangan acak tidak diketahui. Kondisi computationally secure akan didapat dengan cara mem-pubish algoritma yang digunakan. Hal ini mendorong bnyak pihak di luar untuk melakukan serangan. Serangan-serangan inilah yang akan terus membangun algoritma hingga algoritma ini selalu tahan terhadap serangan. Sampai saat ini pemuktian matematika tidak bisa membuktikan kekuatan dari generator.

LFSR adalah salah satu generator yang dapat dinotasikan dalam kombinasi linier.LFSR tiak banyak dipaai karena mudah dalam melakukan serangan. Yang banyak dipakai adalah kombinasi NLFSR yang dianggap lebih kuat terhadap serangan linier. Ada beberapa jenis kombinasi NLFSR yakni nonlinier combination generator, filter generator, dan clock control generator. Dari ketiganya, geffe generator termasuk nonlinier combination generator.

Fungsi kombinasi yang digunakan harus balance artinya menghasilkan barisan yag jumlah bit 1 dan 0 nya seimbang, harus dipilih secara teliti hingga tidak ada hubungan antara satu input ke output dan juga hubungan antar output, memiliki nonlinieritas yang tinggi yang tidak bisa dinotasikan dalam kombinasi linier, serta polynomial yang digunakan memiliki order pangkat yang tertinggi.

Terdapat n max panjang LFSR, yaitu R1,R2,….Rn dengan panjang L1,L2,,,,Ln dimasukkan dalam sebuah generator kombinasi non linier. Jika hubungan polinomial pada LFSR dan fungsi kombinasi f diketahui publik, maka jumlah kunci yang berbeda pada generator adalah .sebuah kunci terdiri daqri panjang initial state pada LFSR.

Terdapat korelasi antara keystream dengan rangkaian output pada R1, dengan probabilitas korelasi p > ½. Jika panjang segmen pada keystream diketahui, initial state pada R1 dapat diperoleh dengan menghitung jumlah coincidence antara keystream dan semua kemungkinan pergeseran pada output sequence R1, hingga mencapai probabilitaas korelasi yaitu p. untuk mendapatkan initial state maka akan dilakukan 2L1 – 1 kali percobaan. Dalam hal ini ada korelasi antara keystream dan output sequence pada setiap R1,R2,….Rn. initial state pada setiap LFSR dapat ditentukan secara independent dengan total kira-kira percobaan. Jumlah ini sedikit lebih jauh dibandingkan dengan perbedaan kunci. Dengan cara yang sama, kita bisa mendapatkan korelasi antara output sequence pada LFSR dengan keystream.

Geffe Generator

Terdiri dari 3 buah LFSR dengan memiliki panjang L1,L2,L3, yang saling relatif prima, dengan kombinasi linier

Keystream di-generate dengan memiliki periode dan kompleksitas linier


Secara kriptografi, geffe generator lemah karena informasi tentang state pada LFSR1 dan LFSR3 terpecahkan dalam output sequence. Untuk melihatnya, x1(t),x2(t),x3(t),z(t) dinotasikan dengan tth output bit LFSR 1,2,3 dan keystream. Maka probabilitas korelasi pada x1(t) terhadap sequence output z(t) adalah:

P(z(t)=x1(t))= P(x2(t)=1) + P(x2(t)=0) . P(x3(t)=x1(t))

= ½ + ½ . ½ = ¾

P(z(t)=x3(t))=3/4.

Correlation Attack

Correlation attack diperkenalkan olej Siegenthaler pada tahun 1985. Serangan ini diaplikasikan pada sembarang running key generator yang terdiri dari beberapa LFSR. Correlation attack berbasis divide-and-conquer technique, yang bertujuan untuk mencari initial state dari setiap LFSR secara parsial berdasarkan pengetahuan tentang sebagian kunci stream outputnya.

Correlation attack orisinil diaplikasikan pada suatu combination generator yang terdiri dari n LFSR dengan panjang L1, L2, …, Ln. Serangan ini memungkinkan memperoleh inisialisasi yang lengkap dari generator hanya dengan melakukan j=1ån (2Li – 1) percobaan dibandingkan j=1Pn (2Li – 1) percobaan pada bruce force attack. Correlation attack memanfaatkan adanya ketergantungan statistik antara kunci stream dengan output dari sebuah LFSR konstituennya. Ketergantungan tersebut ada jika dan hanya jika output dari fungsi kombinasi f berkorelasi dengan satu dari inputnya, yaitu :

pi = Pr[f(x1,x2,…,xn) ¹ xi ] ¹ ½

untuk beberapa i, 1 £ i£n.

Ekivalen bahwa rangkaian kunci s =(st)t³0 berkorelasi dengan barisan u =(ut)t³0 yang dibangkitkan oleh salah satu LFSR konstituennya. Korelasi antara kedua barisan yang dihitung pada N-bit t=0åN-1 (-1)st+ut mod 2 merupakan variabel acak yang berdistribusi binomial dengan rata-rata N(1-2pi) dan variansi 4Npi(1-pi), dimana N cukup besar

Secara praktis, suatu initial state diterima jika nilai korelasi melebihi daerah kritis dari nilai probabilitas. Panjang kunci yang dibutuhkan tergantung pada probabilitas yang digunakan dan juga panjang LFSR yang teribat.

Pseudocode yang digunakan adalah sebagai berikut :

n Input. s0s1…sN-1 bit kunci stream,

pi = Pr[f(x1,x2,…,xn) ¹ xi ] ¹ ½

n Output. u0u1…uLi-1 ; initial state dari LFSR kontituen ke-i.

n Untuk setiap kemungkinan initial state

Generate N bit pertama dari barisan u yang dihasilkan oleh LFSR ke-i dengan initial state yang dipilih.

Hitung korelasi antara barisan s dan u :

a ¬ t=0åN-1 (-1)st+ut mod 2

Jika a mendekati N(1-2pi)

return u0u1…uLi-1

Berikut adalah contoh correlation attack yang dilakukan pada geffe generator

LFSR 1 : 1+x+x4 initial key :1000 ,100011110101100

LFSR 2 : 1+x+x3 initial key : 110 ,010011101001110

LFSR 3 : 1x2+x5 initial key : 10101 ,101011101100011

Output sequence adalah 101011100101101

Cara yang digunakan untuk melakukan exhaustive key search adalah 15*7*31=3255, dengan correlation attack hanya membutuhkan 15+7+31=53
Sumber