Key stretching

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

มีวิธียืดกุญแจหลายอย่าง วิธีหนึ่งก็คือการใช้ฟังก์ชันแฮชเข้ารหัสลับ (cryptographic hash function) หรือบล็อกไซเฟอร์ (block cipher) โดยทำซ้ำ ๆ เป็นวง ยกตัวอย่างเช่นในไซเฟอร์ที่ใช้กุญแจ อาจจะเปลี่ยนขั้นตอนวิธีกำหนดรายการกุญแจของไซเฟอร์ให้ทำการเป็นเวลานานตามกำหนด หรือใช้ฟังก์ชันแฮชเข้ารหัสลับที่ต้องใช้ความจำมาก ซึ่งอาจได้ผลกับผู้โจมตีที่มีความจำจำกัด

กระบวนการ

การยืดกุญแจจะต้องอาศัยขั้นตอนวิธีที่ได้กุญแจดั้งเดิมเป็นอินพุตแล้วใช้ความพยายามมากเพื่อสร้างไซเฟอร์ที่เรียกว่า กุญแจเพิ่มสมรรถนะ (enhanced key)^[] เป็นกุญแจที่ยาวกว่าแต่ดูเหมือนกับเป็นเลขสุ่ม ขั้นตอนวิธีการยืดกุญแจนี้จะต้องไม่มีทางลัด ดังนั้น การเปลี่ยนอินพุตให้เป็นไซเฟอร์ที่ดีสุดก็คือการใช้ขั้นตอนวิธีเอง จึงทำให้ผู้โจมตีโดยใช้กำลังต้องใช้ความพยายามมากเท่า ๆ กันกับผู้ใช้สำหรับกุญแจที่ทดลองแต่ละตัว ถ้าความพยายามที่เพิ่มขึ้นเท่ากับการตรวจสอบหากุญแจที่มีขนาดหนึ่งโดยเฉพาะทุก ๆ ตัว ก็จะเรียกได้ว่ากุญแจดั้งเดิมได้ยืดให้ยาวขึ้นเท่ากับกุญแจขนาดเฉพาะนั้น

การยืดกุญแจจะทำให้ผู้โจมตีมีทางเลือกสองทาง คือ

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

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

กระบวนการนี้ไม่ได้เปลี่ยนเอนโทรปีของกุญแจดั้งเดิม การยืดกุญแจเป็นขั้นตอนวิธีเชิงกำหนด กุญแจขนาดเล็กตัวหนึ่งจะแปลงเป็นกุญแจขนาดใหญ่ตัวเดียวกันอย่างแน่นอน จริง ๆ จึงไม่ได้เพิ่มเอนโทรปีของกุญแจที่ได้ ดังนั้น จึงยังเสี่ยงต่อวิธีการโจมตีที่แลกเปลี่ยนเวลากับความจำ เช่นการใช้ฐานข้อมูล rainbow table ที่ใช้เก็บค่าแฮชซึ่งคำนวณล่วงหน้าคู่กับกุญแจดั้งเดิม แล้วใช่ค่าแฮชที่ขโมยได้เพื่อเทียบกับกุญแจคำนวณเแล้วดูค่ากุญแจดั้งเดิม ดังนั้น การยืดกุญแจจึงมักใช้ร่วมกับค่าซอลต์ (salt) ที่สร้างขึ้นโดยสุ่ม เมื่อค่าซอลต์มีขนาดใหญ่พอ การคำนวณค่าแฮชสำหรับค่าซอลต์ทุกค่าไว้ก่อนจึงทำไม่ได้

แบบใช้แฮช

คลังโปรแกรมหลายอย่างมีฟังก์ชันที่มีการยืดกุญแจ เช่น crypt (C) ส่วนฟังก์ชัน PBKDF2 ใช้สำหรับสร้างกุญแจเข้ารหัสลับจากรหัสผ่าน แต่อาจไม่ใช้ในการพิสูจน์ตัวจริงด้วยรหัสผ่าน อนึ่ง ก็ใช้ได้สำหรับทั้งสองอย่างเลยถ้าจำนวนบิตที่เอาต์พุตมีจำนวนน้อยกว่าหรือเท่ากับขั้นตอนวิธีการแฮชที่ใช้ภายใน ซึ่งปกติมักจะเป็น SHA-2 (มีได้มากสุดถึง 512 บิต)

ความแข็งแกร่งและเวลาที่ใช้

