กระบวนการถอดรหัส

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



ในบทความนี้เราจะยกตัวอย่างบางเทคนิคที่ใช้กันในการถอดรหัส

ความถี่ของข้อมูล (Frequency Counting)

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



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

กระบวนการนับความถี่อาศัยความจริงพื้นฐานว่าข้อมูลที่เราเข้ารหัสไปนั้น มักมีข้อมูลบางรูปแบบที่ใช้ซ้ำไปบ่อยกว่าข้อมูลแบบอื่นๆ ทุกวันนี้ แม้การใช้งานอินเทอร์เน็ตจะซับซ้อนกว่าตัวอักษร 26 ตัวอักษรแล้ว แต่รูปแบบการใช้งานยังคงคล้ายเดิมอย่างมาก เราจะพบว่าข้อความบางรูปแบบถูกใช้ซ้ำไปมา รูปแบบของการนับความถี่ในยุคใหม่พัฒนาไปจากเดิมมาก เนื่องจากการเข้ารหัสยุคใหม่ๆ นั้นไม่ปล่อยให้ข้อมูลที่เหมือนเดิมเข้ารหัสแล้วได้ข้อความเดิมอีกต่อไปแล้ว การนับความถี่อาจจะอาศัยข้อมูล เช่น ขนาดของข้อมูล, ระยะเวลาของห้วงการส่งข้อมูลแต่ละครั้ง (time interval) สิ่งเหล่านี้แม้ไม่ได้เปิดเผยข้อมูลภายในตัวมันเอง แต่สามารถนำไปสังเกตเพื่อหาข้อมูลเพิ่มเติมบางอย่างได้ เช่น ผู้ร้ายที่ดักฟังข้อมูลอยู่ อาจจะคาดเดาได้ว่ามีการเปิดหน้าเว็บใด แม้จะเชื่อมต่อ VPN ไว้ก็ตามที

Brute-Force

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

การโจมตีแบบ Brute-Force ที่สำคัญคือการโจมตีอัลกอริธึม DES ที่มีขนาดกุญแจ 56 บิต หลังจากที่ไอบีเอ็มได้ออกแบบให้ใช้กุญแจขนาด 112 บิตในตอนแรก และถูกร้องขอโดย NSA (เจ้าของเดียวกับ PRISM และ XKeyscore) ให้ลดขนาดกุญแจเหลือครึ่งเดียวโดย DES กลายเป็นมาตรฐานในปี 1975 และถูกใช้เข้ารหัสฐานข้อมูลจำนวนมาก ทั้งข้อมูลทางการเงิน, สมาร์ตการ์ด, และเอกสารลับของรัฐบาล

โดยตัวคุณสมบัติทางคณิตศาสตร์เอง DES ไม่ได้มีปัญหาอะไรมากนัก นอกจากขนาดกุญแจที่เล็กเกินไป และคอมพิวเตอร์มีความเร็วเพิ่มขึ้นอย่างรวดเร้ว ภายในเวลาเพียง 20 ปี DES ก็ถูกรหัสได้ภายในไม่กี่วันด้วยคอมพิวเตอร์เฉพาะทางราคา 220,000 ดอลลาร์ แสดงให้เห็นว่ามันอ่อนแอเกินไปที่จะรักษาข้อมูลที่มีมูลค่าสูง

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

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

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

Known Plaintext

การเข้ารหัสนั้นมักจะตั้งสมมติฐานว่าคนที่เราไม่ต้องการให้รู้ข้อความ นั้นไม่รู้ข้อความอยู่ก่อนหน้า (ไม่อย่างนั้นเราจะเข้ารหัสทำไม?) และไม่รู้กุญแจลับที่เราใช้เข้ารหัส แต่จะเกิดอะไรขึ้นถ้าผู้โจมตีกลับรับรู้ข้อความอยู่ก่อนแล้ว

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

