ยังไม่ได้อ่านเปเปอร์ SHA-1 is a Shambles จนเข้าใจแต่ก็พอได้ fact บางอย่างซึ่งคิดว่าน่าจะเอาไปใช้เพื่อเป็นเหตุผลหรือคำอธิบายว่ามันเกิดอะไรขึ้นและเราควรทำยังไงต่อได้ ดังนั้นจึงขอเอามาทดไว้เป็นอีกซีรีส์หนึ่งของบล็อกชุดกระดาษทดด้านล่างครับ

Cryptographic Hash Properties

เวลาเราพูดถึงฟังก์ชัน hash เราจะกร่อนคำคุณศัพท์ข้างหน้าโดยทั่วไปกันจนชินจนบางทีก็อาจลืมไปถึงคุณสมบัติสำคัญที่เจ้าฟังก์ชัน hash มันพึงมี โดยคำคุณศัพท์ข้างหน้าที่หายไปนั้นคือคำว่า cryptographic หรือ secure ซึ่งในที่นี้จะขอย่อเป็น CHF เพื่อความง่ายในการพิมพ์ครับ

อย่างที่คนซึ่งสามารถแยกได้ว่าอัลกอริธึมอย่าง MD5/SHA1 ไม่ใช่การเข้ารหัส (encryption) ทราบกันดี CHF มีคุณสมบัติซึ่งจำเป็นต้องมีถึงจะถูกเรียกได้ว่าเป็น CHF อยู่หลัก 3 อย่าง ได้แก่

  1. คุณสมบัติ Pre-image resistance (ขอย่อว่า PIR) เป็นคุณสมบัติที่ระบุว่า ถ้ากำหนด \(H\) คือฟังก์ชันแฮช, \(m\) คือ message หรือข้อความ, และ \(h\) คือค่าแฮชซึ่งเป็นผลลัพธ์จากการเอา message ไปผ่านฟังก์ชันแฮชหรือ \(h = H(m)\) มันจะต้องยากที่จะหาข้อความอันเดิมอันนั้นก่อนผ่านฟังก์ชันแฮชโดยที่เรารู้แค่ค่าแฮช
  2. คุณสมบัติ Second pre-image resistance (ขอย่อว่า SPIR) เป็นคุณสมบัติที่ระบุว่า ถ้าเรามี \(m_1\) คือ message และ \(h_1\) คือค่าแฮชของ \(H(m_1)\) มันจะต้องยากที่จะหา \(m_2\) ที่ทำให้ได้ \(h_1\) จาก \(H(m_1)\) และต้องเป็น \(h_1\) ของ \(m_1\) นั้น
  3. คุณสมบัติ Collision resistance (ขอย่อว่า CR) เป็นคุณสมบัติว่าจะต้องเป็นเรื่องยากในการคู่ random message ใดๆ คือ \(m_1\) และ \(m_2\) ที่ทำให้ \(H(m_1) = H(m_2)\)

เวลาเราบอกว่าเป็นเรื่องยาก คำว่ายากมีความหมายซ่อนอยู่ในตัวมันอีกหลายความหมายซึ่งในทางทฤษฎีส่วนใหญ่จะใช้คณิตศาสตร์มาพิสูจน์

SPIR และ CR ซึ่งมีนิยามใกล้เคียงกันนั้นมีจุดแตกต่างกันอยู่ที่ทำให้คุณสมบัติ SPIR ถูกเรียกว่าเป็น Weak collision resistance ส่วน CR ถูกเรียกว่าเป็น Strong collision resistance ซึ่งจุดแตกต่างอยู่ที่ \(m\) ที่ใช้กับฟังก์ชันแฮช โดยในกรณีของ SPIR นั้น \(m_1\) คือตัวตั้งเพื่อนำไปสู่การหา \(m_2\) ที่มีค่า \(h\) เดียวกันซึ่งทำให้ผลลัพธ์ที่เกี่ยวข้องกับการที่ \(m_1\) เป็นค่านั้นเสมอ แต่ในกรณีของ CR นั้น \(m_1\) และ \(m_2\) สามารถเป็นค่าใดๆ ก็ได้ที่แตกต่างกันซึ่งนำไปสู่การผ่านฟังก์ชันแฮชและทำให้ได้ค่าแฮชเดียวกัน