ตัวอย่างต่อไปนี้สมมุติว่าซีพียูที่ผู้บริโภคใช้สามารถคำนวณค่าแฮช SHA-1 ได้ 65,000 ค่า/วินาที ดังนั้น โปรแกรมที่ยืดกุญแจ 65,000 รอบก็จะชะลอผู้ใช้เพียงแค่วินาทีเดียว

ทั่วไปแล้วการทดสอบว่ารหัสผ่านหรือพาสเฟรซถูกต้องหรือไม่จะต้องคำนวณแฮชค่าเดียว แต่ถ้ายืดกุญแจ ผู้โจมตีก็จะต้องคำนวณค่ากุญแจเพิ่มสมรรถภาพสำหรับกุญแจทุกดอกที่ทดลอง ซึ่งหมายความว่าต้องคำนวณค่าแฮช 65,000 ค่า/ตัวกุญแจ ซึ่งเพิ่มงานที่ต้องทำถึง 65,000 เท่า (ราว ๆ 2¹⁶) ซึ่งก็หมายความว่า กุญแจเพิ่มสมรรถภาพเพิ่มความแข็งแกร่งของกุญแจดั้งเดิมได้ถึง 16 บิต

กฎของมัวร์ระบุว่าคอมพิวเตอร์จะเร็วขึ้นเป็นทวีคูณประมาณทุก ๆ สอง ปี ดังนั้น ทุก ๆ สองปี ผู้โจมตีก็จะสามารถเจาะกุญแจที่แข็งแกร่งเพิ่มขึ้นได้อีกหนึ่งบิต ซึ่งหมายความว่าความแข็งแกร่งเพิ่มขึ้น 16 บิตจะเพิ่มเวลาเจาะรหัสขึ้นถึง 16×2 = 32 ปี แต่ก็หมายความด้วยว่า จำนวนรอบที่ยืดกุญแจก็ควรเพิ่มเป็นทวีคูณทุก ๆ สองปีเพื่อให้ได้ความมั่นคงระดับเดียวกัน แต่กุญแจโดยมากก็มั่นคงเกินจำเป็น ดังนั้นระบบที่ต้องสร้างกุญแจอย่างกำหนดได้มักจะไม่อัปเดตจำนวนรอบในการยืดกุญแจ ในกรณีเช่นนี้ ผู้ออกแบบขั้นตอนวิธีควรพิจารณาว่า ระบบการแปลงรหัสให้เป็นกุญแจจะต้องใช้ได้นานแค่ไหนโดยที่ไม่เปลี่ยนจำนวนการแฮช แล้วเลือกจำนวนรอบการแฮชให้สมควรกับระยะเวลานั้น

ฟังก์ชันแฮชที่เน้นซีพียูยังอ่อนแอต่อการโจมตีด้วยฮาร์ดแวร์ที่ออกแบบมาโดยเฉพาะ เช่น มีการทำแฮช SHA-1 ให้เกิดผลโดยใช้ลอจิกเกตเพียง 5,000 ตัวโดยคำนวณได้ภายในรอบนาฬิกา 400 รอบเอฟพีจีเอเป็นล้าน ๆ ตัวมีราคาไม่เกิน 3,200 บาท ดังนั้น ผู้โจมตีสามารถสร้างเครื่องเจาะรหัสแบบไม่ดำเนินการเป็นวงโดยไม่เกิน 158,000 บาท^[] เมื่อใช้สัญญาณนาฬิกาที่ 100 MHz ก็จะสามารถทดสอบกุญแจได้ 300,000 ตัว/วินาที โดยอาจออกแบบสร้างเครื่องตามราคาโดยแลกเปลี่ยนกับความเร็ว เช่น ทำเครื่องที่สามารถเจาะได้ 150,000 ตัว/วินาทีแต่ในราคา 79,000 บาท^[] แต่การยืดกุญแจก็ยังชะลอการโจมตีเช่นนี้ได้ เช่น เครื่องที่ทดสอบกุญแจได้ 300,000 ตัว/วินาทีจะทดลองเหลือได้แค่ 300,000÷2¹⁶ ≈ 4.578 ตัว/วินาที^[]

อนึ่ง หน่วยประมวลผลกราฟิกส์ (จีพียู) ที่ผู้บริโภคใช้ในปัจจุบันก็สามารถทำให้คำนวณค่าแฮชได้เร็วขึ้นมาก เช่นจีพียูรุ่น Nvidia RTX 2080 SUPER FE สามารถคำนวณค่าแฮช SHA1 ได้หมื่นล้านตัว/วินาที

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

ประวัติ

