การทดสอบและตรวจสอบการนำ RNG ไปใช้

การทดสอบตัวสร้างตัวเลขสุ่มเผชิญความท้าทายพื้นฐานประการหนึ่ง: ลำดับที่สุ่มอย่างแท้จริงและลำดับเทียมสุ่มจาก PRNG ที่ดีจะดูเหมือนกันในการทดสอบทางสถิติ ไม่มีการทดสอบที่มีความยาวจำกัดใดพิสูจน์ได้ว่าลำดับหนึ่งเป็นการสุ่ม การวิเคราะห์ทางสถิติทำได้เพียงตรวจจับความไม่สุ่มด้วยระดับความเชื่อมั่นบางประการ การทดสอบตรวจสอบว่า RNG ไม่มีอคติหรือรูปแบบที่เห็นได้ชัด แต่ไม่สามารถพิสูจน์ความปลอดภัยด้านการเข้ารหัสได้ การทดสอบ RNG ด้านการเข้ารหัสมีเป้าหมายที่แตกต่างกันสองประการ: (1) คุณภาพทางสถิติ คือการตรวจสอบว่าการกระจายของเอาต์พุตดูสม่ำเสมอและเป็นอิสระ (2) ความแข็งแกร่งด้านการเข้ารหัส คือการตรวจสอบว่าขั้นตอนวิธี DRBG ถูกนำไปใช้ได้อย่างถูกต้อง และข้ออ้างด้านความปลอดภัยเป็นจริง เป้าหมายทั้งสองนี้ต้องใช้แนวทางการทดสอบที่แตกต่างกัน

NIST SP 800-22 มีการทดสอบทางสถิติ 15 รายการสำหรับประเมินลำดับบิต การทดสอบเหล่านี้ได้แก่ การทดสอบความถี่ (บิตเดี่ยว) — สัดส่วนของเลข 1 ควรใกล้เคียง 0.5 การทดสอบความถี่แบบบล็อก — ความถี่ของเลข 1 ในแต่ละบล็อกขนาด m บิต การทดสอบช่วงต่อเนื่อง — จำนวนช่วงของบิตที่เหมือนกันและไม่ขาดตอน การทดสอบช่วงที่ยาวที่สุด — ความยาวของช่วงเลข 1 ที่ยาวที่สุด การทดสอบอันดับเมทริกซ์ไบนารี — อันดับของเมทริกซ์ไบนารีที่สร้างจากลำดับ การทดสอบเชิงสเปกตรัม (DFT) — ตรวจหารูปแบบที่เกิดซ้ำเป็นคาบ การจับคู่แม่แบบที่ทับซ้อนกัน — นับจำนวนครั้งที่รูปแบบเฉพาะปรากฏ การทดสอบทางสถิติแบบสากลของ Maurer — บีบอัดลำดับแล้ววัดว่าลำดับสั้นลงมากเพียงใด การทดสอบแต่ละรายการจะสร้างค่า p โดยค่า p < 0.01 บ่งชี้ความไม่สุ่ม การทดสอบใช้กับข้อมูลตั้งแต่ 1 ล้านถึง 1 พันล้านบิต

TestU01 (เลอคูเยร์และซีมาร์ด, 2007) เป็นชุดการทดสอบทางสถิติที่ครอบคลุมและใช้กันอย่างแพร่หลายในแวดวง RNG SmallCrush: การทดสอบ 10 รายการ ใช้เวลาประมาณ 35 วินาที เหมาะสำหรับการตรวจสอบอย่างรวดเร็ว Crush: การทดสอบ 144 รายการ ใช้เวลาประมาณ 2 ชั่วโมง BigCrush: การทดสอบ 160 รายการ ใช้เวลาประมาณ 24 ชั่วโมง การทดสอบ BigCrush ตรวจจับสหสัมพันธ์ที่ละเอียดอ่อนซึ่ง NIST SP 800-22 ตรวจไม่พบ DRBG ด้านการเข้ารหัสที่ออกแบบมาอย่างดี เช่น HMAC_DRBG และ CTR_DRBG ผ่าน BigCrush ได้อย่างง่ายดาย เพราะเอาต์พุตของมันแยกแยะเชิงคำนวณจากการสุ่มไม่ได้สำหรับขั้นตอนวิธีที่ใช้เวลาพหุนาม PRNG ที่ไม่ใช่การเข้ารหัส เช่น Mersenne Twister และตัวสร้างแบบสอดคล้องเชิงเส้น ไม่ผ่านการทดสอบ BigCrush บางรายการ การไม่ผ่าน BigCrush เป็นตัวบ่งชี้ที่ชัดเจนว่าไม่ควรใช้ RNG นั้นเพื่อวัตถุประสงค์ด้านการเข้ารหัส

