ฟังก์ชัน hash ทางการเข้ารหัส

ในบทเรียนนี้เราจะดู cryptographic hash functions ซึ่งมีการใช้งานอย่างแพร่หลายในการตรวจสอบและ authentication อย่างรวดเร็ว

ภายในสิ้นบทเรียนเราจะได้ครอบคลุม:

• Cryptographic hash functions คืออะไร
• ตัวอย่าง Python code ที่แสดงการใช้งาน hash functions
• การมองที่การประยุกต์ใช้ cryptographic hashing
• ความปลอดภัยของ cryptographic hashing
• ภัยคุกคามต่ออัลกอริทึมเหล่านี้จากทั้งคอมพิวเตอร์แบบ classical และ quantum

บทนำสู่ cryptographic hashing

Hash functions เป็น construct ที่มีคุณค่าในการเข้ารหัส เนื่องจากช่วยให้การตรวจสอบมีความลับ ด้วยเหตุนี้ hash functions จึงเป็นส่วนประกอบสำคัญของกลไกสำหรับ authentication และ integrity ของข้อมูล เช่น hash-based message authentication codes (HMAC) และ digital signatures บทความนี้จะอภิปรายถึงแนวคิดพื้นฐานและการพิจารณาด้านความปลอดภัยที่เป็นพื้นฐานของ cryptographic hash functions และร่างความเปราะบางที่อาจเกิดขึ้นจากการถือกำเนิดของ quantum computing

หลักการพื้นฐานและการออกแบบของ hash functions

มีสถานการณ์มากมายที่จำเป็นต้องทำ authentication และการตรวจสอบ integrity อย่างราคาถูกและโดยไม่เปิดเผยข้อมูลส่วนตัวแก่ฝ่ายที่ทำการตรวจสอบ

ตัวอย่างเช่น เมื่อดาวน์โหลดซอฟต์แวร์จาก remote server จำเป็นต้องมีกลไกที่มีประสิทธิภาพในการตรวจสอบว่าซอฟต์แวร์ที่ดาวน์โหลดมาจริงๆ ยังไม่ถูกแก้ไขนับแต่ถูกสร้างโดยผู้เขียนต้นฉบับ ในทำนองเดียวกัน เมื่อทำ authentication ผู้ใช้ของ web applications ก็เป็นที่พึงประสงค์ที่จะใช้กลไกที่ไม่เกี่ยวข้องกับการจัดเก็บหรือส่งรหัสผ่านจริงๆ ทางกายภาพ ซึ่งอาจเป็นอันตรายต่อความลับ

Cryptographic hash functions (CHFs) จัดการกับความต้องการเหล่านี้ได้อย่างมีประสิทธิภาพและปลอดภัย

โดยพื้นฐาน cryptographic hash function รับ input (หรือ message) ที่มีความยาวตามอำเภอใจและส่งคืน string ขนาดคงที่ n-bits เป็น output ผลลัพธ์ของ CHF ยังเรียกว่า digest CHF ที่มีประโยชน์ควรมีคุณสมบัติสำคัญหลายประการ:

1. Uniformity: digests ที่ผลิตโดย CHF ควรกระจายตัวอย่างสม่ำเสมอและดูเหมือนสุ่ม เป้าหมายคือเพื่อให้แน่ใจว่า output ไม่รั่วข้อมูลเกี่ยวกับ input
2. Determinism: สำหรับ input ที่กำหนด CHF ต้องผลิต digest เดิมเสมอ นั่นคือมันต้องเป็น deterministic
3. Irreversibility: CHF เป็น one-way function ในแง่ที่ว่าเมื่อได้รับ digest ควรเป็นไปไม่ได้ที่จะ invert การ hashing เพื่อได้ input
4. Approximate injectivity: แม้ว่า CHFs จะเป็นฟังก์ชัน many-to-one แต่ดูเหมือนว่าจะเป็นฟังก์ชัน one-to-one ซึ่งทำได้โดยการรวม output space ขนาดมหึมากับ avalanche effect ที่การเปลี่ยนแปลงเล็กน้อยใน input นำไปสู่ digests ที่แตกต่างกันอย่างสุดขีด ลักษณะนี้เรียกว่า approximate injectivity

ด้วยเหตุนี้ จึงเป็นไปได้ที่จะตรวจสอบข้อมูลกับ instance ต้นฉบับโดยการเปรียบเทียบ digest ของข้อมูลกับ digest ของต้นฉบับ

