Fungsi hash kriptografi

Dalam pelajaran ini kita akan melihat fungsi hash kriptografi yang digunakan secara meluas dalam pengesahan pantas dan pengesahan identiti.

Menjelang akhir pelajaran ini, kita akan telah membahas:

• Apakah fungsi hash kriptografi
• Contoh kod Python yang menunjukkan penggunaan fungsi hash
• Tinjauan aplikasi pencincangan kriptografi
• Keselamatan pencincangan kriptografi
• Ancaman terhadap algoritma ini daripada komputer klasik mahupun komputer kuantum

Pengenalan kepada pencincangan kriptografi

Fungsi hash merupakan konstruk yang bernilai dalam kriptografi kerana ia membantu membolehkan pengesahan dengan kerahsiaan. Oleh itu, fungsi hash membentuk komponen penting dalam mekanisme pengesahan dan integriti data, seperti kod pengesahan mesej berasaskan hash (HMAC) dan tandatangan digital. Artikel ini akan membincangkan idea asas dan pertimbangan keselamatan yang menjadi asas fungsi hash kriptografi serta menggariskan potensi kelemahan daripada kemunculan pengkomputeran kuantum.

Rasional asas dan reka bentuk fungsi hash

Terdapat banyak situasi di mana pengesahan identiti dan pengesahan integriti perlu dilakukan secara murah dan tanpa mendedahkan maklumat peribadi kepada pihak yang melakukan pengesahan.

Contohnya, semasa memuat turun perisian dari pelayan jauh, mekanisme yang cekap diperlukan untuk mengesahkan bahawa perisian yang dimuat turun itu tidak telah diubah sejak dicipta oleh pengarang perisian yang asal. Begitu juga, semasa mengesahkan pengguna aplikasi web, adalah lebih baik menggunakan mekanisme yang tidak melibatkan penyimpanan atau penghantaran kata laluan sebenar secara fizikal, yang boleh mendedahkan kerahsiaannya.

Fungsi hash kriptografi (CHF) menangani keperluan sedemikian secara cekap dan selamat.

Pada dasarnya, fungsi hash kriptografi mengambil input (atau mesej) dengan panjang sewenang-wenangnya dan mengembalikan rentetan tetap n-bit sebagai output. Output sebuah CHF juga dirujuk sebagai digest. CHF yang berguna harus memenuhi beberapa sifat utama:

1. Keseragaman: Digest yang dihasilkan oleh CHF harus diedarkan secara seragam dan kelihatan rawak. Tujuannya adalah untuk memastikan output tidak mendedahkan sebarang maklumat tentang input.
2. Determinisme: Untuk input tertentu, CHF mesti selalu menghasilkan digest yang sama, iaitu, ia mesti bersifat deterministik.
3. Ketidakbolehbalikan: CHF adalah fungsi sehala dalam erti kata bahawa, diberikan sebuah digest, adalah tidak mungkin untuk menyongsangkan pencincangan dan mendapatkan semula input.
4. Injektiviti hampir: Walaupun CHF adalah fungsi banyak-ke-satu, ia harus kelihatan seperti fungsi satu-ke-satu. Ini dicapai dengan menggabungkan saiz ruang output yang sangat besar dengan kesan avalans di mana perubahan kecil dalam input membawa kepada digest yang sangat berbeza. Ciri ini dikenali sebagai injektiviti hampir.

Berdasarkan ini, adalah mungkin untuk mengesahkan sekeping data terhadap contoh asal dengan membandingkan digest data itu dengan digest asal.

• Jika kedua-dua digest sepadan, kita boleh yakin dengan kebarangkalian tinggi bahawa data adalah sama dengan yang asal.
• Jika digest berbeza, kita boleh pastikan bahawa data telah dimanipulasi atau tidak autentik.

Oleh kerana digest CHF sendiri tidak mendedahkan kandungan sebenar data atau yang asal, ia membolehkan pengesahan sambil mengekalkan privasi.

Mathematical description

Fungsi hash $H$ boleh didefinisikan sebagai:

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

di mana $Σ^*$ adalah set semua rentetan yang mungkin yang boleh kita anggap sebagai rentetan binari dengan panjang apa pun.

Fakta bahawa saiz domain input $Σ^*$ bagi $H$ adalah tidak terbatas sementara domain bersama $\{0,1\}^n$ adalah terbatas bermakna $H$ semestinya adalah pemetaan banyak-ke-satu yang memetakan infiniti banyak input kepada mana-mana rentetan n-bit yang diberikan.

Sifat keseragaman dan determinisme dirangkum dengan baik dalam model oracle rawak pencincangan kriptografi.

Contoh pencincangan kriptografi dalam Python dengan SHA-256

Contoh mudah ini menunjukkan pencincangan kriptografi menggunakan algoritma SHA-256 yang popular seperti yang disediakan oleh pustaka Python cryptography. Pertama, kita tunjukkan bagaimana perbezaan kecil dalam teks biasa membawa kepada perbezaan 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

