Fungsi Hash MD5 dan SHA-1

Fungsi hash adalah fungsi yang menerima masukan string atau pesan yang panjangnya sembarang dan mengkonversinya menjadi string keluaran yang panjangnya tetap atau fixed. Fungsi hash yang dihasilkan biasanya dituliskan dalam notasi persamaan :

h = H (M)

Dimana h merupakan nilai hash yang dihasilkan, sedangkan H adalah fungsi hash-nya itu sendiri dan M adalah message atau pesan yang akan diubah dan dikonversikan menjadi nilai hash (hash value). Nilai hash yang dihasilkan disebut juga pesan ringkas atau message digest. Fungsi hash dapan mengkonversikan sembarang pesan yang berukuran berapa saja menjadi message digest yang berukuran tetap dan biasanya lebih pendek dari panjang pesan yang asli. 

Berikut contoh penggunaan fungsi hash yang mengubah suatu string dengan panjang berapapun menjadi sebuah message digest dengan panjang tetap :

Hash memang umumnya digunakan untuk mengecek integritas dari sebuah pesan atau file. File atau pesan yang sudah berubah akan memiliki nilai hash yang berbeda. Sebagai contoh, dengan sebuah algoritma hash, pesan 'hello' akan memberikan nilai hash 12345 sedangkan pesan 'hallo' memiliki nilai hash 83746. Dengan kata lain output hash dari kata 'hello' tidak akan sama dengan 'hallo'.

Nama lain fungsi hash adalah:

• Fungsi kompresi (compression function)
• Cetak-jari (fingerprint)
• Cryptographic checksum
• Message integrity check (MIC)
• Manipulation detection code (MDC)

Sifat - sifat fungsi hash :

• Pre-image resistance. Untuk suatu nilai hash yang sembarang (tidak diketahui asalusulnya), sangat sukar untuk mencari naskah yang mempunyai nilai hash tersebut.
• Second pre-image resistance. Untuk suatu naskah m1, sangat sukar untuk mencari naskah lain m2 (m1 ≠ m2) yang mempunyai nilai hash yang sama (hash(m1) = hash(m2)). Persyaratan ini kerap disebut juga weak collision resistance.
• Collision resistance. Sangat sukar untuk mencari dua naskah m1 dan m2 yang berbeda (m1 ≠ m2) yang mempunyai nilai hash yang sama (hash(m1) = hash(m2)). Persyaratan ini kerap disebut juga strong collision resistance.

Algoritma biasanya terdiri dari dua tahap:

1. Preprocessing dan
2. Hashing.

Tahap preprocessing biasanya terdiri dari padding dan parameter setup. Tahap hashing membuat sidik jari dengan mengkompresi naskah yang sudah diberi padding. Hash adalah suatu teknik "klasik" dalam Ilmu Komputer yang banyak digunakan dalam praktek secara mendalam. Hash merupakan suatu metode yang secara langsung mengakses record-record dalam suatu tabel dengan melakukan transformasi aritmatik pada key yang menjadi alamat dalam tabel tersebut. Pelacakan dengan menggunakan Hash terdiri dari dua langkah utama, yaitu:

1. Menghitung Fungsi Hash

Fungsi Hash adalah suatu fungsi yang mengubah key menjadi alamat dalam tabel. Fungsi Hash memetakan sebuah key ke suatu alamat dalam tabel. Idealnya, key-key yang berbeda seharusnya dipetakan ke alamat-alamat yang berbeda juga. Pada kenyataannya, tidak ada fungsi Hash yang sempurna. Kemungkinan besar yang terjadi adalah dua atau lebih key yang berbeda dipetakan ke alamat yang sama dalam tabel. Peristiwa ini disebut dengan collision (tabrakan). Karena itulah diperlukan langkah berikutnya, yaitu collision resolution (pemecahan tabrakan).

2. Collision Resolution

Collision resolution merupakan proses untuk menangani kejadian dua atau lebih key di-hash ke alamat yang sama. Cara yang dilakukan jika terjadi collision adalah mencari lokasi yang kosong dalam tabel Hash secara terurut. Cara lainnya adalah dengan menggunakan fungsi Hash yang lain untuk mencari lokasi kosong tersebut.

Hash juga termasuk salah satu bentuk teknik kriptografi dan dikategorikan sebagai kriptografi tanpa key (unkeyed cryptosystem) karena pada prosesnya fungsi hash ini tidak menggunakan key tetapi menggunakan fungsi untuk menghasilkan message digest. Berbeda dengan teknik enkripsi dalam kriptografi, tujuan hash memang mengubah sebuah pesan yang dapat dibaca (readable text) menjadi pesan acak (unreadable text) sama seperti enkripsi, namun hal mendasar yang menjadi perbedaan dari hash adalah pesan yang telah acak tadi tidak dapat diubah kembali menjadi pesan yang seharusnya. Inilah mengapa hash disebut juga sebagai “one-way function“. Sebuah pesan yang dilewatkan ke fungsi hash akan menghasilkan keluaran yang disebut Message Authenticated Code (MAC). Dilihat dari sisi matematik, fungsi hash memetakan satu set data ke dalam sebuah set yang lebih kecil dan terbatas ukurannya.

