การโจมตีวันเกิดในการรับรองความถูกต้องของข้อความทำงานอย่างไร

ใน วิศวกรรมการเข้ารหัส:

2.7.1 การโจมตีวันเกิด

การโจมตีในวันเกิดได้รับการตั้งชื่อตามความขัดแย้งในวันเกิด ถ้าคุณมี 23 คนในห้องหนึ่งโอกาสที่เขาสองคนจะมีเท่ากัน วันเกิดเกิน 50% นั่นเป็นความน่าจะเป็นที่สูงมากอย่างน่าประหลาดใจ ว่ามีวันเกิดที่เป็นไปได้ 365 วัน

ดังนั้นการโจมตีวันเกิดคืออะไร? เป็นการโจมตีที่ขึ้นอยู่กับข้อเท็จจริง ค่าที่ซ้ำกันหรือที่เรียกว่าการชนกัน ปรากฏเร็วกว่ามาก คุณจะคาดหวัง สมมติว่าระบบสำหรับการทำธุรกรรมทางการเงินที่ปลอดภัย ใช้รหัสรับรองความถูกต้อง 64 บิตใหม่สำหรับแต่ละธุรกรรม (สำหรับ เรียบง่าย เราถือว่าไม่มีการใช้การเข้ารหัส) มี $2^{64}$ ($=18\cdot 10^{18}$ หรือหนึ่งหมื่นแปดพันล้าน) ค่าคีย์ที่เป็นไปได้ ดังนั้นสิ่งนี้ คงจะหักยากทีเดียว จริงไหม? ผิด! พอเห็นประมาณ $2^{32}$ ($=4\cdot 10^9$ หรือสี่พันล้านรายการ) ผู้โจมตีสามารถคาดหวังได้ การทำธุรกรรมสองรายการใช้รหัสเดียวกัน สมมติว่าอย่างแรก ข้อความรับรองความถูกต้องจะเหมือนเดิมเสมอ "คุณพร้อมรับ ธุรกรรม?” ข้อความ หากธุรกรรมสองรายการใช้การรับรองความถูกต้องเดียวกัน คีย์ จากนั้นค่า MAC ในข้อความแรกจะเป็นค่า เหมือนกันซึ่งง่ายต่อการตรวจจับสำหรับผู้โจมตี โดยทราบมาว่า คีย์สองคีย์เหมือนกัน ผู้โจมตีสามารถแทรกข้อความจาก ธุรกรรมที่เก่ากว่าลงในธุรกรรมที่ใหม่กว่าในขณะที่กำลังดำเนินการอยู่ เนื่องจากพวกเขาได้รับการรับรองความถูกต้องด้วยรหัสที่ถูกต้อง ข้อความหลอกลวงเหล่านี้ จะได้รับการตอบรับซึ่งเป็นการหักล้างธุรกรรมการเงิน ระบบ.

สิ่งนี้ไม่ดี:

โดยทราบมาว่า คีย์สองคีย์เหมือนกัน ผู้โจมตีสามารถแทรกข้อความจาก ธุรกรรมที่เก่ากว่าลงในธุรกรรมที่ใหม่กว่าในขณะที่กำลังดำเนินการอยู่

?

สมมติว่าธุรกรรมสองรายการมี MAC เดียวกัน ซึ่งหมายความถึงคีย์การรับรองความถูกต้องเดียวกัน

ข้อความจากธุรกรรมที่เก่ากว่านั้นไม่เหมือนกับข้อความในธุรกรรมที่ใหม่กว่าใช่หรือไม่ ดังนั้นการเปลี่ยนจะไม่เปลี่ยน?

ในบริบทนี้ การทำธุรกรรม $t_i$ มีข้อความมากมาย $m_i^t$ โดยที่แต่ละข้อความถูก MAC'ed ด้วยรหัสธุรกรรม $k_i$.

สมมติว่าคีย์ MAC ของแต่ละธุรกรรมถูกสร้างขึ้น สุ่มอย่างสม่ำเสมอ[1]. หลังจากนั้นประมาณ $2^{32}$ ธุรกรรม เราคาดว่าคีย์จะเกิดขึ้นอีกครั้งโดยมีความน่าจะเป็น 50% ตามวันเกิดที่ขัดแย้งกัน นี่คือส่วนที่ชนกัน สมมติ $t_i$ และ $t_j$ มีรหัส MAC เดียวกัน $k_i$.

ตามที่กล่าวไว้ในย่อหน้า หากข้อความแรกของธุรกรรมเหมือนกัน ผู้โจมตีที่จัดเก็บธุรกรรมจะเห็นว่าคีย์ถูกใช้ซ้ำ - คีย์จากธุรกรรม $t_i$ ใช้ในการทำธุรกรรม $t_j$.

ร้านค้าผู้โจมตี

