Tahun 2013 saya pernah repost artikel "Hash functions: dead or alive?" karya mey lee dari echo|zine volume 5 issue 16 di blog lama saya, UpicoS: Hash functions. Tulisan ini saya tulis ulang dengan bahasa saya sendiri dan saya update dengan perkembangan setelahnya. Kredit untuk materi aslinya tetap milik penulisnya, dan referensi aslinya saya cantumkan di bagian akhir.
Setiap kali login, password kamu hampir pasti nggak disimpan apa adanya di database. Yang disimpan adalah hasil olahan sebuah hash function. Konsep ini dipakai di mana-mana: password, digital signature, verifikasi file download, sampai Git.
Apa itu hash function?
Hash function adalah fungsi yang menerima input sepanjang apa pun, lalu menghasilkan output pendek dengan panjang tetap. Output-nya disebut hash atau digest.
Anggap saja hash itu sidik jari digital. File 2 GB atau satu kata saja, hasil SHA-256-nya sama-sama 256 bit.
Asalnya dari ilmu komputer biasa: butuh cara memadatkan string panjang jadi nilai pendek, misalnya untuk menentukan posisi data di hash table. Di kriptografi, syaratnya jauh lebih ketat.
Di kriptografi, hash function dibagi dua:
- Unkeyed hash function (Manipulation Detection Code, MDC): input-nya cuma satu, yaitu pesan. Inilah yang biasa kita sebut "hash function".
- Keyed hash function (Message Authentication Code, MAC): input-nya dua, yaitu pesan dan kunci rahasia. Contoh yang paling umum sekarang adalah HMAC.
Sifat yang wajib dimiliki
Hash kriptografis yang bagus harus memenuhi tiga syarat ini:
- Preimage resistance (one-way): kalau dikasih hash
Y, secara komputasi nggak mungkin menemukan pesanXdenganh(X) = Y. Konsep one-way function ini diperkenalkan Diffie dan Hellman di paper New Directions in Cryptography.
- Second preimage resistance: kalau dikasih pesan
X, nggak mungkin menemukan pesan lainX'dengan hash yang sama. Sifat ini kadang disebut weak collision resistance.
- Collision resistance: nggak mungkin menemukan dua pesan apa pun yang hash-nya sama. Definisi formalnya diperkenalkan Yuval di paper How to Swindle Rabin.
Menemukan second preimage jelas nggak lebih gampang daripada menemukan collision. Karena itu, collision resistance adalah syarat paling berat, dan biasanya sifat inilah yang pertama jebol.
Ada satu sifat lagi yang bikin hash berguna, yaitu avalanche effect: beda satu huruf saja di input, hasilnya berubah total.
$ printf 'halo dunia' | shasum -a 256
09b50b2f685e7a783eeee02d8070e670d48af118a4b00f7bfebe9f8f0e5d3d52 -
$ printf 'Halo dunia' | shasum -a 256
8f6b9417cd9a7ba37b13d684eba2a6be2ea9c349b51c81395c57e1cb3ab7e126 -Dipakai buat apa?
Password
Aplikasi nggak menyimpan password kamu, tapi hash-nya. Saat login, input kamu di-hash lagi, lalu hasilnya dicocokkan dengan yang ada di database. Dengan begitu, dua nilai bisa dibandingkan tanpa perlu tahu isi aslinya.
Tapi hati-hati: untuk password, jangan pakai hash biasa seperti MD5 atau SHA-256 langsung. Hash biasa didesain supaya cepat, dan itu justru memudahkan brute-force. Untuk password, pakai algoritma yang sengaja dibuat lambat dan memakai salt, seperti Argon2id, scrypt, atau bcrypt.
Integritas file
Pernah lihat checksum SHA-256 di halaman download? Setelah download, hitung hash file-nya. Kalau hasilnya sama dengan yang tertera, berarti file-nya utuh dan nggak diubah di tengah jalan. Hash-nya bisa dikirim lewat jalur lain, jadi kalau file-nya lewat jalur yang nggak aman sekalipun, keasliannya tetap bisa dicek.
Digital signature
Yang ditandatangani biasanya bukan pesan aslinya, tapi hash dari pesan itu. Lebih cepat dan tetap aman. Alurnya kira-kira begini:
- Pengirim menghitung hash dari pesan.
- Hash itu ditandatangani dengan private key pengirim, hasilnya jadi signature.
- Pesan dan signature dikirim ke penerima.
- Penerima memverifikasi signature dengan public key pengirim, lalu menghitung hash pesan yang ia terima sendiri.
- Kalau cocok, pesan dijamin asli dan utuh. Kalau beda satu huruf saja, hash-nya beda total dan signature-nya gagal diverifikasi.
Algoritma yang populer
MD5
MD5 (RFC 1321) dibuat Ron Rivest dari MIT. Output-nya 128 bit, dan dulu jadi algoritma hash paling populer. Sekarang MD5 sudah rusak: collision bisa dibuat dalam hitungan detik di laptop biasa.
Keluarga SHA
SHA (Secure Hash Algorithm) dirancang NSA dan distandarkan pemerintah AS lewat NIST. SHA-1 sempat dipakai luas di SSL/TLS, PGP, SSH, S/MIME, dan IPsec.
Algoritma | Ukuran digest (bit) | Internal state (bit) | Ukuran blok (byte) | Status |
SHA-0 | 160 | 160 | 64 | Rusak |
SHA-1 | 160 | 160 | 64 | Rusak |
SHA-224 | 224 | 256 | 64 | Aman |
SHA-256 | 256 | 256 | 64 | Aman |
SHA-384 | 384 | 512 | 128 | Aman |
SHA-512 | 512 | 512 | 128 | Aman |
SHA-3 | 224–512 | 1600 | 72–144 | Aman |
Internal state adalah nilai hash sementara setelah setiap blok data diproses.
Perjalanan jebolnya MD5 dan SHA-1
Artikel echo|zine tadi mencatat serangan-serangan ini, dan sejarahnya ternyata masih berlanjut:
- 1998: Chabaud dan Joux mempresentasikan serangan ke SHA-0 dengan kompleksitas 2^61, lebih rendah dari batas ideal 2^80.
- 2004: Biham dan Chen menemukan near-collision SHA-0, yaitu 142 dari 160 bit sama. Pada 12 Agustus 2004, Joux, Carribault, Lemuet, dan Jalby mengumumkan collision penuh SHA-0 dengan kompleksitas sekitar 2^51, butuh sekitar 80.000 jam CPU di superkomputer berisi 256 prosesor Itanium 2.
- Agustus 2004: di rump session CRYPTO 2004, Wang, Feng, Lai, dan Yu menunjukkan collision untuk MD5 dan beberapa hash lain.
- Februari 2005: Wang, Yin, dan Yu mengumumkan collision SHA-0 dalam sekitar 2^39 operasi, sekaligus serangan ke SHA-1 yang jauh di bawah batas idealnya.
- Agustus 2005: Wang, Andrew Yao, dan Frances Yao menurunkan serangan SHA-1 ke sekitar 2^63.
- Oktober 2005: NIST mengadakan workshop khusus hash function di Santa Barbara untuk membahas pengganti SHA-1.
Setelah artikel itu ditulis, ceritanya berlanjut:
- 2007–2012: NIST menggelar kompetisi terbuka untuk mencari standar hash baru. Pemenangnya Keccak.
- 2015: Keccak resmi jadi SHA-3 lewat FIPS 202. Jadi pertanyaan "akankah ada standar baru?" di artikel aslinya sudah terjawab.
- 2017: Google dan CWI Amsterdam merilis SHAttered, collision SHA-1 pertama yang nyata: dua file PDF berbeda dengan hash SHA-1 yang sama.
- 2020: serangan SHA-1 is a Shambles membuat chosen-prefix collision SHA-1 jadi praktis dan murah.
- 2022: NIST mengumumkan SHA-1 akan dihentikan sepenuhnya paling lambat akhir 2030.
Jadi, pakai yang mana sekarang?
- Integritas file, digital signature, umum: SHA-256, SHA-512, atau SHA-3.
- Autentikasi pesan dengan kunci: HMAC-SHA-256.
- Password: Argon2id, scrypt, atau bcrypt. Jangan hash cepat.
- MD5 dan SHA-1: jangan dipakai untuk keamanan. Masih boleh untuk hal non-keamanan seperti cache key atau deteksi duplikat.
Jadi, hash function: dead or alive? Jawabannya alive, asal algoritmanya dipilih dengan benar 😄
Referensi
Artikel asli
- mey lee, "Hash functions: dead or alive?", echo|zine volume 5 issue 16. Di-repost di UpicoS.
Referensi dari artikel asli
- Bruce Schneier, Applied Cryptography, Second Edition, John Wiley & Sons, 1996.
- Alfred J. Menezes, Paul C. van Oorschot, Scott A. Vanstone, Handbook of Applied Cryptography, CRC Press, 1997.
- William Stallings, Cryptography and Network Security, Third Edition, Prentice Hall.
- Chabaud dan Joux, Differential Collisions in SHA-0, 1998. fchabaud.free.fr/English/Publications/sha.pdf
- Xiaoyun Wang, Dengguo Feng, Xuejia Lai, Hongbo Yu, Collisions for Hash Functions MD4, MD5, HAVAL-128 and RIPEMD, 2004. eprint.iacr.org/2004/199
- Xiaoyun Wang, Yiqun Lisa Yin, Hongbo Yu, Collision Search Attacks on SHA-1, 2005. theory.csail.mit.edu/~yiqun/shanote.pdf
- Xiaoyun Wang, Yiqun Lisa Yin, Hongbo Yu, Finding Collisions in the Full SHA-1. infosec.sdu.edu.cn/paper/sha1-crypto-auth-new-2-yao.pdf
- E. Biham dan R. Chen, Near-Collisions of SHA-0, Advances in Cryptology – CRYPTO 2004, hlm. 290–305, Springer-Verlag, Agustus 2004.
- E. Biham dan R. Chen, New Results on SHA-0 and SHA-1, CRYPTO 2004 Rump Session, Agustus 2004.
- E. Biham, R. Chen, A. Joux, P. Carribault, W. Jalby, C. Lemuet, Collisions of SHA-0 and Reduced SHA-1, Advances in Cryptology – EUROCRYPT 2005, hlm. 36–57, Mei 2005.