Matasano Crypto Challenge 29: Break a SHA-1 keyed MAC Using Length Extension

Pada tulisan sebelumnya dibahas mengenai implementasi SHA-1 dan MAC. Untuk tulisan hari ini akan dibahas mengenai cara memecahkan SHA-1 MAC dengan panjang ekstensi.

Challenge

Secret-prefix SHA-1 MAC bisa dipecahkan dengan mudah.

Serangan pada secret-prefix SHA-1 bersandar pada fakta bahwa anda dapat mengambil luaran SHA-1 dan menggunakannya sebagai titik awal untuk SHA-1, dengan demikian pengambilan hash SHA-1 secara paksa akan “memberi tambahan data lebih”.

Dalam secret-prefix, kunci mendahului data. Jika anda beri SHA-1 pada data maka kunci akan nampak.

Untuk melakukan serangan, anda akan membutuhkan catatan untuk fakta bahwa SHA-1 mempunyai padding dengan panjang bit dalam pesan; Pesan anda akan membutuhkan padding. Matasano menyebut ini “glue padding”. Pesan yang sebenarnya bisa ditempa dengan fungsi seperti berikut:

SHA1(kunci || pesan asli || glue-padding || pesan baru)

(Dimana padding akhir pada pesan yang akan dimasukkan)

Catat juga untuk menghasilkan glue padding, anda akan butuh hal tersebut agar bisa tahu panjang bit pesan yang sebenarnya; pesan itu sendiri diketahui oleh attacker, namun kunci tidak, jadi anda butuh itu untuk menebak kunci.

Kedengarannya lebih rumit dibanding prakteknya.

Untuk mengimplementasikan serangan ini, pertama tulis fungsi untuk menghitung padding MD pada pesan dan verfikasi bahwa anda harus menghasilkan padding yang sama pada implementasi SHA-1 yang anda gunakan. Biasanya akan memakan waktu 5-10 menit.

Sekarang, ambil secret-prefix SHA-1 dan MAC pesan yang ingin anda tempa — ini hanya SHA-1 hash — dan pecahkan hal tersebut kedalam 32 bit SHA-1 registers (“a”,”b”,”c”,&c).

Modifikasi implementasi SHA-1 anda sehingga pemanggil dapat melewati nilai baru untuk “a”, “b”, “c” &c (Normalnya dimulai dengan angka magic). Dengan registers “fixated”, lakukan hash pada tambahan data yang ingin anda tempa.

Gunakan serangan ini, untuk menghasilkan secret-prefix MAC dengan kunci rahasia (pilih kata acak dari /usr/share/dict/word atau sesuatu) yang termasuk string:

“comment1=cooking%20MCs;userdata=foo;comment2=%20like%20a%20pound%20of%20bacon”

Tempa varian pesan ini yang diakhiri dengan “;admin=true”.

Serangan ini sangat berguna.

Thai Duong dan Juliano Rizzo, yang mempunyai serangan ini sebelum Matasano, digunakan untuk memecahkan API Flickr.

 

Solved

Ini dia penampakannya :).

break_sha1_keyed_mac_using_length_extension

Mengapa hanya share screenshot saja? Alasannya bisa anda lihat pada tulisan ikhtisar MCC sebelumnya.

Sekian tulisan hari ini, semoga bermanfaat.

Keep Fun Coding 😀

[1] Unknown. (????). Break a SHA-1 keyed MAC Using Length Extension. Tersedia: cryptopals.com/sets/4/challenges/29/. [12 Februari 2015].

Advertisements

One thought on “Matasano Crypto Challenge 29: Break a SHA-1 keyed MAC Using Length Extension

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s