Sifat-sifat fungsi hash satu-arah adalah sebagai berikut :

• Fungsi H dapat diterapkan pada blok data berukuran berapa saja.
• H menghasilkan nilai (h) dengan panjang tetap (fixed-length output).
• H(x) mudah dihitung untuk setiap nilai x yang diberikan.
• Untuk setiap h yang dihasilkan, tidak mungkin dikembalikan nilai x sedemikian sehingga H(x) = h. Itulah sebabnya fungsi H dikatakan fungsi hash satu-arah (one-way hash function).
• Untuk setiap x yang diberikan, tidak mungkin mencari y ≠ x sedemikian sehingga H(y) = H(x).
• Tidak mungkin mencari pasangan x dan y sedemikian sehingga H(x) = H(y). Masukan fungsi hash adalah blok pesan (M) dan keluaran dari hashing blok pesan sebelumnya, hi = H(Mi, hi – 1)

Skema fungsi hash ditunjukkan pada Gambar

Fungsi hash sering sekali digunakan di kehidupan sehari – hari. Beberapa aplikasi fungsi hash dalam kehidupan nyata bertujuan untuk :

1. Menjaga integritas data

Fungsi hash sangat peka terhadap perubahan 1 bit pada pesan. Pesan berubah 1 bit, nilai hash berubah sangat signifikan. Bandingkan nilai hash baru dengan nilai hash lama. Jika sama, pesan masih asli. Jika tidak sama, pesan sudah dimodifikasi

2. Menghemat waktu pengiriman

Misal untuk memverifikasi sebuah salinan arsip dengan arsip asli. Salinan dokumen berada di tempat yang jauh dari basisdata arsip asli daripada mengirim salinan arsip tersebut secara keseluruhan ke komputer pusat (yang membutuhkan waktu transmisi lama), lebih mangkus mengirimkan message digest-nya. Jika message digest salinan arsip sama dengan message digest arsip asli, berarti salinan arsip tersebut sama dengan arsip master. Contoh lainnya adalah dalam pengiriman hash 1 block pada bit torrent.

3. Menormalkan panjang data yang beraneka ragam.

Selain memendekan panjang data yang beragam, fungsi hash juga dapat digunakan untuk menormalkan atau menyeragamkan panjang data yang beragam. Misalkan password panjangnya bebas (minimal 8 karakter) Password disimpan dalam database di komputer host (server) untuk keperluan otentikasi pemakai komputer. Untuk menyeragamkan panjang field password di dalam database, password disimpan dalam bentuk nilai hash (panjang nilai hash tetap).

Beberapa contoh fungsi hash :

Dalam tulisan ini hanya akan diulas algoritma Secured Hash Algorithm (SHA) terutama SHA-1 dan Message Digest (MD5).

Message Digest 5 (MD5)

MD5 ialah fungsi hash kriptografi yang digunakan secara luar dengan nilai hash 128- bit. Pada standard internet (RFC 1321), MD5 telah dimanfaatkan secara bermacam-macam pada aplikasi keamanan dan MD5 juga umum digunakan untuk melakukan pengujian integritas sebuah file. MD5 adalah salah satu dari serangkaian algortima message digest yang didesain oleh Profesor Ronald Rivest dari MIT (Rivest, 1994).

Algoritma MD5 menerima sebuah input/pesan dengan panjang sebarang dan akan menghasilkan sebuah output dengan panjang tertentu, yaitu 128-bit, “fingerprint” atau “message digest” dari input. Secara komputasional, diduga sangat tidak mungkin untuk menghasilkan message digest yang sama dari dua pesan yang berbeda, ataupun mendapatkan pesan asli dari sebuah message digest. Algoritma MD5 dimaksudkan untuk aplikasi digital signature, dimana sebuah file besar “dikompres” secara terstruktur, sebelum dienkripsi dengan metode enkripsi yang ada, umumnya public-key cryptosystem seperti RSA. Algoritma MD5 didesain agar cepat pada komputer 32-bit. Selain itu, MD5 juga tidak memerlukan tabel substitusi yang besar sehingga algoritma ini dapat dikodekan secara ringkas.

Algoritma MD5 adalah pengembangan dari algoritma MD4. MD5 lebih lambat dari MD4, namun lebih “konservatif”dari segi desain. MD5 didesain karena MD4 dirasa sudah berada pada batas akan dapat dibobol dengan serangan cryptanalytic. MD5 mengorbankan sedikit kecepatan untuk keamanan yang jauh lebih baik. Banyak reviewer yang memberikan saran-saran terutama pada sisi optimisasi. Algoritma MD5 diberikan secara terbuka kepada publik untuk direview dan dapat juga diadopsi untuk dijadikan sebuah standar.

Saat kerja analitik menunjukkan bahwa pendahulu MD5, yaitu MD4 mulai tidak aman, MD5 kemudian didesain pada tahun 1991 sebagai pengganti dari MD4 (kelemahan MD4 ditemukan oleh Hans Dobbertin). Pada tahun 1993, den Boer dan Bosselaers memberikan awal, bahkan terbatas, hasil dari penemuan pseudo-collision dari fungsi kompresi MD5. Dua vektor inisialisasi berbeda I dan J dengan beda 4-bit diantara keduanya.

