KOMPLEKSITAS WAKTU UNTUK ALGORITMA MD5

  KOMPLEKSITAS  WAKTU  UNTUK  ALGORITMA  MD5     Yudi  Prayudi      

Abstraksi    

Integritas   bukti   digital   adalah   salah   satu   issue   penting   dalam   aktivitas   digital   forensics.  Secara  umum,  bukti  digital  tidak  boleh  mengalami  perubahan  apapun  dalam   setiap   tahap   digital   forensics.     Dalam   hal   ini,   fungsi   hash   secara   umum   dalam   digital   forensics  telah  digunakan  untuk  kepentingan  menjaga  integritas  bukti  digital.    Sebagai   sebuah   fungsi   matematis   yang   kemudian   diterjemahkan   dalam   sebuah   algoritma,   ternyata   penggunaan   fungsi   hash   juga   memiliki   sejumlah   issue   seputar   kompleksitas.     Berdasarkan  cara  kerja  dan  karakteristik  algoritma  MD5  ternyata  kompleksitas  waktu   dari  algoritma  tersebut  adalah  Big  O  (n)  atau  fungsi  asimtotik  linier.  Dengan  demikian   secara  umum  bertambahnya  input  (panjang  message  yang  akan  dicarikan  nilai  fungsi   hash  MD5)  akan  sebanding  pula  dengan  bertambahnya  waktu  secara  linier  

 

Keyword  :  Integritas,  Bukti  Digital,  Digital  Forensics,  Fungsi  Hash  MD5,  Kompleksitas   Waktu  

    1. Pengantar     Tema   dalam   usulan   penelitian   disertasi   adalah   tentang   penanganan   barang   bukti   digital   dalam   sebuah   aktivitas   digital   forensics.   Permasalahan   yang   diangkat   adalah   tentang   bagaimana   menerapkan   penanganan   barang   bukti   yang   lazimnya   dilakukan   secara   konvensional,   kemudian   diambil   analoginya   untuk   diterapkan   dalam   lingkup   aktivitas   digital.   Fokus   penelitian   adalah   pada   permasalahan   digital   chain   of   custody,   yaitu   sebuah   prosedur   untuk   secara   kronologis   melakukan   pendokumentasian   terhadap   barang   bukti.       Salah   satu   issue   penting   pada   bidang   digital   forensics   adalah   bagaimana   menjaga   authenticity   and   integrity   bukti   digital.   Authenticity   menurut  (Cohen,  2013)  adalah  kemampuan  untuk  mempertahankan  identitas   awal   ketika   bukti   digital   tersebut   pertama   kali   didapat   serta   menjaga   integritasnya   dalam   setiap   tahapan   proses   digital   forensics.     Sementara   integrity   menurut   Vanstode   dalam   (Cosic   &   Baca,   2010),   adalah   sebuah   property   dimana   data   digital   tidak   mengalami   perubahan   oleh   pihak   yang   tidak   memiliki   wewenang   untuk   melakukan   perubahan.   Perubahan   dan   kontak   kepada   bukti   digital   hanya   dilakukan   oleh   mereka   yang   memiliki   otorisasi   saja.     Authenticity   and   integrity   dari   bukti   digital   menjamin   bahwa   eksplorasi,  analisis  serta  informasi  yang  dipresentasikan  adalah  lengkap  dan   tidak   mengalami   perubahan   dari   sejak   pertama   kali   ditemukan   sampai   akhirnya  digunakan  dalam  proses  persidangan.     Makalah   ini   akan   membahas   tentang   bagaimana   penerapan   fungsi   hash  yang  lazim  digunakan  dalam  lingkup  digital  forensics  sebagai  prosedur  