เนื่องจากฟังก์ชันที่เราเรียกว่า CHF นั้นเป็น deterministic function ซึ่งหมายความว่า \(m_1\) ซึ่งผ่านฟังก์ชัน \(H\) จะทำให้ได้ \(h_1\) เสมอ และ \(m_2\) ซึ่งผ่านฟังก์ชัน \(H\) จะทำให้ได้ \(h_2\) เสมอจะเป็น \(h_1\) หรือ \(h_n\) ที่ไม่ใช่ \(h_2\) ไม่ได้ ฟังก์ชันแฮชในลักษณะนี้จึงมีปัญหาซึ่งไม่สามารถหลีกเลี่ยงให้ไม่เกิดขึ้นได้เสมอคือปัญหาที่ \(h\) ทั้งหมดที่เป็นไปได้จะถูกใช้จนหมด และนั่นคือจังหวะที่การชน (collision) เกิดขึ้น

ถ้าเรามีฟังก์ชันแฮชหนึ่งฟังก์ชัน แล้วเราพยายามใส่ \(m\) ในทุกรูปแบบที่เป็นไปได้จนถึง "ขีดสุด" ของฟังก์ชันแฮชที่มันจะสร้าง \(h\) สำหรับค่า \(m\) ซักค่าหนึ่งได้ ฟังก์ชันอาจสร้างค่า \(h\) ที่เคยสร้างไปแล้ว ทำลายคุณสมบัติ PIR และ SPIR ลง มันก็ไม่อาจจะถูกเรียกได้ว่าเป็น CHF อีก และจะส่งผลกระทบโดยตรงต่อ "trust" ที่ถูกยืนยันภายใต้พื้นฐานของฟังก์ชันแฮชดังกล่าว

Collision Attack

ลักษณะของการที่เรามี h ที่จำกัดแต่กลับมี m ที่ไม่จำกัดนั้นมีชื่อว่า Pigeonhole principle

Pigeonhole principle นำไปสู่ความพยายามในการประเมินและวัดผลความเป็นไปได้ที่จะเกิดเงื่อนไขดังกล่าวในทฤษฎีความน่าจะเป็นภายใต้ชื่อเรียกว่า Birthday problem หรือ Birthday paradox

Birthday problem เมื่อนำมาใช้เพื่อโจมตีในมุมของวิทยาการเข้ารหัสจึงถูกเรียกว่า Birthday attack ซึ่งระบุไว้ว่าถ้าค่าแฮชมีขนาดเป็น n แล้ว การชนกันของแฮชจะเกิดขึ้นเมื่อเราลองใส่ m ไปจนถึง \({\textstyle {\sqrt {2^{n}}}=2^{n/2}}\) หรือครึ่งหนึ่งของขนาดของค่าแฮชนั้น ซึ่ง Birthday attack จะถูกเอามาใช้ในการประเมินหาโอกาสที่ควรจะเป็นในการเกิด collision ตามขนาด \(n\) หรือจำนวนบิตด้วย

มีวิธีการมากมายที่จะใช้เพื่อพิสูจน์คุณสมบัติของ CHF ซึ่งนับรวมไปถึงการทำ brute force attack ไปเรื่อยๆ โดยในกรณีของอัลกอริธึมของ SHA-1 นั้น มันถูกกำหนดความแข็งแกร่งไว้ที่ \(2^{80}\) (ครึ่งหนึ่งของจำนวนบิตทั้งหมด) หรือเป็นตัวเลขคือ 1,208,925,819,614,629,174,706,176 operation ซึ่งเป็นเรื่องยากที่จะทำได้แบบ practical (โดยไม่พึ่ง quantum computer)

อย่างไรก็ตามการ cryptanalysis กับ SHA-1 ให้ผลลัพธ์ที่น่าประหลาดใจ โดยในปี 2017 กูเกิลและ Centrum Wiskunde & Informatica ประกาศว่าสามารถสร้างไฟล์ PDF ที่แตกต่างกันแต่มีค่าแฮช SHA-1 ที่เหมือนกันได้ภายใน \(2^{63.1}\) operation กับฟังก์ชันแฮช SHA-1 ที่ไม่ลดทอนหรือถูกตัดคุณสมบัติใดๆ โดยการโจมตีนั้นเกิดขึ้นได้จากระบบที่มี processing power มหาศาล ซึ่งเทียบเท่ากับการใช้คอมพิวเตอร์ที่มี CPU เพียงหน่วยเดียวทั้งหมด 6,500 ปี และคอมพิวเตอร์ที่มี GPU เพียงหน่วยเดียวทั้งหมด 110 ปี (ดู Shattered)