MD5compress(I,X) = MD5compress(J,X)

Pada tahun 1996 Dobbertin mengumumkan sebuah kerusakan pada fungsi kompresi MD5. Dikarenakan hal ini bukanlah serangan terhadap fungsi hash MD5 sepenuhnya, hal ini menyebabkan para pengguna kriptografi menganjurkan pengganti seperti WHIRLPOOL, SHA-1 atau RIPEMD-160. Ukuran dari hash 128-bit cukup kecil untuk terjadinya serangan brute force.. MD5CRK adalah proyek distribusi mulai Maret 2004 dengan tujuan untuk menunjukkan kelemahan dari MD5 dengan menemukan kerusakan kompresi menggunakan brute force attack. Bagaimanapun juga, MD5CRK berhenti pada tanggal 17 Agustus 2004,

saat kerusakan hash pada MD5 diumumkan oleh Xiaoyun Wang, Dengguo Feng, Xuejia Lai dan Hongbo Yu. Serangan analitik mereka dikabarkan hanya memerlukan satu jam dengan menggunakan IBM P690 cluster.

Pada tanggal 1 Maret 2005, Arjen Lenstra, Xiaoyun Wang, and Benne de Weger mendemontrasikan kunstruksi dari dua buah sertifikat X.509 dengan public key yang berbeda dan hash MD5 yang sama, hasil dari demontrasi menunjukkan adanya kerusakan. Konstruksi tersebut melibatkan private key untuk kedua public key tersebut. Dan beberapa hari setelahnya, Vlastimil Klima menjabarkan dan mengembangkan algortima, mampu membuat kerusakan Md5 dalam beberapa jam dengan menggunakan sebuah komputer notebook. Hal ini menyebabkan MD5 tidak bebas dari kerusakan.

Dikarenakan MD5 hanya menggunakan satu langkah pada data, jika dua buah awalan dengan hash yang sama dapat dibangun, sebuah akhiran yang umum dapat ditambahkan pada keduanya untuk membuat kerusakan lebih masuk akal. Dan dikarenakan teknik penemuan kerusakan mengijinkan pendahuluan kondisi hash menjadi arbitari tertentu, sebuah kerusakan dapat ditemukan dengan awalan apapun. Proses tersebut memerlukan pembangkitan dua buah file perusak sebagai file template, dengan menggunakan blok 128-byte dari tatanan data pada 64-byte batasan, file-file tersebut dapat mengubah dengan bebas dengan menggunakan algoritma penemuan kerusakan.

Saat ini dapat diketahui, dengan beberapa jam kerja, bagaimana proses pembangkitan kerusakan MD5. Yaitu dengan membangkitkan dua byte string dengan hash yang sama. Dikarenakan terdapat bilangan yang terbatas pada keluaran MD5 (2128), tetapi terdapat bilangan yang tak terbatas sebagai masukannya, hal ini harus dipahami sebelum kerusakan dapat ditimbulkan, tapi hal ini telah diyakini benar bahwa menemukannya adalah hal yang sulit.

Sebagai hasilnya bahwa hash MD5 dari informasi tertentu tidak dapat lagi mengenalinya secara berbeda. Jika ditunjukkan informasi dari sebuah public key, hash MD5 tidak mengenalinya secara berbeda jika terdapat public key selanjutnya yang mempunyai hash MD5 yang sama. Bagaimanapun juga, penyerangan tersebut memerlukan kemampuan untuk memilih kedua pesan kerusakan. Kedua pesan tersebut tidak dengan mudah untuk memberikan serangan preimage, menemukan pesan dengan hash MD5 yang sudah ditentukan, ataupun serangan preimage kedua, menemukan pesan dengan hash MD5 yang sama sebagai pesan yang diinginkan.

Hash MD5 lama, yang dibuat sebelum serangan-serangan tersebut diungkap, masih dinilai aman untuk saat ini. Khususnya pada digital signature lama masih dianggap layak pakai. Seorang user boleh saja tidak ingin membangkitkan atau mempercayai signature baru menggunakan MD5 jika masih ada kemungkinan kecil pada teks (kerusakan dilakukan dengan melibatkan pelompatan beberapa bit pada bagian 128-byte pada masukan hash) akan memberikan perubahan yang berarti. Penjaminan ini berdasar pada posisi saat ini dari kriptoanalisis. Situasi bisa saja berubah secara tiba-tiba, tetapi menemukan kerusakan dengan beberapa data yang belum ada adalah permasalahan yang lebih susah lagi, dan akan selalu butuh waktu untuk terjadinya sebuah transisi.

Kelebihan :

• Untuk memeriksa integritas file dalam berbagai situasi.
• Sebagai fungsi enkripsi sertifikat SSL
• Menghasilkan tanda tangan digital sepanjang 32 karakter, tanpa tergantung panjang input.
• Hasil output tidak akan sama untuk input yang berbeda.
• Sulit untuk dipecahkan walaupun dengan serangan brute force, tingkat keamanan

MD5 adalah salah satu yang terbaik, tidak bisa diubah kembali (Irreversible).

Kelemahan :

1. Serangan Collision