2   Komputasi  dan  Kompleksitas  –  Program  Doktor  Ilmu  Komputer  UGM     standard   untuk   menjaga   integritas   bukti   digital.   Sebagai   sebuah   fungsi   matematis   yang   kemudian   diterjemahkan   dalam   sebuah   algoritma,   ternyata   penggunaan   fungsi   hash   juga   memiliki   sejumlah   issue   seputar   kompleksitas.   Untuk   itu   pada   bagian   lain   dari   makalah   ini   akan   dibahas   issue   seputar   kompleksitas  algoritma  dari  fungsi  hash,  khususnya  untuk  algoritma  MD5.     2. Barang  Bukti  Digital     Salah   satu   faktor   penting   dalam   proses   investigasi   adalah   hal   terkait   dengan   barang   bukti.   Dalam   hal   ini   terdapat   dua   istilah   yang   hampir   sama,   yaitu   barang   bukti   elektronik   dan   barang   bukti   digital.   Barang   bukti   elektronik   adalah   bersifat   fisik   dan   dapat   dikenali   secara   visual   (komputer,   handphone,   camera,   CD,   harddisk   dll)   sementara   barang   bukti   digital   adalah   barang  bukti  yang  diekstrak  atau  di-­‐recover  dari  barang  bukti  elektronik  (file,   email,  sms,  image,  video,  log,  text).  Secara  khusus  terdapat  beberapa  definisi   sederhana  dari  bukti  digital,  yaitu  :     • any   information   of   probative   value   that   is   either   stored   or   transmitted   in   digital  form  (Richter  &  Kuntze,  2010)   • information  stored  or  transmitted  in  binary  form  that  may  be  relied  upon  in   court.(Turner,  2005)     Menurut   Matthew   Braid   dalam   (Richter   &   Kuntze,   2010),   agar   setiap   barang   bukti   dapat   digunakan   dan   mendukung   proses   hukum,   maka   harus   memenuhi   lima   kriteria   yaitu   :   admissible,   authentic,   complete,   reliable   dan   believable.   Sementara   (Schatz,   2007)   menyebutkan   dua   aspek   dasar   agar   barang  bukti  dapat  mendukung  proses  hukum,  yaitu  aspek  hokum  itu  sendiri   dengan   kriteria:     authentic,   accurate,   complete,   serta   aspek   teknis   dengan   kriteria  :  chain  of  evidence,  transparent,  explainable,  accurate.       Berbeda   dengan   barang   bukti   konvensional,   barang   bukti   digital   memiliki   sejumlah   karakteristik,   yaitu   :   mudah   untuk   diduplikasi   dan   ditransmisikan,   sangat   rentan   untuk   dimodifikasi   dan   dihilangkan,   mudah   terkontaminasi   oleh   data   baru   serta   bersifat   time   sensitive.   Barang   bukti   digital  juga  sangat  dimungkinkan  bersifat  lintas  negara  dan  yuridiksi  hukum.     Berbeda   dengan   barang   bukti   fisik   pada   umumnya,   barang   bukti   digital  akan  sangat  bergantung  dari  proses  interpretasi  terhadap  kontennya.   Karena   itu,   integritas   dari   barang   bukti   serta   kemampuan   dari   expert   dalam   menginterpretasikannya   akan   berpengaruh   terhadap   pemilahan   dokumen-­‐ dokumen  digital  yang  tersedia  untuk  dijadikan  sebagai  barang  bukti  (Schatz,   2007).   Sementara   itu   dari   aspek   hukum,   setiap   negara   memiliki   ketentuan   tersendiri   terhadap   jenis,   karakter   dan   prosedur   barang   bukti   digital   agar   bisa   diterima   untuk   proses   hukum   /   persidangan.   Karenanya   setiap   digital   investigator   /   forensics   analyst   harus   memahami   dengan   baik   peraturan   hukum   dan   perundangan   yang   terkait   dengan   barang   bukti   digital   serta   proses   hukum   yang   melibatkan   barang   bukti   digital.   (Boddington,   Hobbs,   &   Mann,   2008).   Dalam   hal   ini,   untuk   wilayah   hukum   Indonesia,   barang   bukti   digital   telah   diatur   dalam   Undang-­‐Undang   No.   11   tahun   2008   tentang   Informasi  dan  Transaksi  Elektronik  (UU  ITE).  

      3. Fungsi  Hash  Untuk  Integritas  Barang  Bukti  Digital   Salah   satu   issue   dalam   chain  of  custody   adalah   masalah   integritas   data.   Dalam  hal  ini  menurut  Vanstode  dalam  (Cosic  &  Baca,  2010),  digital  integrity   adalah  sebuah  property  dimana  data  digital  tidak  mengalami  perubahan  oleh   pihak   yang   tidak   memiliki   wewenang   otorisasi   melakukan   perubahan.   Perubahan   dan   kontak   kepada   barang   bukti   digital   hanya   dilakukan   oleh   mereka   yang   memiliki   otorisasi   saja.   Integritas   barang   bukti   digital   menjamin   bahwa   informasi   yang   dipresentasikan   adalah   lengkap   dan   tidak   mengalami   perubahan  dari  sejak  pertama  kali  ditemukan  sampai  akhir  digunakan  dalam   proses  persidangan.     Pada   barang   bukti   fisik/   konvensional,   perubahan   terhadap   barang   bukti   dapat   dengan   mudah   di   kontrol   dan   diawasi.   Namun   demikian   tidak   mudah   melakukan   hal   itu   pada   barang   bukti   digital   (Saleem,   Popov,   &   Dahman,   2011).   Penerapan   kunci   hash   (MD5,   SHA1)   adalah   metode   standar   sebagai   solusi   melakukan   kontrol   terhadap   integritas   dan   kredibilitas   bukti   digital.   Dalam   hal   ini   setiap   orang   yang   menggunakan   sebuah   file,   untuk   memastikan   bahwa   dua   buah   file   adalah   sama   dilihat   dari   nilai   kunci   hash   yang  sama  antara  kedua  file  tersebut.  Hampir  setiap  tools  untuk  imaging  atau   eksplorasi  bukti  digital  akan  menyediakan  fasilitas  untuk  menghasilkan  serta   mendeteksi  kunci  hash.   Dalam   bidang   digital   forensics,   menurut   (Buncle,   2009)   fungsi   hash   MD5   maupun   SHA-­‐1   digunakan   sebagai   ‘digital   fingerprint’   dari   suatu   rangkaian   bit   data.   Fungsi   hash   secara   umum   dalam   digital   forensics   digunakan   untuk   kepentingan   deteksi   error   selama   proses   image/duplikasi   data,   file   atau   rangkaian   bit   data   lainnya   yang   termasuk   dalam   bukti   digital.   Dengan   demikian,   salah   satu   prosedur   dalam   investigasi   digital,   setiap   penanganan   barang   bukti   digital   harus   selalu   dicatat   dan   diperhatikan   nilai   dari   fungsi   hash   yang   menyertai   bukti   digital   tersebut.   Perubahan   atas   nilai   fungsi   hash   dapat   diindikasi   sebagai   adanya   perubahan   konten   yang   berdampak  pada  hilangnya  sifat  integritas  dari  bukti  digital  tersebut.     Dalam  konteks  bukti  digital,  setiap  file  memiliki  nilai  hash  yang  berbeda,   maka   fungsi   hash   dimanfaatkan   untuk   verifikasi   integritas   file.   Yang   dimaksud  dengan  intergritas  file  yaitu  keaslian  file,  apakah  file  sudah  diubah   atau   belum.   Bila   sebuah   file   berubah   walaupun   satu   bit   saja,   maka   nilai   hashnya   akan   berbeda   sehingga   orang   bisa   menyadari   bahwa   file   tersebut   sudah  tidak  asli  lagi.     4. Mengenal  MD-­‐5   MD5   (Message-­‐Digest   algortihm   5)   sebenarnya   adalah   merupakan   algoritma  yang  banyak  gunakan  dalam  bidang  kriptografi.  Dalam  hal  ini  MD5   adalah   sebuah   fungsi   hash   kriptografik   yang   digunakan   secara   luas   dengan   hash   value   128-­‐bit.   Pada   standart   Internet   (RFC   1321),   MD5   telah   dimanfaatkan   untuk   berbagai   jenis   aplikasi   keamanan,   selain   itu   MD5   juga   umum   digunakan   untuk   melakukan   pengujian   integritas   sebuah   file.   MD5      

