Pages

3/14/2013

MD5 กับ Hash Collision


วันนี้มีคนมาถามเรื่องว่า MD5 มีโอกาสเกิด Hash Collision เท่าไหร่

ขอเกริ่นย่อๆ สำหรับคนไม่รู้ว่าแต่ละตัวคืออะไรก่อนนะ

  • hash = วิธีการการย่อยข้อมูลเพื่อสร้างรหัสเฉพาะแต่ละข้อมูลออกมา เช่น file ไฟล์ๆนึงขนาดใหญ่มาก อาจจะคำนวนค่า hash ได้เหลือแค่ไม่กี่ bytes
  • MD5 = เป็นวิธีการคำนวนค่า hash วิธีหนึ่ง โดยผลลัพธ์ของ MD5 จะมีขนาด 128 bits หรือ 16 bytes
  • ส่วน Hash Collision (หรือเรียกอีกอย่างว่าปัญหา Birthday Attack) = รหัสเฉพาะข้อมูลที่สร้างขึ้นมา(hash)เนี่ย มันมีโอกาสที่จะซ้ำกันได้ 

ซึ่งความน่าจะเป็นนั้นเท่าไหร่มาดูกัน

เริ่มจาก..

สมมุติว่าตอนนี้มี Hash อยู่ในมือ k ตัว (k มีไม่กี่ตัว ซึ่ง k < N มากๆ)
ถ้าเราเอาแต่ละตัวมาจับเทียบกัน จะสามารถจับคู่ได้ทั้งหมด k*(k-1)/2 คู่
โดยมาจาก
  เราเลือกตัวซ้ายได้ k ตัว แต่พอจะเลือกตัวขวาที่จะมาจับคู่ด้วยจะเหลือเลือกได้แค่ k-1 ตัว(เพราะว่าตัวซ้ายโดนเลือกไปแล้วตัวนึง)
  และในการจับคู่กัน อาจจะเกิดการสลับที่กันได้ แบบ A-B, B-A ดังนั้นเพื่อลดปัญหาคู่เหมือนกันแต่สลับที่กัน เลยต้องหาร 2 ออก

จากจำนวนคู่ตรงนี้พักไว้ก่อน

ต่อมาลองมาคิดในภาพใหญ่ว่า...

ถ้าเกิด Hash จะชนกันได้ โอกาสมันจะเป็นเท่าไหร่
เนื่องจากถ้าเป็น MD5 ซึ่งมีผลลัพธ์ของ MD5 ออกมาขนาด 128 bits (16 bytes)
ดังนั้นจะสามารถสร้างค่า Hash ได้ไม่ซ้ำกันทั้งหมด
N = 2^128 = 340282366920938463463374607431768211456 = 3.4*10^38 ตัว
ดังนั้นถ้าเราเลือก Hash ออกมาซักคู่นึง โดยล๊อคค่าทางฝั่งซ้ายมือไว้ แล้วหวังว่าคู่ของมันจะมีโอกาสซ้ำเนี่ย
เนื่องจาก hash อีกตัวจะเป็นอะไรก็ได้ใน hash ทั้งหมดที่สามารถสร้างได้
ดังนั้น
ความน่าจะเป็นที่มันจะซ้ำกัน ก็คือ หยิบออกมา 1 ใน hash ทั้งหมดที่สร้างได้ ซึ่งก็คือ 1/N หรือ 1/2^128 = 2^-128
พอได้ความน่าจะเป็นที่มันจะซ้ำใน 1 คู่ใดๆแล้ว เราก็สามารถเอามาคำนวนความน่าจะเป็นเฉลี่ยได้ว่า

ในจำนวน hash k ตัวที่เรามีเนี่ย จะมีกี่ตัวที่ซ้ำ ด้วยการเอาไปคูณกับจำนวนคู่ที่เราคำนวนไว้ตอนแรก

ความน่าจะเป็นเฉลี่ยที่จะมี hash ชนกันในกลุ่ม hash จำนวน k ตัว จะมีค่า = จำนวนคู่ทั้งหมด * ความน่าจะเป็นที่จะเกิดการชนกันในแต่ละคู่
   λ = ( k(k-1)/2 ) * ( 1/N )
      = k(k-1)/2N