SP 800-90B และ 90A กำหนดการทดสอบสถานะที่ DRBG ต้องดำเนินการอย่างต่อเนื่องระหว่างการทำงาน การทดสอบ RNG อย่างต่อเนื่อง (CRNGT): แต่ละบล็อกที่สร้างขึ้นจะถูกเปรียบเทียบกับบล็อกก่อนหน้า หากเท่ากัน (แสดงว่า RNG ค้าง) DRBG ต้องเข้าสู่สถานะข้อผิดพลาดและหยุดการสร้างข้อมูล การทดสอบนับจำนวนการซ้ำ: หากตัวอย่างที่ต่อเนื่องกันมีค่าเดียวกันซ้ำมากกว่าที่คาดหมายทางสถิติเมื่อพิจารณาจากค่าประมาณเอนโทรปี ให้ถือว่าการทดสอบไม่ผ่าน การทดสอบสัดส่วนแบบปรับได้: หากค่าที่พบบ่อยที่สุดปรากฏเกินจำนวนเกณฑ์ที่กำหนดภายในช่วงข้อมูล ให้ถือว่าการทดสอบไม่ผ่าน การทดสอบสถานะเหล่านี้ตรวจจับความล้มเหลวของแหล่งเอนโทรปี เช่น เซนเซอร์ค้างหรือความขัดข้องของฮาร์ดแวร์ HWRNG ก่อนที่ความล้มเหลวนั้นจะทำให้การสร้างกุญแจการเข้ารหัสเสียหายโดยไม่มีสัญญาณเตือน

PractRand เป็นเครื่องมือทดสอบ RNG สมัยใหม่ที่ออกแบบมาสำหรับการประเมินแบบออนไลน์ (สตรีมข้อมูล) โดยวิเคราะห์ลำดับขณะที่กำลังสร้างขึ้น แทนที่จะกำหนดความยาวไว้ล่วงหน้า เครื่องมือนี้ใช้การทดสอบต่าง ๆ รวมถึงการทดสอบช่องว่าง การทดสอบการกระจายของบิต และการทดสอบเชิงสเปกตรัมที่มีความแม่นยำแบบปรับได้ PractRand มีประสิทธิภาพเป็นพิเศษในการตรวจจับ RNG ที่สร้างลำดับสั้น ๆ ได้ดี แต่เผยรูปแบบออกมาเมื่อมีข้อมูลหลายพันล้านบิต DRBG ด้านการเข้ารหัสสร้างเอาต์พุตที่ PractRand ไม่สามารถแยกแยะจากการสุ่มได้ไม่ว่าจะมีความยาวเท่าใด ซึ่งเป็นนิยามเชิงปฏิบัติการของการแยกแยะเชิงคำนวณไม่ได้ PractRand ยังใช้ประเมินแหล่งเอนโทรปีด้วย เช่น ทดสอบเอาต์พุตของ /dev/urandom และเอาต์พุตของ RDRAND เพื่อตรวจจับความขัดข้องของฮาร์ดแวร์หรืออคติที่เป็นระบบ

