จากฟังก์ชันแฮชและค่าแฮช คุณบอกได้ไหมว่าสร้างค่าดังกล่าวได้หรือไม่

ฉันเกิดคำถามต่อไปนี้:

กำหนดฟังก์ชันแฮช ชม() และค่าแฮช ชม. ซึ่งอยู่ในโคโดเมน/เรนจ์ของเอาต์พุตของ ชม()คุณสามารถระบุได้ว่า ชม. สามารถผลิตได้โดย ชม() (กล่าวคือ ชม. ในรูปของ ชม())?

ตอบคำถามได้หรือไม่ มันขัดแย้งกับคุณสมบัติการต้านทานของพรีอิมเมจหรือไม่?

มีประโยชน์อะไรบ้างที่คุณสามารถนึกถึงสำหรับฟังก์ชันแฮชที่มีคุณสมบัติข้างต้น (ซึ่งคุณไม่สามารถบอกได้ว่า ชม. สามารถผลิตได้โดยฟังก์ชันแฮช)?

กำหนดฟังก์ชันแฮช H() และค่าแฮช h ที่อยู่ในโคโดเมน/เรนจ์ของเอาต์พุตของ $H()$คุณสามารถระบุได้ว่า $h$ สามารถผลิตได้โดย $H()$ (กล่าวคือ $h$ ในรูปของ $H()$)?

โดยทั่วไป, คุณไม่สามารถ หากคุณพิจารณา $H$ ให้เป็นกล่องดำ ฉันจะแปลกใจถ้ามีค่าที่ฟังก์ชันแฮชไม่สามารถเข้าถึงได้เช่น SHA-2/3 เนื่องจากวิธีการสร้างค่าเหล่านี้ ในคำถาม/คำตอบที่ฉันชี้ไป ในตอนท้าย คุณจะต้องดูการทำงานภายในของฟังก์ชันแฮช

ตอบคำถามได้หรือไม่ มันขัดแย้งกับคุณสมบัติการต้านทานของพรีอิมเมจหรือไม่?

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

มีประโยชน์อะไรบ้างที่คุณสามารถนึกถึงสำหรับฟังก์ชันแฮชที่มีคุณสมบัติข้างต้น (ซึ่งคุณไม่สามารถบอกได้ว่า $h$ สามารถผลิตได้โดยฟังก์ชันแฮช)?

คุณสามารถเช่น ใช้ค่าเหล่านั้นเพื่อระบุว่ามีบางอย่างผิดพลาด - หากคุณสามารถค้นหาค่าเหล่านั้นเจอ ตัวอย่างเช่น คุณอาจนึกถึงช่องแอบแฝงโดยใช้ค่าดังกล่าว แต่โปรดทราบว่าด้วยความต้านทานภาพล่วงหน้า คุณก็สามารถเลือกบางรายการจากโคโดเมนได้เช่นกัน

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

ด้วยโครงสร้างปกติ อาจเป็นเรื่องยากที่จะซ่อนค่าพิเศษประเภทนี้จากค่าอื่นๆ ที่วิเคราะห์โครงสร้างภายในของฟังก์ชันแฮช โดยเฉพาะอย่างยิ่งในระยะยาว ที่กล่าวว่าคุณสามารถดูเช่น Dual_EC_DRBG เพื่อให้เข้าใจว่าคุณสามารถทำสิ่งที่น่ารังเกียจได้ด้วยอัลกอริทึม โดยเฉพาะอย่างยิ่งเมื่อต้องเลือกค่าคงที่

กำหนดฟังก์ชันแฮช $\mathcal H()$ และค่าแฮช $H$ ซึ่งอยู่ในโคโดเมน/เรนจ์ของเอาต์พุตของ $\mathcal H()$คุณสามารถระบุได้ว่า $H$ สามารถผลิตได้โดย $\mathcal H()$ (กล่าวคือ $H$ ในรูปของ $\mathcal H()$)?