| (m10,MAC(m10) |(m11,MAC(m11) | ... | (m1N1,MAC(m1N1)|
| (m20,MAC(m20) |(m21,MAC(m21) | ... | (m2N1,MAC(m2N2)|
....
| (mi0,MAC(mi0) |(mi1,MAC(mi1) | ... | (miNi,MAC(miNi)|
....
| (mj0,MAC(mj0) |(mj1,MAC(mj1) | ... | (mjNi,MAC(mjNi)|

และสังเกต : MAC(mi0) = MAC(mj0)
และอาจส่ง

| (mj0,MAC(mj0) |(mi1,MAC(mi1) | ... | (miNi,MAC(miNi)|

ตอนนี้พวกเขาเพียงแค่รับข้อความ $m_i^t$ จาก $t_i$และแทรกลงในธุรกรรมปัจจุบันที่ใช้คีย์เดียวกัน ดังนั้นธุรกรรมใหม่จึงมี $m_j^t$ ข้อความและส่วนแทรก $m_i^t$ ข้อความเกี่ยวกับความได้เปรียบของผู้โจมตี ผู้โจมตีอาจลบทั้งหมด $m_j^t$ ข้อความของการทำธุรกรรมและสามารถส่ง $m_i^t$แล้วแต่ความได้เปรียบเสียเปรียบ

เป็นผลให้การแทนที่เปลี่ยนข้อความในการทำธุรกรรม

[1] นี่เป็นส่วนสำคัญของการชนและการรักษาความปลอดภัยด้วย

ดังที่เกลากะกล่าวไว้ดูเหมือนจะมีข้อสันนิษฐานโดยปริยายว่า "ธุรกรรม" มีข้อความที่แยกจากกันหลายข้อความ และข้อความนั้นไม่ได้ ถูกล่ามโซ่ ด้วยวิธีใดก็ตาม (เช่น โดยรวมโทเค็น MAC ของข้อความก่อนหน้าในการป้อนข้อมูลในการคำนวณ MAC ของข้อความถัดไป)

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

โดยหลักการแล้วการโจมตีวันเกิด สามารถ ส่งผลต่อรูปแบบการตรวจสอบสิทธิ์หลายข้อความที่ได้รับการออกแบบมาเป็นอย่างดี หากคีย์ MAC และ/หรือโทเค็นสั้นเกินไป อย่างไรก็ตาม รายละเอียดนั้นขึ้นอยู่กับรูปแบบเป็นอย่างมาก และโดยปกติแล้วการโจมตีดังกล่าวจะต้องใช้มากกว่าคีย์สั้นๆ

ตัวอย่างเช่น สมมติว่า $i$-th ข้อความในการทำธุรกรรม $t$ ได้รับการรับรองโดยแท็ก $$\tau_{i,t} = \operatorname{MAC}_{K_t}(\tau_{i-1,t} \mathbin\| i \mathbin\| m_{i,t}),$$ ที่ไหน $K_t$ เป็นคีย์ MAC ต่อธุรกรรม $\tau_{i-1,t}$ เป็นแท็ก MAC สำหรับข้อความก่อนหน้าในการทำธุรกรรม $i$ คือหมายเลขข้อความ (เสริมด้วยความยาวคงที่หรือแยกออกจากอินพุต MAC อื่นอย่างชัดเจน) และ $m_{i,t}$ เป็นข้อความที่จะตรวจสอบความถูกต้อง

จากนั้นจึงจะสามารถแทนที่ข้อความที่ถูกแท็กได้ $(m_{i,t}, \tau_{i,t})$ ที่มีการสกัดกั้นไว้ก่อนหน้านี้ $(m_{i',t'}, \tau_{i',t'})$ จากธุรกรรมอื่น $t'$ และผ่านการตรวจสอบความถูกต้องของ MAC แล้ว ผู้โจมตีไม่ต้องการเพียงแค่ $K_t = K_{t'}$แต่ยัง $i = ฉัน'$ และ $\tau_{i-1,t} = \tau_{i-1,t'}$. นี้ สามารถ เกิดขึ้นโดยบังเอิญ หากความยาวรวมของคีย์ แท็ก และ (ค่าปกติของ) ตัวนับข้อความต่ำพอ แต่มีโอกาสน้อยกว่าการชนกันของคีย์เพียงสองคีย์ ในทางปฏิบัติ แท็ก (หรือคีย์!) จะต้องสั้นพอที่จะเสี่ยงต่อการถูกโจมตีด้วยการปลอมแปลงเดรัจฉานได้โดยตรง แม้ว่าจะไม่ได้ใช้ประโยชน์จากเอฟเฟกต์วันเกิดก็ตาม

ดังนั้น แม้ว่าประเด็นโดยรวมที่หนังสือเล่มนี้พยายามสื่อถึง - ว่ากุญแจควรยาวพอที่จะหลีกเลี่ยงการชนกันในวันเกิดได้ - เป็นหลักการที่ดีที่ควรปฏิบัติตามโดยทั่วไป ฉันไม่เชื่อว่าการโจมตีที่เกิดขึ้นจริงที่พวกเขานำเสนอนั้น เป็นวิธีที่ใช้งานได้จริง อย่างน้อยที่สุดก็ไม่ได้ต่อต้านแผนการใด ๆ ที่ไม่เสี่ยงต่อการถูกโจมตีที่แย่กว่าอยู่แล้ว