Studi Grǿstl sebagai salah satu kandidat SHA 3 Daniel Melando, Ninik Ratna Dewi, R. Ahmad Immanullah Zakariya Tingkat II Teknik Kripto Sekolah Tinggi Sandi Negara
1. Pendahuluan Grǿstl adalah salah satu kandidat SHA 3 yang diadakan oleh NIST. Algoritma ini dikirim oleh Lars Ramkilde Knudsen. Grǿstl adalah algoritma iterated compression hash function yang dibangun dari dua permutasi yang jelas, tetap, dan besar. Desain Grǿstl
sangat berbeda
dengan SHA family. Terdapat dua permutasi yang dibangun dari trail design strategy yang besar yang membuat algoritma ini menjadi tahan terhadap kriptanalisis. Ditambah lagi asumsi bahwa permutasi yang digunakan adalah permutasi ideal, maka menambah kekuatan fungsi hash yang dibangun. Grǿstl berbasis SP network yang mengadopsi banyak komponen AES termasuk S-box yang digunakan maupun layer difusi yang digunakan sehingga kekuatannya ada pada difusi dan konfusi yang dibangun. Grǿstl juga disebut dengan konstruksi wide pipe yang ukuran internal statenya sangat besar dibanding dengan ukuran output. Efek yang ditimbulkan yaitu sangat sulit dalam melakukan serangan. Grǿstl juga memunyai performa yang bagus pada range platform yang luas dan tahan terhadap side channel attack sama seperti AES. 2. Tujuan Desain Tujuan dari desain agoritma ini adalah untuk desain yang elegan, dan mudah dianalisis. Pada kenyataannya, fungsi iterasi yang diaplikasikan pada fungsi kompresi membuat kemiripan dengan sifat algoritma hash yang lain. 2.1 Tujuan desain untuk Grøstl
Analisis Grøstl sangat sederhana. Grøstl menggunakan permutasi bilangan kecil sebagai pengganti block cipher (dengan banyak permutasi)
Terkonstruksi secara aman (dengan asumsi permutasi yang ideal).
Permutasi didasari prinsip desain yang terkenal
Tidak ada persyaratan khusus untuk bentuk tertentu dan ukuran kata, performance yang baik pada platform yang berjarak jauh
Anti terhadap side-channel dengan tambahan biaya yang sedikit
Mendefinisikan variant yang tereduksi untuk kemudahan kriptanalisis
Mencegah length-extension attack
Bisa diimplementasikan untuk mengeksploitasi paralelisasi dalam fungsi kompresi
2.2 Toleransi Kegagalan Desain Permutasi yang digunakan seharusnya idela, sehingga serangan yang ada pada fungsi kompresi tidak akan mempengaruhi fungsi hash.
Internal state lebih besar dibanding output akhir, oleh karena itu, semua jenis serangan yang umum digunakan akan gagal
Teknik yang digunakan untuk mengetahui ketidak idealan permutasi hanya akan bisa dilakukan pada variant yang dikurangi
Serangan pada fungsi kompresi tidak berpengaruh pada ungsi hash.
Tidak ada serangan pada fungsi kompresi yang terbukti memenuhi lower bound
2.3 Pertimbangan desain untuk fungsi kompresi Desain fungsi hash secara tradisional biasanya berdasarkan pada desain blok cipher. Hal ini dikarenakan key schedule nya memiliki peran yang sangat penting. Keuntungan metodologi desain seperti itu adalah sebagai berikut:
Tidak ada serangan melalui key schedule
Karena key schedule pada block cipher seringkali lambat tetapi performance dapat ditingkatkan
Sederhana
3 Spesifikasi Grøstl Grøstl adalah kumpulan dari fungsi hash, mampu mencerna pesan kembali dari sejumlah byte dari 1 sampai 64, yaitu, dari 8 sampai 512 bit pada langkah 8-bit. Sisa varian n bit disebut Grøstl-n. Grøstl termasuk dalam ukuran message digest (MD) 224, 256, 384, dan 512 bit.
3.1 The hash function construction Fungsi hash yang Grøstl mengiterasi fungsi kompresi fungsi f sebagai pesan berikut. Pesan M telah di padding dan dipecah menjadi ℓ-bit blok pesan m 1 ,..., m t , dan setiap pesan blok diproses satu-persatu. Sebuah initial nilai ℓ-bit h 0 =IV didefinisikan, dan kemudian subsekuen pesan blok m i diproses sebagai
Oleh karena itu, f memetakan dua input ℓ bit masing-masing ke output ℓ bit. Masukan pertama yang disebut chaining input, dan masukan kedua disebut message block. Untuk varian Grøstl mengembalikan sampai 256 bit, ℓ didefinisikan sebagai 512. Untuk varian yang lebih besar, ℓ adalah 1024. Setelah blok pesan terakhir diproses, output H(M) pada fungsi hash dihitung sebagai
Dimana Ω adalah output transformation. Ukuran output dari Ω adalah n bit, n < ℓ .
Gambar 1. Grøstl
3.2 Konstruksi fungsi kompresi Fungsi kompresi f berdasarkan 2 permutasi ℓ-bit P dan Q. Didefinisikan sebagai berikut: .
Gambar 2. Fungsi Kompresi
3.3 Transformasi output Trunc n (x) menjadi operasi yang membuang semua deret kecuali deretan n bit dari x. Kemudian output transformasi Ω didefinisikan dengan
3.4 Desain P and Q Seperti disebutkan, fungsi kompresi f berbentuk dua varian, satu digunakan untuk message digest singkat, dan satu digunakan untuk message digest panjang. Setiap varian menggunakan pasangan sendiri dari permutasi P dan Q. Jadi, didefinisikan sebanyak empat permutasi. Permutasi akan ditetapkan dengan subskrip 512 atau 1024.
Gambar 3. Output Transformasi
Desain P dan Q terinspirasi oleh algoritma blok cipher Rijndael. Ini berarti bahwa desain Rijndael terdiri dari beberapa round R, yang terdiri dari beberapa round transformasi. Karena P dan Q jauh lebih besar daripada ukuran normal Rijndael, sebagian besar transformasi round
telah didefinisikan ulang. Dalam Grøstl, sebanyak empat putaran transformasi didefinisikan untuk setiap permutasi. AddRoundconstant SubBytes ShiftBytes MixBytes Ketika
perbedaan
diperlukan,
transformasi
ketiga
ShiftByteswill
akan
disebut
ShiftBytesWide bila digunakan dalam permutasi besar P 1024 dan Q 1024 . Transformasi lain dapat digambarkan dengan cara yang sama untuk semua empat permutasi. Satu round R terdiri dari empat round transformasi ini diterapkan dalam urutan di atas. Dengan demikian,
Semua round mengikuti definisi ini. Jumlah round dinotasikan r. Transformasi yang beroperasi pada state direpresentasikan sebagai matriks A dari byte. Untuk varian pendek, matriks memiliki 8 baris dan 8 kolom, dan untuk varian besar, matriks memiliki 8 baris dan 16 kolom degan notasi v nomor kolom, Bytes konstannya c3. 3.4.1 Pemetaan dari urutan byte ke negara matriks dan sebaliknya Karen Grøstl beroperasi pada byte, pada umumnya endianness netral. Pemetaan yang dilakukan dengan cara yang sama seperti dalam Rijndael yaitu 64-byte urutan dengan urutan 000102...3f
Gambar 4. Transformasi dasar Grǿstl
00 01 02 03 04 05 06 07
08 09 0A 0B
10 11 12 13
0C 0D 0E 0F
14 15 16 17
30 38 31 39 32 3 A 33 3B 1C 24 2C 34 3C 1D 25 2 D 35 3D 1E 6 2 E 36 3E 1F 27 2 F 37 3F 18 20 28 19 21 29 1A 22 2 A 1B 23 2 B
Gambar 5. Matrik Hasil Pemetaan
3.4.2 AddRoundConstant P dan Q memiliki konstanta round yang berbeda yang terletak pada permutasinya. Konstanta round adalah sebuah matrik yang pada kolom dan barisnya hanya terdapat 1 posisi yang bukan nol. Round constant ini digunakan pada P512 dan P1024 yang pada dasarnya sama.
Gambar 6. AddRoundConstant untuk Permutasi P dan Q
3.4.3 SubBytes Subbytes mensubstitusi masing-masing byte pada state matriks dengan nilai lain, mengambil dari s-box S. S-Box yang dipakai sama dengan S-Box satu yang digunakan Rijndael. Oleh karena itu, jika ai,j adalah elemen di dalam baris i dan kolom j dari A, maka Subbytes melaksanakan transformasi sebagai berikut:
3.4.4 Shift Bytes Shiftbytes dan Shiftbyteswide secara siklis menggeser bytes di dalam suatu baris ke kiri oleh sejumlah posisi. Misal s= [ s0, s1,..., s7] daftar bilangan bulat berbeda di dalam cakupan dari 0 untuk v-1.
Gambar 7. SubBytes Subtitude
Maka, Shiftbytes memindahkan semua bytes di baris i pada state matriks si ke kiri. Vektor s didefinisikan sebagai s = [ 0, 1, 2, 3, 4, 5, 6, 7] dalam Shiftbytes, dan = [ 0, 1, 2, 3, 4, 5, 6, 11] pada Shiftbyteswide.
Gambar 8. ShiftByte
Gambar 9. ShiftBytesWide
4.5 Mix Bytes Pada transformasi Mixbytes, masing-masing kolom di dalam matriks ditransformasi secara bebas. Untuk menguraikan transformasi yang dilakukan, kita harus mengenal finite field. Finite
field
ini
sama
dengan
Rijndael
yang
irreducible
polinomial
pada
F2
Matriks ini adalah circulant, yang berarti bahwa masing-masing baris sama dengan pergeseran satu kali ke kanan.
Gambar 10. Matriks Circulant
3.4.6 Jumlah round Jumlah r round adalah suatu parameter keamanan yang tuneable. Di sini direkomendasikan nilai r untuk empat permutasi.
Tabel 1. Permutasi yang Dipakai
3.5 Initial values Initial value ivn Grøstl-N adalah l-bit yang mempresentasikan n. Tabel di bawah menunjukkan initial value yang diperlukan oleh ukuran output 224, 256, 384, dan 512 bit.
Tabel 2. Initial Value
3.6 Padding Panjang masing-masing blok pesan adalah l. Untuk dapat mengoperasikan input dengan panjang sembarang, dilakukan padding. Fungsi padding ini mengambil string x dengan panjang N bit dan menghasilkan string x*= pad(x) yang panjangnya perkalian dari l. Fungsi padding bekerja sebagai berikut. Pertama, menambahkan bit ‘1’ dari x. Kemudian, menambahkan w = - N- 65 mod l ‘0’ bit, dan terakhir menambahkan 64-bit yang merupakan representasi dari ( N+ w+ 65)/l. 4. Keputusan dan Fitur Desain Keuntugan Grǿstl dibanding algoritma yang lain yaitu : a. Keamanan Karena menggunakan permutasi yang ideal, maka Grǿstl resistant dan preimage resistant. b. Fleksibel
memiliki properti collision
Algoritma ini bisa diimplementasi pada beberapa platform karena parameter keamanan r dan jumlah round dapat dengan mudah diubah. c. Sederhana Konstruksi permutasi sederhana dan mudah dipahami. d. Tidak asing Karena algoritma ini berdasar pada Rijndael, maka sudah banyak dikenal dan tidak asing lagi. 4.1 Keamanan konstruksi Konstruksi
fungsi
kompresi
yang
digunakan
dapat
dibuktikan
aman
karena
menggunakan dua permutasi P dan Q yang ideal. Dibutuhkan nilai yang besar dalam percobaan untuk menemukan nilai collision pada algoritma Grǿstl. Asumsi yang digunakan adalah permutasi yang digunakan ideal padahal, pada kenyataannya serangan terhadap permutasi yang tidak ideal tidak akan menambah peluang serangan pada algoritma itu sendiri. 4.2 AddRoundConstant Tujuan dari penambahan konstanta round yaitu agar masing-masing round berbeda dan pada saat yang sama P dan Q juga berbeda. Bila permutasi yang digunakan sama, maka hasilnya merupakan perluasan dari permutasinya, dan hal itu akan menimbulkan jumlah fixed point P dan Q adalah 1. Pada implementasinya, penggunaan P dan Q yang berbeda tidak menimbulkan kesalahan yang besar karena kode masih dapat dishared antara P dan Q. Round constant yang digunakan sederhana agar mengurangi performa dalam melakukan kesalahan. 4.3 SubBytes SubBytes adalah satu-satunya elemen non linear yang ada pada Grǿstl yang menggunakan s-box yang sama seperti AES. Alasan pemakaiannya sebagai berikut : a. Ukuran yang mudah dalam implementasi b. Menggunakan singe s-box agar implementasi mudah dan pertimbangan kriptanalisis c. S-box yang digunakan lebih efisien di hardware dibanding s-box acak d. S-box AES sudah lama dipelajari dan termasuk s-box yang kuat e. Implementasi pada hardware sudah banyak dipelajari 4.4 ShiftBytes dan ShiftBytesWide
Niai pergeseran yang dimiliki harus optimal dalam arti state byte minimal 1 state byte lain. Nilai pergeseran yang digunakan juga merupakan nilai yang ada pada AES. 4.5 MixBytes Tujuan
dari
mixbytes
adalah
memperluas
transformasi
trail
stategi
dengan
menggunakan error correcting code dengan MDS. 4.6 Output Transformasi Transformasi output dibutuhkan karena chaining ukuran variabel lebih besar dibanding output. Transformasi output yang dilakukan dengan cara pemotongan. Karena fungsi kompresi yang digunakan ini tidak ideal, maka fungsi yang dipakai adalah fungsi one way dan collision resistant tetapi bukan fungsi komresi sebelum dilakukan pemotongan. ω (x) = P (x) ⊕ x. Konstruksi
Matyas-Meyer-Oseas
untuk
fungsi
hash
didasarkan
pada blok cipher yang menyediakan fungsi kompresi g dan didasarkan pada fungsi enkripsi EK g (h, m) = Eh (m) ⊕ m Fungsi ini telah terbukti one way dan collision resistant dengan asumsi bahwa E yang digunakan adalah ideal. Dengan fakta itu, maka sulit menyerang Grǿstl dengan menggunakan output transformasi. 4,7 Jumlah putaran Pada square attack, permutasi dapat dibedakan dari permutasi ideal jika jumlah round kurang dari 7. Semakin besar jumlah round, maka akan semakin kuat tingkat keamanan yang dimiliki. 4,8 Trapdoor Semua konstanta yang digunakan dalam Grǿstl harus jelas termasuk penggunaan s-box sehingga termasuk dalam trapdoor. 5. Penggunaan Grǿstl 5.1 Otentikasi pesan HMAC adalah salah satu cara membangun otentikasi pesan menggunakan hash function.
Ket :
K
: Paddingan k menjadi blok dengan panjang sesuai degan fungsi hash
Opad dan ipad
: 2 konstanta yang berbeda yang sudah didefinisikan
Ada lagi metode lain , M adalah M ditambah dengan perkalian dari l bit. 5.2 Randomized Hashing Agar message authenticationnya aman, maka dilakukan penambahan nilai acak yang selalu baru z sebelum pesan dihash.
5.3 Klaim keamanan pada Grǿstl
Tabel 3. Klaim Keamanan Grǿstl
6. Hasil Kriptanalisis Pada tulisan in tidak akan dibahas kriptanalisis Grǿstl secara detail. Secara umum, serangan pada Grǿstl dibagi menjadi lima serangan yakni serangan pada permutasi yang termasuk di dalamnya differential cryptanalysis,linier cryptanalysis, integral, dan algebraic attack collision attack yang di dalamnya mengandung collision attack pada fungsi kompresi, dan collision attack pada fungsi hash, iterasi yang di dalamnya termasuk multicollision attack, second preimage attack, dan length extension attack, dan fixed point. Berdasarkan hal itu, maka hasil kriptanalis data dijadikan table sbagai berikut :
Tabel 4. Serangan Grǿstl
Ternyata selain serangan yang bersifat matematis itu, terdapat side channel attack yaitu cache based timing attacks, power- and em side-channel attacks, dan on countermeasures. 7. Implementasi Secara umum Grǿstl mudah diimplementasikan baik pada software maupun hardware. Pada software, Grǿstl diperuntukkan pada prosesor 64 bit, tetapi performanya bagus untuk prosesor ukuran 32 bit. Pada hardware, Grǿstl adalah algoritma yang mengijinkan penggunanya untuk trade off yang terlalu besar, laten, gerbang count, konsumsi daya, dan lainlain. Benchmarks on pc platforms diperuntukkan bagi pesan yang panjang. Benchmarks on pc platforms ditunjukkan pada tabel di bawah ini
Tabel 5. Implementasi
8. Kesimpulan Grǿstl adalah salah satu kandidat SHA 3 yang dikirim oleh Lars Ramkilde Knudsen dalam NIST. Grǿstl adalah algoritma iterated compression hash function yang dibangun dari dua permutasi yang jelas, tetap, dan besar. Terdapat dua permutasi yang dibangun dari trail design strategy yang besar yang membuat algoritma ini menjadi tahan terhadap kriptanalisis. Grǿstl berbasis SP network yang S-box dan layer difusinya mengamil dari AES. Grǿstl juga disebut dengan konstruksi wide pipe yang ukuran internal statenya lebih besar dibanding dengan output. Hal ini dilakukan agar serangan yang dilakukan sulit. Grǿstl juga memunyai performa yang bagus pada range platform yang luas dan tahan terhadap side channel attack. 9. Referensi Knudsen, dkk. 2008. Grøstl – a SHA-3 Candidate
