Fungsi hash kriptografi

Dalam pelajaran ini kita akan melihat fungsi hash kriptografi yang banyak digunakan dalam validasi dan autentikasi cepat.

Pada akhir pelajaran kita akan sudah membahas:

• Apa itu fungsi hash kriptografi
• Contoh kode Python yang mendemonstrasikan penggunaan fungsi hash
• Tinjauan aplikasi dari hashing kriptografi
• Keamanan dari hashing kriptografi
• Ancaman terhadap algoritma-algoritma ini dari komputer klasik maupun kuantum

Pengenalan hashing kriptografi

Fungsi hash merupakan konstruk yang berharga dalam kriptografi karena membantu memungkinkan validasi dengan kerahasiaan. Sebagai demikian, fungsi hash merupakan komponen penting dari mekanisme autentikasi dan integritas data, seperti hash-based message authentication codes (HMAC) dan tanda tangan digital. Artikel ini akan membahas ide-ide dasar dan pertimbangan keamanan yang mendasari fungsi hash kriptografi serta menguraikan potensi kerentanan dari munculnya komputasi kuantum.

Dasar pemikiran dan desain fungsi hash

Ada banyak situasi di mana autentikasi dan verifikasi integritas perlu dilakukan secara murah dan tanpa mengungkapkan informasi privat kepada pihak yang melakukan validasi.

Misalnya, saat mengunduh perangkat lunak dari server jarak jauh, diperlukan mekanisme yang efisien untuk memverifikasi bahwa perangkat lunak yang diunduh belum dimodifikasi sejak dibuat oleh penulis asli perangkat lunak tersebut. Demikian pula, saat mengautentikasi pengguna aplikasi web, akan lebih baik menggunakan mekanisme yang tidak melibatkan penyimpanan fisik atau transmisi kata sandi yang sebenarnya, yang berpotensi membahayakan kerahasiaannya.

Fungsi hash kriptografi (CHF) memenuhi kebutuhan tersebut secara efisien dan aman.

Pada dasarnya, fungsi hash kriptografi mengambil input (atau pesan) dengan panjang sembarang dan mengembalikan string n-bit berukuran tetap sebagai output. Output dari sebuah CHF juga disebut sebagai digest. CHF yang berguna harus memenuhi beberapa properti kunci:

1. Keseragaman: Digest yang dihasilkan oleh CHF harus terdistribusi secara seragam dan terlihat acak. Tujuannya adalah memastikan output tidak bocorkan informasi tentang input.
2. Determinisme: Untuk input yang diberikan, CHF harus selalu menghasilkan digest yang sama, yaitu, harus deterministik.
3. Tidak dapat dibalik: CHF adalah fungsi satu arah dalam artian bahwa, diberikan sebuah digest, harus tidak mungkin untuk membalik proses hashing dan mendapatkan inputnya.
4. Injektivitas perkiraan: Meskipun CHF adalah fungsi banyak-ke-satu, mereka harus terlihat seperti fungsi satu-ke-satu. Ini dicapai dengan menggabungkan ukuran ruang output yang sangat besar dengan efek avalanche di mana perubahan kecil pada input menyebabkan digest yang sangat berbeda. Karakteristik ini dikenal sebagai injektivitas perkiraan.

Berdasarkan ini, memungkinkan untuk memvalidasi sepotong data terhadap instansi asli dengan membandingkan digest dari data dengan digest dari aslinya.

• Jika dua digest cocok, kita bisa yakin dengan probabilitas tinggi bahwa data identik dengan aslinya.
• Jika digest berbeda, kita bisa yakin bahwa data telah dirusak atau tidak otentik.

Karena digest CHF itu sendiri tidak mengungkapkan konten sebenarnya dari data atau aslinya, mereka memungkinkan validasi sambil menjaga privasi.

Mathematical description

A hash function $H$ can be defined as:

$H : Σ^* \rightarrow \{0,1\}^n$

where $Σ^*$ is the set of all possible strings which we may consider to be binary strings of any length.

