[Cybersecurity] มารู้จักแฮชฟังก์ชันให้มากขึ้น

สำหรับคนที่เรียนทางด้านวิทยาการคอมพิวเตอร์คงจะคุ้นเคยกับสิ่งที่เรียกว่าแฮชฟังก์ชันมาบ้างแล้ว ซึ่งหน้าที่หลักของมันก็คือเปลี่ยนข้อมูล input ใด ๆ ให้กลายเป็น output ที่มีขนาดคงที่

ยกตัวอย่างเช่นไฟล์ pdf ไฟล์หนึ่งมีขนาด 2 เมกะไบต์ เมื่อนำมาไฟล์นี้มาผ่านฟังก์ชันแฮชจะได้ output ขนาดคงที่เช่น 160 บิต โดยผลลัพธ์ที่ได้มาขนาด 160 บิตนี้ จะเป็น ตัวแทน ของไฟล์ pdf ที่มีขนาด 2 เมกะไบต์

ก่อนอื่นขอนิยามคำศัพท์ก่อนว่า output ที่ได้จากฟังก์ชันแฮชมีชื่อเรียกว่า digest ซึ่งต่างจากกระบวนการ encryption ที่เราจะเรียกผลลัพธ์ว่า ciphertext

การที่ข้อมูล plaintext เปลี่ยนแปลงเพียงเล็กน้อยจะส่งผลทำให้ digest เกิดการเปลี่ยนแปลงมหาศาล (ดูตัวอย่างในรูปที่ 1) ซึ่งหนึ่งในคุณสมบัติที่ทำให้เกิดเหตุการณ์แบบนี้เรียกว่า collision resistance ซึ่งจะกล่าวถึงในช่วงต่อไปของบทความ

รูปที่ 1 แสดงการเปลี่ยนแปลงของ digest เมื่อข้อมูล plaintext ถูกเปลี่ยน

สมมติว่าฟังก์ชันแฮชมีขนาดของ 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

รูปที่ 2 แสดง range space และ digest ที่ตกลงในตะกร้า

จะเห็นว่าตะกร้าเบอร์ 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

รูปที่ 3 แสดงความน่าจะเป็นที่มีคนอย่างน้อย 1 คู่เกิดวันเดียวกันตามขนาดของกลุ่มตัวอย่าง

เช่น 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

รูปที่ 4 แสดงความสัมพันธ์ระหว่างจำนวนครั้งในการเก็บสะสมคูปองกับรูปแบบคูปองทั้งหมดที่ได้สะสมแล้ว

อธิบายให้เห็นภาพง่าย ๆ คือ สมมติว่าเซเว่นมีแคมเปญในการสะสมแสตมป์ให้ครบ 77 จังหวัด แน่นอนว่าตอนเริ่มเก็บสะสมมันได้จังหวัดที่ไม่ซ้ำกัน แต่พอเก็บไปเรื่อย ๆ จะเจอปัญหาในการหาจังหวัดท่ีขาดยากขึ้น (เช่นจังหวัดบึงกาฬ หาเท่าไหร่ก็หาไม่เจอ) ซึ่งก็มีคนพิสูจน์ทางสถิติว่าจำนวนครั้งที่จะได้ครบเป็นฟังก์ชันของลอการิทึมธรรมชาติ

ซึ่งหากเรามี 77 จังหวัด จำนวนครั้งที่จะเก็บสะสมแสตมป์ให้ครบทั้ง 77 จังหวัดเท่ากับ n ln(n)ครั้ง = 77log(77) = 335 ครั้ง

ทีนี้เรามาเข้าเรื่องคุณสมบัติของแฮชฟังก์ชันที่ปลอดภัยกันสักที

คุณสมบัติของแฮชฟังก์ชันที่ปลอดภัย

เนื่องจากว่าเราต้องการให้ digest เป็นตัวแทนของ input เราจะต้องปกป้อง input ที่แท้จริงผ่านคุณสมบัติ 3 อย่างต่อไปนี้

1. one-way resistance
   มันต้องยากมาก ๆ ที่จะกลับไปหา plaintext จาก digest
   H(M): one-way resistance
2. weak collision resistance
   สมมติว่าเรามี plaintext 1 ตัว ยากมากที่จะหา plaintext ตัวที่ 2 ที่ให้ digest เหมือนกัน
3. 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 ของไฟล์นั้น ๆ

รูปที่ 5 แสดงการร้องขอไฟล์จาก unsecured server

Digital signature

รูปที่ 6 แสดงการทำ digital signature

จากรูป จะเห็นว่าแทนที่เราจะทำการเข้ารหัสข้อมูลต้นฉบับ เราแค่นำข้อมูลต้นฉบับมาผ่านแฮชฟังก์ชันแล้วทำการเข้ารหัสโดยใช้กุญแจส่วนตัว (ทำการ sign) จากนั้นให้เราส่งข้อมูลที่ต้นฉบับพร้อมทั้ง digest ที่ถูกเข้ารหัสไปยังผู้รับ ซึ่งผู้รับจะใช้กุญแจสาธารณะของผู้ส่งในการถอดข้อมูล digest เพื่อนำมาตรวจสอบว่าข้อมูลต้นฉบับที่ได้รับมานั้นถูกดัดแปลงหรือไม่

สรุปการทำ digital signature มีประโยชน์ที่เห็นได้ชัดเจนมี 2 อย่างคือ

1. ผู้รับสามารถตรวจสอบได้ว่าข้อมูลที่ได้รับมีการดัดแปลงหรือไม่ (integrity)
2. ผู้รับสามารถตรวจสอบได้ว่าผู้ส่งเป็นตัวจริงหรือไม่ (ผู้ถือกุญแจส่วนตัวควรจะมีแค่คนเดียว และไม่สามารถปฏิเสธความรับผิดชอบได้)

อ้างอิง
J. Kubiatowicz, California Berkeley
R. Lee, Princeton University
R, Paruj, Kasetsart