ฟังก์ชันแปลงรหัสผ่านให้เป็นกุญแจที่ตั้งใจทำให้วิ่งช้าตัวแรกก็คือ crypt (3) ซึ่งนักวิทยาการเข้ารหัสลับชาวอเมริกัน รอเบิร์ต มอร์ริส ได้ทำเพื่อเก็บรหัสผ่านสำหรับระบบปฏิบัติการยูนิกซ์ ฟังก์ชันต้องคำนวณ 25 รอบโดยใช้ค่าซอลต์ขนาด 12 บิต และใช้การเข้ารหัสลับที่แปลงจากดีอีเอส จุดประสงค์ที่ไม่ใช้การเข้ารหัสลับของดีอีเอสโดยตรงก็เพื่อให้เป็นอุปสรรคแก่ฮาร์ดแวร์ที่ใช้เจาะดีอีเอส ในระบบนี้ รหัสผ่านจะมีตัวอักษรแอสกีได้แค่ 8 ตัว แม้จะเป็นวิธีการที่นำสมัยในเวลานั้น ฟังก์ชัน crypt (3) ปัจจุบันก็ถือว่าใช้ไม่ได้แล้ว เพราะการคำนวณซ้ำซึ่งออกแบบสำหรับคอมพิวเตอร์สมัย PDP-11 ก็น้อยเกินไป และค่าซอลต์ขนาดแค่ 12 บิตก็เพียงแต่น่ารำคาญและไม่สามารถป้องกันการโจมตีด้วยพจนานุกรมที่คำนวณค่าแฮชไว้ล่วงหน้าได้จริง ๆ

ฟังก์ชันแปลงรหัสผ่านให้เป็นกุญแจที่ใช้ในปัจจุบัน เช่น PBKDF2 จะใช้ฟังก์ชันแฮชเข้ารหัสลับต่าง ๆ เช่น SHA-2 มีค่าซอลต์ที่ใหญ่กว่า เช่น ขนาด 64 บิต และมีรอบคำนวณที่มากกว่า สถาบันมาตรฐานและเทคโนโลยีแห่งชาติสหรัฐฯ (NIST) แนะนำให้ใช้รอบคำนวณอย่างน้อยที่สุด 10,000 รอบโดยไม่ได้ระบุขั้นตอนวิธียืดกุญแจ^: 5.1.1.2 แต่มีคำเตือนเป็นข้อแม้ว่า "สำหรับกุญแจที่สำคัญอย่างวิกฤต หรือสำหรับระบบที่เร็วมาก หรือระบบที่ความรู้สึกว่าวิ่งช้าไม่สำคัญ การคำนวณรอบเป็นสิบล้านรอบอาจจะสมควร"^: 5.2

ในปี 2009 เริ่มมีขั้นตอนวิธีการยืดกุญแจที่ใช้ความจำมากคือ scrypt ซึ่งหมายป้องกันการถูกเจาะด้วยฮาร์ดแวร์ที่ออกแบบโดยเฉพาะและทำการขนานได้เป็นอย่างยิ่งเมื่อใช้เจาะกุญแจ ในปี 2013 มีการแข่งขันวิธีการแฮชรหัสผ่านเพื่อปรับปรุงมาตรฐานยืดกุญแจให้ทนต่อการโจมตีด้วยจีพียูและฮาร์ดแวร์ที่ออกแบบมาโดยเฉพาะ ๆ นักวิทยาการเข้ารหัสลับได้เลือก Argon2 เป็นมาตรฐานในปี 2015 ส่วนสถาบันมาตรฐานและเทคโนโลยีแห่งชาติสหรัฐ (NIST) แนะนำให้ใช้ขั้นตอนวิธี Balloon

ตัวอย่างระบบที่มีการยืดกุญแจ