Kedua-dua mesej berbeza dalam tepat satu aksara.

Seterusnya, kita instantiasikan objek hash untuk membolehkan proses pencincangan, yang melibatkan panggilan kepada dua kaedah: update dan finalize.

Kita lihat bahawa disebabkan kesan avalans dalam SHA-256 CHF, perbezaan satu aksara dalam mesej input menghasilkan dua digest yang sangat berbeza.

# 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 pencincangan kriptografi

Sifat unik CHF menjadikannya sesuai untuk pelbagai aplikasi:

• Semakan integriti data: Fungsi hash boleh digunakan untuk mencipta checksum bagi set data. Sebarang pengubahsuaian pada data, sama ada disengajakan atau tidak, akan menghasilkan checksum yang berbeza, memberitahu sistem atau pengguna tentang perubahan tersebut. Checksum biasanya juga jauh lebih padat daripada data asal, menjadikan perbandingan checksum sangat pantas.

Rajah 1. Pencincangan selamat untuk semakan integriti data

• Tandatangan digital: Hash kriptografi adalah penting untuk fungsi tandatangan digital kerana ia melibatkan perbandingan mesej yang dicincanng secara kriptografi untuk membuktikan keaslian dan integriti sambil mengekalkan privasi.

Rajah 2. Tandatangan digital

• Blockchain dan mata wang kripto: Mata wang kripto seperti Bitcoin bergantung banyak pada CHF, terutamanya dalam mewujudkan integriti transaksi dan membolehkan mekanisme konsensus seperti bukti kerja.

Keselamatan pencincangan kriptografi

Keselamatan sebuah CHF biasanya dinilai berdasarkan rintangan terhadap dua jenis serangan: pra-imej dan perlanggaran.

Rintangan pra-imej

Rintangan pra-imej bermakna bahawa diberikan sebuah digest, adalah tidak mungkin untuk mencari input.

Ini berkaitan dengan sifat sehala CHF.

CHF yang baik direka bentuk sedemikian rupa sehingga pihak yang ingin melakukan serangan pra-imej tidak mempunyai pilihan yang lebih baik daripada pendekatan brute force, yang mempunyai kerumitan masa $2^n$.

mathematical details

Diberikan CHF $H$ dan digest $g$, adalah tidak mungkin secara pengiraan untuk mencari sebarang input $m$ daripada pra-imej $g$ di mana $H(m) = g$.

Rintangan perlanggaran

Rintangan perlanggaran bermakna adalah sukar untuk mencari dua input berbeza yang menghasilkan digest yang sama.

Perlanggaran hash kriptografi berlaku apabila dua input menghasilkan digest yang sama. Walaupun perlanggaran tidak dapat dielakkan memandangkan sifat banyak-ke-satu CHF, CHF yang baik tetap menjadikannya tidak mungkin untuk mencari satu secara sesuka hati.

Rintangan perlanggaran adalah penting untuk aplikasi seperti tandatangan digital dan sijil, di mana ia akan menjadi bencana jika pihak berniat jahat mampu mencipta pemalsuan yang menghasilkan hash kepada nilai yang sama.

mathematical details of hash collisions

$m_1, m_2$ boleh ditemui sedemikian sehingga $H(m_1) = H(m_2)$.

Panjang hash

Rintangan perlanggaran adalah keperluan yang lebih keras daripada rintangan pra-imej dan memerlukan panjang output dua kali lebih panjang daripada yang diperlukan untuk rintangan pra-imej. Ini kerana serangan brute force yang dikenali sebagai serangan hari lahir, yang boleh digunakan untuk mengenal pasti perlanggaran hash, mempunyai kerumitan masa $2^{n/2}$.

Tanpa kelemahan kriptanalisis, keselamatan fungsi hash oleh itu terutamanya dipengaruhi oleh panjang hashnya. Semakin panjang hash, semakin selamat ia, kerana serangan brute force menjadi semakin sukar.

Fungsi hash kriptografi yang biasa digunakan

Jadual berikut menyenaraikan beberapa fungsi hash kriptografi yang biasa digunakan, bersama panjang hash dan domain aplikasi utama mereka:

Fungsi Hash	Panjang Output (bit)	Aplikasi Biasa
MD5	128	Semakan integriti fail, sistem lama, kegunaan bukan kripto
SHA-1	160	Sistem lama, Git untuk kawalan versi
SHA-256	256	Mata wang kripto (Bitcoin), tandatangan digital, sijil
SHA-3	Boleh ubah (hingga 512)	Pelbagai aplikasi kriptografi, pengganti SHA-2
Blake2	Boleh ubah (hingga 512)	Kriptografi, menggantikan MD5/SHA-1 dalam sesetengah sistem
Blake3	Boleh ubah (hingga 256)	Kriptografi, pencincangan fail, integriti data