[Type  text]  

   

 

4   Komputasi  dan  Kompleksitas  –  Program  Doktor  Ilmu  Komputer  UGM     adalah   salah   satu   fungsi   hash   satu   arah   yang   banyak   digunakan   dalam   bidang   kriptografi   yang   menerima   input   string   yang   panjangnya   sembarang   dan   menghasilkan   message   digest   dari   input   yang   panjangnya   tetap   yakni   sepanjang  128  bit  atau  32  karakter   Pada   awalnya,   MD5   di   desain   oleh   Ronald   Rivest   pada   tahun   1991   untuk  menggantikan  hash   function   sebelumnya,  MD4.  Namun  demikian,  pada   tahun  1996,  sebuah  bugs  telah  ditemukan  dalam  desain  algoritmanya,  walau   bukan   kelemahan   fatal,   tetapi   pengguna   kriptografi   mulai   menganjurkan   menggunakan   algoritma   lain,   seperti   SHA-­‐1   (walaupun   dalam   klaim   terbaru   menyatakan   bahwa   SHA-­‐1   juga   cacat).   Pada   tahun   2004,   kecacatan-­‐kecacatan   yang   lebih   serius   ditemukan   menyebabkan   penggunaan   algoritma   tersebut   dalam  tujuan  untuk  keamanan  jadi  makin  dipertanyakan.   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.   Key   merupakan   suatu   input   dari   pemakai   di   mana   pada   umumnya   berupa  nilai  atau  string  karakter.     Pelacakan  dengan  menggunakan  Hash  terdiri  dari  dua  langkah  utama,   yaitu:     • 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).     • 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         Salah   satu   masalah   yang   mungkin   terjadi   dari   fungsi   hash   adalah   collision.   Maksudnya   adalah   ada   2   atau   lebih   teks   yang   menghasilkan   nilai   hash   yang   sama.   Anda   sendiri   telah   melihat   dengan   MD5   bahwa   masukan   sepanjang   berapapun,   akan   menghasilkan   nilai   hash   sepanjang   128   bit.   Itu   artinya   kemungkinan   inputnya   sangat   banyak   jumlahnya,   tak   terhingga,   namun   kemungkinan   nilai   hashnya   hanya   sejumlah   2^128.   Sebagai   ilustrasi,   bayangkan   apa   yang   terjadi  bila  dalam  suatu  negara  jumlah  wanitanya  sangat   banyak,   hingga   5   kali   lipat   jumlah   pria.   Maka   kemungkinan   akan   ada   2   atau   lebih   wanita   yang   memiliki   suami   yang   sama.   Inilah   yang   disebut   collision.   Ada  2  atau  lebih  input  teks  yang  memiliki  nilai  hash  yang  sama.  MD5  memiilki  

  kelemahan   yang   memungkinkan   dicari   2   file   yang   memiliki   nilai   hash   yang   sama   dengan   waktu   yang   singkat.   Ilmuwan   yang   mempublikasikan   cara   mencari   MD5   collision   adalah   ilmuwan   Cina   Xiaoyun   Wang   and   Hongbo   Yu   dari  Shandong  University  (Schmitt  &  Jordaan,  2013).     Fungsi   hash   digunakan   untuk   menjaga   integrity   karena   perubahan   pada   file   1   bit   saja   akan   mengubah   nilai   hashnya.   Namun   bila   terjadi   collision   seperti  pada  MD5,  maka  file  integrity  tidak  lagi  bisa  terjamin.  Peter  Selinger   telah   membuat   demonstrasi   2   buah   file   executable   yang   berbeda   tapi   memiliki  nilai  hash  MD5  yang  sama.  Skenarionya  adalah  dari  dua  file  itu  salah   satunya   adalah   file   yang   asli,   satu   lagi   adalah   file   yang   jahat.   Keduanya   memiliki  ukuran  dan  nilai  hash  MD5  yang  sama.       5. Algoritma  dan  Kompleksitas  MD5      Algoritma   MD5   menerima   masukan   berupa   pesan   dengan   ukuran   sembarang   dan   menghasilkan   message   digest   yang   panjangnya   128   bit.   Dengan   panjang   message  digest  128   bit,   maka   secara   brute  force  dibutuhkan   percobaan  sebanyak  2128  kali  untuk  menemukan  dua  buah  pesan  atau  lebih   yang  mempunyai  message  digest  yang  sama  (Munir,  2006).     MD5   akan   mengolah   blok   512   bit,   dibagi   kedalam   16   subblok   berukuran   32   bit.   Keluaran   algoritma   diset   menjadi   4   blok   yang   masing-­‐ masing  berukuran  32  bit  yang  kemudian  bila  digabungkan  akan  membentuk   nilai  hash  128  bit.  Gambaran  sederhana  dari  cara  kerja  algoritma  MD5  adalah   sebagaimana  ilustrasi  pada  Gambar  1.    