ฉันจะถือว่า "codomain/range of outputs" ถูกกำหนดโดยไม่มีการอ้างอิงถึงสิ่งที่แฮชส่งออกจริง (แทนที่จะเป็นชุดของเอาต์พุตที่แท้จริงของแฮช ซึ่งจะทำให้ทั้งหมดเข้าถึงได้ตามคำจำกัดความ)

หากเป็นฟังก์ชันแฮช $\คณิตศาสตร์ H$ เป็นเช่นนั้นสำหรับส่วนใหญ่ที่ได้รับ $H$ ในโคโดเมนหนึ่งกระป๋อง จัดแสดง ป้อนข้อมูล $M$ ดังนั้น $H(M)=H$ฟังก์ชันนั้นจะไม่ทนต่อภาพพรีอิมเมจ ดังนั้นนิทรรศการดังกล่าวจะต้องเป็นไปไม่ได้ในทางคำนวณสำหรับการสุ่ม $H$.

ถ้าเราจำลองแฮชเป็นฟังก์ชันสุ่ม $\{0,1\}^*\to\{0,1\}^n$จากนั้นต่อ นักสะสมคูปอง ปัญหา จำนวนแฮชของข้อความสุ่มที่คาดไว้เพื่อให้ได้ค่าทั้งหมดคือ $E=2^n\,(n\,\ln(2)+\gamma)+1/2+o(1)$. ในทางปฏิบัติ crypto $n\ge128$ ดังนั้น $\log_2(E)\ประมาณ n+\log_2(n)-0.53$. ดังนั้น โดยเฉลี่ยแล้ว เราจำเป็นต้องแฮชน้อยกว่าข้อความขนาด 33 ไบต์พอดีทั้งหมดเพื่อให้ได้ค่าทั้งหมดสำหรับแฮช 256 บิตในอุดมคติ แต่จำเป็นต้องแฮชมากกว่าข้อความขนาด 65 ไบต์พอดีทั้งหมดเพื่อให้ได้ค่าทั้งหมดสำหรับ 512- ในอุดมคติ แฮชบิต การทำแฮชจำนวนมากนั้นเป็นไปไม่ได้

สำหรับฟังก์ชันแฮชทั่วไป เช่น SHA-1, SHA-256, SHA-512 และผมเชื่อว่า SHA-3 ตามที่ระบุในนั้น คำตอบอื่น ๆเราไม่มีข้อพิสูจน์ทางคณิตศาสตร์ว่าสามารถเข้าถึงค่าเอาต์พุตได้ทุกค่า สิ่งที่ดีที่สุดที่เราสามารถพูดได้ก็คือมันน่าจะคงอยู่ (แม้กระทั่งการจำกัดข้อความที่มีขนาดพอดีกับบล็อกเดียว และยิ่งไปกว่านั้นด้วยจำนวนที่มากกว่านั้น) แต่คงจะน่าแปลกใจหากสามารถพิสูจน์หรือหักล้างได้

แต่ฉันคิดว่าเราสามารถสร้างฟังก์ชันแฮชที่ พิสูจน์ได้ ถึงพื้นที่เอาต์พุตทั้งหมด แต่ยังมีคุณสมบัติที่คาดหวังจากแฮชการเข้ารหัสในระดับมาก นี่คือแฮชผู้สมัครของ bitstring ตามอำเภอใจซึ่งแสดงให้เห็นอย่างชัดเจนถึงทั้งหมด $\{0,1\}^{512}$.

ฉันจะใช้ 3072 บิต นายกปลอดภัย $p$เป็นเช่นนั้น $q=(p-1)/2$ ยังเป็นนายก; และเครื่องกำเนิดไฟฟ้า $g$ ของกลุ่มตัวคูณ $\mathbb Z_p^*$, นั่นคือ $g\in[2,p-2]$ กับ $g^q\equiv-1\pmod p$. เราสามารถใช้ $p=2^{3072}-2^{3008}+2^{64}\,(\left\floor2^{2942}\,\pi\right\rfloor+1690314)-1$ ของ กลุ่ม MODP 3072 บิต, และ $g=\left\floor2^{3070}\,e\right\rfloor$.

คำนวณแฮช $H(M)\in\{0,1\}^{512}$ ของข้อความเข้า $M\in\{0,1\}^*$ ดังนี้

