เหตุการณ์แบ็กดอร์ใน Dual EC DRBG

ตัวสร้างบิตสุ่มเชิงกำหนดแบบเส้นโค้งวงรีคู่ (Dual EC DRBG) เป็นหนึ่งใน DRBG สี่แบบที่ NIST กำหนดมาตรฐานไว้ใน SP 800-90A (2006) โดยสร้างบิตเทียมสุ่มจากจุดบนเส้นโค้งวงรีสองจุดคือ P และ Q ในแต่ละขั้นตอนจะคำนวณ r_i = x(s_i * P) (พิกัด x ของการคูณจุด) จากนั้น s_{i+1} = x(r_i * P) จะอัปเดตสถานะ และ output = x(r_i * Q) จะสร้างบิต ตัวสร้างนี้ดูน่าเชื่อถือเมื่อเขียนในรูปแบบสัญกรณ์ทางวิชาการ ตัวสร้างนี้ถูกรวมไว้ใน NIST SP 800-90A และต่อมาได้รับการรับรองโดย RSA Security ให้เป็นค่าเริ่มต้นในไลบรารีการเข้ารหัส BSAFE ของบริษัท จึงแพร่เข้าสู่ซอฟต์แวร์ระดับองค์กรและรัฐบาล

ช่องลับใน Dual EC DRBG อาศัยความสัมพันธ์ระหว่าง P และ Q หากผู้โจมตีรู้สเกลาร์ลับ e ที่ทำให้ Q = e * P ได้ เมื่อมีบล็อกผลลัพธ์ใด ๆ ผู้โจมตีจะสามารถคำนวณได้ดังนี้: จาก output = x(r * Q) ให้ใช้การไล่ลองทุกค่าหาพิกัด y ของ r*Q จากนั้นคำนวณ r*P = (1/e) * (r*Q) mod n เมื่อได้ r*P แล้ว ก็สามารถคาดเดาผลลัพธ์ทั้งหมดในอนาคตและกู้คืนสถานะภายในได้ การรู้ค่า e คือช่องลับ ซึ่งเทียบเท่ากับลอการิทึมไม่ต่อเนื่องของ Q เมื่อเทียบกับ P มาตรฐานของ NIST ระบุค่า P และ Q โดยไม่อธิบายว่าเลือกค่าเหล่านี้อย่างไร จึงไม่สามารถตรวจสอบได้ว่าเกิดจากการสุ่มโดยไม่มีข้อมูลลับสำหรับเปิดช่องหรือไม่

ในเดือนสิงหาคม 2007 แดน ชูโมว์และนีลส์ เฟอร์กูสันได้นำเสนอเอกสารสำคัญที่ช่วง Rump Session ของ CRYPTO ในชื่อ “ว่าด้วยความเป็นไปได้ของช่องทางลับใน NIST SP800-90 Dual EC PRNG” ทั้งสองแสดงให้เห็นอย่างเป็นทางการว่า หากมีผู้ใดทราบค่า e (ค่า ECDLP ของ Q เมื่อเทียบกับ P) ผู้นั้นจะสามารถทำนายเอาต์พุตทั้งหมดของ Dual EC DRBG ได้จากเอาต์พุตประมาณ 32 ไบต์ ทั้งสองสาธิตเรื่องนี้ด้วยตัวอย่างจำลอง การนำเสนอดังกล่าวได้รับความสนใจอย่างกว้างขวางในแวดวงการเข้ารหัส บรูซ ชไนเออร์เขียนไว้ว่า “เราไม่มีทางรู้ได้เลยว่า NSA สามารถอ่านเอาต์พุตของ Dual_EC_DRBG ได้หรือไม่” แม้จะมีคำเตือนนี้ แต่ Dual EC DRBG ยังคงอยู่ในมาตรฐานต่อไปอีกหกปี