The fact that the size of the input domain $Σ^*$ of $H$ is unbounded while that of the co-domain $\{0,1\}^n$ is bounded means that $H$ is necessarily many-to-one mapping infinitely many inputs to any given n-bit string.

The properties of uniformity and determinism are nicely encapsulated within the random oracle model of cryptographic hashing.

Contoh hashing kriptografi di Python dengan SHA-256

Contoh sederhana ini mendemonstrasikan hashing kriptografi menggunakan algoritma SHA-256 yang populer seperti yang disediakan oleh library Python cryptography. Pertama kita tunjukkan bagaimana perbedaan kecil dalam plain text menghasilkan perbedaan yang sangat besar dalam digest hash.

# Added by doQumentation — required packages for this notebook
!pip install -q cryptography

# Begin by importing some necessary modules
from cryptography.hazmat.backends import default_backend
from cryptography.hazmat.primitives import hashes

# Helper function that returns the number of characters different in two strings
def char_diff(str1, str2):
    return sum(str1[i] != str2[i] for i in range(len(str1)))

# Messages to be hashed
message_1 = b"Buy 10000 shares of WXYZ stock now!"
message_2 = b"Buy 10000 shares of VXYZ stock now!"

print(f"The two messages differ by { char_diff(message_1, message_2)} characters")

The two messages differ by 1 characters

Dua pesan berbeda persis satu karakter.

Selanjutnya, kita instansiasi objek hash untuk mengaktifkan proses hashing, yang melibatkan panggilan ke dua metode: update dan finalize.

Kita melihat bahwa karena efek avalanche dalam SHA-256 CHF, perbedaan satu karakter dalam pesan input menghasilkan dua digest yang sangat berbeda.

# Create new SHA-256 hash objects, one for each message
chf_1 = hashes.Hash(hashes.SHA256(), backend=default_backend())
chf_2 = hashes.Hash(hashes.SHA256(), backend=default_backend())

# Update each hash object with the bytes of the corresponding message
chf_1.update(message_1)
chf_2.update(message_2)

# Finalize the hash process and obtain the digests
digest_1 = chf_1.finalize()
digest_2 = chf_2.finalize()

# Convert the resulting hash to hexadecimal strings for convenient printing
digest_1_str = digest_1.hex()
digest_2_str = digest_2.hex()

# Print out the digests as strings
print(f"digest-1: {digest_1_str}")
print(f"digest-2: {digest_2_str}")

print(f"The two digests differ by { char_diff(digest_1_str, digest_2_str)} characters")

digest-1: 6e0e6261b7131bd80ffdb2a4d42f9d042636350e45e184b92fcbcc9646eaf1e7
digest-2: 6b0abb368c3a1730f935b68105e3f3ae7fd43d7e786d3ed3503dbb45c74ada46
The two digests differ by 57 characters

Aplikasi hashing kriptografi

Properti unik dari CHF membuatnya cocok untuk berbagai aplikasi:

• Pemeriksaan integritas data: Fungsi hash bisa digunakan untuk membuat checksum untuk sekumpulan data. Setiap modifikasi pada data, baik disengaja maupun tidak, akan menghasilkan checksum yang berbeda, memperingatkan sistem atau pengguna tentang perubahan tersebut. Checksum juga biasanya jauh lebih ringkas dari data asli, yang membuat perbandingan checksum menjadi sangat cepat.

Gambar 1. Hashing aman untuk integritas data

• Tanda tangan digital: Hash kriptografi sangat penting untuk berfungsinya tanda tangan digital karena melibatkan perbandingan pesan yang di-hash secara kriptografi untuk menetapkan keaslian dan integritas sambil menjaga privasi.

Gambar 2. Tanda tangan digital

• Blockchain dan mata uang kripto: Mata uang kripto seperti Bitcoin sangat mengandalkan CHF, khususnya dalam menciptakan integritas transaksi dan memungkinkan mekanisme konsensus seperti proof of work.