การ collision ของ SHA-1 ก่อนหน้า Shattered มีมาก่อนแล้วทั้งในทางทฤษฎีและทางปฏิบัติ อย่างไรก็ตามการ collision ที่เกิดขึ้นโดยส่วนใหญ่นั้นไม่ได้เกิดกับฟังก์ชันแฮช SHA-1 แบบเต็ม หรือมีการเกิดขึ้นกับฟังก์ชันที่มีลดทอนหรือถูกตัดคุณสมบัติใดๆ ออก

SHA-1 is Shambles

งานวิจัย SHA-1 is Shambles ไม่ได้ดำเนินตามรอย Shattered แต่ทำสิ่งที่แตกต่างออกไปในการทำให้เกิดการ collision โดยแทนที่จะหา \(m_1\) และ \(m_2\) หรือ \(m_n\) ใดๆ ที่แตกต่างและไม่เกี่ยวข้องกันเพื่อหา \(h\) ค่าเดียวกัน งานวิจัย SHA-1 is Shambles สามารถทำให้เกิดการ collision ของ SHA-1 ได้โดยการเติมค่าใดๆ ไปก็ได้กับ \(m_1\) และ \(m_2\) โดยค่าที่เติมไปไม่จำเป็นต้องเหมือนกัน ซึ่งเมื่อ \(m_1\) และ \(m_2\) ถูกเติมค่าดังกล่าวไปแล้ว จะทำให้ค่าแฮชของทั้ง \(m_1\) และ \(m_2\) เป็นค่าเดียวกันเมื่อผ่านฟังก์ชัน SHA-1

วิธีการโจมตีในลักษณะนี้ถูกเรียกว่า Chosen-prefix collision attack โดย prefix หมายถึงค่า \(p_1\) และ \(p_2\) ที่ถูกเลือก (chosen) เอาไปเติมใส่ \(m_1\) และ \(m_2\) และทำให้เกิดค่า \(h\) เดียวกันได้

การโจมตีในลักษณะนี้เคยเกิดขึ้นและถูกนำมาใช้ในการโจมตีทางไซเบอร์จริงมาแล้วบนอัลกอริธึมของฟังก์ชันแฮช MD5 ซึ่งมัลแวร์ Flame ใช้ในการปลอม digital signature ของไมโครซอฟต์และทำให้ข้ามผ่านการตรวจสอบไปได้

Chosen-prefix collision attack สำหรับ SHA-1 เกิดขึ้นตั้งแต่เดือนเมษายน 2019 โดยงานวิจัย SHA-1 is a Shambles นำเสนอเวอร์ชันปรับปรุงของการโจมตีดังกล่าวที่ทำให้จำนวน operation ของการหาการ collision ลดลง (ทำได้ง่ายขึน) และสามารถทำได้โดยใช้เงิน 1.3 ล้านบาทสำหรับค่า processing power

Future?

ถ้ามองในมุมของปัญหา collision attack ที่หลีกเลี่ยงไม่ได้ สิ่งที่ดูเหมือนจะเป็นทางเลือกเดียวในการจัดการกับปัญหาและทำให้คุณสมบัติ CR ยังคงมีประสิทธิภาพคือการที่ฟังก์ชันแฮชจำเป็นต้องชนะ processing power ที่อาจเพิ่มสูงมากขึ้นในเวลาอันใกล้

ผมจะขอไม่พูดถึงตัวเลือกอย่าง Keccak หรือ BLAKE2 ด้วย internal ของอัลกอริธึมที่ต่างออกไปและส่งผลในคุณสมบัติ CR ด้วย ซึ่งหากมีเวลาได้อ่านแล้วและไม่ขี้เกียจที่จะมาบันทึกไว้ อาจจะได้พูดถึงมันในเร็วๆ นี้ครับ