Algoritma W7 (Stream cipher)

A. DESKRIPSI

A.1. Algoritma W7 dengan basis LFSR

Algoritma W7 merupakan algoritma stream cipher synchronous dengan key input sepanjang 128 bit. Dalam algoritma W7 digunakan LFSR sebagai dasar dalam perancangannya. Algoritma W7 menggunakan 8 kombinasi LFSR yang dioperasikan secara parallel. Setiap kombinasi LFSR tersebut terdiri dari 3 buah shift register. Kombinasi dari 3 shift register tersebut akan menghasilkan 1 bit kunci stream sehingga output dari algoritma W7 adalah 8 bit (1byte) rangkaian kunci tiap 1 satuan waktu.

Pada gambar 2 dapat dilihat salah satu kombinasi LFSR yang digunakan dalam algoritma W7,sedangkan pada gambar 3 merupakan bagan dari key generator algoritma W7.

Gambar 2. Salah satu kombinasi LFSR yang digunakan dalam algoritma W7

 

Output dari algoritma W7 tidak diambil langsung dari setiap LFSR, tetapi diambil dengan mengkombinasikan bit output akhir dari setiap shift register dengan operasi exclusive_OR (XOR). Output akhir dari setiap shift register merupakan hasil dari suatu fungsi filter nonlinier yang merupakan operasi XOR dari dua buah nilai yaitu, output dari LFSR dan operasi AND dari beberapa bit dalam LFSR.

 

C0

C1

C2

C3

C4

C5

C6

C7

Output 8-bit/1-byte kunci tiap satu satuan waktu

LFSR 0 LFSR 1 LFSR 2 LFSR 3 LFSR 4 LFSR 5 LFSR 6 LFSR 7

 

 

 

 

 

 

 

 

Gambar 3. Bagan key generator algoritma W7

Fungsi feedback yang digunakan merupakan sebuah fungsi polynomial karakteristik yang primitive dengan Greatest Common Divisor (GCD) dari panjang tiap stage sama dengan 1.

 

A.2. Inisialisasi Awal

Panjang total dari ketiga LFSR yang dikombinasikan dalam algoritma W7 adalah sebanyak 128 stage, masing-masing stage adalah 38, 43 dan 47 stage. Initial state dari tiap-tiap LFSR adalah bit-bit dari 128 bit bit kunci yang dimasukkan. Dari 128 bit kunci input tersebut satu persatu dimasukkan dalam tiap stage dari ketiga LFSR secara berurutan mulai dari LFSR 1 stage pertama sampai dengan LFSR 3 stage terakhir.

Berikut ini adalah pemetaan 128 bit kunci sebagai inisial state pada tiap stage dari ketiga LFSR tersebut :

LFSR 1 (38 bit) : Stage 0 = bit kunci ke-0

Stage 1 = bit kunci ke-1

Stage 2 = bit kunci ke-2

: :

: :

Stage 37 = bit kunci ke-37

 

LFSR 2 (43 bit) : Stage 0 = bit kunci ke-38

Stage 1 = bit kunci ke-39

: :

: :

Stage 42 = bit kunci ke-80

LFSR 3 (47 bit) : Stage 0 = bit kunci ke-81

Stage 1 = bit kunci ke-82

: :

: :

Stage 46 = bit kunci ke-127

Output yang digunakan sebagai kunci penyandian stream diambil mulai dari byte ke-1032. Setelah dibangkitkan 1031 byte pertama yang muncul diabaikan.

 

A.3. Proses Pembangkitan Rangkaian Kunci

Proses pembangkitan rangkaian kunci diawali dengan beberapa bit dari beberapa LFSR untuk dikombinasikan dari tiap LFSR untuk dioperasikan dengan operasi AND. Hasil operasi AND tersebut kemudian di XOR dengan output dari tiap LFSR. Hasil akhir dari tiap LFSR tersebut dikombinasikan dengan operasi XOR untuk mendapatkan 1 bit kunci dari rangkaian kunci bit kunci stream yang akan digunakan untuk menyandi setelah pengambilan 1 bit output dilanjutkan dengan bergesernya setiap shift register dari ketiga LFSR yang dikendalikan oleh clock dari majority function.

