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

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

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

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

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

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

 แบบใช้แฮช 

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

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

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

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

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

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

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

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

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

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

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