มีการชนกันของการเข้ารหัสเหมือนในฟังก์ชันแฮชหรือไม่?

ในฟังก์ชันแฮช $h(m) = h(m_1)$ เรียกว่าการชนกันและเป็นสิ่งที่ไม่พึงปรารถนาอย่างยิ่งที่จะพบได้เนื่องจากเป็นการบ่อนทำลายความปลอดภัยของแฮช อย่างไรก็ตาม มีข้อกังวลที่คล้ายคลึงกันในการเข้ารหัสเช่น block ciphers (AES-256) หรือ RSA หรือไม่ หากมีคู่คีย์ข้อความธรรมดา $m,k$ ที่ให้ผลไซเฟอร์เท็กซ์ และมีคีย์คู่ข้อความอีกคีย์หนึ่ง $m_1, k_1$ ที่ให้ผลไซเฟอร์เท็กซ์เหมือนกัน นี่เป็นปัญหาที่คล้ายกับการชนกันของแฮชหรือไม่ ที่ได้รับสองคู่จากนั้นคุณสามารถสร้าง 'การเข้ารหัสลับ' และรหัสที่ก้าวหน้า 'เรียนรู้' ว่าทั้งสองจบลงด้วยข้อความรหัสเดียวกันได้อย่างไร

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

การปะทะกันเกิดขึ้นใน Hashing เนื่องจาก หลักการของนกพิราบ. ใน Hashing อินพุตจะมีขนาดใหญ่กว่าเอาต์พุต ดังนั้นการปะทะกันจะเกิดขึ้นคุณไม่สามารถป้องกันได้

นี่ไม่ใช่กรณีที่มีการเข้ารหัส ผลลัพธ์ของการเข้ารหัสอย่างน้อยเท่ากับขนาดของอินพุตเสมอ ดังนั้นหลักการ Pigeonhole Principle จึงใช้ไม่ได้

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

Enc(Plaintext1, key1) ไม่เคยเท่ากับ Enc(Plaintext2, key1)

บล็อก Ciphers ชนกับคีย์ที่แตกต่างกัน

หากมีคู่คีย์ข้อความธรรมดา $m,k$ ที่ให้ผลไซเฟอร์เท็กซ์ และมีคีย์คู่ข้อความอีกคีย์หนึ่ง $m_1,k_1$ ที่ให้ผลไซเฟอร์เท็กซ์เหมือนกัน นี่เป็นปัญหาที่คล้ายกับการชนกันของแฮชหรือไม่

ใช่ มันคล้ายกับการปะทะกันของแฮช มีกรณีการโจมตีหากใช้คีย์เดียวกัน ดูส่วนโบนัส สำหรับคีย์ต่าง ๆ จะไม่เปิดเผยอะไรเลย

หากคุณกำลังใช้ CTR (โหมดการสตรีมใด ๆ ) หากคุณมีการชนกันของข้อความรหัส สิ่งนี้จะไม่เปิดเผยข้อความตั้งแต่

$$m_1 \oplus o_1 = c_1 = c_2 = m_2 \oplus o_2$$ เพราะ

$$m_1 m_2 \oplus = o_1 \oplus o_2$$ และสิ่งนี้จะไม่เปิดเผยข้อความแม้คุณจะเดาก็ตาม

และในทำนองเดียวกัน โหมด CBC จะต้านทานการชนกันภายใต้ปุ่มต่างๆ

ความเป็นไปได้ของการชนกันของ Ciphertext

สมมติว่าเราเข้ารหัส AES 'moon' ด้วยคีย์ 'morehotquestions' รับ 'fjydhpdag' และเราเข้ารหัส 'ดวงอาทิตย์' ด้วยคีย์ 'hotnetworkquestions' ที่ได้รับ 'fjydhpdag' ด้วย เป็นไปได้ไหม

หากเราพิจารณาว่า AES เป็น PRP เราก็มีเงื่อนไขเหมือนกับการโจมตีในวันเกิดทุกประการ ความน่าจะเป็นของบล็อกเดี่ยวสองบล็อกจะมีไซเฟอร์เท็กซ์เหมือนกันคือ $1/2^{128}$ สำหรับบล็อก ECB

หาเราง่ายกว่ามากเนื่องจาก AES นั้นเปลี่ยนกลับได้ พิจารณา ECB สำหรับกรณีที่ง่ายเนื่องจาก AES นั้นกลับด้านได้ ให้ใช้ ciphertext และถอดรหัสด้วยสองคีย์ที่แตกต่างกัน จากนั้นคุณจะได้รับสองข้อความที่แตกต่างกัน แน่นอนว่าไม่จำเป็นต้องมีความหมาย นี่เป็นวิธีง่ายๆ ในการค้นหา/แสดงสิ่งนี้