Gambar  1  Cara  Kerja  Algoritma  MD5  

 

  Sementara  itu  menurut  (Munir,  2006),  ilustrasi  cara  kerja  dari  algoritma  MD5   ini  adalah  dalam  beberapa  tahapan  berikut,  yaitu:    

   

[Type  text]  

   

 

6   Komputasi  dan  Kompleksitas  –  Program  Doktor  Ilmu  Komputer  UGM     •

•

•

•

 

Penambahan   Bit-­‐bit   Pengganjal.   Di   dalam   tahapan   ini,   pesan   di   tambah   dengan   sejumlah   bit   pengganjal   sedemikian   rupa   sehingga   panjang   pesan(dalam  satuan  bit)  kongruen  dengan  448  modulo  512.  Jika  panjang   pesan  adalah  448  bit,  maka  pesan  tersebut  ditambah  512  bit  menjadi  960   bit.   Jadi   panjang   bit-­‐bit   pengganjal   adalah   antara   1-­‐512   bit,   bit-­‐bit   pengganjal  terdiri  dari  sebuah  bit  1  diikuti  dengan  sisanya  bit  0   Penambahan   Nilai   Panjang   Pesan.   Selanjutnya   pesan   yang   telah   diberi   bit-­‐ bit   pengganjal   ditambah   lagi   dengan   64   bit   yang   menyatakan   panjang   pesan   semula.   Jika   panjang   pesan   >   264   maka   yang   diambil   adalah   panjangnya   dalam   modulo   264.   Dengan   kata   lain,   jika   panjang   pesan   semula  adalah  K  bit,  maka  64  bit  yang  ditambahkan  menyatakan  K  modulo   264.   Setelah   ditambah   dengan   64   bit,   panjang   pesan   sekarang   menjadi   kelipatan  512  bit.   Inisialisai  Penyangga  MD.  Pada  tahapan  ketiga,  MD5  membutuhkan  4  buah   penyangga  (buffer)  yang  masing-­‐masing  panjangnya  32  bit.  Total  panjang   penyangga   adalah   4   x   32   =   128   bit.   Keempat   penyangga   ini   menampung   hasil   antara   dan   hasil   akhir.   Keempat   penyangga   ini   diberi   nama   A,   B,   C,   dan   D.   Setiap   penyangga   diinisialisasi   dengan   nilai-­‐nilai   (dalam   notasi   HEX)  sebagai  berikut  :  A  =  01234567;  B  =  89ABCDEF;  C  =  FEDCBA98;  D  =   76543210.     Pengolahan   Pesan   dalam   Blok   Berukuran   512   bit   Pada   tahap   ini,   Pesan   dibagi   menjadi   L   buah   blok   yang   masing-­‐masing   panjangnya   512   bit   (Y0   sampai   YL–1),   dimana   setiap   blok   512   bit   diproses   bersama   dengan   penyangga   MD   sehingga   keluarannya   adalah   128   bit,   proses   ini   disebut   proses  HMD5.  Gambaran  proses  HMD5  adalah  sebagai  berikut  :  

