NIST SP 800-90A
NIST SP 800-90A ("SP" ย่อมาจาก " special publication ") เป็นเอกสารเผยแพร่ของสถาบันมาตรฐานและเทคโนโลยีแห่งชาติ (National Institute of Standards and Technology)ในชื่อ " ข้อแนะนำสำหรับการสร้างเลขสุ่มโดยใช้ตัวสร้างบิตสุ่มแบบกำหนดได้ " เอกสารนี้ประกอบด้วยข้อกำหนดสำหรับตัวสร้างเลขสุ่มเทียมสามตัวที่อ้างว่ามีความปลอดภัยทางด้านการเข้ารหัสสำหรับการใช้งานในด้านการเข้ารหัสได้แก่Hash DRBG (อิงตามฟังก์ชันแฮช ), HMAC DRBG (อิงตามHMAC ) และCTR DRBG (อิงตามการเข้ารหัสแบบบล็อกในโหมดตัวนับ ) เวอร์ชันก่อนหน้านี้มีตัวสร้างตัวที่สี่คือDual_EC_DRBG (อิงตามการเข้ารหัสแบบวงรี ) ต่อมามีรายงานว่า Dual_EC_DRBG อาจมีช่องโหว่ด้านการขโมยข้อมูล ที่แทรกโดย สำนักงานความมั่นคงแห่งชาติของสหรัฐอเมริกา(NSA)
เนื่องจากเป็นผลงานของรัฐบาลกลางสหรัฐอเมริกา NIST SP 800-90A จึงเป็นสาธารณสมบัติและสามารถเข้าถึงได้โดยเสรี
ประวัติศาสตร์
เอกสาร ฉบับก่อนหน้าของ NIST SP 800-90A ได้รับการเผยแพร่โดยสถาบันมาตรฐานและเทคโนโลยีแห่งชาติในเดือนมิถุนายน พ.ศ. 2549 ในชื่อNIST SP 800-90โดยมีชื่อเรื่องว่า คำแนะนำสำหรับการสร้างเลขสุ่มโดยใช้ตัวสร้างบิตสุ่มแบบกำหนดได้เอกสารที่เผยแพร่ในปี พ.ศ. 2549 นี้มีข้อกำหนดสำหรับตัวสร้างเลขสุ่มเทียมสี่แบบที่อ้างว่ามีความปลอดภัยทางด้านการเข้ารหัสสำหรับการใช้งานในด้านการเข้ารหัสได้แก่Hash_DRBG (อิงตามฟังก์ชันแฮช ), HMAC_DRBG (อิงตามHMAC ), CTR_DRBG (อิงตามการเข้ารหัสแบบบล็อกในโหมดตัวนับ ) และDual_EC_DRBG (อิงตามการเข้ารหัสแบบวงรี ) [ sp 1 ]
ในเดือนมีนาคม พ.ศ. 2550 เอกสารNIST SP 800-90 Revised (800-90R) ที่มีชื่อเดียวกันได้เข้ามาแทนที่ฉบับก่อนหน้า นอกจากการแก้ไขข้อความเล็กน้อยแล้ว ยังมีการเปลี่ยนแปลงที่สำคัญในรูปแบบของขั้นตอนเพิ่มเติมสำหรับ Dual_EC_DRBG เพื่อให้มีความต้านทานต่อการย้อนกลับ[ sp 2 ]
ในเดือนมกราคม 2012 NIST SP 800-90Aได้รับการเผยแพร่เพื่อแทนที่ NIST SP 800-90 Revised บันทึกการเปลี่ยนแปลงระบุว่าการแก้ไขส่วนใหญ่เสร็จสิ้นในเดือนสิงหาคม 2008 และข้อแนะนำได้รับการพัฒนาร่วมกับ ANSI X9.82-3 การเปลี่ยนแปลงที่ไม่เกี่ยวข้องกับอัลกอริทึม ได้แก่ การเพิ่มคำอธิบาย คำจำกัดความ และกฎห้ามการสร้างเมล็ดพันธุ์ใหม่ด้วยตนเอง ฟังก์ชันการสร้างอินสแตนซ์สำหรับ Dual_EC_DRBG ได้รับการแก้ไขอย่างมาก ภาคผนวกที่อุทิศให้กับการพิสูจน์ DBRG นี้ได้รับย่อหน้าใหม่ ฟังก์ชันแฮชใหม่จาก FIPS 180-4 ถูกเพิ่มในการอภิปรายเกี่ยวกับแฮช[ sp 3 ]
ในเดือนมิถุนายน พ.ศ. 2558 NIST 800-90A Revision 1 (800-90Ar1) ได้ถูกเผยแพร่ การเปลี่ยนแปลงที่สำคัญที่สุดคือการลบอัลกอริทึม Dual_EC_DRBG ที่น่าสงสัยออกไป[ sp 4 ]
ประวัติโดยย่อของข้อสงสัยที่เกิดขึ้นกับ Dual_EC_DRBG
Dual_EC_DBRG ไม่ได้ถูกนำเสนอต่อสาธารณะเป็นครั้งแรกใน NIST SP 800-90 ปี 2006 แต่ปรากฏในร่าง ANSI X9.82-3 ปี 2004 รวมถึงเวอร์ชันอย่างเป็นทางการของ ISO/IEC 18031:2005 [ 1 ]ข้อบกพร่องของมันได้รับการพิสูจน์ครั้งแรกในเดือนมีนาคม 2006 เมื่อ Kristian Gjøsteen เผยแพร่วิธีการทำนายอคติในเวอร์ชันที่พบในร่าง NIST SP 800-90 เดือนธันวาคม 2015 อย่างไรก็ตาม การตีพิมพ์ครั้งต่อมาในเดือนมิถุนายน 2006 ไม่ได้กล่าวถึงข้อบกพร่องนี้[ 2 ]
ในปี 2007 Dan Shumow และ Niels Ferguson ได้นำเสนอการโจมตีที่ทรงพลังยิ่งขึ้น โดยมีความสามารถในการกู้คืนสถานะภายในทั้งหมดด้วยเอาต์พุตเพียง 32 ไบต์ และสามารถทำนายเอาต์พุตในอนาคตทั้งหมดได้ ค่าคงที่ที่อธิบายไม่ได้ใน Dual_EC_DRBG ถูกตั้งสมมติฐานว่าทำหน้าที่เหมือนกุญแจสาธารณะผู้โจมตีจะใช้ชุดตัวเลขที่แตกต่างกัน (คล้ายกับกุญแจส่วนตัว) เพื่อทำการโจมตี Shumow และ Ferguson ไม่สามารถกู้คืนกุญแจของ NSA ได้ แต่พวกเขาสามารถสร้างคู่กุญแจของตนเองเพื่อสาธิตได้ ในเดือนพฤศจิกายน 2007 Bruce Schneierได้แสดงความคิดเห็นเกี่ยวกับลักษณะที่ "แปลก" ของประวัติของเครื่องกำเนิดตัวเลขสุ่มนี้ และอธิบายการนำเสนอของ Shumow และ Ferguson ในแง่ที่เข้าใจง่ายกว่า[ 3 ]
ความสนใจใน Dual_EC_DRBG กลับมาอีกครั้งในเดือนกันยายน พ.ศ. 2556 จาก บันทึกของ สำนักงานความมั่นคงแห่งชาติที่พบในการรั่วไหลของเอ็ดเวิร์ด สโนว์เดน ซึ่งอ้างว่า มีช่องโหว่แบบขโมยข้อมูล [ 4 ] [ 5 ] การค้นหาสิทธิบัตรและเอกสารที่เกี่ยวข้องกับ DRBG นี้ย้อนหลังพบว่าเทคนิคทั่วไปที่ใช้นั้นได้รับการอธิบายไว้แล้วในเอกสารสองฉบับในปี พ.ศ. 2540 [ 6 ]นอกจากนี้ สิทธิบัตรในปี พ.ศ. 2548 ยังอธิบายถึงเทคนิคที่ใช้ในช่องโหว่นี้อย่างละเอียด รวมถึงวิธีการทำให้เป็นกลางด้วย[ 7 ] [ 1 ]อย่างไรก็ตาม การกำหนดสูตรอย่างละเอียดอ่อนที่ใช้ในมาตรฐานหมายความว่า การปฏิบัติตาม FIPS 140-2จะขัดขวางการใช้เทคนิคการทำให้เป็นกลางใดๆ[ 8 ]
NIST ปฏิเสธการใช้ Dual_EC_DRBG กับ RSA ก่อนวันที่ 26 กุมภาพันธ์ 2014 [ 9 ]เมื่อวันที่ 21 เมษายน 2014 NIST ได้ถอน Dual_EC_DRBG ออกจากร่างคำแนะนำเกี่ยวกับตัวสร้างเลขสุ่ม โดยแนะนำให้ "ผู้ใช้ Dual_EC_DRBG ในปัจจุบันเปลี่ยนไปใช้อัลกอริทึมที่ได้รับการอนุมัติอีก 3 ตัวโดยเร็วที่สุด" [ 10 ]ร่างนี้จะกลายเป็นเอกสารทางการ NIST SP 800-90A Revision 1 ในเดือนมิถุนายน 2015
การวิเคราะห์ความปลอดภัย
NIST อ้างว่า DBRG ทั้งสี่ (แก้ไขเป็นสาม) ตัวนั้น "ทนต่อการย้อนกลับ" และ "ทนต่อการทำนาย" อย่างแรกคือแนวคิดทั่วไปของ " ความลับไปข้างหน้า " ของ PRNG: ในกรณีที่สถานะถูกบุกรุก ผู้โจมตีไม่สามารถกู้คืนสถานะและผลลัพธ์ในอดีตได้ อย่างหลังหมายความว่าหากสถานะถูกบุกรุกและได้รับการใส่เมล็ดใหม่ด้วยเอนโทรปีที่เพียงพอ ความปลอดภัยก็จะได้รับการฟื้นฟู[ 11 ]
Dual_EC_DRBG
การพยายามพิสูจน์ความปลอดภัยของ Dual_EC_DRBG ระบุว่าต้องใช้ปัญหาทางคณิตศาสตร์ที่ยาก 3 ข้อเพื่อให้ Dual_EC_DRBG ปลอดภัย ได้แก่ปัญหาการตัดสินใจ Diffie-Hellmanปัญหาx-logarithmและปัญหาจุดตัด[ 12 ]ปัญหาการตัดสินใจ Diffie-Hellman เป็นที่ยอมรับกันอย่างกว้างขวางว่ายาก[ 12 ]ปัญหา x-logarithm ไม่เป็นที่ยอมรับกันอย่างกว้างขวางว่ายาก มีหลักฐานบางอย่างที่แสดงว่าปัญหานี้ยาก แต่หลักฐานนั้นไม่แน่ชัด[ 12 ]ดังนั้น การพิสูจน์ความปลอดภัยจึงเป็นที่น่าสงสัยและจะถูกพิสูจน์ว่าไม่ถูกต้องหากแสดงให้เห็นว่าปัญหา x-logarithm สามารถแก้ไขได้อย่างมีประสิทธิภาพ ปัญหาจุดตัดต้องใช้บิตจำนวนมากพอที่จะถูกตัดออกจากจุดที่เลือกโดย Dual_EC_DRBG เพื่อให้ไม่สามารถแยกแยะได้จากตัวเลขสุ่มที่แท้จริง[ 12 ]อย่างไรก็ตาม การตัดทอน 16 บิต ซึ่งเป็นค่าเริ่มต้นที่กำหนดโดยมาตรฐาน Dual_EC_DRBG ได้รับการพิสูจน์แล้วว่าไม่เพียงพอที่จะทำให้เอาต์พุตไม่สามารถแยกแยะได้จากตัวสร้างเลขสุ่มที่แท้จริง[ 13 ]และด้วยเหตุนี้จึงทำให้การพิสูจน์ความปลอดภัยของ Dual_EC_DRBG เป็นโมฆะเมื่อใช้ค่าการตัดทอนเริ่มต้น
ช่องโหว่ใน Dual_EC_DRBG
ในฐานะส่วนหนึ่งของ โครงการ Bullrun , NSA ได้แทรกช่องโหว่เข้าไปในระบบการเข้ารหัส หนึ่งในเป้าหมายดังกล่าวได้รับการเสนอแนะในปี 2013 ให้เป็น Dual_EC_DRBG [ 14 ] NSA บรรลุเป้าหมายนี้โดยการทำงานในระหว่างกระบวนการกำหนดมาตรฐานจนในที่สุดก็กลายเป็นผู้แก้ไขมาตรฐานแต่เพียงผู้เดียว[ 15 ]ในการทำให้ Dual_EC_DRBG ได้รับการยอมรับเข้าสู่ NIST SP 800-90A, NSA ได้อ้างถึงการใช้งาน Dual_EC_DRBG ในผลิตภัณฑ์ของบริษัทรักษาความปลอดภัยที่มีชื่อเสียงอย่างRSA Securityอย่างไรก็ตาม RSA Security ได้รับเงิน 10 ล้านดอลลาร์จาก NSA เพื่อใช้ Dual_EC_DRBG เป็นค่าเริ่มต้น ในข้อตกลงที่Reutersอธิบายว่า "ดำเนินการโดยผู้นำทางธุรกิจมากกว่านักเทคโนโลยีล้วนๆ" เนื่องจากสัญญา 10 ล้านดอลลาร์เพื่อให้ RSA Security ใช้ Dual_EC_DRBG นั้น Reuters อธิบายว่าเป็นความลับ บุคคลที่เกี่ยวข้องในกระบวนการยอมรับ Dual_EC_DRBG เข้าสู่ NIST SP 800-90A จึงไม่น่าจะได้รับทราบถึงความขัดแย้งทางผลประโยชน์ที่ชัดเจนนี้[ 16 ]นี่อาจช่วยอธิบายได้ว่าเครื่องกำเนิดตัวเลขสุ่มที่ภายหลังพบว่าด้อยกว่าทางเลือกอื่น (นอกเหนือจากช่องโหว่) เข้ามาอยู่ในมาตรฐาน NIST SP 800-90A ได้อย่างไร
ศักยภาพของช่องโหว่ใน Dual_EC_DRBG ได้รับการบันทึกไว้แล้วโดยDan ShumowและNiels Fergusonในปี 2550 [ 17 ]แต่ยังคงถูกนำไปใช้ในทางปฏิบัติโดยบริษัทต่างๆ เช่น RSA Security จนกระทั่งมีการเปิดเผยในปี 2556 [ 5 ]เนื่องจากข้อบกพร่องที่ทราบกันดีใน Dual_EC_DRBG จึงมีการกล่าวหาว่า RSA Security จงใจใส่ช่องโหว่ของ NSA ลงในผลิตภัณฑ์ของตน RSA ปฏิเสธว่าไม่ได้จงใจใส่ช่องโหว่ลงในผลิตภัณฑ์ของตน[ 18 ]
หลังจากการเปิดเผยช่องโหว่ของ NSA ทาง NIST ได้เปิดกระบวนการตรวจสอบสาธารณะสำหรับมาตรฐาน NIST SP 800-90A อีกครั้ง[ 14 ] [ 19 ]เวอร์ชันที่แก้ไขของ NIST SP 800-90A ที่ลบ Dual_EC_DRBG ออกได้รับการเผยแพร่ในเดือนมิถุนายน 2015 [ 20 ]
Hash_DRBG และ HMAC_DRBG
Hash_DRBG และ HMAC_DRBG มีการพิสูจน์ความปลอดภัยสำหรับการเรียกใช้เพียงครั้งเดียวเพื่อสร้างตัวเลขสุ่มเทียม[ 21 ]เอกสารที่พิสูจน์ความปลอดภัยของ Hash_DRBG และ HMAC_DRBG อ้างถึงความพยายามในการพิสูจน์ความปลอดภัยสำหรับ Dual_EC_DRBG ที่ใช้ในย่อหน้าก่อนหน้านี้ว่าเป็นการพิสูจน์ความปลอดภัยเพื่อบอกว่าไม่ควรใช้ CTR_DRBG เพราะเป็น DRBG เพียงตัวเดียวใน NIST SP 800-90A ที่ไม่มีการพิสูจน์ความปลอดภัย[ 21 ]
HMAC_DRBG ยังมีการพิสูจน์ความปลอดภัยที่ตรวจสอบโดยเครื่องจักรอีกด้วย[ 22 ]วิทยานิพนธ์ที่ประกอบด้วยการพิสูจน์ความปลอดภัยที่ตรวจสอบโดยเครื่องจักรยังพิสูจน์ได้ว่าการประนีประนอมของอินสแตนซ์ HMAC_DRBG ที่ใช้งานอย่างถูกต้องจะไม่กระทบต่อความปลอดภัยของตัวเลขที่สร้างขึ้นก่อนการประนีประนอม[ 22 ]
Woodage และ Shumow (2019) วิเคราะห์แผนการของ NIST โดยละเอียดมากขึ้น โดยเฉพาะอย่างยิ่ง พวกเขาได้ให้หลักฐานความปลอดภัยที่คำนึงถึงการสร้างเมล็ดพันธุ์เริ่มต้นและการสร้างเมล็ดพันธุ์ใหม่ ซึ่งไม่เคยมีการวิเคราะห์มาก่อน ภายใต้ แบบจำลอง ออราเคิลแบบสุ่มและสมมติว่าแหล่งเอนโทรปีเป็นอิสระจากออราเคิล: [ 11 ]
- Hash_DBRG มีความแข็งแกร่งในความหมายของ Dodis และคณะ กล่าวคือ ตรงตามข้อกำหนดด้านความปลอดภัยของ NIST ทั้งสองข้อ
- HMAC_DBRG มีความเสถียรภายใต้เงื่อนไขสองประการ: ต้องเรียกใช้ด้วยเอนโทรปีอินพุตเพิ่มเติม และเอนโทรปีดังกล่าวต้องเป็นไปตามเงื่อนไขเพิ่มเติม แหล่งเอนโทรปีที่ได้รับการอนุมัติจาก NIST ทั้งหมดเป็นไปตาม "เงื่อนไขเพิ่มเติม" เหล่านี้
- HMAC_DBRG ไม่มีความปลอดภัยแบบย้อนหลัง (forward-secure) เมื่อเรียกใช้โดยไม่มีอินพุตเพิ่มเติม
ซีทีอาร์_ดีอาร์บีจี
CTR_DRBGได้รับการพิสูจน์แล้วว่ามีข้อบกพร่องทางทฤษฎีเมื่อใช้กับพารามิเตอร์บางอย่าง เนื่องจากนักเข้ารหัสไม่ได้พิจารณาขนาดบล็อกของการเข้ารหัสเมื่อออกแบบตัวสร้างเลขสุ่มเทียมนี้[ 23 ] CTR_DRBG ดูเหมือนจะปลอดภัยและแยกไม่ออกจากแหล่งกำเนิดเลขสุ่มจริงเมื่อใช้AES เป็นการ เข้ารหัสบล็อก พื้นฐาน และนำบิต 112 บิตจากตัวสร้างเลขสุ่มเทียมนี้[ 23 ]เมื่อใช้ AES เป็นการเข้ารหัสบล็อกพื้นฐานและนำบิต 128 บิตจากแต่ละอินสแตนซ์ ระดับความปลอดภัยที่ต้องการจะได้รับการส่งมอบโดยมีข้อแม้ว่าเอาต์พุตของการเข้ารหัส 128 บิตในโหมดตัวนับสามารถแยกความแตกต่างจากตัวสร้างเลขสุ่มจริงได้[ 23 ]เมื่อใช้ AES เป็นการเข้ารหัสบล็อกพื้นฐานและนำบิตมากกว่า 128 บิตจากตัวสร้างเลขสุ่มเทียมนี้ ระดับความปลอดภัยที่ได้จะถูกจำกัดด้วยขนาดบล็อกแทนที่จะเป็นขนาดคีย์ดังนั้นระดับความปลอดภัยที่แท้จริงจึงน้อยกว่าระดับความปลอดภัยที่บ่งบอกโดยขนาดคีย์มาก[ 23 ]นอกจากนี้ยังพบว่า CTR_DRBG ไม่สามารถให้ระดับความปลอดภัยที่คาดหวังได้เมื่อ ใช้ Triple DESเนื่องจากขนาดบล็อก 64 บิตนั้นน้อยกว่าขนาดคีย์ 112 บิตที่ใช้สำหรับ Triple DES มาก[ 23 ]
ปัจจุบันยังไม่มีวิธีการใดที่ทราบแน่ชัดในการใช้ประโยชน์จากช่องโหว่นี้เมื่อใช้ AES
การลบกุญแจ
รูปแบบ NIST CTR_DRBG จะลบคีย์หลังจากส่งออกค่าสุ่มที่ร้องขอโดยการสร้างค่าสุ่มเพิ่มเติมเพื่อแทนที่คีย์ วิธีนี้สิ้นเปลืองในแง่ของประสิทธิภาพ แต่ไม่ได้ทำให้เกิดปัญหาเกี่ยวกับความลับแบบส่งต่อในทันที อย่างไรก็ตาม เมื่อตระหนักถึงผลกระทบด้านประสิทธิภาพ NIST จึงแนะนำ "อินเทอร์เฟซ AES-CTR-DRBG แบบขยาย" สำหรับ การส่ง โครงการการเข้ารหัสหลังควอนตัม อินเทอร์เฟซนี้อนุญาตให้สร้างชุดค่าสุ่มหลายชุดโดยไม่ต้องลบข้อมูลระหว่างนั้น โดยจะลบข้อมูลก็ต่อเมื่อผู้ใช้ส่งสัญญาณอย่างชัดเจนว่าสิ้นสุดการร้องขอแล้วเท่านั้น ผลก็คือ คีย์อาจยังคงอยู่ในหน่วยความจำเป็นเวลานานหากใช้ "อินเทอร์เฟซแบบขยาย" ในทางที่ผิด ทางเลือกอื่นที่เสนอโดย Bernstein คือการสร้างค่าสุ่มเพื่อแทนที่คีย์ก่อนที่จะส่งออกค่าสุ่มที่ร้องขอ ดังที่ทำใน RNG แบบ "ลบคีย์อย่างรวดเร็ว" [ 24 ]
ขอบเขตความปลอดภัยที่รายงานโดย Campagna (2006) ไม่ได้คำนึงถึงขั้นตอนการเปลี่ยนคีย์ใดๆ[ 24 ]
Woodage และ Shumow (2019) นำเสนอการวิเคราะห์ร่างสถานการณ์ที่ Bernstein กล่าวถึง นั่นคือการรั่วไหลของสถานะโดยสมมติว่ามีความสุ่มจำนวนมาก ( next) ที่สร้างขึ้นระหว่างการเปลี่ยนคีย์ ( final) [ 11 ]