Mga cryptographic hash function

Sa araling ito, tatalakayin natin ang mga cryptographic hash function na malawakang ginagamit sa mabilis na pag-validate at authentication.

Sa pagtatapos ng araling ito, matututunan natin ang:

• Ano ang mga cryptographic hash function
• Mga halimbawa ng Python code na nagpapakita ng paggamit ng hash function
• Isang tingin sa mga aplikasyon ng cryptographic hashing
• Ang seguridad ng cryptographic hashing
• Mga banta sa mga algorithm na ito mula sa parehong klasikal at quantum na mga kompyuter

Panimula sa cryptographic hashing

Ang mga hash function ay isang mahalagang konstruksyon sa cryptography dahil nakakatulong ito sa pag-enable ng validation nang may confidentiality. Dahil dito, ang mga hash function ay isang mahalagang bahagi ng mga mekanismo para sa data authentication at integrity, tulad ng hash-based message authentication codes (HMAC) at digital signature. Tatalakayin ng artikulong ito ang mga pangunahing ideya at konsiderasyon sa seguridad na sumusuporta sa mga cryptographic hash function, at ilalahad ang mga potensyal na kahinaan dulot ng pagdating ng quantum computing.

Pangunahing dahilan at disenyo ng mga hash function

Maraming sitwasyon kung saan kailangang isagawa ang authentication at integrity verification nang mura at hindi ibinubunyag ang pribadong impormasyon sa partidong nagsasagawa ng validation.

Halimbawa, kapag nagda-download ng software mula sa isang remote server, kailangan ng isang mahusay na mekanismo upang ma-verify na ang software na na-download ay hindi nabago mula nang likhain ito ng orihinal na may-akda. Gayundin, kapag ina-authenticate ang mga user ng mga web application, magiging kapaki-pakinabang ang isang mekanismo na hindi nangangailangan ng pisikal na pag-iimbak o pagpapadala ng aktwal na mga password, na maaaring makompromiso ang kanilang confidentiality.

Ang mga cryptographic hash function (CHF) ay epektibo at ligtas na tumutugon sa ganitong mga pangangailangan.

Sa pangunahin, ang isang cryptographic hash function ay tumatanggap ng input (o mensahe) na may arbitrary na haba at nagbabalik ng fixed-size na string ng n-bits bilang output. Ang output ng isang CHF ay tinatawag ding digest. Ang isang kapaki-pakinabang na CHF ay dapat matugunan ang ilang mahahalagang katangian:

1. Pagkakapareho (Uniformity): Ang mga digest na ginawa ng isang CHF ay dapat na pantay-pantay ang distribusyon at mukhang random. Ang layunin ay tiyaking walang impormasyong nakalabas ang output tungkol sa input.
2. Determinismo (Determinism): Para sa isang ibinigay na input, ang isang CHF ay laging dapat gumawa ng parehong digest, ibig sabihin, ito ay dapat na deterministic.
3. Irreversibility: Ang isang CHF ay isang one-way function sa kahulugang, kapag ibinigay ang isang digest, hindi dapat maisagawa ang pag-invert ng hashing upang makuha ang input.
4. Approximate injectivity: Kahit na ang mga CHF ay many-to-one na mga function, dapat silang mukhang one-to-one na mga function. Nagagawa ito sa pamamagitan ng pagsasama ng napakalaking laki ng output space at ng avalanche effect kung saan ang maliliit na pagbabago sa input ay nagbubunga ng lubos na magkakaibang mga digest. Ang katangiang ito ay kilala bilang approximate injectivity.

Dahil dito, posibleng i-validate ang isang piraso ng data laban sa orihinal na instance sa pamamagitan ng paghahambing ng digest ng data sa digest ng orihinal.

• Kung magkatugma ang dalawang digest, maaari tayong maging tiwala nang mataas na posibilidad na pareho ang data sa orihinal.
• Kung magkaiba ang mga digest, maaari tayong maging sigurado na ang data ay napalitan o hindi tunay.

Dahil ang mga CHF digest mismo ay hindi nagbubunyag ng aktwal na nilalaman ng data o ng orihinal, nagbibigay-daan ang mga ito sa pag-validate habang pinapanatili ang privacy.

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.

Halimbawa ng cryptographic hashing sa Python gamit ang SHA-256

Ipinapakita ng simpleng halimbawang ito ang cryptographic hashing gamit ang sikat na algorithm na SHA-256 na ibinibigay ng Python library na cryptography. Una, ipinapakita natin kung paano ang isang maliit na pagkakaiba sa mga plain text ay nagbubunga ng napakalaking pagkakaiba sa mga hash digest.

# 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

Ang dalawang mensahe ay nagkakaiba ng eksakto sa isang karakter.

Susunod, mag-instantiate tayo ng mga hash object upang paganahin ang proseso ng hashing, na kinabibilangan ng mga tawag sa dalawang pamamaraan: update at finalize.

Makikita natin na dahil sa avalanche effect sa SHA-256 CHF, ang isang-karakter na pagkakaiba sa mga input na mensahe ay nagbubunga ng dalawang napaka-magkaibang digest.