• ถ้า digests สองอันตรงกัน เราสามารถมั่นใจด้วยความน่าจะเป็นสูงว่าข้อมูลเหมือนกับต้นฉบับ
• ถ้า digests แตกต่างกัน เราสามารถแน่ใจได้ว่าข้อมูลถูกแก้ไขหรือไม่แท้จริง

เนื่องจาก CHF digests เองไม่เปิดเผยเนื้อหาจริงของข้อมูลหรือต้นฉบับ จึงเปิดใช้งานการตรวจสอบในขณะที่รักษาความเป็นส่วนตัว

Mathematical description

สามารถนิยาม hash function $H$ ได้ว่า:

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

โดยที่ $Σ^*$ คือชุดของ strings ที่เป็นไปได้ทั้งหมดซึ่งเราอาจพิจารณาเป็น binary strings ที่มีความยาวใดก็ได้

ข้อเท็จจริงที่ว่าขนาดของ input domain $Σ^*$ ของ $H$ ไม่มีขอบเขตในขณะที่ co-domain $\{0,1\}^n$ มีขอบเขต หมายความว่า $H$ จำเป็นต้องเป็น many-to-one mapping inputs จำนวนอนันต์ไปยัง n-bit string ที่กำหนดใดๆ

คุณสมบัติของ uniformity และ determinism ถูกรวบรวมได้ดีภายใน random oracle model ของ cryptographic hashing

ตัวอย่าง cryptographic hashing ใน Python ด้วย SHA-256

ตัวอย่างง่ายๆ นี้แสดง cryptographic hashing โดยใช้อัลกอริทึม SHA-256 ที่นิยมซึ่งให้บริการโดย Python library cryptography อันดับแรกเราแสดงให้เห็นว่าความแตกต่างเล็กน้อยใน plain texts นำไปสู่ความแตกต่างที่มากมายใน hash digests

# 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

ข้อความสองข้อความต่างกันเพียงหนึ่งตัวอักษร

ต่อไป เรา instantiate objects hash เพื่อเปิดใช้งานกระบวนการ hashing ซึ่งเกี่ยวข้องกับการเรียกใช้สองวิธี: update และ finalize

เราเห็นว่าเนื่องจาก avalanche effect ใน SHA-256 CHF ความแตกต่างหนึ่งตัวอักษรใน input messages ให้ digests สองอันที่แตกต่างกันมาก

# 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

การประยุกต์ใช้ cryptographic hashing

คุณสมบัติเฉพาะของ CHFs ทำให้เหมาะกับการใช้งานที่หลากหลาย:

• การตรวจสอบ data integrity: Hash functions สามารถใช้สร้าง checksum สำหรับชุดข้อมูล การปรับเปลี่ยนข้อมูลใดๆ ไม่ว่าจะตั้งใจหรือไม่ จะส่งผลให้ checksum แตกต่างกัน แจ้งเตือนระบบหรือผู้ใช้ถึงการเปลี่ยนแปลง checksum ยังมักขนาดเล็กกว่าข้อมูลต้นฉบับมาก ซึ่งทำให้การเปรียบเทียบ checksum รวดเร็วมาก

รูปที่ 1 Secure hashing สำหรับ data integrity

• Digital signatures: Cryptographic hashes มีความสำคัญต่อการทำงานของ digital signatures เนื่องจากเกี่ยวข้องกับการเปรียบเทียบ messages ที่ hash ด้วย cryptography เพื่อสร้าง authenticity และ integrity ในขณะที่รักษาความเป็นส่วนตัว

รูปที่ 2 Digital signatures

• Blockchain และ cryptocurrencies: Cryptocurrencies เช่น Bitcoin พึ่งพา CHFs อย่างมาก โดยเฉพาะอย่างยิ่งในการสร้าง transaction integrity และเปิดใช้งานกลไก consensus เช่น proof of work

ความปลอดภัยของ cryptographic hashing

ความปลอดภัยของ CHF มักประเมินตามความทนทานต่อการโจมตีสองประเภท: pre-image และ collision

การทนทานต่อ pre-image

Pre-image resistance หมายความว่าเมื่อได้รับ digest ควรเป็นไปไม่ได้ที่จะหา input

สิ่งนี้เกี่ยวข้องกับคุณสมบัติ one-way ของ CHFs

CHF ที่ดีได้รับการออกแบบในลักษณะที่ฝ่ายที่ต้องการดำเนินการ pre-image attack ไม่มีทางเลือกที่ดีกว่าการ brute force ซึ่งมี time complexity $2^n$