Keamanan hashing kriptografi

Keamanan CHF biasanya dinilai berdasarkan ketahanan terhadap dua jenis serangan: pre-image dan collision.

Ketahanan pre-image

Ketahanan pre-image berarti bahwa diberikan sebuah digest, harus tidak mungkin menemukan inputnya.

Ini terkait dengan properti satu arah dari CHF.

CHF yang baik dirancang sedemikian rupa sehingga pihak yang ingin melakukan serangan pre-image tidak memiliki pilihan yang lebih baik selain pendekatan brute force, yang memiliki kompleksitas waktu $2^n$.

mathematical details

Given a CHF $H$ and digest $g$, it should be computationally infeasible to find any input $m$ from the pre-image of $g$ whereby $H(m) = g$.

Ketahanan collision

Ketahanan collision berarti bahwa sulit menemukan dua input berbeda yang di-hash ke digest yang sama.

Sebuah collision hash kriptografi terjadi ketika dua input di-hash ke digest yang sama. Meskipun collision pasti ada mengingat sifat banyak-ke-satu dari CHF, namun CHF yang baik tetap membuatnya tidak mungkin untuk menemukan satu sesuai keinginan.

Ketahanan collision sangat penting untuk aplikasi seperti tanda tangan digital dan sertifikat, di mana akan sangat berbahaya jika pihak yang tidak bertanggung jawab bisa membuat pemalsuan yang di-hash ke nilai yang sama.

mathematical details of hash collisions

$m_1, m_2$ can be found such that $H(m_1) = H(m_2)$.

Panjang hash

Ketahanan collision adalah persyaratan yang lebih sulit daripada ketahanan pre-image dan memerlukan panjang output dua kali lebih panjang dari yang dibutuhkan untuk ketahanan pre-image. Ini karena serangan brute force yang dikenal sebagai birthday attack, yang bisa digunakan untuk mengidentifikasi hash collision, memiliki kompleksitas waktu $2^{n/2}$.

Tanpa adanya kelemahan kriptanalisis, keamanan fungsi hash oleh karena itu terutama dipengaruhi oleh panjang hash-nya. Semakin panjang hash, semakin aman, karena semakin sulit untuk melancarkan serangan brute force.

Fungsi hash kriptografi yang umum digunakan

Tabel berikut mencantumkan beberapa fungsi hash kriptografi yang umum digunakan, beserta panjang hash dan domain aplikasi utamanya:

Fungsi Hash	Panjang Output (bit)	Aplikasi Umum
MD5	128	Pemeriksaan integritas file, sistem lama, penggunaan non-kriptografi
SHA-1	160	Sistem lama, Git untuk version control
SHA-256	256	Mata uang kripto (Bitcoin), tanda tangan digital, sertifikat
SHA-3	Variabel (hingga 512)	Berbagai aplikasi kriptografi, penerus SHA-2
Blake2	Variabel (hingga 512)	Kriptografi, menggantikan MD5/SHA-1 di beberapa sistem
Blake3	Variabel (hingga 256)	Kriptografi, hashing file, integritas data

• MD5 dan SHA-1, meskipun masih terlihat di aplikasi yang kurang sensitif, dianggap sudah usang dalam hal ketahanan collision dan tidak direkomendasikan untuk sistem baru. SHA-256, bagian dari keluarga SHA-2, banyak digunakan dan saat ini aman untuk sebagian besar aplikasi.
• SHA-3 adalah standar yang lebih baru yang dipilih oleh NIST pada tahun 2015 sebagai pemenang kompetisi fungsi hash NIST. Dirancang sebagai pengganti drop-in untuk SHA-2, tetapi juga memiliki beberapa karakteristik internal yang berbeda dan tahan terhadap jenis serangan tertentu yang mungkin efektif terhadap SHA-2.
• Blake2 dan Blake3 adalah fungsi hash kriptografi yang lebih cepat dari MD5, SHA-1, SHA-2, dan SHA-3, tetapi setidaknya seaman standar terbaru, SHA-3. Mereka semakin banyak digunakan dalam sistem baru, terutama di mana kecepatan penting.

