ผู้เขียน: Sylvain Pelissier เรียบเรียง: Cointime.com 237

บล็อกเชนสาธารณะมีประวัติการโจมตีลายเซ็น ECDSA มาอย่างยาวนาน เนื่องจากธุรกรรมทั้งหมดเปิดเผยต่อสาธารณะ จึงเป็นพื้นที่ทดสอบที่สมบูรณ์แบบสำหรับการโจมตีด้วยการเข้ารหัส การโจมตีแบบตาข่ายที่เรียกว่า "กรณีที่น่าสงสัยของตัวเลขสุ่ม ECDSA ครึ่ง Bitcoin" ได้รับการเผยแพร่และทดลองกับ Bitcoin เมื่อเร็วๆ นี้ ในฐานะทีมสวิสที่ชื่นชอบฟองดูแบบแบ่งครึ่งแล้วแบ่งครึ่ง เราต้องตรวจสอบการโจมตีครั้งนี้ เราพบว่าการโจมตี "เลขสุ่มโพลิโนเมียล" ครั้งก่อนของเรายังทำงานร่วมกับวิธีสร้างเลขสุ่ม ECDSA แบบนี้ได้ด้วย ในเอกสารนี้ เราจะอธิบายวิธีการทำและแสดงวิธีที่เราเปรียบเทียบกับผลลัพธ์ที่ได้รับในกระดาษ

การโจมตีครั้งก่อน

ในการเซ็นชื่อข้อความ ECDSA จะใช้ค่าที่เรียกว่า nonce nonce จะต้องสร้างแบบสุ่มและต้องไม่ซ้ำกันสำหรับแต่ละข้อความที่จะลงนาม สำหรับเส้นโค้ง secp256k1 ของ Bitcoin และ Ethereum ค่า nonce ทั่วไปจะเป็นดังนี้:

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

อย่างไรก็ตาม ECDSA nonces มีความสำคัญอย่างยิ่งที่แม้แต่ความลำเอียงในการสร้างก็สามารถนำไปสู่การกู้คืนคีย์ส่วนตัวได้ ดังนั้น การโจมตีแบบตาข่ายที่แยบยลมากขึ้นจึงถูกนำมาใช้กับบล็อกเชนสาธารณะในภายหลัง การโจมตีเหล่านี้สามารถกู้คืนความยาวที่สั้นกว่าที่คาดไว้ได้ไม่น้อย โดยมีความยาว 64, 110, 128 และ 160 บิต ตัวอย่างเช่น ตัวเลขสุ่มที่สร้างขึ้นดังต่อไปนี้มีความเสี่ยงต่อการโจมตีแบบตาข่าย:

ยิ่ง nonce มีขนาดเล็กเท่าใด มิติของตาข่ายที่ใช้สำหรับการโจมตีก็จะยิ่งเล็กลง และจำนวนลายเซ็นที่จำเป็นสำหรับการโจมตีก็จะยิ่งน้อยลงเท่านั้น ตามเอกสาร Biased Random Numbers ตัวเลขสุ่ม 128 บิตสองตัวและโครงตาข่าย 3 มิติให้ความน่าจะเป็น 75% ที่จะสำเร็จ (การกู้คืนคีย์ส่วนตัว) เมื่อใช้ตัวเลขสุ่ม 170 บิตสามตัวและตาข่าย 4 มิติ เรามีโอกาสสำเร็จ 95% เป็นต้น ตัวแปรของการโจมตียังใช้เพื่อค้นหา nonce ที่มีคำนำหน้าและคำต่อท้ายที่ใช้ร่วมกัน ตัวอย่างเช่น ตัวเลขสุ่มที่สร้างขึ้นดังต่อไปนี้มีความเสี่ยงพอๆ กันต่อการโจมตีดังกล่าวและการสร้างส่วนต่อท้ายทั่วไป:

โพลินอนเซ่

อีกวิธีในการโจมตี ECDSA คือการใช้ความสัมพันธ์เชิงพีชคณิตระหว่างตัวเลขสุ่ม ทีมงานของเราเสนอการโจมตีแบบ Polynonce ซึ่งถือว่ามีความสัมพันธ์พหุนามระหว่างค่าสัมประสิทธิ์ที่ไม่รู้จัก a_i ในรูปแบบต่อไปนี้:

k_{n+1} = a_1 k_n + a_0

หรือ

k_{n+1} = a_2 k_n^2 + a_1 k_n + a_0

จากนั้น การโจมตีแบบ Polynonce จะสามารถกู้คืนคีย์ส่วนตัวในทางพีชคณิตโดยมีโอกาสสำเร็จ 100% แต่ต้องใช้ 4 ลายเซ็นในกรณีเชิงเส้น 5 ลายเซ็นในกรณีกำลังสอง และอื่นๆ การโจมตีต้องอาศัยการแก้สมการพหุนามเป็นหลัก ดังนั้นมันจึงรวดเร็วมากเมื่อเทียบกับการโจมตีแบบตาข่าย สำหรับรายละเอียดเพิ่มเติม การโจมตีจะถูกนำเสนอในการประชุม DEFCON ที่กำลังจะมีขึ้น

ลายเซ็นเดียว

การโจมตีก่อนหน้านี้ทั้งหมดต้องการลายเซ็นอย่างน้อยสองลายเซ็นจากคีย์ส่วนตัวเดียวกัน อย่างไรก็ตาม กระเป๋าเงินเช่นบัญชีแยกประเภทเซ็นธุรกรรมด้วยรหัสส่วนตัวเดียวแล้วเปลี่ยนรหัสส่วนตัว สิ่งนี้จะอธิบายได้ว่าทำไมที่อยู่สาธารณะของ Bitcoin จำนวนมากจึงใช้เพียงครั้งเดียว ด้านล่างนี้คือกราฟของข้อมูลการโอน Bitcoin (ณ วันที่ 5 กันยายน 2022 บล็อก 752759) พล็อตในระดับลอการิทึมที่จำกัดเฉพาะธุรกรรม P2PKH:

นี่แสดงให้เห็นว่า 92% ของคีย์สาธารณะที่ใช้สำหรับธุรกรรม P2PKH นั้นใช้เพียงครั้งเดียว ฟีเจอร์นี้มีไว้เพื่อความเป็นส่วนตัวเป็นหลัก แต่ยังป้องกันการโจมตีก่อนหน้านี้ในทางอ้อมอีกด้วย สำหรับ Ethereum สถานการณ์จะแตกต่างออกไปเล็กน้อย เราวิเคราะห์ลายเซ็น 1759432087 จากคีย์เฉพาะ 151429561 และสร้างพล็อตสเกลเชิงเส้น:

นี่แสดงให้เห็นว่า 92% ของคีย์สาธารณะที่ใช้สำหรับธุรกรรม P2PKH นั้นใช้เพียงครั้งเดียว ฟีเจอร์นี้มีไว้เพื่อความเป็นส่วนตัวเป็นหลัก แต่ยังป้องกันการโจมตีก่อนหน้านี้ในทางอ้อมอีกด้วย สำหรับ Ethereum สถานการณ์จะแตกต่างออกไปเล็กน้อย เราวิเคราะห์ลายเซ็น 1759432087 จากคีย์เฉพาะ 151429561 และสร้างพล็อตสเกลเชิงเส้น:

นี่เป็นสถานการณ์ที่ค่อนข้างแตกต่าง: 42% ของคีย์สาธารณะใช้สำหรับลายเซ็นเดียว 22% สำหรับสองลายเซ็น 13% สำหรับสามลายเซ็น และอื่นๆ ดังนั้นจึงดูเหมือนว่าวิธีการรักษาความเป็นส่วนตัวมีแอปพลิเคชันน้อยหรือไม่มีเลยบน Ethereum

เลขสุ่มครึ่งตัว

วิธีการโจมตีแบบใหม่ได้เกิดขึ้นเมื่อเร็วๆ นี้ซึ่งสร้างปัญหาเมื่อ nonce เชื่อมกับครึ่งบนของคีย์ส่วนตัวโดยใช้แฮชข้อความครึ่งบน กล่าวอีกนัยหนึ่ง หมายเลขสุ่ม k สามารถแสดงเป็น:

k = h_{msb} || d_{msb}