• ซอฟต์แวร์เข้ารหัสลับดิสก์บางอย่าง เช่น veracrypt
• 7-Zip
• ไฟล์รหัสผ่านของอะแพชี เว็บเซิร์ฟเวอร์ คือ .htpasswd "APR1" และของโอเพนเอสเอสแอล คือ "passwd" ทั้งสองยืดรหัสผ่านด้วยเอ็มดี5 1,000 รอบ
• โปรแกรมจัดการรหัสผ่านเสรีและโอเพนซอร์ส คีย์พาสและคีย์พาสเอ็กซ์ซีรุ่นปี 2020 ใช้ขั้นตอนวิธียืดกุญแจ Argon2d โดยตั้งค่าเบื้องต้นให้ใช้เวลา 1 วินาที
• ลินุกซ์และระบบคล้ายยูนิกซ์มีทางเลือกเป็นโหมด SHAcrypt ที่คำนวณค่าแฮช SHA256 หรือ SHA512 จำนวน 5,000 รอบเป็นค่าตั้งต้น โดยสามารถตั้งค่าต่ำสุดเป็น 1,000 รอบและสูงสุดเป็น 999,999,999 รอบ
• โปรแกรมจัดการรหัสผ่านเสรีและโอเพนซอร์ส Password Safe
• ซอฟต์แวร์เข้ารหัสลับ PGP และ GPG โดยอย่างหลังคำนวณค่าแฮช 65,536 รอบเป็นค่าตั้งต้น
• โพรโทรคอลการเข้ารหัสลับของวายฟาย คือ Wi-Fi Protected Access รวมทั้งรุ่น WPA และ WPA2 ในโหมดส่วนตัว (personal mode) จะคำนวณค่าแฮช PBKDF2 4,096 รอบ ส่วน WPA3 ใช้โพรโทรคอล Simultaneous Authentication of Equals ซึ่งอ้างว่าไม่เปิดเผยค่าแฮชของรหัสผ่าน

ดูเพิ่ม

• ฟังก์ชันแปลงให้เป็นกุญแจ มักจะใช้วิธียืดกุญแจ
  • , , , เป็นขั้นตอนวิธียืดกุญแจที่ใช้กันอย่างแพร่หลาย

อ้างอิง

1. Kelsey, John; Schneier, Bruce; Hall, Chris; Wagner, David A. (1997). "Secure Applications of Low-Entropy Keys". ใน Okamoto, Eiji; Davida, George I.; Mambo, Masahiro (บ.ก.). Information Security, First International Workshop, ISW '97, Tatsunokuchi, Japan, September 17-19, 1997, Proceedings. Lecture Notes in Computer Science. Vol. 1396. Springer. pp. 121–134. doi:10.1007/BFb0030415. ISBN .
2. McMillan, Troy (2022-07-07). CompTIA Advanced Security Practitioner (CASP+) CAS-004 Cert Guide (ภาษาอังกฤษ). Pearson IT Certification. ISBN .
3. O'Neill, Máire. (PDF). คลังข้อมูลเก่าเก็บจากแหล่งเดิม (PDF)เมื่อ 2012-03-19.
4. . คลังข้อมูลเก่าเก็บจากแหล่งเดิมเมื่อ 2011-07-16. สืบค้นเมื่อ 2010-08-08.
5. https://gist.github.com/epixoip/47098d25f171ec1808b519615be1b90d , PBKDF2-HMAC-SHA1 with 1,000 iterations costs 2,002 SHA-1 hashes at a speed of 5,164.9 kH/s which comes to 10,340,129,800 SHA-1 hashes per second.
6. Morris, Robert; Thompson, Ken (1978-04-03). . Bell Laboratories. คลังข้อมูลเก่าเก็บจากแหล่งเดิมเมื่อ 2003-03-22. สืบค้นเมื่อ 2011-05-09.
7. Grassi, Paul A. (June 2017). SP 800-63B-3 - Digital Identity Guidelines, Authentication and Lifecycle Management. NIST. doi:10.6028/NIST.SP.800-63b.
8. Turan, Meltem Sönmez; Barker, Elaine; Burr, William; Chen, Lily (December 2010). SP 800-132 - Recommendation for Password-Based Key Derivation, Part 1: Storage Applications. NIST. doi:10.6028/NIST.SP.800-132.{{}}: CS1 maint: multiple names: authors list ()
9. Percival, Colin (2009). scrypt: A new key derivation function. BSDCan 2009. จากแหล่งเดิมเมื่อ 2024-06-29.
10. . คลังข้อมูลเก่าเก็บจากแหล่งเดิมเมื่อ 2013-09-02. สืบค้นเมื่อ 2013-03-03.
11. "NIST SP800-63B Section 5.1.1.2" (PDF). nvlpubs.nist.gov.
12. Password Hashing Competition
13. "Free Open source disk encryption with strong security for the Paranoid". VeraCrypt. จากแหล่งเดิมเมื่อ 2024-06-07. สืบค้นเมื่อ 2024-06-29.
14. "7z Format".
15. KBDF 4
16. KeePassXC—Creating Your First Database
17. Drepper, Ulrich. "Unix crypt using SHA-256 and SHA-512".
18. RFC 4880