Seperti telah dibahas di atas, proses MD5 akan menghasilkan keluaran yang ukurannya selalu 128 bit. Ini berarti bahwa untuk kemungkinan panjang masukan yang tak terhingga, hanya akan ada 2128 kemungkinan nilai hash yang akan dihasilkan MD5. Bahkan untuk nilai kosong :

X = “ ”

Dalam kasus MD5 (128 bit), maka dari itu, jumlah percobaan yang diperlukan bukan 2128 kali, namun hanya setengah pangkatnya dari ini (264 kali). Jumlah percobaan 2n/2 ini disebut birthday bound dan merupakan batasan bawah keamanan ideal dari fungsi kriptografik secara probabilitas

2. Kriptanalisis lebih lanjut tehadap MD5

Dalam kasus MD5, kriptanalisis lebih lanjut menunjukkan bahwa MD5 jauh lebih lemah daripada probabilitas teoritis ini. Secepat tahun 1996, sekitar 5 tahun setelah peluncurannya, collision sudah mampu ditemukan pada sistem kompresi MD5 oleh H.Dobbertin. Walaupun collision yang ditemukan ini adalah pseudocollision dalam arti suatu collision dengan nilai awal tertentu dan merupakan suatu peristiwa terisolasi, peringatan kemudian dikeluarkan untuk tidak mengandalkan MD5 untuk kegunaankegunaan yang memerlukan ketahanan terhadap collision.

Masukan yang sama sekali berbeda isinya pun dapat dengan relatif mudah disesuaikan sehingga nilai hash-nya sama dengan suatu pesan lain, asalkan terdapat potongan dari kedua pesan itu yang collision-nya sudah ditemukan.

3. Preimage Attack

Preimage attack merupakan serangan terhadap fungsi hash yang menyerupai collision attack, namun dengan tujuan mencari masukan m2 apabila masukan m1 sudah diketahui, sehingga f(m1) = f(m2). Tidak seperti collision attack di mana tujuannya adalah mencari kedua masukan m1 dan m2. Serangan preimage pada umumnya lebih kompleks dibandingkan serangan collision dan tidak jarang alternatif satu-satunya untuk melakukan serangan ini adalah dengan menggunakan brute force.

4. Proses perubahan data asli menjadi MD5 perlu waktu relatif lama (resource hardware)

Perbandingan MD5 dan MD2

1. Pada MD2 ukuran padding byte paling sedikit 1 byte sampai 16 byte, sedangkan MD5 antara 1 sampai 512 byte.
2. Panjang pesan (dalam satuan bit) kongruen dengan 448 modulo 512, sedangkan MD2, panjang pesan kongruen dengan 0 modulo 16.
3. Penambahan checksum pada MD2 sebanyak 16 byte, pada MD5 sebenyak 64 bit dari pesan semula.
4. Inisialisasi penyangga pada MD2 dengan nilai 0 (nol), sedangkan MD5 diinisialisasi dengan nilai-nilai dalam HEX.

Perbandingan MD5 dan MD4

1. MD5 memiliki empat putaran, sedangkan MD4 hanya tiga. Akibatnya, fungsi kompresi MD5 meliputi 64 langkah, sedangkan fungsi kompresi MD4 memiliki 48 langkah.
2. Setiap langkah MD5 memiliki konstanta tambahan yang unik, sedangkan setiap putaran dari MD4 menggunakan konstan yang tetap.
3. Fungsi G di putaran kedua MD5 kurang simetris daripada fungsi G MD4.
4. Setiap langkah MD5 menambahkan hasil dari langkah sebelumnya, yang tidak terjadi di MD4. Tujuan modifikasi ini adalah untuk menghasilkan avalanche effect yang lebih cepat.
5. Pada MD5, urutan input words diakses pada putaran kedua dan ketiga yang kurang mirip satu sama lain daripada yang terjadi di MD4.
6. Diklaim bahwa di MD5, “jumlah pergeseran dalam setiap putaran telah kira-kira dioptimalkan, untuk hasil ‘avalanche effect‘ yang lebih cepat”. Selain itu, pergeseran bekerja di masing-masing putaran MD5 yang berbeda, yang tidak terjadi di MD4.

Cara kerja Message Digest 5

Misal kita memiliki sebuah pesan dengan panjang b-bit sebagai input, dan kita ingin mendapatkan message digest-nya. Disini b adalah pesan dengan panjang sebarang. Panjang sebuah pesan tentu saja tidak negatif, tapi masih mungkin untuk nol. Panjang tersebut tidak harus kelipatan dari delapan dan boleh juga sangat panjang. Misal bit dari pesan tersebut ditulis sebagai

m_0 m_1 …. m_{b-1}

Preprocessing dimulai dengan penambahan padding bits sebagai berikut :