• MD5 dan SHA-1, walaupun masih digunakan dalam aplikasi yang kurang sensitif, dianggap lapuk dari segi rintangan perlanggaran dan tidak disyorkan untuk sistem baru. SHA-256, sebahagian daripada keluarga SHA-2, digunakan secara meluas dan kini selamat untuk kebanyakan aplikasi.
• SHA-3 adalah standard yang lebih baharu yang dipilih oleh NIST pada tahun 2015 sebagai pemenang pertandingan fungsi hash NIST. Ia direka bentuk sebagai pengganti langsung untuk SHA-2, tetapi ia juga mempunyai beberapa ciri dalaman yang berbeza dan tahan terhadap jenis serangan tertentu yang mungkin berkesan terhadap SHA-2.
• Blake2 dan Blake3 adalah fungsi hash kriptografi yang lebih pantas daripada MD5, SHA-1, SHA-2, dan SHA-3, tetapi sekurang-kurangnya selamat seperti standard terkini, SHA-3. Mereka semakin banyak digunakan dalam sistem baru, terutamanya di mana kelajuan adalah penting.

Risiko kuantum terhadap pencincangan kriptografi tradisional

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

Diberikan digest tertentu, penyerang akan mencuba input rawak sehingga menemui satu yang menghasilkan digest yang sama.

Dengan $n$ bit dalam input, terdapat $2^n$ nilai yang mungkin. Oleh itu, penyerang perlu mencuba sekitar $2^{n-1}$ input untuk mempunyai peluang kejayaan lebih daripada 50%.

Algoritma Grover

Untuk konteks carian tidak berstruktur seperti ini, algoritma Grover boleh memberikan percepatan kuadratik menggunakan teknik yang dikenali sebagai amplifikasi amplitud kuantum, mengurangkan kerumitan masa serangan pra-imej kepada $2^{n/2}$.

Dalam istilah praktikal, ini bermakna CHF 256-bit, yang kini dianggap selamat terhadap serangan pra-imej oleh komputer klasik, akan memberikan tahap keselamatan yang sama seperti CHF 128-bit apabila berhadapan dengan penyerang kuantum yang menggunakan algoritma Grover.

Algoritma Grover dengan sendirinya tidak diketahui memberikan percepatan kuantum tambahan berkenaan serangan perlanggaran melebihi had yang ditetapkan oleh serangan hari lahir, yang boleh dijalankan pada komputer klasik. Oleh kerana serangan hari lahir klasik sudah memerlukan CHF menggunakan panjang hash yang dua kali lebih panjang daripada yang diperlukan untuk rintangan pra-imej, fakta bahawa carian Grover secara efektif mengurangkan separuh panjang hash berkenaan serangan pra-imej tidak menimbulkan ancaman praktikal.

Contohnya, dalam kes SHA-256, melaksanakan sekitar $2^{128}$ operasi untuk melakukan serangan pra-imej berbantuan Grover masih tidak mungkin dilakukan dalam masa terdekat.

Algoritma BHT

Algoritma kuantum yang menggabungkan aspek serangan hari lahir dengan carian Grover dicadangkan pada tahun 1997 oleh Brassard, Høyer, dan Tapp (BHT) dan memberikan penskalaan teori $O(2^{n/3})$ untuk mencari perlanggaran hash. Walau bagaimanapun, penskalaan yang lebih baik ini bergantung pada kewujudan teknologi memori akses rawak kuantum QRAM, yang kini tidak wujud.

Tanpa QRAM, penskalaan yang boleh dicapai adalah $\tilde{O}(2^{2n/5})$ dan untuk panjang hash yang kini digunakan, penambahbaikan marginal dalam keupayaan mencari perlanggaran berbanding serangan hari lahir ini tidak mewakili ancaman kritikal.

Ringkasan

Fungsi hash kriptografi adalah komponen penting untuk memastikan integriti dan privasi data dalam sistem maklumat digital dan digunakan secara meluas dalam banyak konteks.

Keperluan keselamatan CHF terutamanya difahami dari segi rintangan mereka terhadap serangan pra-imej dan perlanggaran. Untuk CHF yang direka bentuk dengan baik, panjang hash adalah proksi yang baik untuk tahap keselamatan.

Walaupun kemunculan komputer kuantum yang melaksanakan algoritma Grover dan BHT secara teori mempengaruhi rintangan pra-imej dan perlanggaran CHF tradisional, panjang hash yang panjang yang sudah digunakan hari ini bermakna algoritma pencincangan kriptografi moden, seperti SHA-3, berkemungkinan kekal selamat kecuali ditemui serangan kriptanalisis yang belum diketahui.

Relevansi CHF terletak pada peranannya sebagai blok binaan asas untuk skim kriptografi tahan kuantum, memastikan maklumat digital kekal selamat walaupun berhadapan dengan potensi kemajuan masa depan dalam algoritma dan teknologi pengkomputeran kuantum.