Algoritma Twofish

Deskripsi dan pengenalan

Pada tahun 1972 dan 1974, US the National Bureau of Standards (sekarang bernama the National Institute of Standards and Technology, atau NIST - sebuah lembaga yang mengatur tentang standar-standar) mengeluarkan publikasi pertama untuk sebuah standar enkripsi, yang menghasilkan algoritma data Encryption Standard (DES) [NBS77], yang tidak dapat disangkal sebagai algoritma kriptografi yang sangat terkenal dan sangat berhasil.
Disamping kepopulerannya, DES sering diserang dengan berbagai kontroversi. Beberapa orang kriptografer mempertanyakan desain algoritma DES yang mengimplementasikan kunci dan ukuran blok yang terlalu kecil. Dengan berkembangnya pengetahuan tentang kunci terdistribusi akhir-akhir ini, tidak ada keraguan bahwa DES memang memiliki ukuran blok dan kunci yang tidak sesuai dengan kebutuhan masyarakat saat ini.
Triple-DES ditawarkan untuk menjawab pertanyaan diatas, dan memang merupakan solusi sementara dari permasalahan diatas. TDES telah diadopsi oleh banyak sekali aplikasi yang membutuhkan tingkat keamanan tinggi seperti perbankan namun algoritma TDES dirasakan sangat lamban, apalagi dengan hardware pada saat itu.
Merespon kebutuhan masyarakat untuk pengganti DES, NIST mengeluarkan semacam sayembara bernamakan program Advanced Encryption Standard (AES) pada tahun 1997 [NIS97a]. Sebuah sayembara untuk para kriptografer dunia untuk merancang algoritma kriptografi baru sebagai calon pengganti DES.
NIST mengumumkan syarat-syarat minimum yang harus dimiliki algoritma baru tersebut.
 
Kriteria NIST
 Adapun kriteria-kriteria yang disyaratkan NIST adalah sebagai berikut: 
- Merupakan algoritma kriptografi simetris cipher blok, dengan panjang blok adalah 128 bit. 

- Memiliki tiga opsi panjang kunci, yaitu: 128 bit, 192 bit, dan 256 bit. 

- Tidak memiliki kunci lemah (weak key). 

- Memiliki efisiensi yang tinggi, baik pada software diatas prosesor kelas pentium, maupun ditanamkan pada chip hardware. 

- Memiliki rancangan yang fleksibel, yaitu dapat dimodifikasi dengan mudah, misal memperpanjang kunci, dapat diaplikasikan pada cipher aliran, memiliki fungsi hash yang dapat diubah, dll.

Walaupun menuntut banyak kemampuan, namun desain algoritma harus sesederhana mungkin. Terdapat beberapa kriteria yang menyangkut hardware yang spesifik, tidak ditampilkan disini. Setelah twofish diterima sebagai kandidat pengganti DES, maka NIST mensyaratkan kriteria tambahan khusus untuk twofish, yaitu: 

- Twofish 16 putaran tidak boleh memiliki chosen-palintext attack yang memerlukan kurang dari 280 chosen plaintext dan menghabiskan waktu 2n dengan n adalah panjang kunci. 

- Twofish 12 putaran tidak boleh memiliki related-key attack yang memerlukan kurang dari 264 chosen plaintext dan menghabiskan waktu 2n dengan n adalah panjang kunci.

Dari semua kriteria yang disyaratkan NIST, twofish berhasil memenuhinya. Dengan terpenuhinya kriteria-kriteria tersebut, twofish maju dalam 5 besar memperebutkan tahta pengganti DES.

1. Finalis tersebut adalah:Rijndael (dari Vincent Rijmen dan John Daemen – Belgia, 86 suara) 

2. Serpent (dari Ross Anderson, Eli Biham, dan Lars Knudsen – Inggris, Israel dan Norwegia, 59 suara) 

3. Twofish (dari tim yang diketuai oleh Bruce Schneier – USA, 31 suara)  

4. RC6 (dari Laboratorium RSA– USA, 23 suara) 
5. MARS (dari IBM, 31 suara)

Namun hasil akhir memutuskan bahwa twofish belum mampu menjadi algoritma standar. Twofish dan rijndael bersaing memperebutkan posisi teratas. Namun rijndael yang keluar sebagai pemenang dan berubah nama menjadi AES, suksesor dari DES.
Berdasarkan penelitian yang dilakukan oleh (Aulia Rahma Amin, Pocut Viqorunnisa, Igor Bonny Tua Panggabean, Muhammad Bahari Ilmy dari ITB) maka diperoleh tabel perbandingan algoritma di bawah ini:
 
