Kandidat SHA-3 ECHO Asti Meysita, Jenny Irna, Jupri Rahman, Ricky Aji Tingkat III Teknik Kripto I. Spesifikasi Fungsi hash ECHO membutuhkan message dan salt sebagai input. Output ECHO didapat dari panjang 128 ke 512 bit. Dimana kita menentukan perhatian dan deskripsi nya harus mencukupi pada keempat nilai dari 224, 256, 384 dan 512. Sama halnya ketika ECHO mempunyai fleksibilitas mengambil pesan dengan panjang bit sampai 2128 -1, focus utama kita pada versi ECHO yang menghash pesan yang panjangnya sampai 264 -1. Salt yang panjangnya 128 bit dan juka untuk beberapa alas an, itu tidak diperlukan atau ditinggalkan, kemudian diambil semua nilai nol yang ditentukan. Echo terdiri dari aplikasi serial dari fungsi kompresi dan paradigm Merkle-Damgard yang dipahami dengan baik. Pada saat yang sama, kita menghindari kekurangan tertentu dengan membawa state besar dari satu iterasi ke yang berikutnyav dan dengan mengadopsi ciri-ciri model HAIFA. Ciri-ciri ini memberi kemampuan tambahan untuk desain dasar. Seperti halnya telah diketahui, fungsi kompresi pada paradigm Merkle-Damgard memperbaharui nilai
chaining variable dibawah tindakan dari blok pesan yang ukurannya
tertentu. Dan beberapa input lain. Spesifikasi ECHO akan dibagi menjadi bagian-bagian berikut :
Bagian I menetapkan notasi dan konvensi
Bagian 2 menguraikan bagaimana fungsi kompresi pada ECHO digunakan untuk menghash pesan dengan panjang berubah-ubah.
Bagian 3 menetapkan fungsi kompresi untuk output hash yang panjangnya antara 128256 bit
Bagian 4 menetapkan fungsi komp[resi untuk output hash yang panjangnya antara 257512 bit.
1. Notasi dan Konvensi
Unit dasar komputasi ECHO adalah panjang bit 128. Dimana ada byte yang mendasarinya berorientasi struktur yang memberikan catatan mudah diimplementasikan. Pengaturan padding akan diaplikasikan ke pesan
input dari ECHO dan menjamin bahwa padding pesan M’
mempunyai panjang n yang merupakan kelipatan dari 128. Padding pesan yang oleh karena itu akan dipresentasikan sebagai bitstring.
Atau sama seperti
deret
byte (dimana kita menggunakan
untuk menunjukkan
rangkaiannya)
Echo dibangun disekitar AES dan akan menjadi saling mempengaruhi antara deret 128 bit dan konsep mereka yang cocok di byte array 4
4. Sepanjang kita menggunakan konvensi
yang sama dengan AES dan kita mempunyai packing bit selanjutnya dari word pada array :
Dengan kesamaan input string dapat ditunjukkan sebagai deret
128 bit word, dan kita
dapat menunjukkan packing byte kedalam word sebagai
Pada ECHO, fungsi kompresi akan dioperasikan pada enambelas string 128 bit yang dapat di packing kedalam array 4
4 di jalan yang sama dengan AES :
Bit string didapatkan dari nilai integer yang akan mempunyai LSB ke kiri dan , dalam byte, MSB ke kiri. 2. Domain Extention Tergantung pada panjang dari output hash, ECHO akan menggunakan satu dari dua fungsi kompresi : COMPRESS512 atau COMPRESS1024. Hal tersebut mengacu pada panjangnya variable chaining, untuk ditandai CSIZE, dan pada iterasi I kedua fungsi kompresi memerlukan 4 input : 1. Nilai saat ini dari variable chaining , Vi-1, yang panjangnya CSIZE. 2. Blok pesan yang saat ini diproses, Mi. panjangnya MSIZE bit dimana MSIZE = 2048 – CSIZE. 3. Total jumlah bit pesan yang tidak dipadding di hash pada akhir iterasi, Ci. 4. Salting Untuk output hash yang panjangnya sampai 256 bit COMPRESS512 akan digunakan. Untuk hash yang panjangnya antara 257 – 512 bit, kita menggunakan COMPRESS1024. Output yang panjangnya kurang dari 256 atau 512 bit, akan diperoleh dengan truncation. IV dari variable chaining ditunjukkan V0 dan pada iterasi i, untuk 128
Ketika 257
HSIZE
HSIZE
256, kita akan mengkomputasi
512, kita akan mengkomputasi :
Seperti yang dapat kita lihat, dua fungsi kompresi tersebut hamper sama. Ketika ECHO mempunyai desain yang fleksibel untuk menggunakan 128 bit counter Ci, aplikasi praktis yang membutuhkan seperti panjang counter susah untuk dipertimbangkan. Jadi versi pertama dari ECHO menggunakan 64 bit counter Ci dan manghash pesan yang panjangnya sampai 264 – 1 bit. Panjang input dan output fungsi kompresi untuk nilai yang memenuhi, dibutuhkan oleh NIST dapat diringkas sebagai berikut :
Rangkaian iterasi dari fungsi kompresi setelah iterasi t menjelaskan dibawah ini. Rincian feedforward dan XOR akan diberikan kemudian. Seperti yang sebelumnya, IV variabel chaining V0 menegaskan ketika T menunjukkan pilihan truncation.
2.1 Inisialisasi Awal memulai hashing counter C adalah setting C0 = 0. Counter ini digunakan untuk menghitung banyaknya bit pesan yang dihashing. IV variabel chaining di-set sedemikian sehingga setiap word dari variabel chaining menyandi 128 bit untuk output hash yang diharapkan. Untuk output fungsi hash yang menggunakan COMPRESS512 , dinamakan output hash yang ukurannya 128 bit
HSIZE
256, variabel chaining terdiri dari 4 string 128
Untuk dua nilai NIST yang harus sesuai di rentang ini, IV-nya 0
3,
Untuk output fungsi hash yang menggunakan COMPRESS1024 , dinamakan output hash yang ukurannya
257
bit IV-nya 0
HSIZE
512,
variabel
chaining
terdiri
dari
8
string
128
dan untuk dua nilai NIST yang harus sesuai di rentang ini, 7,
2.2 Padding Pesan Padding pada input pesan M selalu dilakukan. Hasil padding pesan M’ yang panjangnya kelipatan MSIZE. Diasumsikan bahwa pesan yang dihash panjangnya L bit,kemudian padding dilakukan dengan menambahkan jumlahnya di bagian belakang : 1. Satu buah bit “1” ditambahkan di akhir pesan M. 2. Tambahkan sebanyak x bit 0, dimana :
3. Penyajian 16 bit biner dari HSIZE ditambahkan berikutnya. Untuk kepentingan dokumen ini, kemungkinan nilai sebagai string bit di notasi hexadecimal adalah E000, 0001, 8001 dan 0002. 4. Akhirnya penyajian 128 bit yang panjangnya L dimasukkan. Hasilnya pesan yang dipadding dari bentuk berikut (dengan panjang bit yang ditandai) :
3. Kompresi untuk 128
HSIZE
256
Pesan yang dipadding M’ dibagi kedalam t blok pesan
, setiap MSIZE = 1536 bit
panjangnya. Ini diproses menggunakan fungsi kompresi COMPRESS512 . Nilai t + 1 dari variabel chaining yang digenerator sampai fungsi komputasinya menunjukkan Vi, untuk 0
t . IV
diberikan di bagian 2.1 dan pada iterasi I , kita mengkomputasikan
Dimana Ci sama banyaknya dengan jumlah bit pesan yang akan diproses di akhir iterasi. Setiap blok pesan Mi dapat dipecah menjadi string 128 bit :
Variabel chaining Vi-1 ditunjukkan sebagai deret dari 4 nilai 128 bit :
Campuran dari variabel dan pesan selama kompresi memerlukan jenis-jenis opereasi bagian S, san S dapat ditunjukkan sebagai array 4
pada
4:
Pada awal dari iterasi ke-I dari fungsi kompresi, variabel chaining dan pesan diidi sebagai berikut :
Input lain untuk fungsi kompresi, terlepas dari variabel chaining dan blok pesan, adalah salting dan counter Ci. Salting dapat digunakan selama kompresi ketika Ci digunakan untuk menyediakan IV kepada conter internak K. komputasi pada COMPRESS 512 dijalankan lebih dari 8 langkah dari BIG.ROUND yang pada gilirannya terdiri dari aplikasi percontohan ketiga fungsi berikut :
Ini sama formatnya dengan 1 round AES dan kesamaannya mendekati genap jika kita mempertimbangkan setiap operasi pada gilirannya. 3.1
Operasi BIG.SUBWORDS (S, SALT,k) Operasi ini diakibatkan oleh tabel look-up dari S-box. Sbox adalah fungsi substitusi pada
128-bit words dan tepatnya menggunakan dua round AES tanpa perubahan. Diberikan 128-bit word w, kita dapat notasikan fungsi w pada round pertama AES, dengan subkunci k, yaitu w’= AES(w,k)
Fungsi round AES disini adalah fungsi round penuh yang terdiri atas SubBytes, ShiftRows, MixColumn, dan AddRoundKey. Subkunci pada round AES akan diberikan dengan SALT dan internal counter k. Internal counter k diinisialisasikan dengan nilai Ci. Counter k dan Ci memiliki panjang yang sama dan internal counter k akan naik selama proses komputasi kompresi. Ci tidak naik selama kompresi, namun Ci digunakan untuk menghitung jumlah bit pesan yang di-hash hingga akhir iterasi. Perhatikan, nilai tersebut adalah jumalh bit pesan asli, bukan jumlah bit pesan yang telah dipadding. Maka, Ci akan selalu mempunyai nilai yang tepat dari banyak ukuran pesan kecuali pada iterasi terakhir, misal iterasi t, ketika proses padding bit terjadi. Jika bit pesan dan bit padding diproses pada akhir fungsi kompresi lalu Ct akan bernilai L. Jika pada iterasi terakhir hanya memproses bit padding tanpa bit pesan (dapat terjadi ketika L adalah banyak ukuran pesan) maka kita tentukan Ct menjadi nilai 0. Pada versi sebelumnya, internal counter k mempunyai panjang 64 bit, dan dua subkunci round k1 dan k2 didapatkan dari : k1 = k || 0...0 (64 bit)
dan
k2 = SALT
Operasi Big.SubWords (S, SALT, k) telah digambarkan, dan setiap word wi dari pernyataan S diubah menjadi wi’ dengan W0’ = AES (AES (w0,k1), k2), dengan perubahan k 1 bit W1’ = AES (AES (w1,k1), k2), dengan perubahan k 1 bit, hingga W15’ = AES (AES (w15,k1), k2), dengan perubahan k 1 bit Setelah setiap komputasi dari wi’ kita naikkan counter k dengan 1 mod 264( atau modulo 2128 untuk counter yang lebih panjang). Lalu, subkunci k1 yang digunakan pada operasi AES yang berubah dari satu tahap ke tahap berikutnya. Karena nilai k pada setiap word dari pernyataan dapat seketika dihitung, operasi Big.SubWords dapat digunakan paralel secara efisien. Kita dapat melanjutkan perubahan nilai k pada seluruh round, sehingga perhitungan round kedua akan dimulai dengan k=Ci+16.
Aplikasi yang dibutuhkan pada panjang input pesan tertentu Algoritma ECHO diperuntukkan terutama pada pesan dengan panjang mencapai 264 – 1 bit, dengan desain yang mendukung pada panjang pesan hingga 2128 – 1 bit. Untuk counter Ci dan k
diimplementasikan pada 128 bits. Dua subkunci k1 dan k2 digunakan pada round AES dengan k1 = k dan k2 = SALT. 3.2
Operasi BIG.SHIFTROWS (S) Operasi Big.ShiftRows adalah analogi seksama dari operasi ShiftRows pada AES. Array
4x4 yang mewakili pernyataan S dipermutasikan dengan pergeseran baris dari 128-bit words, sama seperti permutasi byte-array pada AES. Lalu dapat kita notasikan fungsi word w0,w1,..,w15 pada Big.ShiftRows dengan, w’i+4j = wi+4((i+j)mod 4) untuk 0 ≤ i, j ≤ 3. Hal ini dapat digambarkan dengan
3.3
Operasi BIG.MIXCOLUMNS (S) Operasi ini adalah analogi seksama dengan operasi MixColumns pada AES. Operasi
MixColumn dilakukan berdasarkan MDS dengan pengacakan 4 bytes, dan pada AES dilakukan setiap 4 kolom dari table state. Proses ini diperluas dengan cara yang jelas dalam ECHO dimana dapat kita lihat 4 kolom 128-bit setiap state S yang terdiri dari 64 kolom dengan panjang 1 byte. Lalu kita gunakan operasi AES MixColumuntuk setiap kolom pada S.
Lebih jelasnya, ditentukan 4x128-bit w1,...,wi+3 untuk i ϵ { 0,4,8,12 } dalam bentuk kolom pada S. Penulisan dalam byte string yaitu: wi = (B16i, B16i+1, ... , B16i+15) wi+1 = (B16i+16, B16i+17, ... , B16i+31) wi+2 = (B16i+32, B16i+33, ... , B16i+47) wi+3 = (B16i+48, B16i+49, ... , B16i+63) dengan menggunakan notasi dalam FIPS-197, kita hitung untuk i ϵ { 0,4,8,12 } dan 0 ≤ j ≤ 15,
Hal ini hanyalah operasi MixColumns AES dimana aritmatika fiels ditentukan dengan polinomial Rijndael x8+x4+x3+x+1. 3.4
Kompresi akhir untuk 128 ≤ HSIZE ≤ 256 Fungsi kompresi lengkap COMPRESS512 dapat digambarkan dengan operasi pokok: Repeat Big.SubWords(S, SALT, k) Big.ShiftRows (S)
Big.MixColumn (S) Eight times Big.Final Operasi Big.Final digunakan untuk mendapatkan nilai output dari variabel chainning. Operasi ini menggabungkan nilai feedforwad dari input dan jika kita notasikan nilai akhir S dengan w0,...,w15 maka Big.Final (untuk COMPRESS512) digambarkan sbb:
3.5
Nilai output hash untuk 128 ≤ HSIZE ≤ 256 Nilai akhir dari variabel chainning dilihat dalam string 512-bit v0t || v1t || v2t ||v3t. Untuk memberikan output h hash dari bit HSIZE yang terkecil. Nilai output hash dari HSIZE dapat dicari dengan mudah.
4. Fungsi Kompresi untuk 257 ≤ HSIZE ≤ 512 Jika output hash lebih besar dari 256 bit yang dibutuhkan, kita gunakan fungsi kompresi COMPRESS1024. Fungsi ini sama dengan fungsi COMPRESS512 kecuali: 1.
Pesan yang dipadding M’ dibagi menjadi t blok pesan M1,...,Mt, setiap blok memiliki panjang 1024 bit
2.
Variabel chainning terdiri atas 8x128-bit words Vi= v0i...v7i dan diinisialisasi sama seperti bab 2.1
3.
Pada awal fungsi kompresi, variabel chainning dan blok pesan dibagi menjadi 4x4 array state
4. Fungsi komputasi terdiri dari 10 iterasi Big.Round (termasuk 8 iterasi menggunakan
COMPRESS512) 5.
Jika kita notasikan nilai akhir S dengan w0,..,w15, operasi Big.Final untuk mendapatkan variabel chainning yang baru dengan:
4.1
Output hash untuk 257 ≤ HSIZE ≤ 512
Nilai akhir dari variabel chainning dilihat sebagai string 1024-bit:
Untuk menghasilkan output hash h dari bit HSIZE, kita gunakan bit terkecil dari HSIZE. Sebagai contoh, untuk HSIZE = 384, kita dapatkan
Dan ketika HSIZE = 512, output yang dihasilkan
Output hash untuk nilai lain dari HSIZE dapat dihasilkan dengan mudah.
5.
Fungsi Kompresi ECHO memiliki fungsi kompresi yang beroperasi pada internal state yang besar yaitu
2048 bit. Hal ini memang sudah menjadi konsekuensi jika kita ingin algoritma hash ini kuat ,
karena telah dicoba dengan ukuran internal state yang lebih kecil, namun hasilnya tidak begitu kuat. Dengan internal state yang besar maka sifat konfusi dan difusi akan terpenuhi. 5.1. Konfusi dan Difusi Konfusi dan difusi merupakan suatu isu yang diangkat Shannon untuk mengukur kekuatan suatu algoritma block cipher. Namun sifat konfusi dan difusi ini pun dapat diterapkan pada fungsi hash meskipun didalamnya tidak ada secret key. Hal ini karena pada intinya konfusi dan difusi tergantung dari cara pandang seseorang, yang terpenting konfusi adalah suatu kondisi dimana hubungan antara bit-bit input itu rumit / kompleks, sementara difusi adalah penyebaran dari pengaruh suatu perubahan bit input. Memang tidak selalu mudah untuk mengidentifikasi secara tepat komponen-komponen yang berkontribusi dalam mendapatkan konfusi ataupun difusi. Sehingga suatu hasil analisis tidak perlu dianggap terlalu serius. Akan tetapi kita telah mengetahui bahwa AES memiliki suatu komponen yang merupakan sumber konfusi yang baik, yaitu Sbox-nya. Karena memiliki Sbox tersebut, AES tahan terhadap linier dan differential cryptanalysis. Maka karena ECHO merupakan AES varian, sifat-sifat tadi pun dimiliki oleh ECHO. Sebagai tambahan, kita akan menitikberatkan pada internal counter k yang digunakan pada BIG.SUBWORDS. Dan karena internal counter k tersebut berubah dari cell ke cell untuk tiap dua round AES maka mengakibatkan terbentuknya suatu different transformation. Faktanya bit counter Ci yang menentukan nilai k , tidak pernah bernilai sama. 5.2 . Differential Cryptanalysis ECHO Differential cryptanalysis tidak hanya digunakan untuk menyerang block cipher, tapi juga dapat diterapkan dengan baik pada fungsi hash. Namun karena pada fungsi hash terdapat collision, maka untuk mengontrol differential path dilakukan secara sangat hati-hati. Namun untuk selebihnya, apa-apa yang dapat diterapkan pada block cipher juga dapat diterapkan pada fungsi hash dengan baik. Untuk differential cryptanalysis pada ECHO, kita terapkan pada fungsi kompresi COMPRESS512 dan COMPRESS1024 tanpa melibatkan BIG.FINAL dan operasi-operasi feedforward. Setelah perpindahan operasi-operasi tersebut, akan ditemukan suatu block cipher yang disebut sebagai ECHO.AES yang memiliki ukuran blok 2048 bit dan tersusun atas fungsi round r ECHO.ROUND yang tiap round-nya tersebut mengambil input sebagai state block cipher
S dan sebuah round key K 4096 bit. Round key ini merupakan suatu sequence 128 bit words yang terdiri atas 16 pasang (k1,k2) untuk setiap cell S seperti di bawah ini :
Fungsi round ini mirip dengan BIG.ROUND meski inputannya berupa (S,K) bukan (S, salt, k). Fungsi round ECHO.ROUND terdiri dari tiga buah fungsi berikut ini :
Fungsi ECHO.SUBWORD (S,K) sangat berhubungan dengan fungsi BIG.SUBWORD dan didefinisikan sebagai berikut :
Untuk tujuan analisis, kita akan menggunakan ECHO.SBOX untuk menotasikan permutasi berbasis AES pada 128-bit word w dengan 128-bit kunci k1 dan k2 seperti di bawah ini :
Namun perlu digarisbawahi bahwa ECHO.AES hanyalah sebuah tool untuk mempermudah dalam menganalisis fungsi kompresi ECHO. 5.3. Ketahanan terhadap Metode Serangan AES lainnya Karena fungsi kompresi ECHO berhubungan dekat dengan AES, kita bisa menginvestigasi ketahanannya terhadap berbagai metode serangan yang telah dilakukan terhadap AES. 5.3.1. Structural attacks Beberapa serangan yang efektif terhadap versi AES reduced-round adalah berasaskan efficient distingusiher. Dua dari kebanyakan distinguisher yang efisien adalah distinguisher integral tiga round dari Square attack dan distinguisher integral emapt round yang digunakan untuk meningkatan kriptanalisis terhadap round-reduced AES.
Selama distinguisher yang meningkat terhadap ECHO.AES dan ECHO tidak keluar, hubungan dekat desain ECHO terhadap AES dan jumlah studi yang telah dilakukan pada AES, meminjamkan kekuatan yang cukup untuk kita percaya bahwa distinguisher berbasis integral atau collision mewakili resiko yang kecil terhadap ECHO. 5.3.2. Known-key distinguisher Known-key distinguisher mengeksploitasi keberadaan distinguisher integral yang efisien untuk enkripsi AES pada empat round terakhir dan dekripsi pada tiga round pertama. Pihak lawan mulai dari sebuah struktur yang cocok dari 256 blok pertengahan dan mengeksploitasi distinguisher ini untuk membentuk pasangan plaintext/cipertext. Transposisi distinguisher ini ke ECHO.AES jelas. Ini akan memperbolehkan kita untuk mendistinguish tujuh round ECHO.AES tanpa transformasi BIG.MIXCOLUMNS pada round ke-tujuh dan komplesitasnya dekat ke 2896 komputasi tujuh round ECHO.AES. Walaupun demikian, karena kompleksitas yang besar dan jumlah blok input yang terlibat, distinguisher ini secara jelas tidak mengancam keamanan fungsi kompresi ECHO. 5.3.3. Algebraic attacks AES mempunyai deskripsi aljabar sederhana secara relatif; yang dapat dideskripsikan jarang dan ditentukan pada sistem quadratik multivariate dari 5248 persamaan pada GF (28) dengan 2600 state variabel dan 1408 key variabel. Observasi ini dapat diperluas ke ECHO.AES dan digilirkan ke ECHO, tapi menghasilkan sistem aljabar yang jauh lebih besar. Mengingat tidak adanya kemajuan dalam kriptanalisis aljabar pada sistem semacam ini, kita akan terkejut jika teknik kriptanalisis aljabar dapat diterapkan pada sebagian besar di ECHO. 5.3.4. Related-key attacks Desain ECHO tidak mempunyai key schedule konvensional; penyerang tidak bisa mengontrol chaining variable dan input pesan untuk membangkitkan differences yang mungkin input melalui komputasi.