# 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

Mga aplikasyon ng cryptographic hashing

Ang natatanging mga katangian ng mga CHF ay nagpapahintulot sa kanila para sa malawak na hanay ng mga aplikasyon:

• Mga tseke ng integridad ng data (Data integrity checks): Maaaring gamitin ang mga hash function upang lumikha ng checksum para sa isang set ng data. Ang anumang pagbabago sa data, sinasadya man o hindi, ay magreresulta sa ibang checksum, na nagaalerto sa mga sistema o gumagamit ng pagbabago. Ang checksum ay karaniwang mas compact din kaysa sa orihinal na data, na nagpapabilis ng mga paghahambing ng checksum.

Figure 1. Secure hashing para sa integridad ng data

• Mga digital signature: Ang mga cryptographic hash ay mahalaga sa pagpapatakbo ng mga digital signature dahil kinabibilangan ang mga ito ng paghahambing ng mga cryptographically hashed na mensahe upang maitaguyod ang authenticity at integrity habang pinapanatili ang privacy.

Figure 2. Mga digital signature

• Blockchain at mga cryptocurrency: Ang mga cryptocurrency tulad ng Bitcoin ay lubos na umaasa sa mga CHF, lalo na sa paglikha ng integridad ng transaksyon at pag-enable ng mga consensus mechanism tulad ng proof of work.

Seguridad ng cryptographic hashing

Ang seguridad ng isang CHF ay karaniwang sinusuri batay sa pagtitibay laban sa dalawang uri ng pag-atake: pre-image at collision.

Pagtitibay sa pre-image

Ang pagtitibay sa pre-image ay nangangahulugang kapag ibinigay ang isang digest, hindi dapat maisagawa ang paghahanap ng input.

Ito ay kaugnay ng one-way na katangian ng mga CHF.

Ang isang magandang CHF ay idinisenyo sa paraang ang isang partidong nagnanais na magsagawa ng pre-image attack ay walang mas magandang pagpipilian kundi ang brute force na paraan, na may time complexity na $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$.

Pagtitibay sa collision

Ang pagtitibay sa collision ay nangangahulugang mahirap mahanap ang dalawang magkaibang input na nagha-hash sa parehong digest.

Ang isang cryptographic hash collision ay nangyayari kapag ang dalawang input ay nagha-hash sa parehong digest. Kahit na ang mga collision ay hindi maiiwasang umiiral dahil sa many-to-one na katangian ng mga CHF, ang isang magandang CHF ay nagpapahirap pa rin na mahanap ang isa nang kusang-loob.

Ang pagtitibay sa collision ay mahalaga para sa mga aplikasyon tulad ng mga digital signature at sertipiko, kung saan maaaring mapanganib kung ang isang malisyosong partido ay makakagawa ng pamalsipikasyon na nagha-hash sa parehong halaga.

mathematical details of hash collisions

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

Haba ng hash

Ang pagtitibay sa collision ay isang mas mahirap na kinakailangan kaysa sa pagtitibay sa pre-image at nangangailangan ng mga output length na dalawang beses na mas mahaba kaysa sa kinakailangan para sa pagtitibay sa pre-image. Ito ay dahil ang isang brute force attack na kilala bilang birthday attack, na maaaring gamitin upang makilala ang mga hash collision, ay may time complexity na $2^{n/2}$.

Sa kawalan ng mga kahinaan sa cryptanalysis, ang seguridad ng isang hash function ay pangunahing naiimpluwensyahan ng haba ng hash nito. Habang mas mahaba ang hash, mas ligtas ito, dahil mas nahihirapan ang mga brute force attack.

Mga karaniwang ginagamit na cryptographic hash function

Inililista ng sumusunod na talahanayan ang ilang karaniwang ginagamit na cryptographic hash function, kasama ang kanilang mga haba ng hash at pangunahing mga larangan ng aplikasyon:

Hash Function	Output Length (bits)	Common Applications
MD5	128	File integrity checking, older systems, non-crypto uses
SHA-1	160	Legacy systems, Git for version control
SHA-256	256	Cryptocurrency (Bitcoin), digital signatures, certificates
SHA-3	Variable (up to 512)	Various cryptographic applications, successor to SHA-2
Blake2	Variable (up to 512)	Cryptography, replacing MD5/SHA-1 in some systems
Blake3	Variable (up to 256)	Cryptography, file hashing, data integrity

• Ang MD5 at SHA-1, kahit pa nakikita pa rin sa mga hindi gaanong sensitibong aplikasyon, ay itinuturing na deprecated pagdating sa pagtitibay sa collision at hindi inirerekomenda para sa mga bagong sistema. Ang SHA-256, bahagi ng pamilyang SHA-2, ay malawakang ginagamit at kasalukuyang ligtas para sa karamihan ng mga aplikasyon.
• Ang SHA-3 ay isang mas bagong pamantayan na pinili ng NIST noong 2015 bilang nanalo sa NIST hash function competition. Idinisenyo ito bilang drop-in replacement para sa SHA-2, ngunit mayroon din itong ilang magkakaibang panloob na katangian at lumalaban sa ilang uri ng pag-atake na maaaring epektibo laban sa SHA-2.
• Ang Blake2 at Blake3 ay mga cryptographic hash function na mas mabilis kaysa sa MD5, SHA-1, SHA-2, at SHA-3, ngunit hindi bababa sa seguridad kaysa sa pinakabagong pamantayan, SHA-3. Lalong ginagamit ang mga ito sa mga bagong sistema, lalo na kung mahalaga ang bilis.

