คีย์ ECDSA สองคีย์ที่อยู่ห่างกันอย่างใกล้ชิด

สมมติว่าใช้สองคีย์ส่วนตัว $x_1$ และ $x_2$ เพื่อสร้างคีย์ ECDSA สาธารณะสองรายการ $y_1$ และ $y_2$ (เช่น ใช้เป็นรหัสสาธารณะสำหรับที่อยู่ Bitcoin) ระยะห่างระหว่าง $x_1$ และ $x_2$ มีขนาดเล็ก (เช่น น้อยกว่า ${2^{20}}$). อะไรนะ แย่ เกี่ยวกับมัน?

ฉันรู้ว่าถ้าแตก $x_1$ย่อมนำไปสู่การแตกดับ $x_2$ ด้วยความพยายามเพียงเล็กน้อยในการค้นหา แต่สมมติว่ายกเว้น $|x_1 - x_2|$ แนวทางปฏิบัติอื่น ๆ ทั้งหมดมีความปลอดภัยเพียงเล็กน้อยเช่น อย่าใช้ nonces ของ randon ซ้ำในการเซ็นชื่อ มีผลเสียอื่นๆ อีกไหม (ยกเว้นการหักหนึ่งเหรียญก็เหมือนหักสอง)

อนุญาต $d=x_2-x_1$และให้คีย์สาธารณะอยู่บนจุดฐานที่รู้จักกันดี $G$. ดังนั้นคีย์คู่จะเป็น $(x_1, X_1=x_1G)$ และ $(x_2, X_2=x_2G)$.

มูลค่า $d$ สามารถบังคับเดรัจฉานโดยใช้ ก้าวใหญ่-ก้าวเล็ก วิธีซึ่งจะใช้เวลาน้อยกว่าหนึ่งวินาทีใน CPU สมัยใหม่เมื่อ $n=20$.

หากคุณใช้ลายเซ็น Schnorr เพื่อเซ็นข้อความ $m$ โดยใช้ $X_1$คุณจะสร้างคู่ลายเซ็น $(ค, r_1)$ โดยเลือก nonce แบบสุ่มอย่างสม่ำเสมอ $k$แล้วคำนวณ $c=H(kG\mathbin\| m)$ และ $r_1=k-cx_1$.

ลายเซ็นได้รับการตรวจสอบโดยการตรวจสอบ $c\overset{?}{=}H(r_1G+cX_1 \mathbin\| ม.)$.

ผู้โจมตีซึ่งมีกำลังดุร้าย $d$จากนั้นสามารถสร้างลายเซ็นในข้อความเดียวกัน แต่ดูเหมือนว่าจะถูกเซ็นโดยคีย์ส่วนตัวอื่นของคุณ $x_2$ดังต่อไปนี้:

ค่าของ $k$ และ $ค$ จะยังคงเหมือนเดิม จากนั้นคำนวณ $r_2=r_1-cd$. ลายเซ็นปลอมเป็นของคู่กัน $(ค, r_2)$.

ลายเซ็นจะถูกตรวจสอบโดยการตรวจสอบที่ $c\overset{?}{=}H(r_2G+cX_2 \mathbin\| ม.)$.

สิ่งนี้จะตรวจสอบได้สำเร็จว่า $kG==r_2G+cX_2$ซึ่งจะเป็นจริงถ้า $k==r_2+cx_2$.

โดยแทนที่ $r_2==r_1-cd$ และ $x_2==d+x_1$เราจะเห็นว่าสิ่งนี้จะเป็นจริงด้วยการเลือกของเรา $r_2$.

การโจมตีนี้จะใช้ได้เฉพาะเมื่อแฮชหรือข้อความไม่ผูกลายเซ็นกับคีย์สาธารณะเฉพาะ หากโปรโตคอลกำหนดว่า $ค$ แทนที่จะคำนวณเป็น $c=H(kG\mathbin\| X_1\mathbin\| m)$การโจมตีจะไม่ทำงานเนื่องจากค่าของ $ค$ ไม่สามารถใช้ซ้ำระหว่างลายเซ็นได้ (เนื่องจากตัวตรวจสอบจะตรวจสอบลายเซ็นโดยการเชื่อมข้อมูล $X_2$ ภายในแฮชแทน $X_1$).