โครงการตรวจสอบความถูกต้องของขั้นตอนวิธีการเข้ารหัส (CAVP) จัดเตรียมเวกเตอร์การทดสอบอย่างเป็นทางการสำหรับ DRBG ตาม SP 800-90A การทดสอบ CAVP ประกอบด้วยการส่งการติดตั้งใช้งานไปยังระบบทดสอบอัตโนมัติของ NIST พร้อมเวกเตอร์การทดสอบคำตอบที่ทราบล่วงหน้า (KAT): เมื่อได้รับอินพุตเอนโทรปี ค่า nonce สตริงปรับเฉพาะบุคคล และ additional_input ที่กำหนดไว้ การติดตั้งใช้งานนั้นต้องสร้างบิตเอาต์พุตที่คาดหมายไว้ได้ตรงทุกประการ CAVP ไม่ได้ทดสอบคุณสมบัติทางสถิติ แต่ทดสอบความถูกต้องของขั้นตอนวิธี การรับรอง FIPS 140-3 กำหนดให้ต้องผ่านการตรวจสอบ CAVP สำหรับขั้นตอนวิธีการเข้ารหัสทั้งหมดที่ใช้ภายในขอบเขตของโมดูล เวกเตอร์การทดสอบ CAVP เปิดให้สาธารณชนใช้งานได้จากเซิร์ฟเวอร์ ACVP (โพรโทคอลตรวจสอบการเข้ารหัสอัตโนมัติ) ของ NIST และถูกรวมไว้ในชุดการทดสอบของ OpenSSL, mbedTLS และ BoringSSL

ก่อนที่ DRBG จะเริ่มต้นทำงานอย่างปลอดภัยได้ ต้องตรวจสอบความถูกต้องของแหล่งเอนโทรปีก่อน SP 800-90B กำหนดสิ่งต่อไปนี้: (1) การประมาณเอนโทรปี — วัดเอนโทรปีจริงต่อบิตโดยใช้การทดสอบทางสถิติ (การประมาณเอนโทรปีต่ำสุด) (2) การทดสอบเมื่อเริ่มต้น — ตรวจสอบว่าแหล่งเอนโทรปีสร้างเอาต์พุตที่ถูกต้องก่อนการใช้งานครั้งแรก (3) การทดสอบตามคำขอ — การทดสอบเพิ่มเติมที่แอปพลิเคชันเรียกใช้ (4) การทดสอบสถานะของแหล่งสัญญาณรบกวน — ตรวจจับการเสื่อมสภาพของฮาร์ดแวร์ แหล่งเอนโทรปีทั่วไปและค่าเอนโทรปีโดยประมาณต่อบิต ได้แก่ CPU RDRAND/RDSEED (ประมาณ 1 บิตต่อบิต และผ่านการรับรองด้านฮาร์ดแวร์), /dev/urandom (ผสมหลายแหล่งเข้าด้วยกัน จึงใช้ค่าประมาณเอนโทรปีแบบอนุรักษนิยม), TRNG แบบออสซิลเลเตอร์วงแหวน (0.5–0.9 บิตต่อบิต ขึ้นอยู่กับการออกแบบ) และสัญญาณรบกวนจาก ADC (0.1–0.5 บิตต่อบิต) การตรวจสอบตาม SP 800-90B ต้องผ่านการทดสอบในห้องปฏิบัติการด้วยอุปกรณ์เฉพาะทาง