ในเดือนกันยายน 2013 The New York Times, The Guardian และ ProPublica ได้เผยแพร่รายงานที่อ้างอิงเอกสารซึ่งเอ็ดเวิร์ด สโนว์เดนเปิดเผย โดยระบุว่า NSA ได้แอบนำช่องโหว่เข้าสู่มาตรฐานการเข้ารหัส เอกสารฉบับหนึ่งชื่อ “โครงการเอื้ออำนวยการข่าวกรองสัญญาณ” อธิบายโครงการมูลค่า 250 ล้านดอลลาร์ต่อปีเพื่อ “มีอิทธิพลต่อ” มาตรฐานและผลิตภัณฑ์การเข้ารหัสอย่างลับ ๆ แม้เอกสารดังกล่าวจะไม่ได้ระบุชื่อ Dual EC DRBG โดยตรง แต่เมื่อประกอบกับการสาธิตทางคณิตศาสตร์ของชูโมว์และเฟอร์กูสัน แวดวงการเข้ารหัสก็สรุปกันอย่างกว้างขวางว่า NSA ได้ใส่ช่องทางลับไว้โดยเลือก P และ Q ที่มีความสัมพันธ์ e ซึ่งทราบอยู่แล้ว แล้วเก็บ e เป็นความลับขณะส่งค่าคงที่ดังกล่าวให้ NIST

รอยเตอร์สรายงานในเดือนธันวาคม 2013 ว่า NSA ได้จ่ายเงินให้ RSA 10 ล้านดอลลาร์ เพื่อทำให้ Dual EC DRBG เป็นค่าเริ่มต้นในชุดเครื่องมือการเข้ารหัส BSAFE ของ RSA Security ซึ่งในขณะนั้นเป็นแผนกหนึ่งของ EMC และได้จัดจำหน่าย BSAFE ในซอฟต์แวร์สำหรับองค์กรที่สถาบันการเงิน บริษัทด้านการดูแลสุขภาพ และผู้รับเหมาของรัฐบาลใช้งาน แถลงการณ์ของ RSA ปฏิเสธว่าไม่ได้ติดตั้งช่องทางลับโดยรู้เห็น แต่ยอมรับว่าได้รับสัญญาดังกล่าว การเปิดเผยนี้สร้างความเสียหายอย่างมากเป็นพิเศษ: BSAFE ถูกทำตลาดในฐานะผลิตภัณฑ์ด้านความปลอดภัย และลูกค้าเลือกใช้ผลิตภัณฑ์นี้โดยเฉพาะเพราะต้องการความมั่นใจด้านการเข้ารหัส เหตุการณ์นี้ทำลายชื่อเสียงของ RSA Security อย่างรุนแรง และนำไปสู่การคว่ำบาตรการประชุม RSA ในปี 2014

หลังการเปิดเผยข้อมูลของสโนว์เดน NIST ได้ดำเนินการหลายประการ ในเดือนกันยายน 2013 NIST เปิดให้แสดงความคิดเห็นต่อ SP 800-90A อีกครั้ง และแนะนำให้หลีกเลี่ยงการใช้ Dual EC DRBG ระหว่างที่การทบทวนยังดำเนินอยู่ ในเดือนเมษายน 2014 NIST เผยแพร่ SP 800-90A ฉบับแก้ไขครั้งที่ 1 ซึ่งถอด Dual EC DRBG ออกทั้งหมด เหลือเพียง Hash_DRBG, HMAC_DRBG และ CTR_DRBG เท่านั้น NIST ยังเริ่มทบทวนมาตรฐานและแนวทางการเข้ารหัสทั้งหมดของตน โดยตรวจสอบเป็นพิเศษว่าอิทธิพลของ NSA ทำให้มาตรฐานอื่นถูกลดทอนความปลอดภัยหรือไม่ นอกจากนี้ยังจัดตั้งคณะทำงานกระบวนการมาตรฐานและแนวทางการเข้ารหัสของ NIST เพื่อเพิ่มความโปร่งใสและการมีส่วนร่วมของสาธารณชนในการจัดทำมาตรฐานในอนาคต

