Score:1

องค์ประกอบของฟังก์ชันต้านทานการชน H' = h1(h2()) ต้านทานการชนหรือไม่

ธง id

สมมติว่ามีฟังก์ชันแฮชที่ป้องกันการชนกันสองฟังก์ชัน $h_1$ และ $h_2$ ด้วยขนาดเอาต์พุตของ $n_1$ และ $n_2$ ตามลำดับ

เป็น $H'(x) = h_1(h_2(x))$ ทนต่อการชนกันสำหรับความสัมพันธ์ที่แตกต่างกันระหว่าง $n_1$ และ $n_2$?


สิ่งนี้ทำให้ฉันและเพื่อนร่วมงานสับสนในช่วงสองสามวันที่ผ่านมา เนื่องจากสองแนวทางที่แตกต่างกันขัดแย้งกัน:

วิธีที่ 1:

ตามคำจำกัดความของความต้านทานการชน $H'$ มีเอาต์พุตของ $n_1$ ความยาวและดังนั้นหากเราพบการโจมตีที่มีความซับซ้อนน้อยกว่า $\mathcal O(2^{n_1/2})$ มันไม่ทนต่อการชน

พวกเราต้องการ $$\mathcal O(2^{n_2/2}) < \mathcal O(2^{n_1/2}) \implies \ldots \implies n_2 < n_1$$

ดังนั้นหาก $n_2 < n_1, H'$ ไม่ทนต่อการชน และในกรณีอื่นๆ


วิธีที่ 2:

สมมติว่า $H'$ ไม่ทนต่อการชน

แล้วมีอยู่แตกต่างกัน $x_1$ และ $x_2$ ดังนั้น $H'(x_1) = H'(x_2)$ เช่น. $h_1(h_2(x_1)) = h_1(h_2(x_2))$

ที่สามารถเกิดขึ้นได้หาก $h_2(x_1) = h_2(x_2)$, แต่ $h_2$ มีความทนทานต่อการชน

นอกจากนี้ยังสามารถเกิดขึ้นได้หาก $h_1(A) = h_1(B)$ ที่ไหน $A = h_2(x_1)$ และ $B = h_2(x_2)$ แต่ $h_1$ มีความทนทานต่อการชน

เราได้พิสูจน์แล้วว่า $H'$ มีความทนทานต่อการชนและความสัมพันธ์ของ $n_1$ และ $n_2$ ไม่เป็นไร

kelalaka avatar
in flag
ยินดีต้อนรับสู่ [cryptography.se]นี่เป็นคำถามการบ้านหรือไม่? (เรามีหลอกสำหรับสิ่งนี้)
kelalaka avatar
in flag
คำใบ้: ถ้า $n_1 = n_2$ ดังนั้นวิธีที่ 1 จะเหมือนกับวิธีที่ 2 เมื่อต่างกัน $n_2
John St avatar
id flag
มันเป็นการเตรียมตัวสำหรับการสอบวิทยาการเข้ารหัสลับประยุกต์ของอาจารย์ ฉันเคยเห็นคนหลอกลวงแต่ไม่พบแนวทางแรกที่ไหนเลย
John St avatar
id flag
จากความคิดเห็นของคุณฉันรู้ว่าโซลูชันหลังถือว่า $n_1=n_2$ ? แม้ว่าฉันจะเข้าใจได้อย่างไรว่ามันใช้ไม่ได้กับปัญหานี้
Score:4
ธง my

สิ่งนี้ทำให้ฉันและเพื่อนร่วมงานสับสนในช่วงสองสามวันที่ผ่านมา เนื่องจากสองแนวทางที่แตกต่างกันขัดแย้งกัน

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

ความพยายามครั้งแรกใช้คำจำกัดความ 'ไม่มีการชนกันของการค้นหาสิ่งที่แนบมาซึ่งใช้เวลาน้อยกว่านั้น $\mathcal{O}(2^{n/2})$ การดำเนินงาน; เพราะ $n$ ได้รับการแก้ไขแล้ว เราใช้สิ่งนี้เป็นชวเลขสำหรับ 'การจู่โจม $c2^{n/2}$ การดำเนินการสำหรับบางคน $ค$ ไม่ไกลจาก 1 มากนัก และคำจำกัดความของการดำเนินการที่สมเหตุสมผล (ในกรณีนี้ การประเมินฟังก์ชันแฮช)

ปัญหาของคำจำกัดความนี้คือมันนำไปสู่ข้อสรุปที่ไร้สาระ เช่น SHA-256 ที่ถูกตัดเหลือ 8 บิตคือ 'ทนต่อการชนกัน' ตามคำจำกัดความนี้ ในอีกทางหนึ่ง เอาต์พุต 1kbyte จาก SHAKE-256 ไม่ใช่ 'การต้านทานการชน' เนื่องจากคุณจะพบการชนกันที่น้อยกว่า $2^{8192/2}$ การประเมินแฮช

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

ด้วยคำจำกัดความนี้ แนวทางที่ 2 อาจถูกเปลี่ยนใหม่เป็น 'หากเราคิดไปเอง' $H'$ ไม่ชนกันก็รู้แล้ว $x \n y$ กับ $H'(x) = H'(y)$. แล้วอย่างใดอย่างหนึ่ง $h_2(x) = h_2(y)$ (และด้วยเหตุนี้ $h_2$ ไม่ทนต่อการชนอย่างที่เราทราบกันดีว่าเกิดการชนกัน) หรือ $h_2(x) \ne h_2(y)$ซึ่งในกรณีนี้เรามี $h_1(u) = h_1(v)$ สำหรับ $u = h_2(x), v = h_2(y), คุณ \ne v$ (และด้วยเหตุนี้ $h_1$ ไม่ทนต่อการชน ดังที่เราทราบกันดีว่าเกิดการชนกัน)