สภาพแวดล้อมเสมือนก่อให้เกิดความท้าทายเฉพาะด้านการทดสอบ RNG โดย VM อาจพบสภาวะเอนโทรปีต่ำเมื่อเริ่มต้นระบบ (ไม่มีเหตุการณ์จากฮาร์ดแวร์) หรือหลังการกู้คืนสแนปช็อต (สถานะถูกตั้งค่าใหม่) ส่วนคอนเทนเนอร์ Docker ใช้ RNG ของเคอร์เนลโฮสต์ร่วมกัน — คอนเทนเนอร์จึงไม่สามารถทดสอบคุณภาพเอนโทรปีพื้นฐานได้โดยตรง การทดสอบสำหรับการนำ VM ไปใช้งานมีดังนี้: (1) วัดเวลาจนการอ่าน /dev/random เสร็จสมบูรณ์ — การรอเป็นเวลานานบ่งชี้ว่าเอนโทรปีไม่เพียงพอ (2) ตรวจหาค่า UUID หรือคีย์ซ้ำที่สร้างขึ้นแบบขนานในอินสแตนซ์ VM (เป็นโหมดความล้มเหลวจริงที่มีการบันทึกไว้ในการนำไปใช้งานบนคลาวด์) (3) ตรวจสอบว่า VIRTIO-RNG (virtio_rng.ko) ถูกโหลดใน VM แล้ว — สิ่งนี้จะฉีดเอนโทรปีจากโฮสต์เข้าสู่ระบบแขก (4) ตรวจสอบลำดับการเริ่มต้นแอปพลิเคชัน: การสร้างคีย์เกิดขึ้นก่อนที่จะมีเอนโทรปีเพียงพอหรือไม่

การทดสอบความปลอดภัยต่อการแยกกระบวนการของ RNG ช่วยป้องกันช่องโหว่ที่ตรวจพบได้ยาก: เมื่อกระบวนการแยกตัว กระบวนการแม่และกระบวนการลูกจะใช้สถานะ DRBG เดียวกัน ทำให้สร้างลำดับค่าเหมือนกัน การตรวจจับทำได้โดยสร้างกระบวนการลูก N กระบวนการ สร้าง UUID ในแต่ละกระบวนการ และตรวจสอบว่า UUID ทั้งหมดไม่ซ้ำกัน หากมีคู่ใดตรงกัน แสดงว่า RNG ไม่ปลอดภัยต่อการแยกกระบวนการ OpenSSL แก้ไขข้อบกพร่องด้านความปลอดภัยต่อการแยกกระบวนการในปี 2020 (CVE-2020-1971 ไม่ได้เกี่ยวข้องโดยตรงกับ DRBG แต่รูปแบบของปัญหาคล้ายกัน) ปัจจุบัน OpenSSL ใช้การอัปเดตค่าเริ่มต้นตาม PID: หาก PID เปลี่ยนไปนับตั้งแต่การเรียกใช้ครั้งล่าสุด (ซึ่งบ่งชี้ว่ามีการแยกกระบวนการ) ระบบจะสร้างค่าเริ่มต้นของ DRBG ใหม่โดยอัตโนมัติ การทดสอบเรื่องนี้ทำได้โดยเรียกใช้การทดสอบก่อนและหลังการแยกกระบวนการ แล้วตรวจสอบผลลัพธ์ที่แตกต่างกันเพื่อยืนยันว่ามีการสร้างค่าเริ่มต้นใหม่

รายการตรวจสอบเชิงปฏิบัติสำหรับการตรวจประเมินการใช้งาน RNG มีดังนี้: (1) RNG ถูกเริ่มต้นจาก OS (getrandom, BCryptGenRandom) แทนการใช้ค่าเริ่มต้นตามเวลาหรือไม่ (2) ประเภท DRBG เป็นกลไกที่ได้รับอนุมัติตาม NIST SP 800-90A (Hash, HMAC, CTR) หรือไม่ (3) ความยาวของค่าเริ่มต้นเพียงพอกับระดับความปลอดภัยที่อ้างไว้หรือไม่ (4) มีการเรียกใช้การสร้างค่าเริ่มต้นใหม่เป็นระยะ ๆ หรือหลังจากเรียกใช้การสร้างค่าครบจำนวนที่กำหนดหรือไม่ (5) การใช้งานรองรับความปลอดภัยต่อการแยกกระบวนการหรือไม่ (มีการสร้างค่าเริ่มต้นใหม่หลังการแยกกระบวนการ) (6) เปิดใช้การทดสอบความสมบูรณ์หรือไม่ และระบบหยุดทำงานเมื่อการทดสอบล้มเหลวหรือไม่ (7) สถานะถูกล้างเป็นศูนย์เมื่อปิดระบบหรือไม่ (8) มีการเรียกใช้เวกเตอร์ทดสอบของ CAVP ใน CI/CD หรือไม่ (9) มีการจัดทำเอกสารและตรวจสอบความถูกต้องของค่าประมาณเอนโทรปีหรือไม่ (10) สำหรับข้อกำหนดของ FIPS: โมดูลได้รับการรับรอง FIPS 140-3 หรือไม่

