echo|zine, volume 5 issue 16 Hash functions : dead or alive ? by mey lee <adis_axe[at]yahoo[dot]com> ---// Pengantar Dalam dunia kriptografi, hash function bukan merupakan suatu barang yang baru. Merupakan salah satu cabang dalam kriptografi, hash function memiliki daya tarik tersendiri dikarenakan cukup banyak aplikasi yang menggunakan hash function dalam penerapannya. Hash function digunakan sebagai autentikasi, integritas dan digital signature, salah satu aplikasinya yaitu penggunaan password dalam aplikasi digital atau internet. Cryptographic Hash Function adalah suatu fungsi dengan inputan yang berubah-ubah panjangnya (atau sangat panjang) dan memetakannya sehingga menghasilkan output yang pendek dan panjang nya tetap. Hash functions berawal dari ilmu komputer, dimana dibutuhkan sebuah fungsi yang berguna untuk mengkompresi sebuah string dengan panjang yang berubah-ubah menjadi sebuah string tetap yang lebih pendek. Hash functions digunakan untuk menentukan secara keseluruhan tempat penyimpanan yang mungkin dari sebuah file. Pada aplikasi kriptografi, hash function dibedakan menjadi unkeyed dan keyed hash functions. 1.Unkeyed Hash Function (Manipulation Detection Codes = MDCs) Hanya memerlukan satu parameter input, yaitu berita 2.Keyed Hash Function (Message Authentication Codes = MACs) Menggunakan dua parameter input, yaitu berita dan kunci Selanjutnya, Unkeyed hash functions atau MDCs yang akan dikenal sebagai Hash Functions. Hash functions juga dapat digunakan untuk keamanan pada autentikasi berita yaitu dengan melakukan autentikasi dari hasil hash berita tersebut. Contoh sederhana misalnya proses komunikasi pengiriman file ukuran besar yang melalui jalur insecure, autentikasi yang dilakukan yaitu dengan mengirimkan hasil hash dari berita melalui jalur komunikasi biasa misalnya mail biasa atau melalui telefax. Aplikasi hash functions yang umum adalah digital signatures yaitu aplikasi untuk menandatangani hasil hash dan hal ini jauh lebih baik daripada menandatangani berita aslinya, dan akan mendapatkan keuntungan keamanan sekaligus performance. Dengan hash functions kita dapat membandingkan dua buah nilai tanpa harus membuka berita. Misalnya password dan passphrase. -----// Bagaimanakan penerapan hash function dalam sebuah password?? A adalah seorang user pada suatu aplikasi yang memerlukan proses autentikasi dalam hal ini password. Aplikasi tersebut akan meminta input dari A kemudian dengan algoritma hash functions yang digunakan oleh aplikasi tersebut maka akan diubah inputan tersebut menjadi suatu output yang unik dan dengan suatu panjang tertentu. Tidak ada satupun output atau hasil hash functions dalam aplikasi tersebut yang nilainya sama. Selanjutnya, aplikasi tersebut hanya akan mencocokkan hasil output setiap kali user A login dengan database yang ia punya. -----// Bagaimanakan penerapannya dalam digital signatures?? Sebuah digital signatures digunakan sebagai fungsi integritas suatu berita atau data yang dikirim. Apakah berita itu asli? Adakah kekurangan dalam berita tersebut? Inputan dalam algoritma Hash Function dapat berubah-ubah panjangnya (atau sangat panjang) untuk kemudian menghasilkan output yang panjang nya tetap (misalnya 128 bit, 256 bit). User A ingin mengirimkan sebuah berita kepada user B, sebelumnya user A mencari digital signatures berita yang telah terenkripsi dengan menggunakan suatu algoritma hash function. Dan mengenkripsi digital signature tersebut. Kemudian user A mengirimkan berita dan digital signature berita yang keduanya telah di enkripsi tersebut kepada user B. User A |--------| di enkripsi |--------------------| Dicari Hash |-------------------| | Berita |--------------> | Berita terenkripsi |------------>| Digital signature | |--------| |--------------------| |-------------------| | | di enkripsi \|/ + |-------------------| | digital signature | | yang terenkripsi | |-------------------| User B akan menerima berita yang telah terenkripsi dan digital signature dari user A. Langkah pertama, user B akan mendekripsi digital signature tersebut. Kemudian ia mencari nilai hash dari berita yang telah terenkripsi untuk kemudian dicocokkan dengan digital signature berita tersebut. Jika hasil nya sama, maka berita tersebut asli, dan berita tersebut terjamin keutuhannya. Jika hasilnya berbeda maka integritas berita tersebut patut dipertanyakan. Karena perbedaan satu huruf pada inputan hash function akan menghasilkan nilai hash yang jauh berbeda. Sehingga kita dapat melihat integritas atau keaslian berita tersebut tanpa harus membuka berita tersebut. User B |-------------------| |-----------| | digital signature |di dekripsi | Digital | | yang terenkripsi |----------->| signature | |-------------------| |-----------| /\ || dibandingkan, apakah sama ? \/ |--------------------| Dicari Hash |-------------------| | Berita terenkripsi |------------>| Digital signature | |--------------------| |-------------------| Jika sama, maka berita tersebut asli, user B dapat mendekripsi berita tersebut ---// Sifat umum hash functions Hash function adalah sebuah fungsi h yang : -----// 1. One-Way Hash Function (OWHF) Konsep One-Way Hash Function diperkenalkan pertama kali oleh Diffie dan Hellman pada papernya "New Directions in Cryptography". Definisi 1 Sebuah One-Way Hash Function (OWHF) adalah fungsi h yang memenuhi kondisi : 1.Sebuah X dapat mempunyai panjang yang bervariasi dan hasil dari h(x) hanya mempunyai sebuah panjang yang tetap yaitu n bit 2.Hash Function akan bersifat one-way yaitu jika diberikan sebuah Y hasil dari h, maka akan tidak mungkin (secara perhitungan) untuk menemukan sebuah berita X dimana h(X) = Y (preimage resistant) dan diberikan X dan h(X) maka akan tidak mungkin (secara perhitungan) untuk menemukan sebuah berita X’ ≠X dimana h(X’) = h(X) (second preimage resistant). Sebuah fungsi yang bersifat preimage resistant dikenal dengan one-way function (namun preimage resistance biasanya digunakan untuk hash function). Beberapa penulis menyebutkan second preimage resistantce sebagai weak collision resistance. Untuk beberapa aplikasi (seperti fungsi pseudo-random dan algoritma MAC yang berdasarkan hash functions) sebagian besar dari input dapat diketahui namun sulit untuk menemukan bagian yang tidak diketahui pada input tersebut. Hal seperti ini disebut dengan partial preimage resistance. -----// 2. Collision Resistant Hash Function Definisi dari collision resistance hash functions (CRHF) secara formal di perkenalkan oleh Yuval pada papernya "How to swindle Rabin". Definisi 1 Sebuah Collision Resistance Hash Functons (CRHF) adalah fungsi h yang memenuhi kondisi : 1.Sebuah X dapat mempunyai panjang yang bervariasi dan hasil dari h(x) hanya mempunyai sebuah panjang yang tetap yaitu n bit 2.Hash Function tersebut harus merupakan OWHF, yaitu memenuhi preimage resistance dan second preimage resistance. 3.Hash function tersebut harus bersifat collision resistant, yaitu dimana tidak mungkin (secara perhitungan) untuk menemukan dua berita yang mempunyai nilai hash yang sama. -----// 3. Relating between definitions Hubungan dari kedua definisi Jelas dilihat bahwa menemukan sebuah second preimage tidak akan lebih mudah dibanding menemukan sebuah collision. Bagaimanapun juga untuk menentukan hubungan yang pasti dari kedua kondisi diatas memerlukan definisi khusus. Pada kondisi tertentu, collision resistance menyebabkan preimage resistance dan second preimage resistance. ---// Beberapa algoritma hash functions -----// 1. MD5 MD5 Message Digest Algorithm (RFC 1321) ditemukan oleh Ron Rivest pada MIT. Sampai beberapa tahun ketika brute-force dan kriptanalisa berkembang pesat, MD5 adalah algoritma hash function yang paling banyak digunakan. Input algoritma ini adalah sebuah berita dengan panjang yang bervariasi dan menghasilkan output sebuah 128-bit message digest. -----// 2. SHA (Secure Hash Algorithm) family SHA Family adalah merupakan algoritma hash function yang dibuat oleh National Security Agency (NSA) dan dipublikasikan sebagai standar oleh pemerintah USA.. Algoritma SHA family yang paling banyak digunakan adalah SHA-1 dan telah banyak diaplikasikan pada berbagai macam aplikasi keamanan dan protokol keamanan seperti SSL, PGP, SSH, S/MIME dan IPSec. ---\\ Perbandingan SHA family ================================================================= | Algoritma Hash | Ukuran Digest | Ukuran Internal| Ukuran Blok | | | Hash (bits) | State (bits) | (bytes) | ================================================================= | SHA-0 | 160 | | | | SHA-1 | 160 | 160 | 64 | | SHA-224 | 224 | 256 | 64 | | SHA-256 | 256 | 256 | 64 | | SHA-384 | 384 | 512 | 128 | | SHA-512 | 512 | 512 | 128 | ----------------------------------------------------------------- Catatan : Internal state adalah “sum (digest) internal hash“ setelah tiap kompresi dari satu blok data. ---// Cryptanalysis on Hash Functions Banyak peneliti yang mencoba melakukan cryptanalysis terhadap algoritma hash functions yang ada. Dan perkembangan cryptanalysis tersebut sangat mengejutkan. - Pada konferensi CRYPTO 98, dua peneliti asal Perancis mempresentasikan sebuah attack terhadap SHA-0 [3] dimana collisions dapat ditemukan dengan kompleksitas 261; lebih rendah dari 280, kompleksitas ideal suatu hash functions. - Pada tahun 2004, Biham dan Chen menemukan near-collisions untuk SHA-0 [8] , yaitu menemukan dua berita yang hampir mempunyai nilai hash yang sama, dimana dari 160 bit output, 142 bitnya sama. Mereka juga menemukan full collisions pada SHA-0 dengan 62 round dari total 80 round. - Berikutnya, pada 12 Agustus 2004, sebuah collision untuk full SHA-0 diumumkan oleh Joux, Carribault, Lemuet dan Jalby. Dengan menggunakan Chabaud dan Joux Attack[10]. Yaitu menemukan collisions dengan kompleksitas 251 dan memerlukan 80.000 jam dengan menggunakan superkomputer yang didalamnya terdapat 256 buah prosesor Itanium 2. - Pada 17 Agustus 2004, pada Rump Session CRYPTO 2004, sebuah hasil pendahuluan telah diumumkan oleh Wang, Feng, Lai dan Yu, mengenai attack terhadap MD5, SHA-0 dan hash functions lainnya [5]. Kompleksitas attack mereka terhadap SHA-0 adalah sekitar 240, jauh lebih baik dibandingkan attack yang dilakukan oleh Joux dan yang lainnya. - Pada Februari 2005, sebuah attack kembali dilakukan oleh Xiaoyun Wang, Yiqun Lisa Yin, dan Hongbo Yu, dan diumumkan bahwa mereka dapat menemukan collision pada SHA-0 dalam 239 operasi [6]. - Berdasarkan beberapa kriptanalisis terhadap SHA-0, beberapa ahli menyarankan untuk menggunakan SHA-1 sebagai kriptosistem baru. Setelah hasil tersebut dipublikasikan, NIST mengumumkan bahwa mereka berencana menghapus setahap demi setahap penggunaan SHA-1 sampai 2010, dan menggantikan nya dengan SHA-2 variant. - Pada tanggal 17 Agustus 2005, perkembangan attack terhadap SHA-1 diumumkan oleh Xiaoyun Wang, Andrew Yao dan Frances Yao pada rump session CRYPTO 2005, dan dapat menemukan collision dengan kompleksitas 263. ---// Penutup Karena telah ditemukannya full-collision pada beberapa algoritma hash functions (selain SHA-1 dapat juga diterapkan pada MD5, RIPEMD) oleh para peneliti dari China tersebut, NIST (National Institute of Standards and Technology) mengadakan suatu workshop khusus mengenai hash functions di Santa Barbara pada Oktober 2005. Dalam workshop tersebut mereka mengeluarkan issue mengenai algoritma hash function yang dapat menggantikan SHA-1. Issue tersebut sangat penting mengingat SHA-1 telah dijadikan standard algoritma hash function oleh pemerintah USA (NIST). Sampai saat ini belum ada algoritma hash yang dijadikan standard (dalam hal ini oleh USA dan indonesia sendiri belum mempunyai standard tersendiri mengenai hal ini), padahal aplikasi yang menggunakan hash functions sebagai digital signature, autentikasi banyak dipakai di perbankan atau aplikasi online lainnya. Hal ini akan menjadi masalah tersendiri bagi keamanan informasi. Akankan akan ada standard baru algoritma hash functions? Bagaimana keamanan aplikasi yang sudah terlanjur menggunakan algoritma hash functions yang tidak aman? Apakah Indonesia akan memiliki standard sendiri mengenai algoritma hash functions tersebut? dan Bagaimana kebijakan nya? That’s the next big issues!! ---// Greetz : - My beloved husband and son : you are all my everyting, - Mas ammar yang udah ngasih ’petunjuk’ :), - All of my family and friends, cant go through without you all. ---// Reference : [1] Bruce Schneier, "Applied Cryptography Second Edition" , John Wiley & Sons. Inc, 1996 [2] Alfred J. Menezes, Paul C. Van Oorschot, Scott A. Vanstone," Handbook of Applied Cryptography", CRC Press, 1997. [3] William Stallings, "Cryptograpgy and Network Security,Third edition", Prentice Hall. [4] Chabaud and Joux, Different Collisions in SHA-0, 1998, http://fchabaud.free.fr/English/Publications/sha.pdf [5] Xiaoyun Wang, Dengguo Feng, Xuejia Lai, Hongbo Yu, "Collision for Hash Functions, MD4, MD5, Haval-128 and RIPEMD", 2004. http://eprint.iacr.org/2004/199.pdf [6] Xiaoyun Wang, Yiqun Lisa Yin, Hongbo Yu, "Collision Search Attacks on SHA-1", 2005, http://theory.csail.mit.edu/~yiqun/shanote.pdf [7] Xiaoyun Wang, Yiqun Lisa Yin, Hongbo Yu, "Finding Collision in the Full SHA-1" http://www.infosec.sdu.edu.cn/paper/sha1-crypto-auth-new-2-yao.pdf [8] E. Biham and R. Chen. Near Collisions of SHA-0. Advances in Cryptology – Crypto’04, pp.290-305, Springer-Verlag, August 2004. [9] E. Biham and R. Chen. New Results on SHA-0 and SHA-1. Crypto’04 Rump Session, August 2004. [10] E. Biham, R. Chen, A. Joux, P. Carribault, W. Jalby and C. Lemuet. Collisions in SHA-0 and Reduced SHA-1. Advances in Cryptology–Eurocrypt’05, pp.36-57,May 2005.
Hash functions
Subscribe to:
Post Comments
(
Atom
)
No comments :
Post a Comment