(a)  Proses  HMD5                                                                                                            (b)  Operasi  Dasar  MD5     Gambar  2  Proses  HMD5  dan  Operasi  Dasar  MD5    

 

    Berdasarkan   Gambar   2(a)   tersebut,   Yq   menyatakan   blok   512   bit   ke-­‐q   dari  pesan  (yang  telah  ditambah  bit-­‐bit  pengganjal  dan  tambahan  64  bit  nilai   panjang   pesan   semula),   dan   MDq   adalah   nilai   message   digest   128   bit   dari   proses  HMD5  ke-­‐q.  Proses  HMD5  terdiri  dari  4  buah  putaran,  dimana  masing-­‐ masing   putaran   melakukan   operasi   dasar   MD5   sebanyak   16   kali   dan   setiap   operasi   dasar   memakai   sebuah   elemen   T.   Jadi   setiap   putaran   memakai   16   elemen   Tabel   T.   Berdasarkan   Gambar   2(a)   fungsi-­‐fungsi   fF,   fG,   fH,   dan   fI   masing-­‐masing  berisi  16  kali  operasi  dasar  terhadap  masukan,  setiap  operasi   dasar  menggunakan  elemen  Tabel  T.       Operasi   dasar   MD5   diperlihatkan   pada   Gambar   2(b).   Keterangan   variabel  yang  ada  pada  Gambar  2(b)  adalah  sebagai  berikut  :     a,  b,  c,  d   :  Empat  buah  peubah  penyangga  32  bit  A,  B,  C,  D     g       :  Salah  satu  fungsi  F,  G,  H,  I     CLSs       :  Circular  left  shift  sebanyak  s  bit     X[k]       :  Kelompok  32-­‐bit  ke-­‐k  dari  blok  512  bit  message  ke-­‐q,               Nilai  k  =  0  sampai  15     T[i]      :  Elemen  Tabel  T  ke-­‐i  (32  bit)     +       :  Operasi  penjumlahan  modulo  232       1

//Catatan: Seluruh variable pada unsigned integer 32-bit dan dan wrap modulo 2^32 saat melakukan perhitungan //Mendefinisikan r sebagai berikut

t

2 3 4

var int[64] r, k r[ 0..15] := {7,12,17,22,7,12,17,22,7,12,17,22,7,12,17,22} r[16..31] := {5, 9,14,20,5, 9,14,20,5, 9,14,20,5, 9,14,20}

1 1 1

5 6 7 8 9 9 10 11 12 13 14 15 16 17 18 19 20