ช่องทางลับของ Dual EC DRBG ส่งผลกระทบอย่างลึกซึ้งต่อความไว้วางใจของแวดวงการเข้ารหัสที่มีต่อหน่วยงานกำหนดมาตรฐาน เหตุการณ์นี้แสดงให้เห็นว่าหน่วยงานข่าวกรองระดับชาติยอมลดทอนความปลอดภัยของมาตรฐานการเข้ารหัสที่ใช้งานทั่วโลกโดยเจตนา ซึ่งส่งผลไม่ใช่แค่ต่อฝ่ายตรงข้าม แต่ยังรวมถึงพันธมิตร ธุรกิจ และประชาชนทั่วไป เหตุการณ์นี้เร่งให้มีการนำขั้นตอนวิธีแบบเปิดที่ตรวจสอบได้และใช้ตัวเลขที่ไม่มีอะไรซ่อนอยู่มาใช้มากขึ้น: Keccak ของ SHA-3 ใช้ขั้นตอนวิธีที่มีการบันทึกที่มาไว้สำหรับค่าคงที่ ส่วน BLAKE2 และ BLAKE3 สร้างค่าคงที่จากส่วนเศษของค่าคงที่ทางคณิตศาสตร์ และ Curve25519 ใช้จำนวนเฉพาะ (2^255 - 19) ที่เลือกมาโดยเฉพาะให้ตรวจสอบได้ การสร้างพารามิเตอร์เส้นโค้งวงรีแบบ “สุ่มที่ตรวจสอบยืนยันได้” กลายเป็นแนวปฏิบัติมาตรฐาน

คดีอื้อฉาวของ Dual EC DRBG ทำให้แนวคิดเรื่องค่าคงที่แบบ “nothing-up-my-sleeve” (NUMS) ได้รับความนิยม ซึ่งหมายถึงพารามิเตอร์การเข้ารหัสที่สร้างจากแหล่งข้อมูลซึ่งสาธารณชนตรวจสอบได้ และไม่สามารถมีช่องทางลับแฝงอยู่ได้ ตัวอย่างเช่น SHA-2 ใช้ค่าแฮชเริ่มต้นที่ได้จากรากที่สองของจำนวนเฉพาะแปดตัวแรก และใช้ค่าคงที่ของรอบที่ได้จากรากที่สามของจำนวนเฉพาะ 64 ตัวแรก BLAKE2 สร้างค่าคงที่จากส่วนเศษของ pi และค่าคงที่ทางคณิตศาสตร์อื่น ๆ Ed25519 ใช้จำนวนเฉพาะ 2^255 - 19 และจุดฐานที่ลอการิทึมไม่ต่อเนื่องเมื่อเทียบกับจุดอื่นใดก็ตามพิสูจน์ได้ว่าไม่ทราบค่า (จุดนี้ถูกเลือกให้เป็นแฮชของสตริง) แนวปฏิบัติเหล่านี้ทำให้ทุกคนตรวจสอบได้ว่าค่าคงที่ไม่ได้ถูกเลือกโดยอาศัยความรู้ลับ

ในเดือนธันวาคม 2015 Juniper Networks เปิดเผยว่ามีโค้ดที่ไม่ได้รับอนุญาตอยู่ใน ScreenOS ซึ่งเป็น OS ของไฟร์วอลล์ของบริษัทมาตั้งแต่ปี 2012 การตรวจสอบพบช่องทางลับสองแห่ง: แห่งแรกแทนที่ค่าคงที่ Q ของ Dual EC DRBG ด้วยค่าที่ผู้โจมตีควบคุม ทำให้ผู้โจมตีที่ทราบค่า e ที่สอดคล้องกันสามารถถอดรหัสข้อมูล VPN ได้ ส่วนช่องทางลับแห่งที่สองอยู่ในรหัสผ่านผู้ดูแลระบบ SSH การแทนที่ Q ของ Dual EC มีความซับซ้อนเป็นพิเศษ: Juniper ใช้ค่า Q ที่ไม่เป็นมาตรฐานอยู่ก่อนแล้ว และผู้โจมตีก็แทนที่ค่านั้นด้วยค่าของตนเอง โดยใช้ประโยชน์จากโครงสร้างช่องทางลับของ Dual EC ถึงสองครั้ง เหตุการณ์นี้แสดงให้เห็นว่าแม้แต่การติดตั้งใช้งานที่เบี่ยงเบนจากค่า P/Q ของ NIST ก็อาจถูกโจมตีได้โดยผู้ใดก็ตามที่นำ Q ของตนเองเข้าไปวางไว้