ณ จุดนี้ ถ้าหากใช้ Poisson Distribution เพื่อคำนวนหาความน่าจะเป็นที่จะเกิดการชนกัน
และเนื่องจากค่าเฉลี่ยของการเกิดเหตุการณ์ใดๆใน Poisson Distribution จะมีความน่าจะเป็น = E(X) = λ
เราสามารถย้อนกลับไปใช้ สูตรความน่าจะเป็นใดๆของ Poisson ได้ด้วยสูตร
 P(X=x) = (x^k * e^-λ)/x!
โดย x คือ จำนวนคู่ที่ hash เกิดการชนกัน
ถ้าต้องการความน่าจะเป็นที่ไม่เกิดการชนกันขึ้นเลย(x=0) จะได้ค่าเท่ากับ
 P(X=0) = (0^k * e^-λ)/0!
      = e^-λ
      = e^-(k(k-1)/2N)
และความน่าจะเป็นที่จะเกิดการชนกันขึ้นอย่างน้อย 1 ตัวขึ้นไป (x=1,2,3,..) จะมีค่าเท่ากับ
P(X=1,2,3...) = 1 - P(X=0) = 1 - e^-(k(k-1)/2N)
ซึ่งเมื่อแทนค่า N ซึ่งเป็นขนาด Hash ทั้งหมดที่สามารถสร้างได้ของ MD5 แล้ว (N=2^128) ก็จะได้สมการเป็น
P(X=1,2,3...) = 1 - e^-(k(k-1)/2^129)
ซึ่งจะสามารถ plot เป็นกราฟได้ดังรูป

http://www.wolframalpha.com/input/?i=1+-+e%5E-%28k%28k-1%29%2F2%5E129%29

ซึ่งจะเห็นได้ว่า  เมื่อเริ่มต้นที่เรามีจำนวนhash น้อยๆ (k ต่ำ)
โอกาสการชนกันของ hash ในมือจะต่ำมาก
และโอกาสการชนกันของ hash จะเริ่มเพิ่มขึ้นเรื่อยๆ เมื่อ k มีค่าสูงเพิ่มขึ้น

หรือหมายถึงว่า ยิ่งเรามี hash มากเท่าไหร่ ยิ่งได้เปอร์เซนต์ในการชนกันที่สูงขึ้น

ซึ่งโดยปกติแล้ว เขามักจะคิดว่าการเกิด hash collision จะอาการหนักมากๆ เมื่อมีความน่าจะเป็นในการเกิด collision > 50%

ถ้าเรานำค่านั้นมาแทนในสมการ เพื่อทำการหาค่า k จะได้ว่า
 P(ในการชน) = 50% = 0.5 = 1 - e^-(k(k-1)/2^129)
       e^-(k(k-1)/2^129) = 1-0.5 = 0.5
       -(k(k-1)/2^129) = ln(0.5)
       k(k-1)/2^129 = ln(0.5^-1) = ln(2)
       k(k-1) = 2^129 * ln(2)
ณ จุดนี้เพื่อความง่าย ขอประมาณค่า k(k-1)==>k^2 เมื่อ k มีค่ามากๆ
จะได้เป็น
       k^2 = 2^129(ln(2))
       k = sqrt(2^129(ln(2))) = sqrt(2)*2^64*sqrt(ln(2))
       k = 21,719,381,355,163,560,000 = 2.1719 * 10^19
ตามรูป
http://www.wolframalpha.com/input/?i=1+-+e%5E-%28k%28k-1%29%2F2%5E129%29+%3D+0.5



สรุป

MD5 ซึ่งมีผลลัพธ์ออกมาเป็นค่า 128 bits จะมีโอกาสเกิด Hash Collision มากๆ (50% ขึ้นไป) เมื่อมีจำนวน hash มากกว่า 2.1719 * 10^19 ตัวขึ้นไป หรือประมาณ 2^64.2 ตัวขึ้นไป

References:


ป.ล. 
ปัจจุบันมีคนหาวิธีทำให้เกิด MD5 Hash Collision ที่เร็วๆได้แล้ว ในระดับที่สร้างค่า hash ประมาณ 2^24.1 ตัวเท่านั้น ซึ่งสามารถทำเสร็จได้ภายในเวลาประมาณ 6 วินาที(ด้วย CPU 2.6 GHz)
อ้างอิงเพิ่ม



No comments:

Post a Comment