ระบบลายเซ็นเช่น RSA-Sign

ระบบลายเซ็นใช้แฮชของข้อความเพื่อเซ็นชื่อ วิธีหนึ่งในการปลอมแปลงผู้โจมตีจำเป็นต้องมีการโจมตีด้วยภาพล่วงหน้าครั้งที่สองในฟังก์ชันแฮช จะเกิดอะไรขึ้นถ้าเรามีผู้เซ็นชื่อหรือเลขาของผู้เซ็นชื่อที่ประสงค์ร้าย สมมติว่าพวกเขาใช้ MD5 ซึ่งการชนกันใกล้เข้ามาแล้ว (อย่าใช้ MD5 และ SHA-1 สำหรับลายเซ็น) พวกเขาสามารถค้นหาข้อความสองข้อความที่มีค่าแฮชเดียวกันได้ $h(m_1) = ชั่วโมง(m_2)$ กับ $m_1 \neq m_2$ จากนั้นทั้งสองค่า $$\operatorname{RSA-Sign}(h(m_1)) = \operatorname{RSA-Sign}(h(m_2))$$ เหมือนกัน.

ใช้ฟังก์ชันแฮชการเข้ารหัสที่ป้องกันการชนกันเสมอ เช่น SHA-256, SHA-512, SHA-3, BLAKE2 เป็นต้น เพื่อลดการโจมตีนี้

ส่วนโบนัส: บล็อก Ciphers ชนกับคีย์เดียวกัน

ใช่ มีการโจมตีและความกังวลเกี่ยวกับเรื่องนี้ เช่น Sweet32;

• Sweet32: การโจมตีวันเกิดบนรหัสบล็อก 64 บิตใน TLS และ OpenVPN

  ในระยะสั้นสำหรับบล็อกรหัสขนาด $ข$หากคุณกำลังเข้ารหัส $2^b$ บล็อก ภายใต้คีย์เดียวกัน เราสามารถรับการชนกันของข้อความเข้ารหัสของโหมด CBC ได้ $c_i = c_j$ กับ $i \neq j$. นั่นคือ;

  $$m_i \oplus c_{i-1} = m_j \oplus c_{j-1}$$

  จากนั้นใช้คุณสมบัติของ CBC เราจะได้

  $$m_i \oplus m_j = c_{1-1} \oplus c_{j-1}.$$

  อย่างที่เราเห็นนี่เป็นเพียง x-or ของบล็อคข้อความธรรมดานั่น ผู้โจมตีแบบพาสซีฟสามารถโจมตีได้.

ฉันได้พูดเฉพาะโหมด CBC แต่หน้ากล่าวถึงมากขึ้นและปล่อยให้ตรวจสอบคล้ายกับ CBC;

นี่เป็นสิ่งสำคัญอย่างยิ่งเมื่อใช้โหมดการทำงานทั่วไป: เรากำหนดให้บล็อกรหัสมีความปลอดภัยสูงสุด $2^n$ ข้อความค้นหา แต่โหมดการทำงานส่วนใหญ่ (เช่น CBC, CTR, GCM, โอซีบีฯลฯ) ไม่ปลอดภัยหากมีมากกว่า $2^{n/2}$ บล็อกข้อความ (วันเกิดที่ผูกไว้)

แน่นอนเราเป็น เกือบ ไม่ใช้การเข้ารหัสขนาดบล็อก 64 บิตอีกต่อไป อย่างไรก็ตาม การโจมตีนี้อาจเกิดขึ้นได้หากคุณเข้ารหัสข้อมูลมากเกินไปโดยใช้คีย์เดียวกัน อาจกล่าวได้ว่าการเข้ารหัส $2^{64}$ ข้อมูลมากเกินไปเราจะไม่เข้ารหัสขนาดดังกล่าว จากนั้นเรามีข้อโต้แย้งที่ลึกซึ้งยิ่งขึ้น 50% ของการโจมตีในวันเกิดนั้นมากเกินไปสำหรับข้อได้เปรียบของผู้โจมตีมันยังห่างไกลจากสิ่งเล็กน้อย พวกเขาสามารถมองหาความเป็นไปได้ที่ต่ำกว่าที่จะเปิดเผยบล็อกข้อความบางส่วน คุณควรจำกัดไว้ที่ $2^{32}$- บล็อกเพื่อลดความได้เปรียบของผู้โจมตี