r[32..47] := {4,11,16,23,4,11,16,23,4,11,16,23,4,11,16,23} r[48..63] := {6,10,15,21,6,10,15,21,6,10,15,21,6,10,15,21} //Menggunakan bagian fraksional biner dari integral sinus sebagai konstanta: for i from 0 to 63 k[i] := floor(abs(sin(i + 1)) × 2^32) //Inisialisasi variabel: var int h0 := 0x67452301 var int h1 := 0xEFCDAB89 var int h2 := 0x98BADCFE var int h3 := 0x10325476 //Pemrosesan awal: append "1" bit to message append "0" bits until message length in bits ≡ 448 (mod 512) append bit length of message as 64-bit little-endian integer to message //Pengolahan pesan paada kondisi gumpalan 512-bit: for each 512-bit chunk of message break chunk into sixteen 32-bit little-endian words w(i), 0 ≤ i ≤ 15

1 1

21 22 23 24 25

   

63 1 1 1 1 1 1 1 1 n/512 1

//Inisialisasi nilai hash pada gumpalan ini: var int a := h0 var int b := h1 var int c := h2 var int d := h3

[Type  text]  

1 1 1 1

   

 

8   Komputasi  dan  Kompleksitas  –  Program  Doktor  Ilmu  Komputer  UGM     26 27 28 29 30 31

//Kalang utama: for i from 0 to 63 if 0 ≤ i ≤ 15 then f := (b and c) or ((not b) and d) g := i else if 16 ≤ i ≤ 31

63 1 1 1 1

32 33 34 35 36 37 38 39 40

f := (d and b) or ((not d) and c) g := (5×i + 1) mod 16 else if 32 ≤ i ≤ 47 f := b xor c xor d g := (3×i + 5) mod 16 else if 48 ≤ i ≤ 63 f := c xor (b or (not d)) g := (7×i) mod 16 temp := d

1 1 1 1 1 1 1 1 1

41 42 43

d := c c := b b := ((a + f + k(i) + w(g)) leftrotate r(i)) + b

1 1 1

44 45

a := temp //Tambahkan hash dari gumpalan sebagai hasil:

1

46

h0 := h0 + a

1

47

h1 := h1 + b

1

48 49

h2 := h2 + c h3 := h3 + d

1 1

50

var int digest := h0 append h1 append h2 append h3 //(diwujudkan dalam little-endian)

1

  Berdasarkan  analisa  diatas  maka  :     Baris  2-­‐6     =  5     Baris  8-­‐9     =  63  *  (1)  =  63     Baris  10-­‐17     =  7     Baris  19-­‐40     =  n/512  *  ((  5+  63*(12)  +  5)  =  n/512  (766)     Baris  46-­‐50     =  5     Total  adalah  :  5+  63  +  7  +  (n/512)*766)  +  5  =  766/512  n  +  80       Dengan   menggunakan   pendekatan   Big   Oh,   maka   berdasarkan   Tabel   dan   Gambar   3   terlihat   bahwa   kompleksitas   dari   algoritma   fungsi   hash   MD5   ini  adalah  linier.  Algoritma  yang  persamaan  waktunya  adalah  linier  umumnya   terdapat   pada   kasus-­‐kasus   dimana   setiap   elemen   masukannya   akan   dikenai   proses  yang  sama,  dan  hal  ini  sesuai  dengan  karakteristik  dari  algoritma  MD5.   Semua   masukan   message   pada   algoritma   MD5   ini   akan   dikenakan   proses   yang  sama.    

  Nilai masing-masing fungsi untuk setiap bermacam-macam nilai n log n 0 1 2 3 4 5

n 1 2 4 9 16 32

n log n 0 2 8 24 64 160

n2

n3

2n

1 4 16 64 256 1024

1 8 64 512 4096 32768

2 4 16 256 65536 4294967296

n! 1 2 24 362880 20922789888000 (terlalu besar )

