เอนโทรปีไม่เพียงพอและข้อผิดพลาดจากคีย์อ่อนแอ

ภาวะเอนโทรปีไม่เพียงพอเกิดขึ้นเมื่อระบบขาดข้อมูลนำเข้าที่คาดเดาไม่ได้อย่างเพียงพอสำหรับตั้งต้น CSPRNG เหตุการณ์นี้เกิดขึ้นได้ในอุปกรณ์ฝังตัวที่เพิ่งบูต เซิร์ฟเวอร์เสมือน หรือระบบที่ไม่มีข้อมูลนำเข้าจากผู้ใช้ ทำให้ผลลัพธ์จาก RNG คาดเดาได้

ในปี 2006 นักพัฒนา Debian ลบบรรทัดที่ Valgrind แจ้งเตือนออกไป: MD_Update(&m, buf, j) บรรทัดนี้เป็นแหล่งเอนโทรปี ผลลัพธ์คือ OpenSSL บน Debian ตั้งต้นโดยใช้เพียง PID (มีค่าเป็นไปได้สูงสุด 32,768 ค่า) คีย์ทั้งหมดที่สร้างระหว่างปี 2006-2008 จึงอยู่ในชุดความเป็นไปได้เพียง 32,768 ค่า

คีย์ RSA, DSA และ ECDSA, คีย์โฮสต์ SSH, ใบรับรอง TLS และคีย์ SSL VPN ที่สร้างบนระบบ Debian/Ubuntu ระหว่างปี 2006-2008 ถูกทำให้ไม่ปลอดภัย ระบบที่ได้รับผลกระทบ ได้แก่ Debian Etch, Debian Lenny และ Ubuntu 7.04-8.04 มีการเผยแพร่บัญชีดำและเพิกถอนใบรับรองแล้ว

เครื่องเสมือนสามารถโคลนโดยมีสถานะดิสก์เหมือนกันทุกประการได้ หากเครื่องเสมือนทั้งสองสร้างคีย์จากสถานะ CSPRNG เดียวกัน ก็จะสร้างคีย์เดียวกัน ปัจจุบันไฮเปอร์ไวเซอร์ฉีดเอนโทรปีผ่าน VirtIO RNG หรือตาราง ACPI แล้ว แต่เครื่องเสมือนที่กำหนดค่าไม่ดียังคงเผชิญความเสี่ยงนี้ขณะบูต

อุปกรณ์ IoT (เราเตอร์ กล้อง) มักสร้างคีย์ SSH/TLS ในการบูตครั้งแรก ก่อนที่จะสะสมเอนโทรปีได้เพียงพอ งานศึกษาพบว่าอุปกรณ์หลายล้านเครื่องใช้คู่คีย์ RSA ร่วมกันเพียงไม่กี่พันคู่ เนื่องจากทั้งหมดตั้งต้นจากสถานะการบูตที่มีเอนโทรปีต่ำเหมือนกัน

Lenstra และคณะ (2012) รวบรวมใบรับรอง TLS จำนวน 11.7 ล้านใบและคำนวณ GCD แบบจับคู่ พบคีย์ RSA จำนวน 12,720 คีย์ที่ใช้ตัวประกอบจำนวนเฉพาะร่วมกัน ซึ่งหมายความว่าสามารถแยกตัวประกอบคีย์ทั้งสองได้ทั้งหมด คีย์สาธารณะ 0.2% จากทั้งหมดถูกทำลาย สาเหตุคือเอนโทรปีขณะบูตไม่เพียงพอ

ECDSA ต้องใช้นอนซ์สุ่ม k ที่ไม่ซ้ำกันสำหรับลายเซ็นแต่ละรายการ หากใช้ k ซ้ำ (หรือ k ไม่แข็งแรงพอ) ก็จะกู้คืนคีย์ส่วนตัวได้ทันที: d = (s1-s2)^{-1} * (z1-z2) * k / (r1-r2) mod n เครื่องเล่น PS3 ของ Sony ใช้ k=constant ทำให้สามารถลงลายเซ็นเกมทั้งหมดด้วยคีย์ที่กู้คืนมาได้

Java SecureRandom บน Android 4.x ถูกตั้งต้นด้วยเวลาของระบบภายใต้เงื่อนไขบางอย่าง แอปกระเป๋า Bitcoin หลายแอปสร้างลายเซ็นด้วยนอนซ์ k เดียวกัน ทำให้คีย์ส่วนตัวรั่วไหล มีเงินถูกขโมยไปหลายล้านดอลลาร์ Google แก้ไขการทำงานของ SecureRandom แล้ว

เครื่องมือ ได้แก่ ssh-vulnkey (ตรวจสอบกับบัญชีดำคีย์ที่อ่อนแอของ Debian), badkeys (ตรวจสอบใบรับรอง TLS ว่ามีจำนวนเฉพาะที่ทราบว่าอ่อนแอหรือไม่) และอัลกอริทึม GCD แบบกลุ่มสำหรับตรวจสอบคีย์ RSA จำนวนมาก บันทึก Certificate Transparency ช่วยให้วิเคราะห์ข้อมูลในระดับประชากรทั้งหมดได้

ใช้ getrandom(GRND_RANDOM) เมื่อสร้างคีย์ครั้งแรก อ่านจาก /dev/urandom หลังรอให้การตั้งต้นครั้งแรกเสร็จสมบูรณ์ (ตรวจสอบว่า /proc/sys/kernel/random/entropy_avail > 128) ใช้ฮาร์ดแวร์ RNG (RDRAND) เป็นเอนโทรปีเสริม ห้ามสร้างคีย์ในการบูตครั้งแรกโดยไม่หน่วงเวลา

คงสถานะ CSPRNG ไว้ข้ามการรีบูต: บันทึก 32 ไบต์จาก /dev/urandom ลงในไฟล์ค่าเริ่มต้นเมื่อปิดระบบ จากนั้นอ่านและป้อนกลับเข้าไปเมื่อบูต วิธีนี้ช่วยให้เอนโทรปีต่อเนื่องกันระหว่างการบูตเครื่องแบบเย็น Linux ทำเช่นนี้โดยอัตโนมัติ แต่ระบบฝังตัวมักไม่ทำ

สาเหตุรากของบั๊กเอนโทรปีใน OpenSSL บน Debian คืออะไร

ภาวะเอนโทรปีไม่เพียงพอทำให้เกิดคีย์ที่คาดเดาได้ เหตุการณ์ที่เกิดความเสียหายจริง ได้แก่ OpenSSL บน Debian (ตั้งต้นด้วย PID เพียงอย่างเดียว), การโจมตีด้วย GCD ต่ออุปกรณ์ IoT, การใช้นอนซ์ ECDSA ซ้ำบน PS3 และกระเป๋า Bitcoin บน Android ต้องตั้งต้นจากเอนโทรปีของ OS เสมอ และตรวจสอบการสร้างคีย์บนระบบฝังตัวอย่างรอบคอบ บทถัดไป: การสร้างคีย์ นอนซ์ และเวกเตอร์เริ่มต้นอย่างปลอดภัย