Score:2

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

ธง cz

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

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

corsiKa avatar
us flag
ฉันอยากจะบอกว่าดีสำหรับการมีความรู้สึกว่าเพียงเพราะมีบางอย่างที่ใช้กับการแฮชที่ใช้กับการเข้ารหัสและในทางกลับกัน ใช่ ทั้งสองอย่างซับซ้อน และมักจะใช้อัลกอริทึมเดียวกันหรือคล้ายกัน แต่เป็นเครื่องมือสองอย่างที่แตกต่างกันสำหรับปัญหาสองปัญหาที่แตกต่างกัน และการตั้งสมมติฐานเกี่ยวกับสิ่งหนึ่งจากอีกสิ่งหนึ่งนั้นไม่ฉลาด - อันที่จริง เมื่อความปลอดภัยเป็นสิ่งสำคัญ คุณ ควร * เสมอ * ตั้งคำถามกับสมมติฐานของคุณ!
nimrodel avatar
cz flag
ฉันไม่ได้ถือว่าการชนกันเกิดขึ้นในการเข้ารหัสเพียงบางส่วนหรือแม้แต่บางส่วนเท่านั้นที่ทำให้เกิดการแฮช แต่ฉันนำแฮชมาเป็นตัวอย่าง 'ชอบในแฮช' ฉันสนใจว่า m1xk1 เข้ารหัสเป็น m2xk2 ตั้งแต่แรกหรือไม่ และมีความกังวลว่าจะถอดรหัสใดเมื่อมีหลายตัวเลือก (เช่นเดียวกับในแฮช) ดังนั้นคุณจึงถือว่าฉันสันนิษฐาน
Score:4
ธง et

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

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

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

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

ilkkachu avatar
ws flag
จริง แต่โปรดทราบว่าพวกเขามีสองคีย์ที่แตกต่างกัน $k$ และ $k_1$ ที่นั่น คำถามไม่ใช่ $E(m_1, k) = E(m_2, k)$ แต่ $E(m_1, k_1) = E(m_2, k_2)$
kelalaka avatar
in flag
สิ่งนี้อ่านไม่ถูกต้องเหมือนที่ฉันทำมาก่อน OP ขอชนกับคีย์ที่แตกต่างกัน การพิสูจน์ว่ามีอยู่เป็นเรื่องง่าย การค้นหาด้วยข้อความที่เฉพาะเจาะจงนั้นยาก ตรวจสอบส่วนแรกของคำตอบของฉัน
Score:3
ธง in

บล็อก 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}$- บล็อกเพื่อลดความได้เปรียบของผู้โจมตี

nimrodel avatar
cz flag
สมมติว่าเราเข้ารหัส AES 'moon' ด้วยคีย์ 'morehotquestions' รับ 'fjydhpdag' และเราเข้ารหัส 'ดวงอาทิตย์' ด้วยคีย์ 'hotnetworkquestions' ที่ได้รับ 'fjydhpdag' ด้วย เป็นไปได้ไหม ฉันกำลังถามถึงสองคีย์และข้อความที่แตกต่างกันโดยสิ้นเชิง ถ้าพวกเขาสามารถเข้ารหัสเป็น 'fjydhhpdag' เดียวกันได้ ระบบถอดรหัส AES จะสับสน นั่นคือมันถอดรหัสเป็นข้อความธรรมดาทั้งสองด้วยคีย์ที่แตกต่างกันหรือไม่
kelalaka avatar
in flag
คีย์ที่แตกต่างกันจะเลือกการเรียงสับเปลี่ยนที่แตกต่างกัน และโดยทั่วไปแล้วสิ่งนี้จะป้องกันการโจมตีได้ การโจมตี Sweet32 ต้องการคีย์เดียวกับที่คุณไม่ต้องการคุณควรกำหนดโหมดการทำงานของคุณเพื่อพูดคุยเกี่ยวกับเรื่องนี้เพิ่มเติม เนื่องจาก Devil อยู่ในรายละเอียด (โปรดอย่าแก้ไขคำถามเนื่องจากมีคำตอบบางส่วน)
kelalaka avatar
in flag
ฉันเขียนส่วนสำหรับคำถามเฉพาะของคุณที่ฉันพลาดและตอบความคิดเห็นของคุณด้วย

โพสต์คำตอบ

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