Gambar  3  Tabel  da  Grafik  Fungsi  Asimtotik  

 

  6. Diskusi     Algoritma  adalah  sekumpulan  berhingga  dari  instruksi-­‐instruksi  untuk   melakukan   perhitungan   atau   memecahkan   suatu   masalah.   Sebuah   algoritma   tidak  saja  harus  benar,  tetapi  juga  harus  efisien.  Algoritma  yang  bagus  adalah   algoritma  yang  efektif  dan  efisien.  Algoritma  yang  efektif  diukur  dari  berapa   jumlah   waktu   dan   ruang   (space)   memori   yang   dibutuhkan   untuk   menjalankannya.    Algoritma   yang   efisien   adalah   algoritma   yang   meminimumkan   kebutuhan   waktu   dan   ruang.   Kebutuhan   waktu   dan   ruang   suatu   algoritma   bergantung   pada   ukuran   masukan   (n),   yang   menyatakan   jumlah   data   yang   diproses.   Keefektifan   algoritma   dapat   digunakan   untuk   menilai  algoritma  yang  sebaiknya  digunakan.     Waktu   yang   diperlukan   oleh   sebuah   algoritma   dapat   dicari   dengan   menghitung   banyaknya   operasi/instruksi   yang   dieksekusi.   Bila   besaran   waktu  untuk  eksekusi  dikonversi  kedalam  satuan  detik  untuk  melaksanakan   sebuah   operasi   tertentu,   maka   secara   keseluruhan   dapat   dihitung   berapa   waktu   sesungguhnya   yang   diperlukan   untuk   mengeksekusi   algoritma   tersebut.     Secara   umum   terdapat   dua   jenis   komleksitas,   yaitu   waktu   dan   ruang.   Kompleksitas   waktu,   T(n),   dihitung   dari   jumlah   tahapan   komputasi   yang      

[Type  text]  

   

 

10   Komputasi  dan  Kompleksitas  –  Program  Doktor  Ilmu  Komputer  UGM     diperlukan  untuk  menjalankan  algoritma  sebagai  fungsi  dari  ukuran  masukan   n.   Sementara   kompleksitas   ruang,   S(n),   diukur   dari   memori   yang   digunakan   oleh   struktur   data   yang   terdapat   di   dalam   algoritma   sebagai   fungsi   dari   ukuran   masukan   n.   Dengan   demikian   melalui   penggunaan   besaran   kompleksitas  waktu/ruang  algoritma,  pada  prinsipnya  dapat  ditentukan    laju   peningkatan   waktu(ruang)   yang   diperlukan   algoritma   melalui   parameter   meningkatnya  ukuran  masukan  n.     Dalam   prakteknya   kompleksitas   waktu   dihitung   berdasarkan   jumlah   operasi  abstrak  yang  mendasari  suatu  algoritma,  dan  memisahkan  analisisnya   dari   implementasi.   Hal   inilah   yang   juga   dilakukan   dalam   melakukan   analisis   kompleksitas  waktu  pada  algoritma  fungsi  hash  MD5.     Kinerja   sebuah   algoritma   biasanya   diukur   dengan   menggunakan   patokan  keadaan  terburuk  (worst  case)  yang  dinyatakan  dengan  Big-­‐O.  Selain   Big   O,   sebenarnya   terdapat   beberapa   jenis   notasi   asimtotik,   tetapi   dalam   penelitian   tersebut   digunakan   notasi   Big   O   karena   merupakan   notasi   yang   paling   populer   dan   paling   banyak   digunakan   pada   kalangan   peneliti   ilmu   komputer.   Notasi   Big-­‐O   digunakan   untuk   mengkategorikan   algoritma   ke   dalam   fungsi   yang   menggambarkan   batas   atas   (upper   limit)   dari   pertumbuhan   sebuah   fungsi   ketika   masukan   dari   fungsi   tersebut   bertambah   banyak.       Perhitungan   jumlah   langkah   dan   pertumbuhannya   yang   dilakukan   pada   bagian   sebelumnya   merupakan   langkah-­‐langkah   untuk   mendapatkan   fungsi   Big-­‐O   dari   algoritma   MD5.   Dalam   hal   ini   Algoritma   perpangkatan   dengan  pertumbuhan  linear  yang  dihasilkan  dari  analis  sebelumnya  memiliki   kelas  Big-­‐O  yaitu  O(n).  Berdasarkan  karakteristik  algoritma  fungsi  hash  MD5,   maka  yang  paling  mungkin  untuk  dicari  adalah  Big-­‐O  (worst  case).  Sementara   keadaan  rata-­‐rata  Omega  (avarage)  dan  terbaik  Theta  (best  case)  tidak  akan   didapat   oleh   fungsi   MD5.   Hal   ini   terjadi   karena   fungsi   MD5   ini   hanya   akan   bekerja   bila   ada   input   message/string   sepanjang   n.   Sehingga   nilai   n   akan   selalu  menjadi  nilai  input  bagi  fungsi  hash  MD5  ini.       Selanjutnya,   fakta   bahwa   algoritma   fungsi   hash   MD5   ini   memiliki   kompleksitas   waktu   yang   linier   diperkuat   pula   dengan   pembuktian   yang   dilakukan   oleh   (Hossain,   Islam,   Das,   &   Nashiry,   2012).   Gambar   4   adalah   merupakan  salah  satu  output  yang  menunjukkan  hasil  penelitian  (Hossain  et   al.,  2012)  tentang  kompleksitas  waktu  dari  fungsi  hash  MD5.    