Berikut ini adalah table dari bit-bit yang dioperasikan dalam fungsi feedback, fungsi filter dan bit-bit clock :

Kombinasi LFSR 0

LFSR 0a (38 bit)

Fungsi feedback : 37 32 29 27 26 21 20 14 12 10 9 8 5 2 0

Clock : 22

Output filter : 37 (36,33) (32,29) (28,25,22)

LFSR 0b (43 bit)

Fungsi feedback : 42 5 3 2

Clock : 25

Output filter :42 (41,39) (38,36) (35,33,31)

LFSR 0c (47 bit)

Fungsi feedback : 46 4

Clock : 27

Output filter : 46 (45,40) (39,34) (33,28,23)

Kombinasi LFSR 1

LFSR 1a (34 bit)

Fungsi feedback : 37 36 34 31 28 27 26 25 24 22 16 15 10 9 7 4

Clock : 5

Output filter : 37 (3,0) (7,4) (14,11,

LFSR 1b (43 bit)

Fungsi feedback : 42 39 38 36

Clock : 18

Output filter : 42 (2,0) (5,3) (10,8,6)

LFSR 1c (47 bit)

Fungsi feedback : 46 41

Clock : 20

Output filter : 46 (5,0) (11,6) (22,17,12)

Kombinasi LFSR 2

LFSR 2a (38 bit)

Fungsi feedback : 37 28 21 18 17 16 14 10 9 7 4 0

Clock : 21

Output filter : 37 (35,32) (31,2 (27,24,21)

LFSR 2b (43 bit)

Fungsi feedback : 42 29 16 5 4 3 2 0

Clock : 24

Output filter : 42 (40,3 (37,35) (34,32,30)

LFSR 2c (47 bit)

Fungsi feedback : 46 32 18 4

Clock : 26

Output filter : 46 (44,39) (38,33) (32,27,22)

Kombinasi LFSR 3

LFSR 3a (38 bit)

Fungsi feedback : 37 36 32 29 27 26 22 20 19 18 15 13

Clock : 16

Output filter : 37 (4,1) (8,5) (15,12,9)

LFSR 3b (43 bit)

Fungsi feedback : 42 41 39 38 37 36 25 12

Clock : 19

Output filter : 42 (3,1) (6,4) (11,9,7)

LFSR 3c (47 bit)

Fungsi feedback : 46 41 27 13

Clock : 21

Output filter : 46 (4,1) (12,7) (21,18,13)

Kombinasi LFSR 4

LFSR 4a (38 bit)

Fungsi feedback : 37 24 22 11 7 5 3 1

Clock : 20

Output filter : 37 (34,31) (30,27) (26,23,20)

LFSR 4b (43 bit)

Fungsi feedback : 42 34 26 19 18 17 12 5 4 3

Clock : 23

Output filter : 42 (39,37) (36,34) (33,31,24)

LFSR 4c (47 bit)

Fungsi feedback : 46 4 3 0

Clock : 25

Output filter : 46 (43,3 (37,32) (31,26,21)

Kombinasi LFSR 5

LFSR 5a (38 bit)

Fungsi feedback : 37 35 33 31 29 25 14 12

Clock : 17

Output filter : 37 (5,2) (9,6) (16,13,10)

LFSR 5b (43 bit)

Fungsi feedback : 42 38 37 36 29 24 23 22 15 7

Clock : 20

Output filter : 42 (4,2) (7,5) (12,10,

LFSR 5c (47 bit)

Fungsi feedback : 46 45 42 41

Clock : 22

Output filter : 46 (5,2) (13, (22,19,14)

Kombinasi LFSR 6

LFSR 6a (38 bit)

Fungsi feedback : 37 5 4 0

Clock : 19

Output filter : 37 (33,30) (29,26) (25,22,19)

LFSR 6b (43 bit)

Fungsi feedback : 42 29 28 25 17 14 13 9 4 3

Clock : 22

Output filter : 42 (38,36) (35,33) (32,30,2

LFSR 6c (47 bit)

Fungsi feedback : 46 32 18 10 7 4

Clock : 24

Output filter : 46 (42,37) (36,31) (30,25,20)

Kombinasi LFSR 7

LFSR 7a (38 bit)

Fungsi feedback : 37 36 32 31

Clock : 18

Output filter : 37 (6,3) (10,7) (17,14,11)

LFSR 7b (43 bit)

Fungsi feedback : 42 38 37 28 27 24 16 13 12

Clock : 21

Output filter : 42 (5,3) (8,6) (13,11,9)

LFSR 7c (47 bit)

Fungsi feedback : 46 41 38 35 27 13

Clock : 23

Output filter : 46 (6,3) (14,9) (23,20,15)

A.3. Proses Enkripsi Dan Dekripsi Algoritma W7

Proses enkripsi dari algoritma W7 adalah 1 byte kemudian di XOR dengan 1 byte teks terang untuk menghasilkan 1 byte teks sandi, demikian pula proses dekripsinya. Setiap 1 byte teks sandi di XOR dengan 1 byte kunci yang sama dengan saat menyandi untuk mendapatkan 1 byte teks terang. Proses enkripsi dilakukan setelah run up rangkaian kunci sebanyak 1031 byte. Bagan proses enkripsi dari algoritma W7 dapat dilihat pada gambar 4 dibawah ini :

Key Stream Generator

 

K_i (byte kunci ke-1032)

XOR

Plain (P_i)

 

Cipher(C_i)

Gambar 4. Bagan proses enkripsi dari algoritma W7

B. ANALISIS

B.1. Panjang Periode Kunci Algoritma W7

Algoritma W7 menggunakan 8 kombinasi LFSR, dimana setiap kombinasi terdiri dari 3 buah shift register dimana panjang stage masing-masing shift register yaitu 38, 43 dan 47 memiliki GCDnya adalah 1 dan tiap shift register merupakan polynomial karakteristik yang primitive maka periode dari tiap LFSR tersebut ≤ (2³⁸-1)(2⁴³-1)(2⁴⁷-1)

Karena W7 menggunakan 8 buah kombinasi LFSR untuk menghasilkan 8 bit/1 byte persatuan waktu maka periode dari algoritma W7 adalah ≤ ((2³⁸-1)(2⁴³-1)(2⁴⁷-1))⁸.

 

B.2. Kerandoman Kunci Yang Dihasilkan Dari Algoritma W7

Dilihat dari basis yang digunakannya adalah LFSR, dimana sudah diketahui bahwa LFSR lulus dalam kerandoman golomb maka algoritma W7 dapat dikatakan cukup kuat. Tetapi untuk memastikan bahwa output yang dihasilkan tetap sesuai dengan yang diharapkan, maka output yang dihasilkannya pun harus diuji terlebih dahulu dengan uji yang telah disepakati.

 

B.3. Crypanalisa Terhadap Algoritma W7

Karena Algoritma W7 dengan Algoritma A5/1 tidak terlalu berbeda jauh maka attack yang dapat dilakukannya tidak terlalu berbeda juga. Attack yang dapat/pernah dilakukan pada A5/1 diantaranya :

Ø Brute force attack : Dengan menggunakan komputer dengan kecepatan proses yang sangat tinggi maka Algoritma A5/1 dapat dipecahkan.

Ø Alex Biryukof dan Adi Shamir (Co-Inventor of RSA) mengklaim mampu membuka algoritma A5/1yang digunakan GSM kurang dari 1 detik menggunakan PC dengan RAM 128 MB dan Hard Drives yang sangat besar.

Dari gambaran diatas dapat dilihat bahwa crypanalysis terhadap Algoritma W7 masih mungkin dapat dilakukan.