เหตุการณ์ Dual EC DRBG ให้บทเรียนหลายประการ (1) ความโปร่งใส: พารามิเตอร์การเข้ารหัสต้องมีที่มาที่ตรวจสอบได้ ค่าคงที่ที่ไม่มีเอกสารอธิบายที่มาควรถือว่าน่าสงสัย (2) การออกแบบขั้นตอนวิธี: ขั้นตอนวิธีไม่ควรมีโครงสร้างที่อาจซ่อนช่องทางลับได้ ความสัมพันธ์ Q/P ของ Dual EC ไม่มีประโยชน์ด้านความปลอดภัยเหนือการออกแบบ DRBG ที่เรียบง่ายกว่า (3) ผลประโยชน์ทับซ้อน: หน่วยงานจัดทำมาตรฐานต้องจัดการผลประโยชน์ทับซ้อนกับหน่วยงานข่าวกรองอย่างเข้มงวด (4) การทบทวนโดยชุมชน: ควรให้อำนาจนักเข้ารหัสเชิงวิชาการยกข้อกังวลขึ้นมาก่อนเผยแพร่มาตรฐาน ไม่ใช่หลังจากนั้น (5) ความระมัดระวังในการนำไปใช้งาน: องค์กรควรตรวจสอบว่าคลังการเข้ารหัสของตนใช้ DRBG ใด และถอดตัวเลือกที่ไม่แนะนำออกล่วงหน้า

หลังจากถอด Dual EC ออก ภูมิทัศน์ของ DRBG ที่แนะนำก็รวมศูนย์อยู่ที่ Hash_DRBG, HMAC_DRBG และ CTR_DRBG ชุมชนโอเพนซอร์สยังนำ DRBG ที่ไม่ใช่ของ NIST มาใช้ในบริบทที่ไม่ไว้วางใจมาตรฐานของ NIST ด้วย: RNG ที่ใช้ ChaCha20 เป็นพื้นฐาน ซึ่งใช้ในเคอร์เนลลินุกซ์ตั้งแต่รุ่น 5.17, OpenBSD และ libsodium ได้รับการมองอย่างกว้างขวางว่าต้านทานช่องทางลับได้ เพราะ ChaCha20 เป็นรหัสลับแบบสตรีมที่เรียบง่ายและไม่มีโครงสร้างช่องทางลับ Fortuna ซึ่งใช้ใน FreeBSD และ macOS รุ่นเก่า มีมาก่อน SP 800-90A และยังคงได้รับความไว้วางใจ เหตุการณ์ Dual EC ยังทำให้เกิดความสนใจใน RNG ฮาร์ดแวร์ (RDRAND) ในฐานะแหล่งเอนโทรปีอีกครั้ง แม้ RDRAND เองก็เคยถูกกล่าวหาว่าอาจมีช่องทางลับ จนนำไปสู่คำแนะนำให้ผสม RDRAND กับเอนโทรปีจากซอฟต์แวร์ แทนที่จะใช้ RDRAND เพียงอย่างเดียว

ความสัมพันธ์ทางคณิตศาสตร์ใดที่ทำให้เกิดช่องทางลับของ Dual EC DRBG

Dual EC DRBG ได้รับการกำหนดเป็นมาตรฐานใน NIST SP 800-90A เมื่อปี 2006 ชูโมว์และเฟอร์กูสันแสดงให้เห็นในปี 2007 ว่าการทราบค่า e (โดยที่ Q=e*P) ทำให้สามารถทำนายเอาต์พุตทั้งหมดจากข้อมูล 32 ไบต์ได้ การรั่วไหลของข้อมูลโดยสโนว์เดนในปี 2013 ยืนยันอิทธิพลของ NSA ที่มีต่อมาตรฐานการเข้ารหัส มีรายงานว่า RSA Security ได้รับเงิน 10 ล้านดอลลาร์เพื่อทำให้ Dual EC เป็นค่าเริ่มต้นใน BSAFE NIST ถอด Dual EC ออกใน SP 800-90A ฉบับแก้ไขครั้งที่ 1 (2014) เหตุการณ์ Juniper ในปี 2015 แสดงให้เห็นว่าช่องทางลับถูกนำไปใช้ประโยชน์ในผลิตภัณฑ์จริง บทเรียนสำคัญ ได้แก่ ค่าคงที่ NUMS การอธิบายที่มาอย่างโปร่งใส การจัดการผลประโยชน์ทับซ้อน และกระบวนการตรวจสอบหลังการจัดทำมาตรฐาน RNG ที่ใช้ ChaCha20 เป็นพื้นฐานกลายเป็นทางเลือกที่ได้รับความไว้วางใจ