รหัสแบบสตรีม

รหัสแบบสตรีม (Stream ciphers) เข้ารหัสข้อมูลโดยการสร้างคีย์สตรีมแบบสุ่มเทียม (pseudorandom keystream) จากคีย์ลับ และนำไปรวมกับข้อความธรรมดา (plaintext) โดยทั่วไปจะทำทีละบิตหรือไบต์ ซึ่งเลียนแบบการทำงานของวันไทม์แพด (one-time pad) ที่ปลอดภัยสมบูรณ์แบบด้วยคีย์สั้นๆ

Definition

รหัสแบบสตรีมคือระบบการเข้ารหัสแบบสมมาตร (symmetric encryption scheme) ที่สร้างคีย์สตรีมแบบสุ่มเทียมที่ยาวจากคีย์ลับ (และโดยปกติคือ nonce) และเข้ารหัสโดยการรวมคีย์สตรีมเข้ากับข้อความธรรมดา ซึ่งส่วนใหญ่ทำโดยการดำเนินการ XOR แบบบิตต่อบิต

Scope

หัวข้อนี้ครอบคลุมการออกแบบและการวิเคราะห์รหัสแบบสตรีม: ตัวสร้างคีย์สตรีมที่สร้างจากรีจิสเตอร์เลื่อนป้อนกลับเชิงเส้น (linear feedback shift registers), โครงสร้างตัวรวมและตัวกรอง (combiner and filter constructions), และการออกแบบที่เน้นซอฟต์แวร์สมัยใหม่ เช่น ChaCha20 และกลุ่มผลิตภัณฑ์ eSTREAM นอกจากนี้ยังกล่าวถึงความสัมพันธ์กับวันไทม์แพด ข้อกำหนดที่สำคัญคือห้ามนำคีย์สตรีมกลับมาใช้ซ้ำ และการโจมตีที่เกิดจากการนำคีย์สตรีมกลับมาใช้ซ้ำหรือตัวสร้างที่อ่อนแอ หัวข้อนี้ไม่รวมถึงรหัสบล็อก (block ciphers) แม้ว่ารหัสบล็อกในโหมดตัวนับ (counter mode) จะทำงานคล้ายกับรหัสแบบสตรีมก็ตาม

Core questions

• คีย์สั้นๆ สามารถยืดออกเป็นคีย์สตรีมที่ยาวและคาดเดาไม่ได้ซึ่งเลียนแบบวันไทม์แพดได้อย่างไร?
• เหตุใดการนำคีย์สตรีมกลับมาใช้ซ้ำจึงเป็นหายนะ และ nonce ป้องกันสิ่งนี้ได้อย่างไร?
• อะไรที่ทำให้ตัวสร้างคีย์สตรีมมีความแข็งแกร่งทางวิทยาการเข้ารหัสลับ แทนที่จะเป็นเพียงการสุ่มทางสถิติ?
• รหัสแบบสตรีมสมัยใหม่เช่น ChaCha20 บรรลุความเร็วได้อย่างไรโดยไม่ต้องใช้ฮาร์ดแวร์เฉพาะ?
• การโจมตีแบบคลาสสิก (การโจมตีแบบสหสัมพันธ์, การโจมตีแบบพีชคณิต) โจมตีการออกแบบที่อิงตาม LFSR ที่อ่อนแอได้อย่างไร?

Key concepts

• คีย์สตรีม
• วันไทม์แพด
• รีจิสเตอร์เลื่อนป้อนกลับเชิงเส้น
• nonce และเวกเตอร์เริ่มต้น
• การนำคีย์สตรีมกลับมาใช้ซ้ำ (วันไทม์แพดสองครั้ง)
• ChaCha20 และ Salsa20
• การโจมตีแบบสหสัมพันธ์
• รหัสแบบซิงโครนัสเทียบกับรหัสแบบซิงโครไนซ์ตัวเอง

Key theories

วันไทม์แพดและความลับที่สมบูรณ์แบบ

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

การสร้างคีย์สตรีมและการสุ่มเทียมทางวิทยาการเข้ารหัสลับ

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

Mechanisms

