Random Number Generator: อะไรก็ได้ ง่ายๆ

by lew
5 May 2013 - 21:00

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

ปัญหาของการสุ่มที่ไม่ดีสร้างปัญหาต่อความปลอดภัยพื้นฐานเป็นอย่างยิ่ง เวลาที่เราเข้ารหัสด้วยกุญแจการเข้ารหัส เรามักคาดหวังว่ากุญแจการเข้ารหัสจะไม่สามารถคาดเดาได้ การเข้ารหัสแบบที่พื้นฐานที่สุดคือ one time pad เป็นการใช้ข้อมูลที่สุ่มอย่างสมบูรณ์ มา XOR กับข้อมูลที่เราต้องการเข้ารหัส หากแฮกเกอร์ไม่สามารถเดาได้ว่าข้อมูลที่สุ่มได้เป็นค่าอะไร ข้อมูลที่เข้ารหัสแล้วจะไม่สามารถถอดรหัสได้ ตัวอย่างปัญหาที่ง่ายที่สุดคือรหัสบัตรเอทีเอ็มที่คนจำนวนมากมักตั้งรหัสผ่านเป็นรหัสที่ง่ายอย่างที่ยกตัวอย่างไปแล้ว

True Random Number Generator

กระบวนการสุ่มอย่างสมบูรณ์เป็นสิ่งที่ปกติแล้วคอมพิวเตอร์พื้นฐานไม่สามารถทำได้ คอมพิวเตอร์ตามสถาปัตยกรรมของ Von Neumann นั้นสามารถทำได้เพียงคำนวณและบันทึกเท่านั้น เพื่อให้คอมพิวเตอร์สามารถ "สุ่ม" ได้ จึงจำเป็นต้องมีแหล่งของความยุ่งเหยิง (entropy source)

ในโลกความเป็นจริงนั้น แหล่งของความยุ่งเหยิงอาจจะอยู่ในรูปของลูกเต๋า หรือการสลับไพ่ที่เป็นแหล่งของความยุ่งเหยิงที่ได้รับการยอมรับกันมาเป็นเวลานาน ในโลกของคอมพิวเตอร์นั้นการใช้ความยุ่งเหยิงจากโลกการพนันมาปรับใช้เป็นเรื่องที่มีมานาน สิทธิบัตรของ Richard P. Dunnigan ทำให้คอมพิวเตอร์สามารถสุ่มตัวเลขได้อย่างสมบูรณ์ด้วยการสร้างเครื่อง "ออกหวย" เลือกลูกปิงปองต่อเข้ากับคอมพิวเตอร์ แล้วจึงได้เลขที่ต้องการสุ่มออกมา

เครื่องของ Dunnigan สุ่มได้ผลดีพอสมควร แต่ปัญหาคือ มันทำงานได้ช้ามาก หากต้องการข้อมูลสุ่มขนาดใหญ่ในระดับเมกกะไบต์ เราอาจจะต้องใช้เวลานับปีกว่าจะสุ่มข้อมูลได้ขนาดนั้น

ในโลกความเป็นจริง เพื่อรักษาความปลอดภัยในระบบคอมพิวเตอร์ เราจำเป็นต้องใช้เลขสุ่มตลอดเวลา ระบบการรักษาความปลอดภัยในการสื่อสารบนอินเทอร์เน็ตอย่าง SSL ต้องการเลขสุ่มเพื่อเป็นกุญแจสำหรับการสื่อสารระหว่างกัน กุญแจนั้นอาจจะมีขนาด 128 บิตขึ้นไป หรือ 16 ไบต์ หากเราใช้เครื่องออกหวยของ Dunnigan เราจะต้องสร้างเครื่องที่มีลูกบอลขนาด 256 ลูก แล้วสุ่มเลือก 16 ครั้งก่อนจะเชื่อมต่อกับเว็บสักเว็บ (นึกภาพพิมพ์คลิก URL แล้วมีเครื่องออกหวยนี้กำลังออกหวย 16 หลัก)

ปัญหาความเร็วของการสุ่มกลายเป็นปัญหาสำคัญ ในระบบรักษาความปลอดภัยยุคแรกๆ ไม่มีมาตรฐานการสุ่มเลข ทำให้ซอฟต์แวร์แต่ละตัวพยายามใช้อะไรที่ให้ค่าดู "มั่ว" เพียงพอ เบราว์เซอร์อย่าง Netscape นั้นยุคแรกเคยใช้ค่า MD5 ของเวลาปัจจุบันที่ความละเอียดเป็นวินาทีร่วมกับหมายเลขโปรเซส (PID) แต่เนื่องจากหมายเลขโปรเซสนั้นมักเป็นค่าที่ไม่เกิน 32768 ทำให้แฮกเกอร์ที่ดักฟังการเชื่อมต่ออยู่ และรู้ช่วงเวลาที่เริ่มเชื่อมต่อ สามารถคาดเดากุญแจในการเชื่อมต่อได้ โดยการสร้างคีย์ต่อหมายเลขโปรเซสที่เป็นไปได้ทั้งหมด ร่วมกับ เช่น หากต้องการสร้างกุญแจทั้งหมดในช่วงเวลาก่อนหน้าการเชื่อมต่อไปสิบวินาทีก็ยังต้องสร้างกุญแจเพียงสามแสนกว่าชุดเท่านั้น