Mga quantum na panganib sa tradisyonal na cryptographic hashing

Ang pangunahing quantum na banta sa cryptographic hashing ay nagmumula sa mga brute force attack.

Kapag ibinigay ang isang partikular na digest, susubukan ng isang attacker ang mga random na input hanggang mahanap niya ang isa na gumagawa ng parehong digest.

Sa $n$ bits sa input, mayroon $2^n$ mga posibleng halaga. Kaya naman, kailangan ng attacker na subukan ang mga $2^{n-1}$ input upang magkaroon ng higit sa 50% na tsansa ng tagumpay.

Algoritmo ni Grover

Para sa ganitong hindi nakastrukturang konteksto ng paghahanap, ang algoritmo ni Grover ay maaaring magbigay ng quadratic speedup gamit ang isang teknik na kilala bilang quantum amplitude amplification, na nagpapababa ng time complexity ng isang pre-image attack sa $2^{n/2}$.

Sa praktikal na termino, nangangahulugan ito na ang isang 256-bit CHF, na kasalukuyang itinuturing na ligtas laban sa mga pre-image attack ng mga klasikal na kompyuter, ay magbibigay ng parehong antas ng seguridad gaya ng isang 128-bit CHF kapag hinaharap ng isang quantum attacker na gumagamit ng algoritmo ni Grover.

Ang algoritmo ni Grover mismo ay hindi kilalang nagbibigay ng karagdagang quantum speedup pagdating sa mga collision attack na higit pa sa limitasyon na itinakda ng birthday attack, na maaaring isagawa sa mga klasikal na kompyuter. Dahil ang klasikal na birthday attack ay nangangailangan na ng mga CHF na gumamit ng mga hash length na dalawang beses na mas mahaba kaysa sa kinakailangan para sa pagtitibay sa pre-image, ang katotohanang epektibong hinhati ng Grover search ang hash length pagdating sa mga pre-image attack ay hindi nagdudulot ng praktikal na banta.

Halimbawa, sa kaso ng SHA-256, ang pagsasagawa ng mga $2^{128}$ operasyon upang maisagawa ang isang Grover-assisted pre-image attack ay magiging hindi pa rin magagawa sa nakikitang hinaharap.

Algoritmo ng BHT

Isang quantum algorithm na pinagsama ang mga aspeto ng birthday attack at Grover search ang iminungkahi noong 1997 ni Brassard, Høyer, at Tapp (BHT) at nagbibigay ng teoretikal na scaling na $O(2^{n/3})$ para sa paghahanap ng mga hash collision. Gayunpaman, ang pinahusay na scaling na ito ay nakasalalay sa pag-iral ng quantum random access memory QRAM na teknolohiya, na kasalukuyang hindi pa umiiral.

Nang wala ang QRAM, ang maisasagawang scaling ay $\tilde{O}(2^{2n/5})$ at para sa mga hash length na kasalukuyang ginagamit, ang marginal na pagpapabuti na ito sa kakayahang mahanap ang collision kumpara sa birthday attack ay hindi kumakatawan sa isang kritikal na banta.

Buod

Ang mga cryptographic hash function ay isang mahalagang bahagi sa pagtiyak ng integridad ng data at privacy sa mga digital na sistema ng impormasyon at malawak na ginagamit sa maraming konteksto.

Ang mga kinakailangan sa seguridad ng mga CHF ay pangunahing nauunawaan sa mga tuntunin ng kanilang pagtitibay sa mga pre-image at collision attack. Para sa mga mahusay na idisenyong CHF, ang haba ng hash ay isang magandang proxy para sa antas ng seguridad.

Kahit na ang pagdating ng mga quantum computer na nagpapatakbo ng mga algoritmo ng Grover at BHT ay teoretikal na nakakaapekto sa pre-image at collision resistance ng mga tradisyonal na CHF, ang mahabang haba ng hash na ginagamit na ngayon ay nangangahulugang ang mga modernong cryptographic hashing algorithm, tulad ng SHA-3, ay malamang na mananatiling ligtas maliban na lang sa matuklasan ang mga hindi pa kilalang cryptanalytic attack.

Ang kaugnayan ng mga CHF ay nasa kanilang papel bilang isang pangunahing building block para sa mga quantum-resistant na cryptographic scheme, na tinitiyak na ang digital na impormasyon ay nananatiling ligtas kahit na sa harap ng mga potensyal na pag-unlad sa mga quantum computing algorithm at teknolohiya sa hinaharap.