ข้อความที่รู้อยู่ก่อนนั้นเกิดขึ้นได้ในหลายรูปแบบ ในกรณีของสงครามโลกครั้งที่สอง ทหารเยอรมันส่งข้อความที่ไม่สำคัญนักไปยังศูนย์กลางโดยการเข้ารหัสอื่นๆ นอกจาก enigma จากนั้นศูนย์จึงส่งกลับฐานทัพด้วย enigma อีกครั้ง ฝ่ายสัมพันธมิตรจึงสามารถรับรู้ข้อความก่อนและหลังเข้ารหัสด้วย enigma ได้

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

ปรากฎว่าในกรณีที่ผู้โจมตีรู้ข้อความอยู่ก่อน เขาสามารถสร้างข้อความในทุกกรณีด้วยกุญแจขนาด 56 บิต ได้คลังขนาด 2^56 กรณีเตรียมไว้ก่อนได้ และถอดรหัสข้อความที่เข้ารหัสแล้วด้วยกุญแจขนาด 56 บิตอีกรอบแล้วนำไปค้นดูในคลัง ว่ามีกุญแจที่รู้อยู่ก่อนแล้วหรือไม่ กระบวนการเช่นนี้ทำให้ความยุ่งยากของการคำนวณอยู่ในระดับ 2^57 ซึ่งไม่ดีกว่ากุญแจ DES เดิมมากนัก ชื่อเรียกเฉพาะของการโจมตีเช่นนี้เรียกว่า meet-in-the-middle attack

Padding Oracle: บางครั้งเซิร์ฟเวอร์ก็สร้างปัญหา

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





ในโหมดการเข้ารหัสแบบ block cipher ในโหมด CBC นั้นกำหนดให้ส่งค่าเริ่มต้นการเชื่อมต่อ (initial vector – IV) เป็นค่าสุ่มและส่งออกมาอย่างเปิดเผย จากนั้นจึงใช้ค่านี้ไป XOR กับข้อมูล “ก่อนเข้ารหัส” ในกระบวนการถอดรหัส และ “หลังถอดรหัส” ในกระบวนการถอดรหัส (ดูภาพ) จากนั้นจึงใช้ข้อความที่เข้ารหัสแล้ว ไปใช้ XOR เช่นเดิมกับบล็อคต่อๆ ไป กระบวนการนี้ทำให้ข้อความแม้จะเหมือนเดิม แต่หากค่า IV ต่างกันก็จะได้ข้อความที่ต่างกันไป

ในกระบวนการแบบ CBC นั้น โปรโตคอล TLS ระบุให้สามารถส่งข้อความยาวเท่าใดก็ได้โดยไม่ต้องสนใจขนาดบล็อคของแต่ละอัล กอลิทึม เนื่องจากแต่ละอัลกอลิทึมมีขนาดบล็อคต่างกันไป โดยเมื่อส่งข้อมูลทุกครั้ง จะต้องลงท้ายข้อมูล (padding) ด้วยข้อมูลที่ระบุว่ามีกี่ไบต์ที่ไม่ใช้งาน เช่น บล็อคขนาด 8 ไบต์ แต่ต้องการส่งข้อมูล 7 ไบต์ จะต้องส่งข้อมูลเป็น \x01 ต่อท้าย เช่น “\xAB\xAB\xAB\xAB\xAB\xAB\xAB\x01″ หรือแม้แต่ข้อมูลที่ขนาดเท่าบล็อคพอดีก็ต้องเพิ่มอีกหนึ่งบล็อคเป็นข้อมูล เติมเต็มเสมอ เช่น “\xAB\xAB\xAB\xAB\xAB\xAB\xAB\xAB\x08\x08\x08\x08\x08\x08\x08\x08″ เป็นข้อมูลในกรณีที่บล็อคเข้ารหัสมีขนาด 8 ไบต์และต้องการส่งข้อมูลขนาด 8 ไบต์พอดี

ในกรณีบล็อคแรกแม้ผู้โจมตีจะรู้เสมอว่าค่า IV และข้อมูลที่เข้ารหัสแล้วเป็นอะไร แต่เนื่องจากไม่รู้กุญแจการเข้าและถอดรหัส ทำให้ไม่รู้ค่าตรงกลางหลังจากข้อมูลถอดรหัสแล้ว ก่อนที่จะมา XOR กับค่า IV

