การปลอมแปลงลายเซ็นดิจิทัล

TLDR: การโจมตีถือว่าไม่ง่าย เป็นไปได้หรือไม่ขึ้นอยู่กับสมมติฐานที่ไม่ได้ระบุ

อันดับแรก เราจะใช้ถ้อยคำคำถามใหม่

เราถือว่าระบบการเข้ารหัสแบบอสมมาตร คล้ายกับตำราเรียน RSA ด้วย

• การสร้างคีย์ของคู่คีย์สาธารณะ/ส่วนตัว $(\mathrm{pk},\mathrm{sk})$,
• การเข้ารหัส $c:=E_\mathrm{pk}(p)$ ที่ไหน $p$ เป็นข้อความธรรมดา $ค$ เป็นไซเฟอร์เท็กซ์
• ถอดรหัสที่ตรงกัน $p:=D_\mathrm{sk}(c)$ ที่เหมาะกับทุกคน $ค$ ได้รับเป็น $E_\mathrm{pk}(p)$
• ที่ไหน $p$ และ $ค$ มาจากช่วงเวลาทั่วไป $[0,น)$, กับ $n$ ฝังอยู่ใน $\mathrm{pk}$ และ $\mathrm{sk}$.

เราถือว่าระบบการเข้ารหัสนี้มีความปลอดภัยภายใต้ การโจมตีข้อความธรรมดาที่รู้จัก.

เราถือว่าเป็นอุดมคติ ฟังก์ชันแฮช $\operatorname{แฮช}$ ด้วยเอาท์พุทใน $[0,h)$, กับ $h\le n$ สำหรับทุกอย่าง $(\mathrm{pk},\mathrm{sk})$ ระบบเข้ารหัสสร้างขึ้น

เราได้มา ลายเซ็นดิจิทัล โครงการที่ไหน

• การสร้างคีย์นั้นเหมือนกับในการเข้ารหัส
• ลายเซ็นของข้อความ $m$ เป็น $s=D_\mathrm{sk}(\operatorname{แฮช}(m))$
• ขั้นตอนการตรวจสอบ $\mathrm{Vrfy}_\mathrm{pk}(m,s)$ เอาต์พุต ผ่าน ถ้า $\operatorname{Hash}(m)=E_\mathrm{pk}(s)$, หรือ ล้มเหลว มิฉะนั้น.

ฉันขอเน้นย้ำว่านี่ไม่ใช่วิธีปกติในการสร้างลายเซ็น: ไม่มีรูปแบบลายเซ็นที่ใช้ในวงกว้างค่อนข้างตรงกัน² และอีกมากมาย เช่น DSA, ECDSA, EdDSA นั้นแตกต่างกันมาก

คำถามถามว่าแฮ็กเกอร์สามารถเลือกได้หรือไม่ $m$ และ $s$ ดังนั้น $\mathrm{Vrfy}_\mathrm{pk}(m,s)$ เอาต์พุต ผ่านเป็นเช่นนั้น $\operatorname{Hash}(m)=E_\mathrm{pk}(s)$.

ข่าวดี: ระบบลายเซ็นยืนยันสำเร็จเมื่อไม่มีการเปลี่ยนแปลงข้อความและลายเซ็น อาร์กิวเมนต์: ตั้งแต่ชุดอินพุตและเอาต์พุตของการเข้ารหัส $E_\mathrm{pk}$ เหมือนกันและมีฟังก์ชันถอดรหัส $D_\mathrm{sk}$ ที่กลับด้าน $E_\mathrm{pk}$ สำหรับทุกอย่าง $p$, ทั้งสอง $E_\mathrm{pk}$ และ $D_\mathrm{sk}$ เป็นการเรียงสับเปลี่ยนของเซตนั้น โดยอันหนึ่งกลับกัน ดังนั้นสำหรับทุกคน $ค$ ในชุดนั้นก็ถือ $E_\mathrm{pk}(D_\mathrm{sk}(c))=c$. ใช้สิ่งนี้กับ $c=\operatorname{แฮช}(m)$ซึ่งเงื่อนไข $h\le n$ ทำให้เป็นไปได้สำหรับทุกคน $m$เราเข้าใจแล้ว $E_\mathrm{pk}(s)=E_\mathrm{pk}(D_\mathrm{sk}(\operatorname{Hash}(m)))=\operatorname{Hash}(m)$, ดังนั้น $\mathrm{Vrfy}_\mathrm{pk}(m,s)$ เอาต์พุต ผ่าน.