Gambar  4  Ouput  Penelitian  dari    (Hossain  et  al.,  2012)  

 

    7. Kesimpulan     Pada   paper   ini   telah   dibahas   tentang   bagaimana   pentingnya   menjaga   integritas   bukti   digital   dalam   sebuah   proses   digital   forensics.   Salah   satu   algoritma   yang   sering   diterapkan   untuk   menjaga   integritas   bukti   digital   adalah   melalui   penerapan   fungsi   hash   MD5.   Berdasarkan   cara   kerja   dan   karakteristik   algoritma   MD5   ternyata   kompleksitas   waktu   dari   algoritma   tersebut  adalah  Big  O  (n)  atau  fungsi  asimtotik  linier.  Dengan  demikian  secara   umum   bertambahnya   input   (panjang   message   yang   akan   dicarikan   nilai   fungsi   hash   MD5)   akan   sebanding   pula   dengan   bertambahnya   waktu   secara   linier.  Hasil  perhitungan  yang  didapat  ternyata  sejalan  dengan  hasil  riset  yang   dilakukan   penelitian   lain   mengenaik   kompleksitas   waktu   dari   fungsi   hash   MD5.         Daftar  Pustaka     Boddington,   R.,   Hobbs,   V.,   &   Mann,   G.   (2008).   Validating   Digital   Evidence   for   Legal   Argument.   In   Australian   Digital   Forensics   Conference.   Pert,   Western   Australia:   Edith   Cowan   University,  Perth  Western  Australia.  Retrieved  from  http://ro.ecu.edu.au/adf/   Buncle,   J.   (2009).   MD5   HASHING   IN   DIGITAL   FORENSICS,   1–5.   Retrieved   from   https://www.jbuncle.co.uk/docs/MD5  Hashing  in  Digital  Forensics.pdf   Cohen,  F.  (2013).  Digital  Forensic  Evidence  Examination,  5th  Edition.   Cosic,   J.,   &   Baca,   M.   (2010).   (   Im   )   Proving   Chain   of   Custody   and   Digital   Evidence   Integrity   with   Time   Stamp.   In   MIPRO,Proceedings   of   the   33rd   International   Convention   International   Conference   (pp.   1226   –   1230).   Opatija,   Croatia.   Retrieved   from   http://czb.foi.hr/upload/datoteke/10_400.pdf   Hossain,   A.,   Islam,   K.,   Das,   S.   K.,   &   Nashiry,   A.   (2012).   Cryptanalyzing   of   Message   Digest   Algorithms   MD4   and   MD5.   International   Journal   on   Cryptography   and   Information   Security(IJCIS),  2(1),  1–13.  doi:10.5121/ijcis.2012.2101   Munir,  R.  (2006).  Kriptografi.  Bandung:  Penerbit  Informatika.   Richter,  J.,  &  Kuntze,  N.  (2010).  Securing  Digital  Evidence.  In  Fifth   International   Workshop   on   Systematic  Approaches  to  Digital  Forensic  Engeneering  (pp.  119–130).  Oakland,  CA,  USA.   Retrieved   from   http://sit.sit.fraunhofer.de/smv/publications/download/EvidentialIntegrity.pdf   Saleem,  S.,  Popov,  O.,  &  Dahman,  R.  (2011).  Evaluation  of  Security  Methods  for  Ensuring  the   Integrity   of   Digital   Evidence.   In   International  Conference  on  Innovations  in  Information   Technology  (pp.  220–225).   Schatz,   B.   (2007,   October).   Digital   Evidence:   Representation   and   Assurance.   Queensland   University   of   Technology,   Australia.   Retrieved   from   http://eprints.qut.edu.au/16507/1/Bradley_Schatz_Thesis.pdf   Schmitt,   V.,   &   Jordaan,   J.   (2013).   Establishing   the   Validity   of   Md5   and   Sha-­‐1  Hashing  in  Digital   Forensic   Practice   in   Light   of   Recent   Research   Demonstrating   Cryptographic   Weaknesses   in   these.   Lex-­‐Informatica.Org,   68(23),   40–43.   Retrieved   from   http://www.lex-­‐informatica.org/2   Ensuring   the   Legality   of   the   Digital   Forensics   Process  in  South  Africa.pdf   Turner,  P.  (2005).  Unification  of  Digital  Evidence  from  Disparate  Sources.  

 

   

[Type  text]