W7 Algorithms (algoritma Berbasis LFSR)

W7 Algorithms

Didi Supriadi (1), Indra Adi Putra (2)
Tingkat II Teknik Rancang Bangun Peralatan Sandi, Sekolah Tinggi Sandi Negara
Email: indraadiputra@ymail.com. http://indraadiputra.co.cc (1), (2)

Abstraksi
Kriptografi atau yang sering dikenal dengan sebutan ilmu penyandian data adalah suatu bidang ilmu dan seni (art and science) yang bertujuan untuk menjaga kerahasiaan suatu pesan. 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.


Keyword : W7 Algorithm, LFSR

1.Pendahuluan
Kriptografi adalah suatu ilmu ataupun seni mengamankan pesan. Orang yang melakukan kegiatan tersebut dinamakan kriptografer. Kriptografi digunakan pada pengamanan informasi dimana menckup masalah-masalah yang sangat penting seperti kerahasiaan suatu pesan (Convidentiality), keutuhan suatu pesan (Massage Integrity), penyangkalan suatu pesan (Non-repudiation0, dan keaslian suatu pesan (Authentication).
Pada kriptografi ada dua tipe algoritma yang digunakan apabila algoritma tersebut berdasarkan pada kuncinya yaitu algoritma simetris (simetric algorithm) dan algoritma kunci publik (public-key algorithm) atau sering disebut algoritma asimetric. Perbedaan utama antara Symetric dengan asimetric algorithm adalah pada kunci yang digunakan dimana pada simetric kunci untuk mengenkrip atau mendekrip sama namun pada asimetric kunci yang digunakan untuk menyandi dan membuka sandi berbeda. Selain itu juga terdapat perbedaan dalam kecepatan proses dan keamananya.
Dalam kriptografi proses yang dilakukan untuk mengubah plaintext ke dalam ciphertext disebut enkripsi. Sedangkan proses untuk mengubah ciphertext kembali ke plaintext disebut dekripsi.

Berdasarkan algoritma penyandiannya algoritma kriptografi dibagi menjadi blok cipher dan stream cipher. Pada blok cipher menggunakan kunci simetrik dimana setiap plain teks dibagi menjadi blok-blok tertentu yang kemudian dienkripsi menjadi blok-blok cipher teks.



2.Notasi
Dalam paper ini akan dijelaskan algoritma Ketupat yang didalamnya terdapat operasi dasar aritmatika yang menyusunnya. Operasi dasar tersebut dapat dilambangkan dengan notasi sebagai berikut ;
a + b , penjumlahan integer dengan mod 232
a + b , bitwise XOR
a b , bitwise exclusive-OR
a <<< b , rotasi word a ke arah kiri sejumlah nilai yang diberikan pada least significant bit b

3.Deskripsi Algoritma
3.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.


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

3.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.

3.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,8)
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,28) (27,24,21)
LFSR 2b (43 bit)
Fungsi feedback : 42 29 16 5 4 3 2 0
Clock : 24
Output filter : 42 (40,38) (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,38) (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,8)
LFSR 5c (47 bit)
Fungsi feedback : 46 45 42 41
Clock : 22
Output filter : 46 (5,2) (13,8) (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,28)
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 :


4.Analisis Algoritma
4.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 ≤ (238-1)(243-1)(247-1)
Karena W7 menggunakan 8 buah kombinasi LFSR untuk menghasilkan 8 bit/1 byte persatuan waktu maka periode dari algoritma W7 adalah ≤ ((238-1)(243-1)(247-1))8.

4.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.


5.Penutup
Algoritma W7 merupakan algoritma stream cipher synchronous dengan key input sepanjang 128 bit. Algoritma W7 menggunakan 8 kombinasi LFSR dimana tiap LFSR terdapat 3 buah shift register yang panjang stagenya masing-masing 38, 43 dan 47 stage.
Karena Algoritma W7 merupakan adopsi dari A5/1 maka attack yang terkena pada A5/1 juga dapat diterapkan kedalam algoritma W7. Walaupun demikian pengaplikasian W7 masih dapat digunakan karena termasuk mudah dalam penerapannya dalam hardware maupun software. Selain itu Algoritma W7 sudah teruji bahwa output yang dihasilkannya lolos dari five basic test.


Daftar Pustaka


[1] J.L. Massey. Cryptography: Fundamentals and applications. Copies of transparencies, Advanced Technology Seminars, 1993.
[2] Schneier, Bruce. 1996. Applied Cryptography: Protocols, Algorithms, and Source Code in C, Second Edition. Neew York: John Wiley & Sons, Inc.
[3] Munir, Rinaldi. 2002. Kriptografi.