ในระบบที่พัฒนาต่อๆ อย่าง Kerberos V4 ที่ใช้รักษาความปลอดภัยในองค์กร (ไมโครซอฟท์ซื้อสิทธิของ Kerberos V5 ไปปรับปรุงเป็นระบบรักษาความปลอดภัยของ ActiveDirectory ในภายหลัง) เคยแก้ปัญหาด้วยการใช้ค่าเวลาเป็น "ไมโครวินาที" แม้จะดูคาดเดายากขึ้น แต่ในความเป็นจริงก็ช่วยได้ไม่มากนัก เพราะแฮกเกอร์ที่อยู่ในเครือข่ายเดียวกันอาจจะจับเวลาเริ่มเชื่อมต่อได้อย่างแม่นยำ

ปัญหาความ "ไม่มั่ว" ของเลขสุ่มทำให้ระบบปฏิบัติการรุ่นใหม่ๆ ต้องหาแหล่งตั้งต้นเพื่อนำมาสร้างเลขสุ่มกันมากขึ้น และฟังก์ชั่นสุ่มที่ติดมากับภาษาโปรแกรมต่างๆ มักมีคำเตือนว่าห้ามใช้ค่าสุ่มสำหรับการทำงานด้านความปลอดภัย ในลินุกซ์ปัจจุบันนี้แหล่งของความยุ่งเหยิงมาจากสี่แหล่งสำคัญ ได้แก่ การพิมพ์คีย์บอร์ด, การขยับเมาส์, อินเทอร์รัปต์ (เช่นมีแพ็กเก็ตเน็ตเวิร์คเข้ามา), และการอ่านเขียนดิสก์ แล้วนำค่ามารวมกันเป็นค่าขนาด 512 ไบต์ ก่อนจะย่อยให้เลือกค่าสุ่มออกมาทีละ 128 ไบต์ ออกมาในไฟล์เสมือนที่ชื่อว่า /dev/random

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

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

i=fread(buf,1,n,in);
if (i <= 0) break;
/* even if n != i, use the full array */
RAND_add(buf,n,i);

คือเป็นการใช้บัฟเฟอร์ทั้งหมดแม้จะอ่านค่ามาได้ไม่ครบความยาวบัฟเฟอร์ แนวทางนี้ทำให้ตัวตรวจจับบั๊กอย่าง Valgrind ที่ตรวจบั๊กสำคัญคือการใช้หน่วยความจำที่ยังไม่กำหนดค่า แจ้งเตือนทุกครั้งที่มีการรันโค้ด หลายโครงการมีนโยบายที่จะรัน Valgrind เพื่อตรวจสอบมาตรฐานโค้ด การสื่อสารกับทีมผู้พัฒนา OpenSSL ที่ผิดพลาดทำให้โครงการ Debian เคยคอมเมนต์โค้ดออกจากโค้ดของ OpenSSL เพื่อลดข้อความแจ้งเตือน แต่กลับทำให้แหล่งค่าสุ่มไม่ได้รับการอัพเดต ผลลัพธ์คือกุญแจสำหรับล็อกอิน Secure Shell นั้นมีความเป็นไปได้เพียง 32768 เป็นเวลานานถึงสองปีเต็ม จนทุกวันนี้ยังต้องมีการห้ามใช้กุญแจทั้งหมดด้วยโปรแกรม ssh-keyscan และ ssh-vulnkey

เพื่อให้การสุ่มสามารถเชื่อถือได้มากขึ้น และทำงานได้รวดเร็ว ไม่ต้องรออินเทอร์รัปต์หรือการพิมพ์จากผู้ใช้ ผู้ผลิตฮาร์ดแวร์หลายรายออกฮาร์ดแวร์สำหรับสุ่มค่าโดยเฉพาะ (การ์ดแพง แต่ผลลัพธ์มั่วมาก :/ ) โดยอาศัยแหล่งของค่าสุ่มจากฮาร์ดแวร์โดยตรง เช่น สัญญาณรบกวนจากภายนอก หรือความผิดเพี้ยนจากกระแสไฟฟ้า กระบวนการนี้ทำให้สามาารถสร้างค่าสุ่มที่มีคุณภาพดีได้อย่างรวดเร็ว ในซีพียูหลายรุ่นนั้นเริ่มมีการเพิ่มฮาร์ดแวร์ส่วนนี้เข้าไว้ในตัว เช่น อินเทลนั้นเพิ่มฮาร์ดแวร์ส่วนนี้ไว้ตั้งแต่ Ivy Bridge เป็นต้นมา ทำให้มีคำสั่ง RDRAND สามารถสั่งขอค่าสุ่มได้จากซีพียูได้ทันที