1. แปลงบิตสตริง $M$ เป็นจำนวนเต็ม $m$ ตามการประชุมใหญ่และติดตามความยาวของบิต $\ell$ ของ $M$.
2. คำนวณ $$\begin{จัด} m_0&=m\bmod(p-1)\ h_0&=(g^{m_0}\bmod p)-1\ h_1&=\left\floor h_0/2^{1024}\right\rfloor\bmod2^{512}\ h_2&=\left\floor h_0/2^{1664}\right\rfloor\bmod2^{512}\ m_1&=\left\lชั้น m/(p-1)\right\rชั้น\ \end{align}$$ หมายเหตุ: ค่าคงที่ 1024 และ 1664 เลือกตำแหน่งของเซ็กเมนต์ 512 บิตที่ไม่ทับซ้อนกันโดยพลการในการแสดงไบนารีของ $h_0$.
3. แปลง $h_1$ เพื่อ bitstring $H_1\in\{0,1\}^{512}$, $h_2$ เพื่อ bitstring $H_2\in\{0,1\}^{512}$, และ $m_1$ เพื่อ bitstring $M_1\in\{0,1\}^{\ell}$ ต่อการประชุมบิ๊กเอนด์
4. คำนวณและส่งออก $H=H_1\oplus H_2\oplus\ชื่อผู้ดำเนินการ{SHA3-512}(M_1)$.

การเปลี่ยนแปลงระหว่าง $m_0$ และ $h_0$ เป็นคำนามของ $[0,p-2]$. หากเป็นไปตามนี้เราคงสามารถค้นพบภาพจำลองได้ $M$ แต่อย่างใด $H\in\{0,1\}^{512}$ ถ้าเราสามารถแก้ DLP ในกลุ่มการคูณได้ $\mathbb Z_p^*$: เราแก้ไข $M_1=0^{3072}$ (ดังนั้น $\ell=3072$ และ $m_0=ม$), $h_0=2^{640}\,h_1$ (ดังนั้น $H_2=0^{512}$) ที่ให้เราคำนวณ $H_1=H\oplus\ชื่อผู้ประกอบการ{SHA3-512}(M_1)$, แล้ว $h_1$, แล้ว $h_0=2^{640}\,h_1$. เราแก้ปัญหา DLP $(g^{m_0}\bmod p)=h_0+1$ ที่จะได้รับ $m_0$, แล้ว $m$จากนั้น 3072 บิต $M$.

ข้อโต้แย้งของฉันที่ว่าแฮชนั้นทนต่อการชนกันและทนต่อพรีอิมเมจได้ $M\mapsto(M_1,m_0)$ เป็นยาฉีด $m_0\mapsto H_1\oplus H_2$ ดูเหมือนจะค่อนข้างยากที่จะพลิกกลับหรือชนกัน และ XORing นั้นด้วยแฮชที่ไม่เกี่ยวข้องกัน $M_1$ น้อยกว่าครึ่งหนึ่งของความต้านทานการชน

มีประโยชน์อะไรบ้างที่คุณนึกถึง ?

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

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

ฉันสามารถจินตนาการถึงแอปพลิเคชันสำหรับแฮชที่อาจไม่สามารถเข้าถึงได้ เป็นที่รู้จัก ค่าในพื้นที่เอาต์พุต (เช่น สามารถจองค่าดังกล่าวไว้เป็นตัวบ่งชี้กรณีพิเศษได้) ในทางกลับกัน เราสามารถสร้างแฮชดังกล่าวได้อย่างง่ายดายจากพื้นฐานทั่วไป ตัวอย่างเช่น สำหรับแฮช 256 บิตที่ไม่สามารถเข้าถึงได้ $0^{256}$เราสามารถใช้ (กับการแปลงปกติระหว่างบิตสตริงและจำนวนเต็ม) $M\mapsto(\operatorname{SHAKE128}(M,416)\bmod(2^{256}-1))+1$. และในทางปฏิบัติ เราสามารถใช้แฮชมาตรฐาน 256 บิตใดๆ ก็ได้