mathematical details

เมื่อมี CHF $H$ และ digest $g$ ควรเป็นไปไม่ได้ในเชิงคำนวณที่จะหา input $m$ ใดๆ จาก pre-image ของ $g$ ที่ $H(m) = g$

การทนทานต่อ collision

Collision resistance หมายความว่าเป็นเรื่องยากที่จะหา inputs สองอันที่ต่างกันซึ่ง hash ไปยัง digest เดิม

Cryptographic hash collision เกิดขึ้นเมื่อ inputs สองอัน hash ไปยัง digest เดิม แม้ว่า collisions จะมีอยู่อย่างหลีกเลี่ยงไม่ได้เนื่องจากธรรมชาติ many-to-one ของ CHFs แต่ CHF ที่ดีก็ยังทำให้เป็นไปไม่ได้ที่จะหาหนึ่งตามต้องการ

Collision resistance มีความสำคัญต่อการใช้งานเช่น digital signatures และ certificates ที่อาจเกิดความหายนะถ้าฝ่ายที่ไม่หวังดีสามารถสร้างของปลอมที่ hash ไปยังค่าเดิมได้

mathematical details of hash collisions

สามารถหา $m_1, m_2$ ได้โดยที่ $H(m_1) = H(m_2)$

ความยาว hash

Collision resistance เป็นข้อกำหนดที่ยากกว่า pre-image resistance และจำเป็นต้องมีความยาว output ยาวเป็นสองเท่าของที่จำเป็นสำหรับ pre-image resistance ทั้งนี้เพราะการโจมตี brute force ที่รู้จักกันว่า birthday attack ซึ่งสามารถใช้ระบุ hash collisions มี time complexity $2^{n/2}$

ในกรณีที่ไม่มีจุดอ่อนในการวิเคราะห์ทางการเข้ารหัส ความปลอดภัยของ hash function จึงได้รับอิทธิพลเป็นหลักจากความยาว hash ยิ่ง hash ยาวยิ่งปลอดภัยมากขึ้น เนื่องจากยากขึ้นในการโจมตี brute force

Cryptographic hash functions ที่ใช้กันทั่วไป

ตารางต่อไปนี้แสดง cryptographic hash functions ที่ใช้กันทั่วไป พร้อมกับความยาว hash และโดเมนการประยุกต์ใช้หลัก:

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

• MD5 และ SHA-1 แม้ยังพบในแอปพลิเคชันที่มีความอ่อนไหวน้อยกว่า แต่ถือว่าล้าสมัยในแง่ของ collision resistance และไม่แนะนำสำหรับระบบใหม่ SHA-256 ซึ่งเป็นส่วนหนึ่งของตระกูล SHA-2 ถูกใช้งานอย่างแพร่หลายและปลอดภัยในปัจจุบันสำหรับแอปพลิเคชันส่วนใหญ่
• SHA-3 เป็นมาตรฐานใหม่กว่าที่ NIST เลือกในปี 2015 ว่าเป็นผู้ชนะการแข่งขัน NIST hash function ออกแบบมาเป็น drop-in replacement สำหรับ SHA-2 แต่ยังมีลักษณะภายในบางอย่างที่แตกต่างและทนทานต่อการโจมตีบางประเภทที่อาจมีประสิทธิผลต่อ SHA-2
• Blake2 และ Blake3 เป็น cryptographic hash functions ที่เร็วกว่า MD5, SHA-1, SHA-2 และ SHA-3 แต่อย่างน้อยก็ปลอดภัยเท่ากับมาตรฐานล่าสุด SHA-3 พวกมันถูกนำมาใช้มากขึ้นในระบบใหม่ โดยเฉพาะที่ความเร็วสำคัญ

ความเสี่ยงของ quantum ต่อ cryptographic hashing แบบดั้งเดิม

ภัยคุกคาม quantum หลักต่อ cryptographic hashing มาจากการโจมตี brute force

เมื่อได้รับ digest เฉพาะ ผู้โจมตีจะลอง inputs สุ่มจนกว่าจะพบ input ที่ให้ digest เดิม

เมื่อมี $n$ bits ใน input มีค่า $2^n$ ที่เป็นไปได้ ดังนั้น ผู้โจมตีต้องลอง inputs ประมาณ $2^{n-1}$ เพื่อมีโอกาสมากกว่า 50% ในการสำเร็จ

อัลกอริทึมของ Grover