ความแปลกใหม่ของการโจมตีนี้คือสามารถกู้คืนคีย์ส่วนตัว d จากลายเซ็นเดียวได้ คล้ายกับการโจมตีแบบตาข่ายก่อนหน้านี้ นิพจน์สำหรับหมายเลขสุ่ม k จะถูกแทรกลงในสูตร ECDSA และจัดเรียงใหม่เพื่อสร้างตัวอย่างของปัญหาจำนวนที่ซ่อนอยู่ จากนั้นอินสแตนซ์จะได้รับการแก้ไขโดยใช้อัลกอริทึม BKZ เทคนิคนี้มีประสิทธิภาพมากเนื่องจากต้องใช้เพียงลายเซ็นเดียวในการโจมตีธุรกรรมที่ออกด้วยรหัสส่วนตัวที่ใช้เพียงครั้งเดียว การโจมตีเวอร์ชันที่ได้รับการปรับปรุงสามารถกู้คืนคีย์ส่วนตัวได้ภายใน 0.48 วินาทีด้วยอัตราความสำเร็จ 99.99% มันค่อนข้างทรงพลัง แต่ผู้เขียนใช้เวลา 49 ปี CPU ในการโจมตี Bitcoin blockchain

การใช้ Polynonce กับตัวเลขสุ่มครึ่งตัว

ในขณะที่อ่านเกี่ยวกับการโจมตีแบบ half-half เราค้นพบว่า Polynonce สามารถใช้เพื่อกู้คืนคีย์ส่วนตัวโดยใช้ตัวเลขสุ่มแบบ half-half สำหรับลายเซ็น ECDSA (r, s), ข้อความแฮช h และคีย์ส่วนตัว d เรามีความสัมพันธ์ที่เกี่ยวข้องกับ nonces ดังต่อไปนี้:

k = s^{-1}(h + rd) mod q

หากเรามีตัวเลขสุ่ม k_0 และ k_1 สองตัวที่สร้างขึ้นโดยใช้สูตรครึ่งต่อครึ่งก่อนหน้านี้ ความแตกต่างคือ:

k_0 - k_1 = s_0^{-1}h_0 - s_1^{-1}h_1 + (s_0^{-1}h_0 - s_1^{-1}h_1)d = h_{0,msb} - h_{1, msb}

เราพบสมการเชิงเส้นสำหรับ d ซึ่งทราบค่าอื่นทั้งหมด นี่เป็นวิธีที่รวดเร็วมากในการแก้สมการและกู้คืนคีย์ส่วนตัว d อย่างไรก็ตาม การใช้ Polynonce ต้องใช้สอง nonce และสองลายเซ็นจากคีย์ส่วนตัวเดียวกัน เราได้สูญเสียความได้เปรียบอย่างมากจากการโจมตีครั้งก่อน อย่างไรก็ตาม เนื่องจากรูปแบบการโจมตีนี้มีความรวดเร็วมาก จึงเป็นไปได้ที่จะใช้รูปแบบนี้กับคีย์สาธารณะที่มีลายเซ็นหลายลายเซ็นก่อน แล้วจึงใช้การโจมตีแบบแลตทิซกับลายเซ็นที่เหลือ

เนื่องจากผลต่างของตัวเลขสุ่มในสมการของเราขึ้นอยู่กับ h_{0,msb} - h_{1,msb} เท่านั้น จึงทำให้เราสามารถย้อนกลับไปใช้สูตร k_i = h_{i,msb} || c (โดยที่ c คือ a ( ลับ ) ค่าคงที่) สร้างตัวเลขสุ่มทั้งหมด นี่เป็นเรื่องทั่วไป แต่ซับซ้อนกว่าเล็กน้อยสำหรับ Bitcoin เริ่มจากลายเซ็น ECDSA (r, s) ลายเซ็นที่แตกต่างกัน (r, -s) ของข้อความเดียวกันก็ใช้ได้เช่นเดียวกัน เนื่องจาก Bitcoin ปฏิเสธลายเซ็นที่มีค่ามากที่สุดของ s เพื่อหลีกเลี่ยงการปลอมแปลงลายเซ็น หมายความว่าเราต้องคำนวณทั้ง -k และ k ดังนั้นในการโจมตีของเรา เราจะต้องเดาสัญญาณของโนนเซ่แต่ละตัว