Twofish dirancang oleh Bruce Schneier. Twofish adalah suksesor dari blowfish. Twofish merupakan algoritma yang beroperasi dalam mode block. Algoritma twofish sendiri merupakan pengembangan dari algoritma Blowfish. Perancangan Twofish dilakukan dengan memperhatikan kriteria-kriteria yang diajukan National Institute Standard (AES), namun algoritma ini tidak terpilih sebagai basis standarisasi.

Algoritma Twofish 
Twofish merupakan algoritma kriptografi yang beroperasi dalam mode blok cipher berukuran 128 bit dengan ukuran kunci sebesar 256 bit, ukuran kunci yang besar ditujukan untuk meniadakan kemungkinan kunci lemah (weak-key).
Algoritma twofish menggunakan struktur sejenis Feistel dalam 16 putaran dengan tambahan teknik whitening terhadap input dan output. Teknik whitening sendiri adalah teknik melakukan operasi XOR terhadap materi kunci sebelum putaran pertama dan sesudah putaran akhir. Elemen di luar jaringan feistel normal yang terdapat dalam algoritma twofish adalah rotasi 1 bit. Proses rotasi ini dapat dipindahkan ke dalam fungsi F untuk membentuk struktur jaringan Feistel yang murni, tetapi hal ini membutuhkan tambahan rotasi kata sebelum langkah output whitening.
Twofish memanfaatkan teknik pemanipulasian bit , kotak permutasi / pemutihan, jaringan feistel, pemutaran ulang dan pergiliran kunci dengan jumlah perputaran dan pergiliran kunci sebanyak 16 kali , tranformasi pseudo-Hadamard , ekspansi dan filter , dan kotak MDS (Most Distance Separable).
 
Beberapa metoda yang digunakan oleh algoritma twofish :
1.    Kotak permutasi / pemutihan
Tujuan dari metode ini adalah untuk mengacak urutan bit-bit pada sebuah blok. Dinamakan kotak permutasi, sebab merupakan sebuah kotak 2 dimensi yang setiap isinya memiliki informasi bit tersebut harus dipindahkan ke urutan keberapa pada blok tersebut. twofish memanfaatkan kotak permutasi dalam beberapa prosesnya. Kotak permutasi ini bertujuan untuk mengacaukan urutan bit, sehingga mencegah kriptanalis yang akan menyerang algoritma tersebut menggunakan metoda seperti metoda kunci lemah.

2.    Jaringan feistel
Dinamakan jaringan feistel setelah perancangnya Horst Feistel berhasil menemukan metoda kriptografi yang efisien, kuat, dan mudah untuk dikembalikan ulang. Jaringan feistel asli menerapkan beberapa langkah yang sudah terstandarisasi. Langkah-langkah tersebut dapat berupa metoda-metoda lain, seperti pergiliran kunci, ekspansi dan filter, dll. Inti dari jaringan feistel adalah sebuah blok dibagi menjadi dua buah blok sama besar. Setengah blok kanan dikopikan kesetengah blok kiri blok hasil dan juga dimasukkan ke metoda ekspansi dan filter bersamaan dengan setengah blok kiri. Hasil dari fungsi ekspansi dan filter tersebut dikopikan ke setengah blok kanan blok hasil. Untuk mendekripsikan metoda ini cukup mudah, yaitu dengan cara mengkopikan setengah blok kiri result cipher ke setengah blok kanan blok hasil sambil dimasukkan kefungsi ekspansi dan filter. Kelebihan lain dari metode ini adalah kemampuannya menggunakan metoda lain yang bersifat irreversible (seperti ekspansi dan filter). Hal tersebut dapat terjadi karena dalam proses enkripsi maupun dekripsi untuk mencapai blok hasil harus melalui fungsi ekspansi dan filter dari arah “atas”, yaitu bukan dari arah “bawah”, seperti dekripsi pada umumnya.

Banyak sekali modifikasi yang dapat dilakukan pada metoda ini. Modifikasi yang paling populer adalah:

- Jaringan feistel dengan tidak hanya membagi menjadi dua buah subblok saja, namun lebih. 

- Jaringan feistel yang membaginya tidak rata, yaitu jumlah bit di subblok kanan tidak sama dengan jumlah bit di subblok sebelah kiri.

twofish memanfaatkan metoda ini, dengan menggunakan metoda asli. Di dalam metoda ini twofish juga mengimplementasikan pergiliran kunci dan ekspandsi dan filter.

3.    Memutar ulang dan pergiliran kunci
Pada hampir semua algoritma modern pasti memiliki metoda memutar ulang, yaitu mengumpulkan beberapa metoda alghoritma, dan dari sekumpulan algoritma tersebut diputar ulang. Hasil blok keluaran kumpulan algoritma tersebut dimasukkan kembali kedalam kumpulan algoritma tersebut hingga beberapa kali. Bisa hanya sekali, dua kali, hingga puluhan kali.
 