ในกระบวนการที่ต้องการสุ่มมากๆ เพราะกุญแจต้องใช้งานเป็นเวลานาน เช่น กุญแจสำหรับหน่วยงานรับรองกุญแจอื่นๆ (root CA) นั้น การเปลี่ยนกุญแจเป็นเรื่องยุ่งยากอย่างยิ่ง จึงต้องพยายามอย่างมากที่จะรับประกันว่ากระบวนการได้มาซึ่งค่าสุ่มนั้นสุ่มจริง กระบวนการสร้างค่าสุ่มของหน่วยงานเหล่านี้จึงต้องใช้คนถึงสามคนในการกดเมาส์และคีย์บอร์ดมั่วๆ เป็นระยะเวลาสูงสุดถึง 12 ชั่วโมง เพื่อเป็นต้นกำเนิดของค่าสุ่มที่จะมาเป็นกุญแจของหน่วยงานต่อไป เรียกกระบวนการนี้ว่า key ceremony

Pseudo Random Number Generator: สุ่มแบบคาดเดาได้

แม้เราจะค้นหาค่าสุ่มอย่างแท้จริงด้วยกระบวนการต่างๆ มาเป็นเวลานาน แต่ในงานหลายอย่างเราต้องการชุดของค่าที่ดูสุ่มแต่สามารถสร้างชุดของค่าสุ่มเช่นเดิมขึ้นมาได้ เราเรียกฟังก์ชั่นเช่นนี้ว่า pseudo random number generator (PRNG) โดยทั่วไปแล้ว PRNG เป็นฟังก์ชั่นที่เก็บสถานะของตัวเองไว้ภายใน เมื่อเริ่มจากสถานะเดิม สามารถให้ค่าที่ "ดูเหมือนค่าสุ่ม"

ในลินุกซ์นั้น นอกจากไฟล์ /dev/random ที่คืนค่ามาช้าแล้ว ยังมีไฟล์ /dev/urandom ที่สามารถคืนค่าได้อย่างรวดเร็ว เพราะอาศัยค่าสุ่มเริ่มต้นจากสภาพแวดล้อมเพียงครั้งเดียว แล้วค่าที่เหลือสามารถสร้างขึ้นมาจากการคำนวณจากสถานะภายใน

ระบบสุ่มในภาษาโปรแกรมหลายภาษามักมี PRNG อยู่ภายในเนื่องจากประสิทธิภาพดีกว่า โดยการเรียกฟังก์ชั่นสร้างสถานะภายใน เช่น random_seed จากนั้นการขอค่าสุ่มจะทำงานได้รวดเร็ว

ฟังก์ชั่น PRNG ทั่วไปนั้นจำเป็นต้องมีคุณสมบัติคือให้ผลที่กระจายไม่มีรูปแบบใดที่สังเกตได้ ไม่สามารถคาดเดาค่าก่อนหน้าหรือค่าต่อไปได้, ค่าต้องวนกลับมาซ้ำค่าเดิม (สถานะกลับสู่สถานะเดิม) ได้ช้ามาก สำหรับค่าการใช้งานเพื่อการเข้ารหัสนั้นต้องสามารถป้องกันไม่ให้ไม่ให้ใครรู้ค่า seed เริ่มต้นซึ่งมักเป็นกุญแจเข้ารหัสได้

PRNG ที่ได้ยินชื่อกันมากฟังก์ชั่นหนึ่ง คือ RC4 ที่ใช้งานในการเข้ารหัส Wi-Fi แบบ WEP ที่ปัจจุบัน RC4 มีคุณสมบัติทางการเข้ารหัสไม่แข็งแกร่งพอ ทำให้แฮกเกอร์สามารถดักฟังเฟรม Wi-Fi จำนวน 85,000 เฟรมก็สามารถถอดรหัสเอากุญแจออกมาได้ด้วยความน่าจะเป็นถึง 0.95

ถึงตอนนี้เวลามีใครสักคนบอกเราว่า "กินอะไรก็ได้ ง่ายๆ" แล้วเราพบว่าการจะเลือกอะไร "ง่ายๆ" นั้นยาก ก็อาจจะต้องนึกว่าในคอมพิวเตอร์นั้นก็ยากพอกัน

Blognone Jobs Premium