รหัสแบบสตรีมแบบซิงโครนัส (synchronous stream cipher) จะเริ่มต้นสถานะภายในจากคีย์และ nonce จากนั้นจะอัปเดตสถานะซ้ำๆ และส่งออกคีย์สตรีมโดยไม่ขึ้นกับข้อความธรรมดา คีย์สตรีมจะถูก XOR กับข้อความธรรมดาเพื่อเข้ารหัส และถูก XOR กับข้อความเข้ารหัส (ciphertext) เพื่อถอดรหัส การออกแบบที่อิงตามรีจิสเตอร์เลื่อนป้อนกลับเชิงเส้นนั้นรวดเร็วในฮาร์ดแวร์ แต่ต้องใช้ตัวรวมที่ไม่เป็นเชิงเส้น (nonlinear combiners) เพื่อต้านทานการโจมตีแบบพีชคณิต (algebraic attacks) ส่วนรหัสซอฟต์แวร์เช่น ChaCha20 ใช้การดำเนินการบวก-หมุน-XOR (ARX) บนสถานะขนาดใหญ่เพื่อความเร็วและความปลอดภัย

Clinical relevance

ChaCha20 (พร้อมตัวตรวจสอบความถูกต้อง Poly1305) ถูกนำไปใช้งานอย่างแพร่หลายใน TLS 1.3, OpenSSH, WireGuard และการส่งข้อความบนมือถือ ซึ่งเป็นที่นิยมมากกว่า AES ในอุปกรณ์ที่ไม่มีการเร่งความเร็ว AES ด้วยฮาร์ดแวร์ รหัสแบบสตรีมเหมาะสำหรับสื่อสตรีมมิ่งและการเชื่อมโยงที่มีความหน่วงต่ำ ในอดีต รหัสแบบสตรีม RC4 เคยปกป้อง SSL/TLS และ WEP Wi-Fi ในยุคแรกๆ จนกระทั่งข้อบกพร่องของมันนำไปสู่การเลิกใช้งาน

Evidence & guidelines

ChaCha20-Poly1305 ได้รับการกำหนดมาตรฐานใน RFC 8439 และได้รับการอนุมัติสำหรับ TLS ส่วน RC4 ถูกห้ามใช้ใน TLS โดย RFC 7465 เนื่องจากข้อบกพร่องของคีย์สตรีม โครงการ eSTREAM (2004-2008) ได้สร้างกลุ่มผลิตภัณฑ์รหัสแบบสตรีมที่ผ่านการตรวจสอบแล้ว กฎสำคัญในทุกมาตรฐานคือคู่ (คีย์, nonce) จะต้องไม่ถูกนำกลับมาใช้ซ้ำเด็ดขาด

History

รหัสแบบสตรีมมีต้นกำเนิดมาจากรหัส Vernam (1917) และวันไทม์แพด ระบบทางทหารในยุคสงครามเย็นใช้ตัวสร้างคีย์สตรีมที่อิงตามรีจิสเตอร์เลื่อน RC4 ซึ่งออกแบบโดย Ron Rivest ในปี 1987 ได้รับความนิยมอย่างแพร่หลาย แต่ในที่สุดก็ถูกเจาะได้ในการใช้งานโปรโตคอล การแข่งขัน eSTREAM และตระกูล Salsa20/ChaCha20 ของ Daniel Bernstein (2008) ได้กำหนดรหัสแบบสตรีมยุคใหม่ที่เป็นมิตรกับซอฟต์แวร์ ซึ่งเป็นที่นิยมในโปรโตคอลอินเทอร์เน็ตในปัจจุบัน

Key figures

• Claude Shannon
• Daniel J. Bernstein
• Ronald Rivest
• Adi Shamir

Seminal works

• shannon1949
• katz2020
• menezes1996

Frequently asked questions

จะเกิดอะไรขึ้นหากมีการนำคีย์สตรีมของรหัสแบบสตรีมกลับมาใช้ซ้ำ?

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

รหัสแบบสตรีมมีความปลอดภัยน้อยกว่ารหัสบล็อกหรือไม่?

ไม่จำเป็น รหัสแบบสตรีมสมัยใหม่เช่น ChaCha20 ถือว่ามีความปลอดภัยเท่ากับ AES และบางครั้งก็เร็วกว่าในซอฟต์แวร์ ความไม่ปลอดภัยเกิดจากการใช้งานที่ไม่ถูกต้อง (การนำคีย์สตรีมกลับมาใช้ซ้ำ) หรือการออกแบบเก่าที่อ่อนแอเช่น RC4 ไม่ใช่จากแนวคิดของรหัสแบบสตรีมเอง