Metoda tersebut biasanya dibarengi dengan pergiliran kunci. Kunci utama yang dimasukkan biasanya tidak digunakan terus menerus dalam semua proses. Setiap level biasanya menggunakan kunci yang berbeda. Dalam menggilirkan kunci, kebanyakan algoritma menggunakan metode kotak permutasi dan penggeseran bit. Masukan awal adalah kunci utama, dan di setiap level, kunci tersebut digeser dan dimasukkan ke kotak permutasi menghasilkan kunci-kunci internal yang bersesuaian dengan level putarannya.

4.    Transformasi Pseudo-Hadamard
Salah satu metoda lain untuk mengacaukan bit adalah transofmasi pseudo-Hadamard. Transformasi ini memanfaatkan beberapa fungsi aritmatika sederhana. Dinamakan pseudo (semi) sebab merupakan manipulasi dari transformasi Walsh-Hadamard yang cukup terkenal dalam dunia matematika dan fisika quantum. Transformasi tersebut menggunakan bantuan operasi aritmatika kompleks yang dapat dikembalikan (reversible). Metoda asli pseudo-Hadamard yaitu dengan membagi blok menjadi dua buah subblok sama besar dan menerapkan operasi aritmatika sederhana.
Enkripsi pseudo-Hadamard:
a’ = a + b (mod 2n)
b’ = a + 2b (mod 2n)
Dekripsi pseudo-Hadamard:
b = b’ - a’ (mod 2n)
a = 2a’ - b’ (mod 2n)Persamaan diatas dapat juga dituliskan sebagai matriks aljabar, dengan memandang a dan b sebagai dua elemen sebuah vektor, dan transformasinya sendiri dipandang sebagai perkalian matriks dengan bentuk:
 
Untuk proses dekripsi dapat dengan cara menginvers matriks tersebut diatas. Kelebihan lain adalah matriks tersebut dapat digeneralkan menjadi matriks dengan dimensi yang lebih tinggi untuk mentransformasikan vektor yang lebih dari dua variabel, dengan fungsi rekursif:
 
Contoh matriks untuk mentransformasi vector dengan 4 buah variabel (a, b, c, dan d):
 

5.    Ekspansi dan filter
Untuk memperkuat algoritma kriptografi, beberapa perancang menggunakan metode ekspansi dan filter. Metode ini bertujuan menggelembungkan ukuran blok dan memprosesnya dengan metode-metode tertentu. Hasil keluaran proses tersebut dimasukkan ke fungsi filter yang akan mengembalikan ukuran blok menjadi seperti semula. Metode ini bersifat irreversible (tidak dapat mengembalikan nilai awal), sehingga metode ini harus dipasangkan dengan metode lain yang memiliki kemampuan enkripsi dan dekripsi irreversible
 
Metode yang umumnya dipakai sebagai wadah metode ekspansi dan filter adalah jaringan feistel. Jaringan feistel memiliki sifat mampu mengenkripsi dan dekripsi dengan memanfaatkan metode irreversible. Untuk mengekspansi blok awal menjadi lebih besar diperlukan kotak ekspansi. Kotak ini bekerja seperti pada kotak permutasi, namun memiliki kemampuan membesarkan blok. Blok yang telah diekspansi tersebut biasanya lalu di lakukan operasi xor dengan kunci internal (bila dilakukan pada metode perulangan). Hasil dari xor tersebut lalu dimasukkan ke dalam kotak substitusi, sebuah kotak yang mampu mengecilkan ukuran blok.

6.    Kotak MDS
Kotak Most Distance Separable (MDS) adalah sebuah matriks yang dapat dioperasikan secara linear kepada sebuah vektor menjadi sebuah vektor hasil. Vektor hasil tersebut merupakan vektor yang terbesar yang dapat dihasilkan namun dengan jarak minimum dari vector awal. Jika ada vektor dengan “a” elemen, dan ada vektor lain dengan “b” elemen, akan menghasilkan vektor baru dengan “a+b” elemen. Dengan mengandung jumlah minimum elemen bukan nol pada setiap bukan nol vektor adalah “b+1”. Sehingga “jarak” antara dua vektor yang berbeda yang dihasilkan dengan kotak MDS adalah sekurang-kurangnya “b+1”. Hanya algoritma twofish saja yang mengimplementasikan metode ini.

Algoritma utama

 

Langkah-langkah algoritma twofish adalah sebagai berikut:

1. Masukan satu blok plain teks adalah 128 bit. Satu blok tersebut dibagi menjadi 4 buah subblok yang masing-masing sepanjang 32 bit (A, B, C, dan D). 
2. Masing-masing subblok tersebut diputihkan dengan mengxorkan dengan kunci K0, K1, K2, dan K3.

Langkah-langkah 1 putaran adalah sebagai berikut:

1. 2 buah 32 bit yang kiri (A dan B) merupakan input dari fungsi g (yang merupakan bagian dari fungsi f), yang salah satunya (B) di geser ke kiri sejauh 8 bit dahulu. 
2. Fungsi g memiliki 4 buah kotak substitusi yang dibangkitkan oleh kunci. 
3. Keluaran fungsi kotak substitusi dilakukan percampuran linear menggunakan kotak Most Distance Separable 
4. Keluaran fungsi g dimasukkan ke fungsi transformasi pseudo-Hadamard, kemudian ditambahkan dengan 2 buah 32 bit dari kunci. 
5. Dua buah 32 bit hasil kemudian di xor kandengan C dan D. Hasil xor dengan C digeser ke kanan sejauh 1 bit. Dan untuk D sebelum dixorkan digeser ke kiri sejauh 1 bit. 
6. 2 buah 32 bit kiri dan kanan dipertukarkan (A dan B dipertukarkan dengan C dan D).

Langkah diatas dilakukan hingga 16 kali putaran. Kemudian langkah-langkah selanjutnya :

1. Hasil keluaran setelah diputar 16 kali, ditukar lagi (A dan B dipertukarkan dengan C dan D). 
2. Hasil dari pertukaran tersebut di xorkan dengan empat buah 32 bit dari kunci menghasilkan cipher teks.

 Fungsi F
Fungsi F adalah permutasi yang bergantung pada kunci dengan nilai 64 bit. Fungsi ini menerima 3 argumen, dua buah 32 bit R0 dan R1, dan nomor putaran untuk menentukan subkunci mana yang dipakai. R0 akan diserahkan ke fungsi g yang akan mengembalikan T0. R1 akan digeser sejauh 8 bit yang kemudian di berikan juga ke fungsi g yang akan mengembalikan T1. Hasil T0 danT1 kemudian dikombinasikan ulang menggunakan transformasi pseudo-Hadamard, yang kemudian ditambahkan dengan dua buah 32 bit dari kunci.
T0 = g(R0);
T1 = g (shift Left (R1,8));
F0 = (T0+T1+K2r+8) mod 232;
F1 = (T0+2T1+K2r+9) mod 232;
F0 dan F1 adalah hasil dari F, yang masing-masing sepanjang 32 bit. Hasil keluaran ini nantinya akan dipertukarkan dan dimasukkan kembali ke putaran selanjutnya.

Fungsi G
Fungsi g merupakan jantung dari keseluruhan algoritma twofish. 32 bit masukan X dari fungsi F dipecah menajdi 4 buah yang masing-masing sepanjang 8 bit. Setiap 8 bit kemudian diproses dengan kotak S yang bersesuaian. Setiap kotak S bersifat bijektif, yaitu menerima 8 bit dan mengeluarkan 8 bit pula. 4 buah 8 bit hasil keluaran kemudian dikalikan dengan matriks Most Distance Separable (MDS) 4x4. Hasil pengalian kemudian diartikan sebagai 32 bit, yang merupakan keluaran dari fungsi g, yang kemudian akan dikembalikan kembali ke fungsi F.
Matriks MDS yang setiap elemennya ditampilkan sebagai heksadesimal adalah sebagai berikut:


Kelebihan dan Kekurangan
Karena Twofish merupakan salah satu contoh dari Algoritma-algoritma kunci-simetris , maka kelebihan dan kekurangan dari Algoritma kunci simetris adalah sebagai berikut :
Kelebihan :

1. Waktu proses untuk enkripsi dan dekripsi relatif cepat, hal ini disebabkan karena efisiensi yang terjadi pada pembangkit kunci. 
2. Karena cepatnya proses enkripsi dan dekripsi, maka algoritma ini dapat digunakan pada sistem secara real-time seperti saluran telepon digital.

Kekurangan :

1. Untuk tiap pasang pengguna dibutuhkan sebuah kunci yang berbeda, sedangkan sangat sulit untuk menyimpan dan mengingat kunci yang banyak secara aman, sehingga akan menimbulkan kesulitan dalam hal manajemen kunci. 
2. Perlu adanya kesepakatan untuk jalur yang khusus untuk kunci, hal ini akan menimbulkan masalah yang baru karena tidak mudah u menentukan jalur yang aman untuk kunci, masalah ini sering disebut dengan “Key Distribution Problem”. 
3. Apabila kunci sampai hilang atau dapat ditebak maka kriptosistem ini tidak aman lagi.