กระบวนการเช่นนี้ใช้มานานและดูจะปลอดภัยดี จนกระทั่งพบว่าเซิร์ฟเวอร์จำนวนมาก มักส่งข้อความตอบกลับแจ้งว่าข้อมูลต่อท้ายนั้นผิดพลาด (invalid padding)

แทนที่จะโจมตีการเข้ารหัสโดยตรง ผู้โจมตี เลือกที่จะตัดเฉพาะบล็อคแรกออกมา แล้วส่งไปใหม่ 256 ครั้ง โดยเปลี่ยนไบต์สุดท้ายของค่า IV ให้มีค่าที่เป็นไปได้ทุกกรณีจำนวน 256 ค่า เกือบทุกค่าเซิร์ฟเวอร์จะแจ้งกลับว่าข้อมูลต่อท้ายนั้นผิดพลาดเสมอ ยกเว้นกรณีที่ไบต์สุดท้ายเป็นค่า \x01 พอดี ที่เซิร์ฟเวอร์จะตอบกลับว่าข้อมูลนี้ถูกต้องแล้ว (มีกรณีอื่นที่เซิร์ฟเวอร์ตอบถูกต้องเช่นกัน คือกรณีไบต์รองสุดท้าย เป็น \x02 พอดี และข้อมูลในไบต์สุดท้ายเป็น \x02 ด้วย แต่กรณีเหล่านั้นมีความเป็นไปได้น้อย และตัดออกได้ง่าย) การตอบว่าข้อมูลถูกต้อง ทำให้ผู้โจมตีรับรู้ได้ทันทีว่าค่าตรงกลางหลังการถอดรหัสแล้วคือค่าอะไร และเมื่อไปดูค่า IV ดั้งเดิมที่ถูกต้อง เขาก็รู้ได้เช่นกันว่าข้อความเดิมก่อนเข้ารหัสในไบต์สุดท้ายคืออะไร

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

Side-Channel Attack: มันไม่เกี่ยวทำให้เกี่ยวยังไงไหว

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

การใช้ขนาดของข้อมูลเป็นประเด็นสำคัญอย่างมากในช่วงหลัง เนื่องจากความซับซ้อนของโปรโตคอลอย่าง HTTP เริ่มมีมากขึ้นเรื่อยๆ มีการใช้มาตรฐานต่างๆ ประกอบกันมากมาย ในกระบวนการโจมตี CRIME อาศัยการบีบอัดข้อมูลของ TLS จากความสามารถของเบราว์เซอร์ที่เปิดให้เว็บหนึ่งๆ สามารถควบคุมเบราว์เซอร์ให้เรียกเว็บอื่นๆ ได้อย่างอิสระ พร้อมกับใส่ข้อมูลที่ต้องการเข้าไปได้ เว็บที่โจมตีเว็บอื่นด้วย CRIME จึงใส่ข้อมูลที่คาดว่าจะมีอยู่ในเนื้อหาของเว็บปลายทาง เช่น คำว่า “Cookie:” เข้าไปในข้อความที่เรียก แล้วดูผลลัพธ์ว่าขนาดผลลัพธ์มีขนาดเท่าใด จากนั้นจึงค่อยๆ เพิ่มทีละตัวอักษรว่าข้อมูลมีขนาดเพิ่มขึ้นหรือเท่าเดิม หากเท่าเดิมแสดงว่ากระบวนการบีบอัดข้อมูลทำงาน และตัวอักษรที่เพิ่มขึ้นนั้นถูกต้องดีแล้ว

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

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

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

ที่มา blognone

กระบวนการถอดรหัส

กระบวนการถอดรหัสที่มีอยู่ในโลกมากมายและถูกพัฒนาอย่างต่อเนื่องจน...
คอละคังดอทคอม
korelakung.com