สำหรับบริบทการค้นหาที่ไม่มีโครงสร้างเช่นนี้ Grover's algorithm สามารถให้ quadratic speedup โดยใช้เทคนิคที่รู้จักกันว่า quantum amplitude amplification ลด time complexity ของ pre-image attack เป็น $2^{n/2}$

ในทางปฏิบัติ หมายความว่า CHF 256-bit ซึ่งปัจจุบันถือว่าปลอดภัยต่อ pre-image attacks โดยคอมพิวเตอร์แบบ classical จะให้ระดับความปลอดภัยเดียวกับ CHF 128-bit เมื่อเผชิญกับผู้โจมตี quantum ที่ใช้ Grover's algorithm

Grover's algorithm โดยตัวเองไม่เป็นที่ทราบว่าให้ quantum speedups เพิ่มเติมเกี่ยวกับ collision attacks นอกเหนือจากขีดจำกัดที่กำหนดโดย birthday attack ซึ่งสามารถดำเนินการบนคอมพิวเตอร์แบบ classical เนื่องจาก classical birthday attack กำหนดให้ CHFs ต้องใช้ความยาว hash ที่ยาวเป็นสองเท่าของที่จำเป็นสำหรับ pre-image resistance แล้ว ข้อเท็จจริงที่ว่า Grover search ลดความยาว hash อย่างมีประสิทธิผลเทียบเท่ากับครึ่งหนึ่งเกี่ยวกับ pre-image attacks จึงไม่เป็นภัยคุกคามที่ปฏิบัติได้จริง

ตัวอย่างเช่น ในกรณีของ SHA-256 การดำเนินการประมาณ $2^{128}$ operations เพื่อดำเนินการ Grover-assisted pre-image attack ก็ยังไม่สามารถทำได้จริงในอนาคตอันใกล้

อัลกอริทึม BHT

Quantum algorithm ที่รวมลักษณะของ birthday attack กับ Grover search ถูกเสนอในปี 1997 โดย Brassard, Høyer และ Tapp (BHT) และให้ scaling ทางทฤษฎีของ $O(2^{n/3})$ สำหรับการหา hash collisions อย่างไรก็ตาม scaling ที่ดีขึ้นนี้ขึ้นอยู่กับการมีอยู่ของเทคโนโลยี quantum random access memory QRAM ซึ่งยังไม่มีอยู่ในปัจจุบัน

หากไม่มี QRAM scaling ที่ทำได้จริงคือ $\tilde{O}(2^{2n/5})$ และสำหรับความยาว hash ที่ใช้อยู่ในปัจจุบัน การปรับปรุงเล็กน้อยในความสามารถในการหา collision เมื่อเทียบกับ birthday attack ไม่ถือว่าเป็นภัยคุกคามที่สำคัญ

สรุป

Cryptographic hash functions เป็นส่วนประกอบสำคัญสำหรับการรับประกัน data integrity และความเป็นส่วนตัวในระบบข้อมูลดิจิทัล และพบการประยุกต์ใช้อย่างแพร่หลายในหลายบริบท

ข้อกำหนดด้านความปลอดภัยของ CHFs ส่วนใหญ่เข้าใจในแง่ของความทนทานต่อ pre-image และ collision attacks สำหรับ CHFs ที่ออกแบบมาดี ความยาว hash เป็นตัวแทนที่ดีของระดับความปลอดภัย

แม้ว่าการถือกำเนิดของคอมพิวเตอร์ quantum ที่รัน Grover และ BHT algorithms ในทางทฤษฎีจะมีผลต่อ pre-image และ collision resistance ของ CHFs แบบดั้งเดิม แต่ความยาว hash ที่ยาวซึ่งใช้ในปัจจุบันหมายความว่าอัลกอริทึม cryptographic hashing สมัยใหม่เช่น SHA-3 มีแนวโน้มที่จะยังคงปลอดภัยอยู่ โดยยกเว้นการค้นพบการโจมตีทางการวิเคราะห์ที่ยังไม่รู้จัก

ความเกี่ยวข้องของ CHFs อยู่ที่บทบาทของพวกมันในฐานะ building block พื้นฐานสำหรับโครงการ cryptographic ที่ทนทานต่อ quantum รับประกันว่าข้อมูลดิจิทัลจะยังคงปลอดภัยแม้เผชิญกับความก้าวหน้าที่อาจเกิดขึ้นในอนาคตของ quantum computing algorithms และเทคโนโลยี