John St avatar
id flag
นี่หมายความว่าทั้งสองวิธีถูกต้อง แต่เกี่ยวข้องกับคำจำกัดความการต้านทานการชนที่แตกต่างกันหรือไม่
poncho avatar
my flag
@JohnSt: จริง ๆ แล้วฉันคิดว่าฉันทำให้ชัดเจนว่าฉันไม่คิดว่าคำจำกัดความในแนวทางที่ 1 นั้นถูกต้องจริงๆ อย่างไรก็ตาม ตราบใดที่คุณเข้าใจปัญหา คุณก็สามารถตัดสินใจได้เอง
John St avatar
id flag
ฉันเข้าใจแล้ว ขอบคุณสำหรับคำอธิบายของคุณ ฉันอยู่บนเรือที่เข้าใกล้ 2 ตั้งแต่เริ่มต้น ดังนั้นฉันจะใช้สิ่งนั้นในกรณีที่ปรากฏในการสอบ และยังระบุว่าฉันจะใช้คำจำกัดความของการต้านทานการชนแบบใด
Score:0
ธง id

ฉันได้โอกาสถามอาจารย์ของฉัน และเขาคาดหวังคำตอบแรก ตามที่ครั้งที่สองสันนิษฐาน $ n_1 = n_2 $ (ฉันยังไม่รู้ว่าทำไปทำไมหรือที่ไหน)

นอกจากนี้เขายังอธิบายว่า:

  • $n_2$ จำนวน 1,000 บิต แล้วแปลงเป็น $n_1$ ของ 2 บิตถือว่าทนต่อการชนกันเนื่องจากคุณใช้การรักษาความปลอดภัยเต็มรูปแบบที่ 2 บิตมอบให้ นั่นคือ คุณได้รับค่าทั้งหมดที่ 2 บิตที่คุณ "จ่าย" ไป
  • ในทางตรงกันข้าม $n_2$ จำนวน 500 บิต แล้วแปลงเป็น $n_1$ 1,000 บิตไม่ถือว่าเป็นการต่อต้านการชนกันเนื่องจากคุณ "จ่าย" เพื่อความปลอดภัย 1,000 บิตและใช้เพียง 500

สิ่งนี้ช่วยให้ฉันเข้าใจแนวคิดด้วยวิธีที่เข้าใจได้ง่ายและมีเหตุผล

poncho avatar
my flag
ดังนั้นเขาจึงอ้างว่าฟังก์ชันแฮชที่มีเอาต์พุต 2 บิตสามารถ "ต้านทานการชนกัน" ได้? ฉันขอโทษ แต่นั่นขัดแย้งกับความเข้าใจของฉันอย่างมากเกี่ยวกับความหมายของ "การต้านทานการชน"...
poncho avatar
my flag
ยิ่งฉันคิดถึงเรื่องนี้มากเท่าไหร่ คำจำกัดความของศาสตราจารย์ก็ยิ่งน้อยลงเท่านั้น เรากำหนดคำ ไม่ใช่เพราะเราชอบสร้างคำนิยาม แต่เพราะคำนิยามเหล่านั้นมีประโยชน์ คำจำกัดความของฉันเกี่ยวกับการป้องกันการชนกัน (เราไม่ทราบถึงการชนกัน และไม่ทราบวิธีปฏิบัติในการค้นหาการชนกัน) ให้ยืมตัวเองเป็นข้อสันนิษฐานด้านความปลอดภัยในการพิสูจน์ความปลอดภัยต่างๆ ของสิ่งต่าง ๆ ที่เกี่ยวข้องกับฟังก์ชันแฮช ในทางตรงกันข้าม ฉันไม่สามารถนึกถึงการใช้เพียงครั้งเดียวสำหรับ "สำหรับฟังก์ชันแฮช 2 บิตนี้ เราจะไม่พบการชนกันโดยไม่ทำการประเมิน $\sqrt{2^2}$ แฮช"
John St avatar
id flag
วิธีที่ฉันได้รับคือคำจำกัดความของความต้านทานการชนนั้นเป็นเกณฑ์การใช้งานมากกว่า ตัวอย่างเช่น มีการใช้ฟังก์ชัน 2 บิตเพื่อให้ค่าความต้านทานสูงสุดที่เป็นไปได้สำหรับความยาวเอาต์พุต ผลิตภัณฑ์ขั้นสุดท้ายจะเพียงพอหรือไม่และมีความต้านทานต่อการชนเพียงพอหรือไม่ (ขึ้นอยู่กับความต้องการไม่ใช่คำจำกัดความ) นั้นเป็นคนละเรื่องกัน
John St avatar
id flag
ที่กล่าวว่าฉันยอมรับว่าคำจำกัดความนั้นค่อนข้างแปลกและทำให้เข้าใจผิด
John St avatar
id flag
ตัวอย่างการใช้งานสำหรับคำจำกัดความนี้คือว่าฟังก์ชันใดๆ $H'$ ที่ประกอบด้วยหลายฟังก์ชันถูกนำไปใช้เพื่อใช้ความปลอดภัยของฟังก์ชันที่เกี่ยวข้องอย่างเต็มที่หรือไม่ (เช่น คุณไม่สามารถหักได้ง่ายขึ้นโดยการเบรกฟังก์ชันภายในที่เป็นส่วนหนึ่งของมัน)

โพสต์คำตอบ

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