ข่าวดีเพิ่มเติม: มันไม่ง่ายเลยสำหรับศัตรูที่ถือ $\mathrm{pk}$ เลือก $m$ และ $s$ ดังนั้น $\operatorname{Hash}(m)=E_\mathrm{pk}(s)$. ดูเหมือนจะไม่มีอะไรตรงไปตรงมา:

• เมื่อฝ่ายตรงข้ามเลือกโดยพลการก่อน $m$และคำนวณ $c=\operatorname{แฮช}(m)$, นั่น $ค$ เป็นเหมือนการสุ่ม ยกเว้นว่าจะอยู่ในเซ็ตย่อยที่ต่ำกว่า $[0,h)$ ของ $[0,น)$. เมื่อพวกเขาพยายามค้นหาต่อไป $s$ กับ $c=E_\mathrm{pk}(s)$โดยพื้นฐานแล้วพวกเขาประสบปัญหาในการถอดรหัสไซเฟอร์เท็กซ์โดยพลการ และนั่นเป็นเรื่องยาก (สามารถพิสูจน์ได้ว่าการถอดรหัสไซเฟอร์เท็กซ์โดยพลการต้องเป็นเรื่องยากภายใต้สมมติฐาน KPA ที่เราสร้างเกี่ยวกับการเข้ารหัส)
• เมื่อฝ่ายตรงข้ามเลือกโดยพลการก่อน $s$ และคำนวณ $E_\mathrm{pk}(s)$พวกเขาได้รับค่าโดยพลการ $ค$ ใน $[0,น)$. ไม่มีประกันว่า $ค$ อยู่ในช่วง $[0,h)$ (และหากไม่ใช่ จะไม่สามารถเป็นแฮชของข้อความใดๆ ได้ $m$). แม้ว่าฝ่ายตรงข้ามจะสามารถหลีกเลี่ยงสิ่งกีดขวางนั้นได้โดยการเลือก $s$ ดังนั้น $ค$ อยู่ในช่วง $[0,h)$ (ตำราไหนที่ RSA อนุญาต เช่น โดยการทำ $s=0$ หรือ $s=1$) ฟังก์ชันแฮชในอุดมคติเป็นสิ่งที่คำนวณได้ยาก $m$ ที่แฮชตามค่าที่กำหนดโดยพลการ $ค$ ในช่วงเอาต์พุตของแฮช นั่นคือค่าความต้านทานพรีอิมเมจแรกของแฮช
• เมื่อศัตรูจับได้ $(ม.,ส)$ คู่ที่ผ่านการตรวจสอบพวกเขาสามารถพยายามที่จะหา $m'$ นอกเหนือจากนี้ $m$ กับ $\operatorname{Hash}(m')=\operatorname{Hash}(m)$ซึ่งจะทำให้มั่นใจได้ว่า $(ม',ส)$ ผ่านการตรวจสอบ แต่ฟังก์ชันแฮชในอุดมคตินั้นยากที่จะคำนวณได้ นั่นคือค่าความต้านทานพรีอิมเมจอันดับสองของแฮช
• ฝ่ายตรงข้ามอาจพยายามสร้างสองข้อความที่แตกต่างกัน $m$ และ $m'$ กับ $\operatorname{Hash}(m)=\operatorname{Hash}(m')$, รับลายเซ็น $s$ ของ $m$, และด้วยเหตุนี้จึงได้ปลอมแปลงขึ้นมาอีก $(ม',ส)$ ที่ผ่านการตรวจสอบ ซึ่งง่ายกว่าการโจมตีครั้งก่อนมาก (เช่น เป็นไปได้กับ SHA-1 เป็น $\operatorname{แฮช}$เมื่อไม่มีการโจมตีครั้งก่อนที่เป็นไปได้) แต่ยังคงมีฟังก์ชันแฮชในอุดมคติอยู่เช่นที่การคำนวณจะทำได้ยาก: นั่นคือความต้านทานการชนกันของแฮช

ข้อมูลข้างต้นไม่ถือเป็นหลักฐานยืนยันความปลอดภัยที่ถูกต้อง และแย่กว่านั้น: การสรุปว่าระบบลายเซ็นปลอดภัยถือเป็นความผิดอย่างเห็นได้ชัด โดยเฉพาะกับ $h=2^{256}$ (เช่น แฮชคือ SHA-256) และเมื่อระบบเข้ารหัสเป็น RSA แบบเรียน ระบบลายเซ็นนี้จะเสี่ยงต่อการปลอมแปลงได้ สมมติเป็นระบบที่มีคูปอง $m$ ของแบบฟอร์ม
อย คูปองมูลค่า $123,456.78 อ้างอิง 4C0D5F62CAF6AF32
ถือว่าผู้ลงนามตรวจสอบว่าข้อเสนอ $m$ เป็นคูปองที่มีรูปแบบที่ดี ซึ่งการอ้างอิงนั้นไม่ซ้ำใคร ได้รับการชำระเงินตามราคาที่ระบุ และอยู่ภายใต้เงื่อนไขเหล่านี้ $m$. เดอะ Desmedt และ Odlyzko โจมตี ให้ฝ่ายตรงข้ามเล่นเกมระบบนั้นโดยการซื้อลายเซ็นของคูปองมูลค่าต่ำและใช้ลายเซ็นเหล่านี้เพื่อค้นหาลายเซ็นของคูปองมูลค่าสูง

ข่าวดี: ด้วยสมมติฐานที่เพิ่มเข้ามา เป็นไปได้ พิสูจน์ ว่าระบบลายเซ็นนี้มีความปลอดภัย สมมติฐานที่ใช้ได้กับ RSA ก็คือ $h$ มีบิตเกือบเท่ากับ $n$. ระบบลายเซ็นนี้เรียกว่า แฮชโดเมนแบบเต็ม. การพิสูจน์นั้นยาก ถึงขนาดเมื่อ FDH ได้รับการพิจารณาเป็นครั้งแรกโดย Mihir Bellare และ Peter Rogaway: ความปลอดภัยที่แน่นอนของลายเซ็นดิจิทัล - วิธีลงชื่อเข้าใช้ด้วย RSA และ Rabin, ใน การดำเนินการของ Eurocrypt 1996พวกเขาไม่สามารถพิสูจน์ระดับความปลอดภัยที่น่าพอใจได้ (และได้คิดค้นระบบลายเซ็นที่ซับซ้อนมากขึ้น: RSA-PSS ซึ่งเป็นพื้นฐานของการใช้กันอย่างแพร่หลาย RSASSA-PSS). หลายปีต่อมา Jean-Sébastien Coron ได้รับระดับความปลอดภัยที่ดีขึ้น: บนความปลอดภัยที่แน่นอนของโดเมนแฮชแบบเต็ม, ใน การดำเนินการของ Crypto 2000 (แต่ลายเซ็น RSA ได้เสถียรแล้วและ FDH ไม่ได้ใช้กันอย่างแพร่หลาย)

¹ ความแตกต่างหลักกับการกำหนดคำถาม:

• เราลงนามด้วยการถอดรหัส ไม่ใช่การเข้ารหัส เนื่องจากการเข้ารหัสด้วยคีย์ส่วนตัวและสามารถถอดรหัสด้วยคีย์สาธารณะขัดแย้งกับเป้าหมายของการเข้ารหัส นอกจากนี้ยังใช้ไม่ได้ในทางปฏิบัติ รวมถึงกับ RSA ที่นำมาใช้ แม้ว่าเราจะลบขั้นตอนการเติม: รูปแบบของคีย์สาธารณะคือ $(น,อี)$ มักจะมีการจำกัดขนาดสำหรับ $e$รูปแบบของคีย์ส่วนตัวคือ $(n,e,d,p,q,d_p,d_q,q_\text{inv})$และการพยายามผลักพับลิกคีย์ในที่ที่คาดว่าไพรเวตคีย์จะล้มเหลว
• เราระบุชุดไซเฟอร์เท็กซ์จำกัดที่มีขนาดเดียวกับชุดข้อความธรรมดา ดังนั้นการเข้ารหัสตามกำหนด มิฉะนั้นการสร้างลายเซ็นหรือการตรวจสอบจะล้มเหลวในบางครั้งภายใต้การใช้งานปกติ
• เราทำให้ข้อความเป็นอินพุตของขั้นตอนการตรวจสอบ เนื่องจากนั่นคือวิธีการกำหนดลายเซ็นในทางทฤษฎีและการใช้งานจริงสมัยใหม่

² RSASSA-PKCS1-v1_5 เป็นเพียงคนเดียวที่ฉันรู้ว่าเข้ามาใกล้อย่างไรก็ตามมัน $\operatorname{แฮช}$ ถูกสร้างขึ้นโดยการต่อคำนำหน้าที่ขึ้นอยู่กับขนาดบิตของ $n$ และ $H(ม)$, ที่ไหน $H$ เป็นแฮชมาตรฐานเช่น SHA-256 ดังนั้น $\operatorname{แฮช}$ ไม่ใช่ฟังก์ชันแฮชในอุดมคติ เนื่องจากคาดว่าจะปรากฏในลักษณะสุ่มบนโดเมนเอาต์พุต