โครงสร้างนี้ควรได้รับการค้นพบโดยการวิจัยก่อนหน้านี้เกี่ยวกับการโจมตีแบบแลตทิซในส่วนต่อท้ายที่ใช้ร่วมกัน แต่อัตราความสำเร็จมีเพียง 75% เท่านั้น

ผลลัพธ์

เราทำการวิเคราะห์ไฟล์ดัมพ์ Bitcoin blockchain ที่ใช้ในการวิเคราะห์ครั้งก่อน (บล็อก 752,759 ณ วันที่ 5 กันยายน 2022) เราวิเคราะห์คีย์สาธารณะ 34 ล้านคีย์ที่มีลายเซ็นอย่างน้อย 2 รายการ บนโปรเซสเซอร์ AMD 16 คอร์ที่โอเวอร์คล็อกที่ 2.7 GHz ใช้เวลา 10 นาที 23 วินาที

เราค้นหาและกู้คืนคีย์ส่วนตัวที่ไม่ซ้ำกัน 110 รายการได้สำเร็จ ตัวอย่างเช่นที่อยู่

18zg6FG5pu8Bpq73L54AYvB8phTw3qCCR7

ธุรกรรม

เราค้นหาและกู้คืนคีย์ส่วนตัวที่ไม่ซ้ำกัน 110 รายการได้สำเร็จ ตัวอย่างเช่นที่อยู่

18zg6FG5pu8Bpq73L54AYvB8phTw3qCCR7

ธุรกรรม

f3151fc1b29c117f1e4b67045b2d2901e7c289f596c242d7de123243fb623981

และ

f7bf1edf9d9cefa8421322c53bb00ecf118f99489171da72a9c11cf8d02b65f8

สร้างตัวเลขสุ่มโดยใช้วิธีครึ่งและครึ่ง สคริปต์ของเราสามารถกู้คืนรหัสส่วนตัวสำหรับที่อยู่นี้:

หากเราคำนวณ nonce ใหม่สำหรับธุรกรรมดังกล่าว เราจะได้รับ:

เราเห็นได้อย่างชัดเจนว่าครึ่งที่มีนัยสำคัญน้อยที่สุดของ nonce เท่ากับครึ่งหนึ่งที่มีนัยสำคัญที่สุดของคีย์ส่วนตัว อย่างไรก็ตาม ดังที่กล่าวไว้ข้างต้น เราสามารถกู้คืนกรณีที่น่าสนใจอื่นๆ ได้ สำหรับที่อยู่เดียวกัน เราพบ nonce สองคน:

ในกรณีนี้ คีย์ส่วนตัวไม่เกี่ยวข้องเนื่องจากเราพบค่าคงที่อื่นที่ไม่รู้จัก เรายังสามารถยืนยันการค้นพบก่อนหน้านี้ว่าคีย์บางคีย์ที่ใช้ตัวเลขสุ่มดังกล่าวเป็นคีย์ขนาดเล็ก: d = {1, 2, 4, 7, 11, 24, 75, 77, 87, 128, 144, 549, 897 } ดังนั้น คีย์เหล่านี้สามารถกู้คืนได้ง่ายด้วยวิธีการดุร้าย คล้ายกับงานที่ทำบนเว็บไซต์ https://privatekeys.pw เราไม่พบบัญชีที่มียอดคงเหลือไม่เป็นศูนย์ ซึ่งเราเชื่อว่ามีการตรวจสอบโดยบอทและว่างเปล่าเมื่อยอดคงเหลือเปลี่ยนแปลง

เนื่องจากการโจมตีนี้รวดเร็วมาก เราจึงทำการโจมตีแบบเดียวกันนี้กับการสร้างตัวเลขกึ่งสุ่มรูปแบบอื่น: k = h_{lsb} || d_{msb}, k = d_{msb} || h_{msb} และ k = d_{msb} || h_{lsb} แต่เราไม่พบผลลัพธ์เพิ่มเติม

เรายังดำเนินการโจมตีชุดข้อมูล Ethereum ที่รวบรวมระหว่างการโจมตีครั้งก่อนอีกด้วย การโจมตีใช้เวลา 49 นาที 11 วินาทีในเครื่องเดียวกัน การโจมตีนี้ไม่ได้กู้คืนคีย์ส่วนตัวใดๆ

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