Risiko kuantum terhadap hashing kriptografi tradisional

Ancaman kuantum utama terhadap hashing kriptografi ditimbulkan oleh serangan brute force.

Diberikan digest tertentu, penyerang akan mencoba input acak sampai menemukan satu yang menghasilkan digest yang sama.

Dengan $n$ bit dalam input, ada $2^n$ kemungkinan nilai. Oleh karena itu, penyerang perlu mencoba sekitar $2^{n-1}$ input untuk memiliki kemungkinan sukses lebih dari 50%.

Algoritma Grover

Untuk konteks pencarian tidak terstruktur seperti ini, algoritma Grover bisa memberikan percepatan kuadratik menggunakan teknik yang dikenal sebagai amplifikasi amplitudo kuantum, mengurangi kompleksitas waktu serangan pre-image menjadi $2^{n/2}$.

Secara praktis, ini berarti bahwa CHF 256-bit, yang saat ini dianggap aman terhadap serangan pre-image oleh komputer klasik, akan memberikan tingkat keamanan yang sama dengan CHF 128-bit ketika dihadapi dengan penyerang kuantum yang menggunakan algoritma Grover.

Algoritma Grover sendiri tidak diketahui memberikan percepatan kuantum tambahan sehubungan dengan serangan collision di luar batas yang ditetapkan oleh birthday attack, yang bisa dilakukan pada komputer klasik. Karena birthday attack klasik sudah mengharuskan CHF menggunakan panjang hash dua kali lebih panjang dari yang diperlukan untuk ketahanan pre-image, fakta bahwa pencarian Grover secara efektif mengurangi setengah panjang hash sehubungan dengan serangan pre-image tidak menimbulkan ancaman praktis.

Misalnya, dalam kasus SHA-256, melakukan sekitar $2^{128}$ operasi untuk menjalankan serangan pre-image yang dibantu Grover tetap tidak dapat dilakukan dalam waktu mendatang.

Algoritma BHT

Algoritma kuantum yang menggabungkan aspek birthday attack dengan pencarian Grover diusulkan pada tahun 1997 oleh Brassard, Høyer, dan Tapp (BHT) dan memberikan skala teoretis $O(2^{n/3})$ untuk menemukan hash collision. Namun, peningkatan skala ini bergantung pada keberadaan teknologi QRAM memori akses acak kuantum, yang saat ini belum ada.

Tanpa QRAM, skala yang bisa diwujudkan adalah $\tilde{O}(2^{2n/5})$ dan untuk panjang hash yang saat ini digunakan, peningkatan marginal dalam kemampuan menemukan collision relatif terhadap birthday attack ini tidak mewakili ancaman kritis.

Ringkasan

Fungsi hash kriptografi adalah komponen penting untuk memastikan integritas data dan privasi dalam sistem informasi digital dan banyak digunakan dalam berbagai konteks.

Persyaratan keamanan CHF terutama dipahami dalam hal ketahanan terhadap serangan pre-image dan collision. Untuk CHF yang dirancang dengan baik, panjang hash adalah proksi yang baik untuk tingkat keamanan.

Meskipun munculnya komputer kuantum yang mengeksekusi algoritma Grover dan BHT secara teori mempengaruhi ketahanan pre-image dan collision dari CHF tradisional, panjang hash yang sudah digunakan saat ini berarti bahwa algoritma hashing kriptografi modern, seperti SHA-3, kemungkinan akan tetap aman kecuali ditemukan serangan kriptanalitik yang belum diketahui sebelumnya.

Relevansi CHF terletak pada perannya sebagai blok bangunan fundamental untuk skema kriptografi yang tahan kuantum, memastikan informasi digital tetap aman bahkan menghadapi potensi kemajuan masa depan dalam algoritma dan teknologi komputasi kuantum.