ฉันได้สะดุดกับความคิดเห็นมากมาย ดังนั้นฉันจึงถามเกี่ยวกับพวกเขาด้วยตัวเอง
อนุญาต $H(x)$ และ $F(x)$ เป็นฟังก์ชันแฮช
พื้นหลัง
จากการค้นคว้าของฉันเอง ฉันพบข้อความที่แนะนำว่าการรวม ชม และ ฉ เป็นวิธีปฏิบัติทั่วไปที่จะรักษาความปลอดภัยเมื่อหนึ่งในนั้นกลายเป็นไม่ปลอดภัย แต่ก็มีความคิดเห็นที่หลากหลายเมื่อพูดถึงว่าการรวมกันดังกล่าวปลอดภัยหรือไม่ สูงสุด (สูง, F) หรือ นาที(สูง, ฉ) ในเรื่องความปลอดภัยแทบไม่มีใครแนะนำว่าความปลอดภัยจะสูงหรือต่ำกว่านี้
ฉันยังพบว่าอัลกอริทึมบางอย่างเกี่ยวกับรหัสผ่านใช้ SHA256dซึ่งโดยหลักแล้ว SHA256(SHA256(x))และในทางทฤษฎีแล้ว การใช้รอบมากขึ้นจะเพิ่มความปลอดภัยในการแฮช ซึ่งไม่ไกลจากการรวมแฮชเข้ากับตัวมันเอง
ฉันยังมีความคิดส่วนตัวเกี่ยวกับเรื่องนี้ ซึ่งมาจากวิชาคณิตศาสตร์ในโรงเรียน ดูเหมือนว่าจะชัดเจนสำหรับฉันว่าถ้า f:A -> B และอย่างมาก |ก| > |ข| และ g:B -> C และอย่างมาก |ข| > |ค| แล้ว ก(ฉ(x)) น่าจะเกิดการชนกันมากกว่านี้ ฉ หรือ ช. แต่ความจริงที่ว่าเรารวมสองฟังก์ชันที่ซับซ้อนเข้าด้วยกันควรจะ "แตก" ได้ยากขึ้น
ดังนั้นสัญชาตญาณของฉันเองก็คือ ก(ฉ(x)) มีการชนกันมากขึ้น แต่เป็นการยากที่จะหาวิธีค้นหาการชนกันโดยตั้งใจ และในกรณีของฟังก์ชันเช่น SHA หรือ เบลค การชนกันที่เพิ่มขึ้นไม่ใช่ปัญหา แต่ประโยชน์ด้านความปลอดภัยนั้นคุ้มค่า
องค์ประกอบไม่ใช่วิธีที่ดีที่สุดในการรวมฟังก์ชันแฮช แต่ความเสี่ยงคือคำถามเกี่ยวกับคุณสมบัติความปลอดภัยที่คุณต้องการ
สำหรับการต้านทานการชน การค้นหาการชนบน $H(F(X))$ ไม่ยากไปกว่าการหาจุดชนกันของ $F(X)$ และถ้า $F$ การปะทะกันถูกบุกรุก ดังนั้นก็คือ $H(F(X))$. หากต้องการดูสิ่งนี้ให้ $m_1$ และ $m_2$ เป็นสองอินพุตที่แตกต่างกันเช่นนั้น $F(m_1)=F(m_2)$ แล้วเพราะ $H$ เป็นหน้าที่ที่เรามี $H(F(m_1))=H(F(m_2))$. ในกรณีพิเศษ $F=H$, $H(สูง(X))$ ไม่ทนต่อการชนมากไปกว่า $H(X)$.
ในทำนองเดียวกันถ้า $H(X)$ เกิดการปะทะกันและ $F(X)$ ภาพล่วงหน้าถูกบุกรุก (ถูกบุกรุกอย่างมากเพื่อให้ภาพล่วงหน้าใช้เวลาน้อยกว่างานวันเกิด) เราสามารถประนีประนอมการชนกันได้ $H(F(X))$ โดยพบการชนบน $H$ แล้วหาภาพล่วงหน้าของข้อความทั้งสองที่ชนกัน
สังเกตความแตกต่างของฟังก์ชันภายในและภายนอก ขณะนี้เราสามารถค้นหาข้อความ $m_1$ และ $m_2$ ดังนั้น $\mathrm{SHA3}(\mathrm{SHA1}(m_1))=\mathrm{SHA3}(\mathrm{SHA1}(m_2))$แต่เราหาไม่เจอ $m_3$ และ $m_4$ ดังนั้น $\mathrm{SHA1}(\mathrm{SHA3}(m_3))=\mathrm{SHA1}(\mathrm{SHA3}(m_4))$.
ในทำนองเดียวกันสำหรับการต่อต้านภาพก่อนวินาที หากฟังก์ชันภายในเป็นภาพก่อนภาพที่สองถูกบุกรุก ดังนั้นการจัดองค์ประกอบภาพก็เช่นกัน
สำหรับการต้านทานภาพล่วงหน้าแบบเต็ม เราสามารถหาภาพล่วงหน้าแบบเต็มสำหรับการจัดองค์ประกอบได้อย่างแน่นอน หากเราสามารถหาภาพล่วงหน้าแบบเต็มสำหรับทั้งสอง $H$ และ $F$. การประนีประนอมภาพล่วงหน้าของฟังก์ชันแฮชเดียวไม่เพียงพอ: พิจารณาแฮชเชิงเส้น $L(X)$ ซึ่งเป็นภาพก่อนหักเล็กน้อย สำหรับเป้าหมาย $Y$เราไม่สามารถหาได้ $X$ ดังนั้น $\mathrm{SHA3}(L(X))=Y$ ก็ไม่เช่นกัน $L(\mathrm{SHA3}(X))=Y$.
ในฐานะที่เป็นเกร็ดความรู้ทั่วไป การรวมการเข้ารหัสแบบดั้งเดิมนั้นไม่ค่อยจะได้ชัยชนะโดยตรง มันสามารถเสริมคุณสมบัติบางอย่างหากทำถูกต้อง แต่ทำให้คุณสมบัติอื่นอ่อนแอลงดังนั้นควรทำเฉพาะเมื่อเสริมความแข็งแกร่งให้กับคุณสมบัติที่คุณสนใจและไม่ทำให้คุณสมบัติที่คุณสนใจลดลง
การรวม H และ F เป็นวิธีปฏิบัติทั่วไปที่จะรักษาความปลอดภัยเมื่อหนึ่งในนั้นกลายเป็นไม่ปลอดภัย แต่มีความคิดเห็นที่หลากหลายเมื่อพูดถึงว่าการผสมดังกล่าวปลอดภัยเท่ากับ MAX(H, F) หรือ MIN(H, F) ในแง่ของ ความปลอดภัยแทบไม่มีใครแนะนำว่าความปลอดภัยจะสูงหรือต่ำกว่านี้
คุณพบความคิดเห็นที่หลากหลายเพราะมันขึ้นอยู่กับว่าคุณทำการผสมผสานอย่างไร (นั่นหรือเพราะคนไม่รู้มันเลยเกิดขึ้น)
ฉันยังมีความคิดส่วนตัวเกี่ยวกับเรื่องนี้ ซึ่งมาจากวิชาคณิตศาสตร์ในโรงเรียน ดูเหมือนว่าจะชัดเจนสำหรับฉันว่าถ้า
f:A -> Bและอย่างมาก|ก| > |ข|และg:B -> Cและอย่างมาก|ข| > |ค|แล้วก(ฉ(x))ควรมีการชนกันมากกว่า f หรือ g มาก
การนับการชนนั้นไม่เกี่ยวข้อง สิ่งที่สำคัญคือความยากลำบากในการค้นหาพวกเขา MD5(x)||SHA1(x) เป็นแฮช 288 บิต และอาจมีการชนกันของสตริง 257 บิตน้อยกว่า SHA256(x) â ในความเป็นจริงเป็นไปได้ว่า MD5(x)||SHA1(x) ไม่มีการชนกันบนสตริง 257 บิตเลย ในขณะที่ SHA256(x) จะต้องมีการชนกันตามหลักนกพิราบ แต่เรารู้วิธีค้นหาการชนกัน MD5(x)||SHA1(x) สำหรับสตริงที่ยาวขึ้นเล็กน้อยในเวลาที่ยาวนานแต่ทำได้ (แพงกว่าการชนกันของ SHA1 เพียงเล็กน้อยเท่านั้น) ในขณะที่เราไม่รู้วิธีค้นหาการชนกันของ SHA256 เลย
แต่ความจริงที่ว่าเรารวมสองฟังก์ชันที่ซับซ้อนเข้าด้วยกันควรจะ "แตก" ได้ยากขึ้น
ไม่ นี่ไม่ใช่ข้อเท็จจริง ทั้งหมดขึ้นอยู่กับสิ่งที่คุณกำลังรวมและอย่างไร
เกี่ยวกับ กัญชา และ ความต้านทานการชน, การเขียนสองแฮชจะลดความปลอดภัย. กล่าวอีกนัยหนึ่ง $H \circ F$ มีความทนทานต่อการชนน้อยกว่า $H$ หรือ $F$ ด้วยตัวมันเอง
มันง่ายที่จะเห็นว่าถ้า $F$ มีการปะทะกันแล้ว $H \circ F$: ถ้า $F(x_1 = F(x_2)$ กับ $x_1 \n x_2$ แล้ว $(H \circ F)(x_1) = H(F(x_1)) = H(F(x_2)) = (H \circ F)(x_2)$. สิ่งนี้เพียงอย่างเดียวหมายความว่าการเขียนสองแฮชนั้นไร้ประโยชน์หากสิ่งที่คุณสนใจคือการต้านทานการชนกัน: คุณอาจใช้ $F$.
ความต้านทานการชนของ $H \circ F$ ได้ดีกว่าของ $H$ ตามลำพัง. ถ้า $H$ มีการชนกัน $H(y_1) = H(y_2)$ กับ $y_1 \ไม่มี y_2$เพื่อใช้ข้อเท็จจริงนี้เพื่อหาข้อขัดแย้งสำหรับ $H \circ F$คุณต้องหาภาพล่วงหน้าสำหรับทั้งคู่ $y_1$ และ $y_2$. คุณจึงมั่นใจได้ว่า $F$ ทนต่อการชนและป้องกันพรีอิมเมจ $H \circ F$ ได้อย่างปลอดภัยกว่า $H$ ในแง่ของการต้านทานการชน อย่างไรก็ตาม เนื่องจากไม่ปลอดภัยกว่า $F$เหตุผลเดียวที่จะใช้การก่อสร้างนี้คือหากปรับปรุงคุณสมบัติอื่น ๆ
ถ้า $H \circ F$ มีการชนกันเช่นถ้า $H(F(x_1)) = H(F(x_2))$ กับ $x_1 \n x_2$แล้วอย่างใดอย่างหนึ่ง $F(x_1) = F(x_2)$ และนี่คือการปะทะกันของ $F$, หรือ $F(x_1) \ne F(x_2)$ และนี่คือการปะทะกันของ $H$. ดังนั้นการจัดองค์ประกอบภาพจึงไม่แย่ไปกว่าการต้านทานการชนของทั้งสองแบบ
การสร้างสองแฮชสามารถปรับปรุงความต้านทานของพรีอิมเมจได้ เพื่อใช้ประโยชน์จากโครงสร้างของ $H \circ F$ เมื่อต้องการค้นหาภาพล่วงหน้า คุณต้องค้นหาภาพล่วงหน้าทั้งสองแบบ $H$ แล้วเป็นภาพล่วงหน้าของสิ่งนั้น $F$. อย่างไรก็ตาม ไม่มีฟังก์ชันแฮชการเข้ารหัสใดที่ฉันจะถือว่ามีคุณสมบัติเป็นกระแสหลักที่เคยมีความต้านทานของพรีอิมเมจเสีย ดังนั้นจึงไม่ใช่เรื่องที่ต้องกังวลในทางปฏิบัติ
ความต้านทานต่อพรีอิมเมจเป็นปัญหาสำหรับ รหัสผ่าน ฟังก์ชันแฮช แต่ ฟังก์ชันแฮชรหัสผ่านเป็นรูปแบบดั้งเดิมของการเข้ารหัสที่แตกต่างอย่างสิ้นเชิงจากฟังก์ชันแฮชแบบธรรมดา. มีพารามิเตอร์ที่แตกต่างกันและวัตถุประสงค์ด้านความปลอดภัยที่แตกต่างกัน ความต้านทานการชนไม่เกี่ยวข้องกับการแฮชรหัสผ่าน การเขียนฟังก์ชันแฮชรหัสผ่านสองฟังก์ชันอาจสมเหตุสมผล แต่คุณต้องระวัง: เป็นไปได้ที่จะทำผิดอย่างแน่นอน.
การสร้างแฮชสองตัวยังสามารถปรับปรุงคุณสมบัติความปลอดภัยอื่นนอกเหนือจากคุณสมบัติที่กำหนดฟังก์ชันแฮชการเข้ารหัส แฮชมักใช้เป็น ออราเคิลแบบสุ่มและแฮชที่ใช้กันทั่วไป (เช่น ตระกูล SHA-2) เป็นที่ทราบกันดีว่าไม่สมบูรณ์ในฐานะออราเคิลแบบสุ่ม เนื่องจาก การโจมตีส่วนขยายความยาว. การสร้างแฮชสองตัว แม้แต่ฟังก์ชันเดียวกัน เช่นใน SHA256d(x) = SHA256(SHA256(x))กำจัดการโจมตีแบบขยายความยาวและไม่แนะนำจุดอ่อนอื่นที่รู้จักในตัวเอง (âด้วยตัวของมันเองâ เป็นสิ่งสำคัญ: หากคุณผสม SHA256d และ SHA256 ในข้อมูลเดียวกัน ผลลัพธ์ที่ได้อาจเสียหายได้)
อีกวิธีง่ายๆ ในการรวมสองแฮชคือการต่อเข้าด้วยกัน: $H(x) || F(x)$. นี่คือการปรับปรุงที่ชัดเจนในแง่ของความต้านทานการชน: หากมีการชนสำหรับ $H || เอฟ$ก็ยังเป็นการชนกันของ $H$ และ $F$. การต่อข้อมูลยังปรับปรุง ความต้านทานพรีอิมเมจที่สอง: ถ้าคุณรู้ $H(x_1) || F(x_1)$ และคุณต้องการหา $x_2 \n x_1$ ดังนั้น $H(x_1) || F(x_1) = H(x_2) || F(x_2)$คุณต้องหาภาพตัวอย่างที่สองสำหรับทั้งคู่ $F$ และ $H$. สำหรับทั้งความต้านทานการชนกันและความต้านทานพรีอิมเมจที่สอง การต่อเชื่อมอย่างน้อยที่สุดจะแข็งแกร่งพอๆ กับที่อ่อนแอกว่าของทั้งสอง และอาจแข็งแกร่งกว่า
ตัวอย่างที่ใช้การต่อข้อมูลในโปรโตคอลในโลกแห่งความเป็นจริงคือเวอร์ชันที่เก่ากว่าของ โปรโตคอล SSL/TLS, อัพเป็นเวอร์ชั่น 1.1. พวกเขาใช้ MD5(x)||SHA1(x) สำหรับลายเซ็นจับมือซึ่งประเด็นสำคัญด้านความปลอดภัยคือการต่อต้านภาพที่สอง ทล.1.2 แทนที่สิ่งนี้ด้วยฟังก์ชันแฮชเดียวที่ปรับแต่งได้ (โดยทั่วไปคือ SHA-256 หรือ SHA-384): ความซับซ้อนที่เพิ่มขึ้นนั้นไม่คุ้มค่า (และไม่มีฟังก์ชันแฮชยอดนิยมที่เหมาะสมที่จะรวมเข้ากับ SHA-256 ในเวลานั้น)
การต่อข้อมูลไม่ใช่การชนะที่ชัดเจน ตัวอย่างเช่นมันลดลง แนวต้านพรีอิมเมจแรก ให้กับผู้ที่อ่อนแอกว่าทั้งสองหน้าที่: ถ้าคุณรู้ $H(x) || F(x)$ แล้วคุณจะพบ $x$ หากคุณรู้วิธีการทำเช่นนี้ผ่านทาง $H(x)$ หรือทาง $F(x)$.
อีกวิธีหนึ่งในการรวมสองแฮชคือการ xor พวกมัน: $H(x) \oบวก F(x)$. คุณสมบัติความปลอดภัยของผลลัพธ์ขึ้นอยู่กับตัวเลือกของฟังก์ชัน สิ่งนี้มีศักยภาพที่ชัดเจนว่าจะเกิดความผิดพลาดอย่างมหันต์: กรณีพิเศษ $H = F$ ผลลัพธ์ในเอาต์พุตที่เป็นศูนย์บิตทั้งหมด ในทางกลับกัน ถ้า $H$ และ $F$ เป็นอิสระแล้ว $H \oบวก F$ อย่างน้อยก็ดีเท่ากับผู้ที่แข็งแกร่งกว่าของทั้งสองในฐานะออราเคิลแบบสุ่ม ฉันไม่แน่ใจว่ามีเงื่อนไขที่เหมาะสมที่จะรับประกันการต้านทานการชนหรือไม่
ความปลอดภัยเป้าหมายของฟังก์ชันแฮชการเข้ารหัส เช่น SHAx, BLAKE เป็นต้น คือการต้านทานการชนกัน ค่าใช้จ่ายในการโจมตีแบบปะทะทั่วไปแบบคลาสสิกคือ $\mathcal{O}(2^{n/2})$- เวลาเนื่องจากการโจมตีวันเกิด
ตอนนี้ดูองค์ประกอบแฮชของคุณในรายละเอียดเล็กน้อย
- เป็น $H(ฟ(x))$ หรือ $F(สูง(x))$ ปลอดภัยกว่า $H(x)$ หรือ $F(x)$
การแฮชสองครั้งเสนอโดย Bruce Schneier เพื่อลด การโจมตีส่วนขยายความยาว ของฟังก์ชันแฮชที่ใช้ MD การโจมตีส่วนขยายความยาวดำเนินการกับคำนำหน้าลับ $H(ความลับ||ข้อความ)$. การแฮชสองครั้งได้รับการออกแบบเป็น $H(สูง(x))$ และ Bitcoin ใช้ SHA256d เพื่อให้การขุดช้า. กรณีของคุณแตกต่างออกไป อย่างไรก็ตาม การโจมตีนี้จะใช้ได้เฉพาะในกรณีที่คุณต้องการใช้แฮชนี้เพื่อสร้าง MAC ด้วยการสร้างคำนำหน้า-ความลับ ในการแฮชสองครั้ง ผู้โจมตีไม่สามารถขยายแฮชภายในได้ ดังนั้นจึงปลอดภัยต่อการขยายความยาว แม้ว่าจะไม่ได้แฮชเดี่ยวก็ตาม อย่างไรก็ตาม ใช้เวลานาน ให้ใช้ SHA3, SHA-512/256, BLAKE2, Shake ที่ปลอดภัยในลักษณะนี้อยู่แล้ว แม้แต่สำหรับคอมพิวเตอร์ควอนตัมเข้ารหัสที่เป็นไปได้
ฟังก์ชันแฮชการเข้ารหัสใด ๆ ที่มีการโจมตีด้วยส่วนขยายความยาวไม่ใช่ Oracle แบบสุ่ม ดังนั้น SHA3 และ BLAKE2 จึงใกล้เคียงกับออราเคิลแบบสุ่มมากกว่า
**
การชนกัน
ความต้านทาน**
หากแฮชภายใน $H$ หรือ $F$ ไม่ทนต่อการชนกันแล้วแฮชที่รวมกัน $H(ฟ(x))$ หรือ $F(สูง(x))$ จะไม่ทนต่อการชนกัน ที่ให้ไว้ $x,y$ กับ $x\neq y$, ถ้า $H(x)=H(y)$ แล้ว $F((H(x))=F(H(y))$ คือการชนกันขององค์ประกอบ และในทำนองเดียวกันสำหรับ $H(F(\cdot))$ กรณี.
หากคุณต้องการลดการโจมตีแบบชนกันของฟังก์ชันแฮชภายใน คำตอบง่ายๆ คือ อย่าใช้มัน
ความต้านทานต่อภาพล่วงหน้า
อิมเมจพรีอิมเมจตัวแรกและตัวที่สองมีปัญหาเดียวกัน ข้ามที่นี่
- เป็น $H(ฟ(x))$ หรือ $F(สูง(x))$ ปลอดภัยเมื่อ $H(x)$ หรือ $F(x)$ กลายเป็นความเสี่ยง
เมื่อไร $F(x)$ มีการปะทะกันแล้ว $H(ฟ(x))$ มีการชนกันเล็กน้อยตอบในส่วนแรก
อนุญาต $F(x)$ ปลอดภัย (ไม่ชน ไม่ต่อความยาว ไม่พรีอิมเมจ) แต่ไม่ใช่ $H(x)$ แล้วจะเป็นอย่างไร $H(ฟ(x))$? นี่เป็นเรื่องยุ่งยากเล็กน้อยที่จะใช้การโจมตีแบบปะทะกันของ $H$ เราต้องหาภาพก่อนของ $F$ ดังนั้นจึงปลอดภัยกว่า
- เป็น $H(สูง(x))$ ปลอดภัยกว่า $H(x)$
ใช่เล็กน้อย; $H(สูง(x))$ ปลอดภัยจากการโจมตีส่วนขยายความยาว หากมีการปะทะกันของ $H$, $H(x)=H(y)$ กับ $x \neq y$ จากนั้นจึงเป็นการชนกันของคู่ $H(สูง(x)) = H(สูง(y))$, ด้วย.
ฉันยังพบว่าอัลกอริทึมบางอย่างที่เกี่ยวข้องกับรหัสผ่านใช้ SHA256d ซึ่งโดยหลักแล้วคือ SHA256(SHA256(x)) และในทางทฤษฎีแล้วการใช้รอบมากขึ้นจะเพิ่มความปลอดภัยในการแฮช ซึ่งไม่ไกลจากการรวมแฮชเข้ากับตัวมันเอง
ใครก็ตามที่ใช้ SHA256d ในการแฮชรหัสผ่าน พวกเขาไม่รู้อะไรเลยเกี่ยวกับพวกเขา การแฮชรหัสผ่านต้องใช้เวลา หน่วยความจำ และการใช้เธรดเพื่อลดการค้นหาจำนวนมากด้วย CPU, GPU หรือ ASIC
SHA256d ใช้ใน Bitcoin ที่จะมี การขุดช้า. ระบบที่ออกแบบใหม่สำหรับการแฮชรหัสผ่านควรใช้ Scrypt เป็นอย่างน้อยหรือ Argon2 ที่ดีกว่า และระบบเก่าควรได้รับการโอนย้ายโดยเร็วที่สุด
สำหรับผลการศึกษาโดยละเอียดเกี่ยวกับตัวรวมแฮชให้เริ่มอ่านจาก
และแม้กระทั่งอาจก่อให้เกิดการชนกันหลายครั้ง
คนส่วนใหญ่ไม่เข้าใจว่าการถามคำถามมากมายจะปลดล็อกการเรียนรู้และปรับปรุงความสัมพันธ์ระหว่างบุคคล ตัวอย่างเช่น ในการศึกษาของ Alison แม้ว่าผู้คนจะจำได้อย่างแม่นยำว่ามีคำถามกี่ข้อที่ถูกถามในการสนทนา แต่พวกเขาไม่เข้าใจความเชื่อมโยงระหว่างคำถามและความชอบ จากการศึกษาทั้ง 4 เรื่องที่ผู้เข้าร่วมมีส่วนร่วมในการสนทนาด้วยตนเองหรืออ่านบันทึกการสนทนาของผู้อื่น ผู้คนมักไม่ตระหนักว่าการถามคำถามจะมีอิทธิพลหรือมีอิทธิพลต่อระดับมิตรภาพระหว่างผู้สนทนา