1. Pesan tersebut akan diberikan tambahan bit sehingga panjangnya, dalam bit, sama dengan 448, modulo 512. Penambahan selalu dilakukan, walaupun panjang dari pesan sudah sama dengan 448, modulo 512. Penambahan bit adalah sebagai berikut: sebuah bit '1' ditambahkan diikuti dengan bit '0' sebanyak yang diperlukan sehinggan panjangnya menjadi 448, modulo 512. Minimal dilakukan penambahan sebanyak satu bit dan maksimal sebanyak 512 bit.
2. 64-bit ditambahkan untuk merepresentasikan panjang sebenarnya dari pesan b pada hasil dari penambahan sebelumnya. Jika panjang pesan asli lebih dari 264 bit maka hanya 64 lower order bit yang dimasukkan. Lower order word untuk panjang pesan asli dimasukkan sebelum high-order word. Setelah langkah kedua ini, maka panjang dari hasilnya adalah kelipatan dari 512 bit. Atau jika dalam word, maka panjangnya akan sama dengan kelipatan dari 16 word (32-bit). Maka hasil dari dua langkah di atas kita notasikan sebagai M[0 …. N-1] dengan N adalah kelipatan dari 16. 

Setelah padding, pesan terdiri dari n word M[0 … n - 1] dimana n adalah kelipatan 16. Langkah berikutnya dalam preprocessing adalah menyiapkan MD buffer sebesar 4 word : 

( A, B, C, D )

dimana A merupakan lower order word. Buffer diberi nilai awal sebagai berikut (nilai dalam hexadecimal dimulai dengan lower order byte).

A: 01 23 45 67
B : 89 ab cd ef
C : fe dc ba 98
D : 76 54 32 10

Proses hashing dilakukan per blok, dengan setiap blok melalui 4 putaran. Proses hashing menggunakan 4 fungsi F, G, H, dan I yang masing-masing mempunyai input 3 word dan output 1 word :

F(X,Y,Z) = (X ^ Y) v (~X ^ Z)
G(X,Y,Z) = (X ^ Z) v (Y ^ ~Z)
H(X,Y,Z) = X xor Y xor Z
I(X,Y,Z) = Y xor (X ^ ~Z)