ความล้มเหลวของ RNG ในอดีตแสดงให้เห็นว่าผลกระทบร้ายแรงเพียงใด Debian OpenSSL (2006-2008): แพตช์หนึ่งลบโค้ดรวบรวมเอนโทรปีไปโดยไม่ตั้งใจ ทำให้กลุ่มค่าเริ่มต้นลดลงเหลือพื้นที่ PID ขนาด 15 บิต — มีการสร้างคีย์ SSH ที่เป็นไปได้เพียง 32,767 ค่าให้กับฐานผู้ใช้ Debian ทั้งหมด คีย์โฮสต์ SSH และคีย์ผู้ใช้ทั้งหมดที่สร้างโดย Debian จึงต้องเปลี่ยนใหม่ กระเป๋าเงิน Bitcoin บน Android (2013): SecureRandom ของ Android ใช้การกำหนดค่าเริ่มต้นระดับ Java ซึ่งล้มเหลวในอุปกรณ์บางรุ่น ทำให้ค่า k ในลายเซ็น ECDSA ซ้ำกัน — และเปิดเผยคีย์ส่วนตัวโดยตรง Sony PS3 (2010): ใช้ค่าที่ใช้ครั้งเดียวคงที่ในการลงลายเซ็นเฟิร์มแวร์ ECDSA ทำให้สามารถดึงคีย์ส่วนตัวจากลายเซ็นสองรายการได้ (การใช้ค่า k เดียวกันกับข้อความต่างกันจะเปิดเผยคีย์ได้ด้วยพีชคณิตอย่างง่าย)

การทดสอบใดต่อไปนี้ตรวจพบว่า DRBG อาจกำลังสร้างผลลัพธ์ค้างอยู่ (เป็นค่าเดิมซ้ำ ๆ)

การทดสอบทางสถิติ (NIST SP 800-22, TestU01 BigCrush, PractRand) ตรวจสอบคุณภาพผลลัพธ์ได้ แต่ไม่สามารถพิสูจน์ความปลอดภัยทางคริปโตกราฟีได้ การทดสอบคำตอบที่ทราบของ CAVP ตรวจสอบความถูกต้องเชิงอัลกอริทึมของการใช้งาน SP 800-90A การทดสอบแหล่งเอนโทรปีตาม SP 800-90B (การประมาณเอนโทรปีขั้นต่ำและการทดสอบความสมบูรณ์) ตรวจสอบความถูกต้องของข้อมูลค่าเริ่มต้น การทดสอบ RNG อย่างต่อเนื่อง (CRNGT) ตรวจจับผลลัพธ์ที่ค้างอยู่ได้แบบเวลาจริง การนำไปใช้งานใน VM และคอนเทนเนอร์ต้องมีการฉีดเอนโทรปี (VIRTIO-RNG) และการตรวจสอบเอนโทรปีเมื่อเริ่มต้นระบบ การทดสอบความปลอดภัยต่อการแยกกระบวนการตรวจสอบว่ากระบวนการลูกไม่ได้สืบทอดสถานะ DRBG ของกระบวนการแม่ ความล้มเหลวในโลกจริง (Debian, Android) แสดงให้เห็นว่าข้อบกพร่องของ RNG นำไปสู่การเปิดเผยคีย์คริปโตกราฟีได้โดยตรง รายการตรวจสอบการตรวจประเมินช่วยจัดรูปแบบการตรวจสอบเหล่านี้สำหรับการนำไปใช้งานจริง