[Cybersecurity] มารู้จักแฮชฟังก์ชันให้มากขึ้น
สำหรับคนที่เรียนทางด้านวิทยาการคอมพิวเตอร์คงจะคุ้นเคยกับสิ่งที่เรียกว่าแฮชฟังก์ชันมาบ้างแล้ว ซึ่งหน้าที่หลักของมันก็คือเปลี่ยนข้อมูล input ใด ๆ ให้กลายเป็น output ที่มีขนาดคงที่
ยกตัวอย่างเช่นไฟล์ pdf ไฟล์หนึ่งมีขนาด 2 เมกะไบต์ เมื่อนำมาไฟล์นี้มาผ่านฟังก์ชันแฮชจะได้ output ขนาดคงที่เช่น 160 บิต โดยผลลัพธ์ที่ได้มาขนาด 160 บิตนี้ จะเป็น ตัวแทน ของไฟล์ pdf ที่มีขนาด 2 เมกะไบต์
ก่อนอื่นขอนิยามคำศัพท์ก่อนว่า output ที่ได้จากฟังก์ชันแฮชมีชื่อเรียกว่า digest ซึ่งต่างจากกระบวนการ encryption ที่เราจะเรียกผลลัพธ์ว่า ciphertext
การที่ข้อมูล plaintext เปลี่ยนแปลงเพียงเล็กน้อยจะส่งผลทำให้ digest เกิดการเปลี่ยนแปลงมหาศาล (ดูตัวอย่างในรูปที่ 1) ซึ่งหนึ่งในคุณสมบัติที่ทำให้เกิดเหตุการณ์แบบนี้เรียกว่า collision resistance ซึ่งจะกล่าวถึงในช่วงต่อไปของบทความ
สมมติว่าฟังก์ชันแฮชมีขนาดของ output 10 บิต เราจะได้ output range space เท่ากับ 2¹⁰ หรือ 1024 รูปแบบ
แสดงว่าสักวันหนึ่งมันจะได้ output เป็น digest ที่ซ้ำกัน เพราะ input ที่เป็นไปได้มีจำนวนรูปแบบเป็นอนันต์ แต่ output ถูกจำกัดไว้เพียง 1024 รูปแบบ
ยกตัวอย่างให้เห็นภาพง่าย ๆ คือ ถ้าเรามีกรงนกพิราบอยู่ 10 กรง (ในที่นี้แทนจำนวนความเป็นไปได้ของ output) แต่เรามีจำนวนนกพิราบอยู่ 11 ตัว (ในที่นี้แทนรูปแบบของ input ที่เป็น plaintext) มันคงจะต้องมีกรงนกพิราบสักกรงหนึ่งที่มีนกพิราบมากกว่า 1 ตัว
ต่อไปเราลองมาวิเคราะห์แฮชฟังก์ชันแฮชกันว่าคุณสมบัติของฟังก์ชันแฮชที่ดีควรเป็นอย่างไร
โดยหลักการของฟังก์ชันแฮช มันต้องมีคุณสมบัติเป็น uniform hashing กล่าวคือ หากเรามี range space อยู่ 2⁴ = 16 รูปแบบ ซึ่งแทนด้วยจำนวนตะกร้าตามรูปที่ 2
จะเห็นว่าตะกร้าเบอร์ 4 และเบอร์ 14 เกิดการชนกัน (collision) กล่าวคือมี input มากกว่า 1 ตัวให้ ผลลัพธ์ digest ที่ตรงกัน
ลักษณะของ uniform คือ เราไม่สามารถทำนายได้อย่างชัดเจนว่าผลลัพธ์ digest มันจะไปตกที่ตะกร้าเบอร์ไหน เพราะมันมีความน่าจะเป็นเท่ากันที่มันจะออกมาเป็น digest ใดๆ ก็ได้ ซึ่งถ้าลองจินตนาการว่าหากฟังก์ชันแฮชไม่มีคุณสมบัตินี้ ผลลัพธ์ digest ที่ได้ออกมามันจะกระจุกอยู่บริเวณใดบริเวณหนึ่ง
หนึ่งในคุณสมบัติที่สำคัญของศาสตร์ทางด้าน cryptography คือ เราต้องการที่จะลดการเกิด collision เพราะสักวันหนึ่งมันจะต้องเกิดขึ้น (เราไม่สามารถหลีกเลี่ยงกฎของกรงนกพิราบได้)
คำถามก็คือ จะทำอย่างไรให้มีความเป็นไปได้ต่ำมาก ๆ ที่จะเกิด collision?
เรามาทบทวนพื้นฐานของวิชาความน่าจะเป็นกันก่อนสักเล็กน้อย
สมมติว่าเรามีตะกร้าจำนวน M ตะกร้า แทน digest ที่เป็นไปได้ทั้งหมด
จำนวนครั้งในการทดลอง (input trials) ก่อนที่จะเกิด collision โดยมีความน่าจะเป็นมากกว่า 50 เปอร์เซ็นต์ จะประมาณ
โดยที่ค่า Pi และค่า 2 เป็นค่าคงที่ที่หารกันแล้วได้ใกล้เคียงกับ 1 ซึ่งไม่มีนัยยะสำคัญหาก M มีค่าเยอะ ๆ
ดังนั้น ค่าความน่าจะเป็นที่จะเกิด collision มี order ประมาณรากที่สองของ M เท่านั้น ซึ่งปัญหานี้มีชื่อเรียกเท่ ๆ ว่า Birthday problem
Birthday problem คือปรากฎการณ์ที่บอกว่าหากเรามีจำนวนคนอยู่ 23 คน โอกาสที่คนในกลุ่มนี้มีวันเกิดเป็นวันเดียวกันอย่างน้อย 1 คู่สูงถึง 50 เปอร์เซ็นต์ ซึ่งสามารถดูได้จากรูปที่ 3
เช่น output ที่ได้จากแฮชฟังก์ชันมี 2²⁰ = 1,048,576 รูปแบบ หากเราทำการแฮชข้อมูล plaintext ที่ไม่ซ้ำกันไปเรื่อย ๆ เพียงแค่ 1,284 ชุด เราจะมีโอกาสเกิด digest collision เกิน 50%
จะเห็นว่าจำนวนครั้งในการแฮชลดลงเยอะมาก จากเดิมที่ต้องใช้ 2²⁰ รูปแบบ เหลือเพียงแค่ประมาณ 2¹⁰ ครั้งเท่านั้น ซึ่งที่มันน้อย เพราะเราไม่ได้ระบุว่าเป็น digest อันไหน (เหมือนเราไม่ได้ระบุวันเกิดว่า ต้องเป็นคู่ที่เกิดวันที่ 1 มีนาคมเท่านั้นนะ ถ้าเป็นคำถามแบบนี้ความน่าจะเป็นจะยิ่งน้อย กล่าวคือต้องใช้จำนวนคนมากขึ้นถึงจะเกิด collision)
คำถามอีกอันคือ จะต้องแฮชข้อมูลกี่ครั้ง (กี่ input trials) ที่จะทำให้ทุกตะกร้ามี output อย่างน้อย 1 อัน ซึ่งก็มีชื่อเรียกเท่ ๆ อีกเหมือนกัน เรียกสิ่งนี้ว่า Coupon collector’s problem ซึ่งจะแสดงในรูปที่ 4
อธิบายให้เห็นภาพง่าย ๆ คือ สมมติว่าเซเว่นมีแคมเปญในการสะสมแสตมป์ให้ครบ 77 จังหวัด แน่นอนว่าตอนเริ่มเก็บสะสมมันได้จังหวัดที่ไม่ซ้ำกัน แต่พอเก็บไปเรื่อย ๆ จะเจอปัญหาในการหาจังหวัดท่ีขาดยากขึ้น (เช่นจังหวัดบึงกาฬ หาเท่าไหร่ก็หาไม่เจอ) ซึ่งก็มีคนพิสูจน์ทางสถิติว่าจำนวนครั้งที่จะได้ครบเป็นฟังก์ชันของลอการิทึมธรรมชาติ
ซึ่งหากเรามี 77 จังหวัด จำนวนครั้งที่จะเก็บสะสมแสตมป์ให้ครบทั้ง 77 จังหวัดเท่ากับ n ln(n)ครั้ง = 77log(77) = 335 ครั้ง
ทีนี้เรามาเข้าเรื่องคุณสมบัติของแฮชฟังก์ชันที่ปลอดภัยกันสักที
คุณสมบัติของแฮชฟังก์ชันที่ปลอดภัย
เนื่องจากว่าเราต้องการให้ digest เป็นตัวแทนของ input เราจะต้องปกป้อง input ที่แท้จริงผ่านคุณสมบัติ 3 อย่างต่อไปนี้
- one-way resistance
มันต้องยากมาก ๆ ที่จะกลับไปหา plaintext จาก digest
H(M): one-way resistance - weak collision resistance
สมมติว่าเรามี plaintext 1 ตัว ยากมากที่จะหา plaintext ตัวที่ 2 ที่ให้ digest เหมือนกัน - strong collision resistance
การหา digest คู่ใด ๆ ที่ซ้ำกันเป็นไปได้ยาก (หาวิธีเลี่ยง birthday problem)
มีการพิสูจน์ว่า ถ้าเราได้คุณสมบัติ strong collision resistance เราจะได้คุณสมบัติ weak collision resistance และ one-way resistance ด้วยโดยอัตโนมัติ
หากมีคุณสมบัติ strong collision resistance จะได้คุณสมบัติ weak collision resistance ด้วย (strong collision resistance — > weak collision resistance)
*เครื่องหมาย — > แทน implies
- พิสูจน์ทฤษฎีนี้ได้อย่างตรงไปตรงมา เพราะการหาค่า M2 โดยกำหนด M1 เป็นเสมือนกรณีพิเศษของการหาค่าทั้ง M1 และ M2 เมื่อเรากำหนดให้ M1 คงที่
หากมีคุณสมบัติ weak collision resistance จะได้คุณสมบัติ one-way resistance ด้วย
(weak collision resistance — > one-way resistance)
- พิสูจน์โดยใช้ contrapositive: (ถ้า p — > q พิสูจน์ยาก เราจะพิสูจน์ ~q — > ~p) ถ้าไม่มี one-way resistance จะเกิด weak collision resistance ไม่ได้
- จะได้ว่าถ้าเรามี digest h = H(M1) เราสามารถหา M1 ที่ H(M2) = h ได้โดยในกรณีที่ domain มีขนาดไม่จำกัด M1 และ M2 จะแตกต่างกัน และเราจะไม่ได้ weak collision resistance อีกต่อไป
หากมีคุณสมบัติ strong collision resistance จะได้คุณสมบัติ one-way resistance ด้วย
(strong collision resistance — > one-way resistance)
- เป็นผลต่อเนื่องจากทฤษฎีสองข้อที่ได้กล่าวมาและพิสูจน์ไว้แล้ว
แฮชฟังก์ชันยอดนิยม
- MD5: digest ขนาด 128 บิต ซึ่งนักวิจัยด้านความปลอดภัยจากประเทศจีนได้ break collision resistance ได้ในปี 2004
- SHA1: digest ขนาด 160 บิต ซึ่งนักวิจัยด้านความปลอดภัยพบปัญหาและไม่แนะนำ SHA1 มาตั้งแต่ปี 2005 จนกระทั่งปี 2017 มีนักวิจัยทางด้านความปลอดภัยของ Google สามารถ break collision resistance ได้ (ดูข้อมูลเพิ่มเติมได้จาก https://security.googleblog.com/2017/02/announcing-first-sha1-collision.html) แต่คุณสมบัติ one-way resistance ยังไม่ถูก break สามารถเข้าไปดูโปรเจคที่ชื่อว่า SHA[TTERED] เพื่อดาวน์โหลดไฟล์ PDF 2 ไฟล์ที่ให้ digest ที่เหมือนกันได้ที่ https://shattered.io/
- SHA2 (SHA0224, SHA-256, SHA-384, SHA-512): digest มีขนาด 225, 256,384 และ 512 บิต ตามลำดับ ซึ่ง ณ ตอนนี้ยังไม่พบปัญหาทางด้านความปลอดภัยใด ๆ
เราทราบดีว่าหากเราเพิ่มจำนวนบิตจะทำให้สมรรถณะในการแฮชช้าลง ซึ่งเป็น classic trade-off ระหว่าง performance กับ security
ตัวอย่างการใช้งาน Hash function
Secured download
ใช้สำหรับดาวน์โหลดไฟล์จาก mirror site ที่ไม่จำเป็นต้อง secure เพื่อลดโหลดของเซิร์ฟเวอร์ แต่ก่อนจะดาวน์โหลดข้อมูลจาก mirror site จะได้สื่อสารกับ secured server ก่อนเพื่อที่จะได้มาซึ่ง hash ของไฟล์นั้น ๆ
Digital signature
จากรูป จะเห็นว่าแทนที่เราจะทำการเข้ารหัสข้อมูลต้นฉบับ เราแค่นำข้อมูลต้นฉบับมาผ่านแฮชฟังก์ชันแล้วทำการเข้ารหัสโดยใช้กุญแจส่วนตัว (ทำการ sign) จากนั้นให้เราส่งข้อมูลที่ต้นฉบับพร้อมทั้ง digest ที่ถูกเข้ารหัสไปยังผู้รับ ซึ่งผู้รับจะใช้กุญแจสาธารณะของผู้ส่งในการถอดข้อมูล digest เพื่อนำมาตรวจสอบว่าข้อมูลต้นฉบับที่ได้รับมานั้นถูกดัดแปลงหรือไม่
สรุปการทำ digital signature มีประโยชน์ที่เห็นได้ชัดเจนมี 2 อย่างคือ
- ผู้รับสามารถตรวจสอบได้ว่าข้อมูลที่ได้รับมีการดัดแปลงหรือไม่ (integrity)
- ผู้รับสามารถตรวจสอบได้ว่าผู้ส่งเป็นตัวจริงหรือไม่ (ผู้ถือกุญแจส่วนตัวควรจะมีแค่คนเดียว และไม่สามารถปฏิเสธความรับผิดชอบได้)
อ้างอิง
J. Kubiatowicz, California Berkeley
R. Lee, Princeton University
R, Paruj, Kasetsart