dimana ^ adalah bitwise and, v adalah bitwise or, xor adalah bitwise exclusive or, dan ~ adalah bitwise not (one's complement). 

Pada setiap posis bit, F berperilaku sebagai : if X then Y else Z. Penting, dan menarik, untuk dicatat bahwa jika setiap bit dari X, Y dan Z independent dan tidak bias, maka setiap bit dari F akan independen dan tidak bisa juga.

Fungsi G, H dan I juga serupa dengan fungsi F, beroperasi pada bitwise parallel untuk menghasilkan output dari input X, Y dan Z. Serta dalam hal jika X, Y dan Z independent dan tidak bias, maka G, H dan I juga independent dan tidak bias.

Tahap ini menggunakan tabel T[1 …. 64] yang dibentuk dari fungsi sinus. Misal T[i] adalah elemen ke-i dari tabel, maka T[i] didefinisikan sebagai 4294967296 * abs(sin(i)), dimana I dalam radian.

Selanjutnya, lakukan algoritma berikut:

/* Process each 16-word block. */

For i = 0 to N/16-1 do

  /* Copy block i into X. */

  For j = 0 to 15 do

    Set X[j] to M[i*16+j].

  end /* of loop on j */

  /* Save A as AA, B as BB, C as CC, and D as DD. */

  AA = A

  BB = B

  CC = C

  DD = D

  /* Round 1. */

  /* Let [abcd k s i] denote the operation

    a = b + ((a + F(b,c,d) + X[k] + T[i]) <<< s). */

  /* Do the following 16 operations. */

  [ABCD 0 7 1] [DABC 1 12 2] [CDAB 2 17 3] [BCDA 3 22 4]

  [ABCD 4 7 5] [DABC 5 12 6] [CDAB 6 17 7] [BCDA 7 22 8]

  [ABCD 8 7 9] [DABC 9 12 10] [CDAB 10 17 11] [BCDA 11 22 12]

  [ABCD 12 7 13] [DABC 13 12 14] [CDAB 14 17 15] [BCDA 15 22 16]

  /* Round 2. */

  /* Let [abcd k s i] denote the operation

    a = b + ((a + G(b,c,d) + X[k] + T[i]) <<< s). */

  /* Do the following 16 operations. */

  [ABCD 1 5 17] [DABC 6 9 18] [CDAB 11 14 19] [BCDA 0 20 20]

  [ABCD 5 5 21] [DABC 10 9 22] [CDAB 15 14 23] [BCDA 4 20 24]

  [ABCD 9 5 25] [DABC 14 9 26] [CDAB 3 14 27] [BCDA 8 20 28]

  [ABCD 13 5 29] [DABC 2 9 30] [CDAB 7 14 31] [BCDA 12 20 32]

  /* Round 3. */

  /* Let [abcd k s t] denote the operation

    a = b + ((a + H(b,c,d) + X[k] + T[i]) <<< s). */

  /* Do the following 16 operations. */

  [ABCD 5 4 33] [DABC 8 11 34] [CDAB 11 16 35] [BCDA 14 23 36]

  [ABCD 1 4 37] [DABC 4 11 38] [CDAB 7 16 39] [BCDA 10 23 40]

  [ABCD 13 4 41] [DABC 0 11 42] [CDAB 3 16 43] [BCDA 6 23 44]

  [ABCD 9 4 45] [DABC 12 11 46] [CDAB 15 16 47] [BCDA 2 23 48]

  /* Round 4. */

  /* Let [abcd k s t] denote the operation

    a = b + ((a + I(b,c,d) + X[k] + T[i]) <<< s). */

  /* Do the following 16 operations. */

  [ABCD 0 6 49] [DABC 7 10 50] [CDAB 14 15 51] [BCDA 5 21 52]

  [ABCD 12 6 53] [DABC 3 10 54] [CDAB 10 15 55] [BCDA 1 21 56]

  [ABCD 8 6 57] [DABC 15 10 58] [CDAB 6 15 59] [BCDA 13 21 60]

  [ABCD 4 6 61] [DABC 11 10 62] [CDAB 2 15 63] [BCDA 9 21 64]

  /* Then perform the following additions. (That is increment each of the four registers by the value it had before this block was started.) */

  A = A + AA

  B = B + BB

  C = C + CC

  D = D + DD

end /* of loop on i */

Output

Message digest dari pesan didapat dengan melakukan penggabungan antara A, B, C dan D
dengan urutan A berada paling kiri, low-order byte, sampai D berada paling kanan, highorder
byte. Proses MD5 sudah selesai.

Kriptanalisis MD5

MD5 dipublikasikan pada tahun 1992 sebagai Informational RFC. Sejak saat itu, MD5 sudah dipelajari secara ekstensif dan serangan-serangan baru terhadap kriptografi pun sudah banyak ditemukan. Algoritma message digest didesain untuk tahan terhadap collision, pre-image dan second pre-image. Selain itu, algoritma ini juga digunakan untuk sharing informasi/data rahasia untuk message authentication pada HMAC.

MD5 tidak lagi dapat digunakan dimana ketahanan terhadap collisions sangat diperlukan, seperti digital signature. Namun, untuk hal lain yang tidak memerlukan kerahasiaan, MD5 masih cukup baik untuk digunakan, untuk checksum misalnya. Karena MD5 tidak boleh digunakan untuk digital signature, desain protokol baru untuk digital signature seharusnya tidak mengadopsi MD5.

1. Ketahanan terhadap collisions.

Pseudo-collisions pada fungsi kompresi MD5 pertama kali ditemukan pada tahun 1993. Pada 1996, Dobbertin mendemonstrasikan pasangan fungsi kompresi MD5 yang mengalami collision. Paper pertama yang mendemonstrasikan collision pada MD5 diterbitkan pada tahun 2004. Teknik penyerangan terhadap MD5 dijelaskan secara mendetail pada publikasi EUROCRYPT 2005. Sejak saat itu, banyak hasil penelitian mempublikasikan peningkatan collision attack pada MD5. Penyerangan yang ditunjukkan oleh Klima pada tahun 2006, dapat menemukan collision pada MD5 dalam waktu satu menit dengan menggunakan notebook dengan spesifikasi standar, Intel Pentium, 1.6GHz. Steven, pada tahun 2007, bahkan mengklaim bahwa beliau mampu menemukan collisions dalam waktu 10 detik atau kurang dengan prosesor 2.6GHz. Steven et al., 2007, menunjukkan bahwa MD5 collisions attack juga berhasil dilakukan pada X.509 certificates. MD5 collisions attack juga dapat dilakukan pada protokol password-based challenge-and-response seperti APOP, Authenticate Post Office Protocol seperti ditunjukkan Leurent pada tahun 2007. Pada kenyataannya, masih banyak penyerangan halus pada MD5 untuk meningkatkan waktu terjadinya collisions telah dipublikasikan belakangan ini. Hal ini menunjukkan bahwa MD5 sudah tidak cocok lagi digunakan pada situasi dimana diperlukan ketahanan terhadap collisions seperti digital signature.

2. Ketahanan terhadap Pre-Image dan Second Pre-Image

Walaupun hasil terbaik dapat menemikan serangan pre-image pada MD5 lebih baik dari pada exhaustive search, seperti ditunjukkan Sasaki dan Aoki pada tahun 2009, namun compleksitas 2^123.4 dirasa masih cukup tinggi.

Secured Hash Algorithm (SHA-1)

NIST (National Institute of Standards and Technology) bersama NSA (National Security Agency) mendesain SHA untuk digunakan sebagai komponen Digital Signature Standard (DSS). Standar hash adalah Secure Hash Standard (SHS) dengan SHA sebagai algoritma yang digunakan. Dapat disimpulkan SHS adalah standar sedangkan SHA adalah algoritma. Standar menetapkan SHA yang diperlukan untuk menjamin keamanan DSA. SHA dibuat berdasarkan rancangan yang serupa dengan MD4 yang dibuat oleh Prof. Ronald L. Rivest dari MIT. Algoritma SHA menerima masukan berupa pesan dengan ukuran maksimum 264 bit (2.147.483.648 gigabyte) dan menghasilkan message digest yang panjangnya 160 bit, lebih panjang dari message digest dengan algoritma MD5 yang hanya 128 bit 

MD ini kemudian dimasukkan ke dalam DSA, yang menghitung tanda tangan digital untuk pesan tersebut. Penandatanganan MD (dan bukannya penandatanganan secara langsung) sering kali meningkatkan efisiensi proses, karena MD biasanya jauh lebih kecil dibanding pesan aslinya. MD pesan yang sama seharusnya dapat diperoleh oleh pemeriksa tanda tangan ketika menerima pesan dari pengirim dengan cara memasukkan pesan tersebut ke fungsi hash SHA. SHA dikatakan aman karena didesain supaya secara matematis tidak dimungkinkan untuk mendapatkan pesan aslinya bila diberikan hashnya atau tidak mungkin mendapatkan dua pesan yang berbeda yang menghasikan MD yang sama (secara komputasi tidak mungkin menemukan pesan yang berkoresponden dengan message digest yang diberikan). 

Algoritma SHA-1 merupakan algoritma yang memiliki prinsip berdasarkan MD4, sebagaimana keluarga SHA lainnya. Dalam gambar di bawah ini, dapat dilihat bagaimana hubungan antara algoritma-algoritma tersebut. 

Ketiga algoritma SHA adalah struktur yang berbeda dan unggul seperti SHA-0, SHA-1, dan SHA-2. SHA-2 menggunakan algoritma identik dengan variabel digest ukuran yang terkenal sebagai SHA-224, SHA-256, SHA-384, dan SHA-512. Algoritmanya mengambil pesan yang panjangnya kurang dari 264 bit dan menghasilkan message digest 160-bit. Algoritma ini lebih lambat daripada MD5, namun message digest yang lebih besar membuatnya semakin aman dari brute force collision dan serangan inversi.

SHA-1 sendiri memiliki proses yang sangat mirip dengan proses yang dilakukan oleh SHA- 0, bedanya hanyalah di fungsi kompresinya (message expansion), yaitu adanya operasi bit shift sebesar 1. Gambaran umum pembuatan message digest dengan algoritma SHA-1 diperlihatkan pada gambar di bawah ini.

Cara Kerja SHA-1

Secara umum, tahap pembuatan message digest dengan SHA-1 adalah sebagai berikut :

A. Preprocessing

Pada tahap preprocessing ini terdiri dari beberapa langkah, yaitu :

1. Penambahan bit-bit pengganjal (padding bits). Pesan ditambah dengan sejumlah bit pengganjal sedemikian sehingga panjang pesan (dalam satuan bit) kongruen dengan 448 modulo 512. Ini berarti panjang pesan setelah ditambahi bit-bit pengganjal adalah 64 bit kurang dari kelipatan 512. Panjang bit-bit pengganjal haruslah berada antara 1 hingga 512 bit. Hal tersebut menyebabkan pesan dengan panjang 448 tetap harus ditambahkan bit penyangga sehingga panjangnya akan menjadi 960 bit. Bit-bit pengganjal sendiri terdiri dari sebuah bit 1 diikuti sisanya dengan bit 0.
2. Penambahan nilai panjang pesan semula. Pesan yang telah diberi padding bits selanjutnya ditambah lagi dengan 64 bit yang menyatakan panjang pesan semula. Setelah ditambah dengan 64 bit, panjang pesan akan menjadi kelipatan 512 bit.
3. Inisialisasi penyangga (buffer) MD. Algoritma SHA-1 dalam operasinya membutuhkan lima buah buffer yang masingmasing besarnya 32 bit sehingga nantinya hasil akhirnya akan menjadi 160 bit. Kelima buffer tersebut dalam operasi SHA-1 ini akan berperan untuk menyimpan hasil antar putaran sekaligus untuk menyimpan hasil akhir. Kelima buffer tersebut memiliki nama A, B, C, D ,dan E. Buffer-buffer tersebut harus diinisialisasi dengan nilai-nilai sebagai berikut (dalam notasi heksadesimal):

A = 67452301
B = EFCDAB89
C = 98BADCFE
D = 10325476
E = C3D2E1F0

B. Hashing 

Proses hashing dilakukan per blok dengan besar 512 bit tiap bloknya. Dalam pengolahan ini terdapat 4 putaran yang tiap putarannya dilakukan sebanyak 20 kali. Tiap putaran memiliki proses yang berbeda – beda. Sebelum putaran pertama dilakukan inisialisasi 5 buah variable dengan besar 32 bit yang menampung buffer inisialisasi.

Pesan dibagi menjadi L buah blok yang masing-masing panjangnya 512 bit. Setiap blok 512-bit diproses bersama dengan buffer MD menjadi keluaran 128-bit. Proses tersebut disebut proses HSHA . Proses HSHA terdiri dari 80 buah putaran dengan setiap putarannya dilakukan hal seperti gambar di atas.

Pada gambar, Yq menyatakan blok 512-bit ke-q dari pesan yang telah ditambah padding bits dan tambahan 64 bit nilai panjang pesan semula. MDq adalah nilai message digest 160-bit dari proses HSHA ke-q. Pada awal proses, MDq berisi nilai inisialisasi buffer MD. Setiap putaran menggunakan operasi dasar yang sama

(dinyatakan sebagai fungsi f).

Operasi dasar SHA yang diperlihatkan pada gambar diatas dapat ditulis dengan persamaan sebagai berikut:

a, b, c, d, e = (CLS₅(a) + f_t(b, c, d) + e + W_t + K_t), a, CLS₃₀(b), c, d

yang dalam hal ini,

a, b, c, d, e = lima buah peubah penyangga 32-bit (berisi nilai penyangga A, B, C, D, E)  

 t                 = putaran, 0 ≤ t ≤ 79 

 f_t                = fungsi logika
CLS_s          = circular left shift sebanyak s bit
W_t         = word 32-bit yang diturunkan dari blok 512bit yang sedang diproses K_t              = konstanta penambah+                = operasi penjumlahan modulo 232

atau dapat dinyatakan dalam kode program berikut:

For t := 0 to 79 do

  Tmp := (a <<<5) + ft(b,c,d) + e + Wt + Kt)

  e := d

  d := c

  c := b <<< 30

  b := a

  a := tmp

endfor

yang dalam hal ini, <<< menyatakan operasi pergeseran circular left shift. Konstanta penambah dalam operasi HSHA memiliki nilai berikut untuk masing-masing putaran, yaitu :

Putaran 0 ≤ t ≤ 19   Kt = 5A827999
Putaran 20 ≤ t ≤ 39 Kt = 6ED9EBA1
Putaran 40 ≤ t ≤ 59 Kt = 8F1BBCDC
Putaran 60 ≤ t ≤ 79 Kt = CA62C1D6

Fungsi fi adalah fungsi logika yang melakukan operasi bitwise. Operasi yang dilakukan dapat dilihat dalam tabel berikut ini: 

Sementara itu, nilai W0 sampai W15 berasal dari 16 word pada blok pesan yang sedang diproses sehingga masing-masing variabel W akan memiliki besar 32-bit, sedangkan nilai Wt berikutnya didapatkan dari persamaan

Wt = W_{t – 16} xor W_{t – 14} xor W_{t – 8} xor W_{t – 3}

Fungsi di atas disebut juga sebagai fungsi kompresi dari SHA-1 karena fungsi tersebut berfungsi untuk melibatkan pesan masukan ke dalam proses putaran SHA-1. Selain itu fungsi di atas juga sering disebut sebagai fungsi message expansion. 

Setelah putaran ke-79, a, b, c, d, dan e dijumlahkan ke A, B ,C, D, dan E dan selanjutnya algoritma memproses blok data berikutnya. Keluaran akhir dari algoritma SHA-1 adalah hasil penyambungan bit-bit di dalam A, B, C, D, dan E.

Kriptanalisis SHA-1

Sejak pertama kali diperkenalkan pada tahun 1995, para peneliti mulai meneliti ketahanan metode hash ini dari penyerangan. Baik itu pre-image attack maupun collision attack. Untuk pre-image attack secara brute force terhadap SHA-1, yang menghasilkan message digest sepanjang 160 bits, perlu melakukan pencarian terhadap 2160 kemunginan yang ada. Sedangkan untuk collision attack, memerlukan waktu rata-rata sebesar 280 dengan menggunakan birthday attack.

1. Ketahanan terhadap collision

Seperti yang terjadi pada MD5, collision attack pada SHA-1 sudah banyak dibicarakan dan diteliti. Seperti pada awal tahun 2005 misalnya, Rijmen dan Oswald mempublikasikan penyerangan terhadap metode SHA-1 yang disederhanakan, dengan hanya menggunakan 53 round dari 80 round yang ada, dapat menemukan collision dengan kemungkinan lebih kecil dari 280, yaitu sekitar 271. Pada Februari 2005, Wang, et al, menemukan serangan pada full version SHA-1, 80 round, yang hanya memerlukan 269 operasi. Pada 17 agustus di tahun yang sama, Wang, et al, kembali meningkatkan kualitas algoritma penyerangannya sehingga mampu menurunkan kompleksitasnya menjadi 263 yang diverifikasi dan dijelaskan oleh Martin pada tahun 2007. Cannière dan Rechberger, pada tahun 2006, meningkatkan kualitas algoritma penyerangan terhadap SHA-1. Dua block yang mengalami collision ditemukan pada penyederhanaan SHA-1 dengan 64-round, hanya dengan melakukan evaluasi sebanya 235 kali. Metode ini dikembangkan menjadi 73 round oleh Grechnikov pada tahun 2010. Pada tahun 2008, Manuel menemukan penyerangan, theoretical attack, terhadap SHA-1 full version dengan kompleksitas antara 251 - 257. Hasil ini, sementara di claim sebagai

hasil teroptimal dari collision attack terhadapt SHA-1. Termasuk proyek HashClash dari Marc Stevent yang baru mencapai kompleksitas 257,5.

2. Ketahanan terhadap pre-image

Sangat jarang orang meneliti pre-image attack. Mungkin karena MD5 pun, yang collision attack-nya hanya beberapa detik masih sulit untuk melakukan pre-image attack. Selain itu, sepertinya collision merupakan topik yang lebih menarik dari pada pre-image attack. Karena, biasanya, pada pengimplementasian SHA, digital signature misalnya, data aslinya sendiri masih dikirimkan bersama dengan message digest-nya. Tidak seperti enkripsi yang menyembunyikan pesan aslinya di dalam ciphertext.

Implementasi Fungsi Hash MD5 dan SHA-1 pada Javascript

Silahkan unduh implementasi MD5 dan SHA-1 pada tautan dibawah ini:

https://dl.dropbox.com/u/10900040/MD5.htm

https://dl.dropbox.com/u/10900040/SHA.htm