อาร์ซี4
| ทั่วไป | |
|---|---|
| นักออกแบบ | รอน ริเวสต์ ( RSA Security ) |
| เผยแพร่ครั้งแรก | ข้อมูลรั่วไหลในปี 1994 (ออกแบบในปี 1987) |
| รายละเอียดรหัสลับ | |
| ขนาดกุญแจ | 40–2048บิต |
| ขนาดของรัฐ | 2064บิต ((มีผลบังคับใช้ ในปี ค.ศ. 1684 ) |
| รอบ | 1 |
| ความเร็ว | 7 รอบต่อไบต์บนPentium ดั้งเดิม[ 1 ] RC4 ที่แก้ไขแล้วบน Intel Core 2: 13.9 รอบต่อไบต์[ 2 ] |
ในด้านการเข้ารหัส RC4 (หรือที่รู้จักกันในชื่อARC4หรือARCFOURซึ่งหมายถึง Alleged RC4 ดูด้านล่าง) เป็นการเข้ารหัสแบบสตรีมแม้ว่าจะโดดเด่นในด้านความเรียบง่ายและความเร็วในการทำงานของซอฟต์แวร์ แต่ก็มีการค้นพบช่องโหว่หลายประการใน RC4 ทำให้มันไม่ปลอดภัย[ 3 ] [ 4 ]โดยเฉพาะอย่างยิ่งมันจะมีความเสี่ยงเมื่อไม่ได้ทิ้งส่วนเริ่มต้นของคีย์สตรีม เอาต์พุต หรือเมื่อใช้คีย์ที่ไม่สุ่มหรือคีย์ที่เกี่ยวข้อง การใช้งาน RC4 ที่มีปัญหาเป็นพิเศษได้นำไปสู่โปรโตคอล ที่ไม่ปลอดภัย เช่น โปรโตคอล WEP ที่ล้าสมัย ซึ่งเคยใช้ในการรักษาความปลอดภัยเครือข่าย WiFi ในอดีต[ 5 ]
มีการคาดการณ์กันมานานแล้วว่าหน่วยงานเข้ารหัสลับของรัฐบางแห่งอาจมีความสามารถในการถอดรหัส RC4 เมื่อใช้ในโปรโตคอลTLS [ 6 ]เพื่อเป็นการตอบสนองIETFได้เผยแพร่RFC 7465เพื่อห้ามการใช้ RC4 ใน TLS [ 3 ] MozillaและMicrosoftได้ออกคำแนะนำที่คล้ายกัน[ 7 ] [ 8 ]
มีการพยายามหลายครั้งเพื่อเสริมความแข็งแกร่งให้กับ RC4 โดยเฉพาะอย่างยิ่ง Spritz, RC4A, VMPCและRC4 +
ประวัติศาสตร์
RC4 เป็นรหัสสตรีมที่ออกแบบโดยRonald Rivestแห่งRSA Securityในปี 1987 ตามที่ Rivest กล่าว ตัวอักษร RC ย่อมาจาก "Ron's Code" [ 9 ]แม้ว่าโดยทั่วไปจะเรียกกันง่ายๆ ว่า RC4 ก็ตาม หลักการตั้งชื่อเดียวกันนี้ใช้กับ RC2, RC5 และ RC6 ด้วย
RC4 เดิมทีเป็นความลับทางการค้าแต่ในเดือนกันยายน พ.ศ. 2537 มีการโพสต์คำอธิบายลงในรายชื่อผู้รับจดหมายCypherpunks โดยไม่ระบุชื่อ [ 10 ]ไม่นานนักก็มีการโพสต์ลงในกลุ่มข่าวsci.crypt ซึ่ง Bob Jenkins สามารถถอดรหัสได้ภายในไม่กี่วัน[ 11 ]จากนั้นก็แพร่กระจายไปยังเว็บไซต์ต่างๆ บนอินเทอร์เน็ตรหัสที่รั่วไหลได้รับการยืนยันว่าเป็นของแท้เนื่องจากพบว่าผลลัพธ์ตรงกับซอฟต์แวร์ที่เป็นกรรมสิทธิ์ที่ใช้ RC4 ที่ได้รับอนุญาตเนื่องจากอัลกอริทึมเป็นที่รู้จักแล้ว จึงไม่ถือเป็นความลับทางการค้าอีกต่อไปชื่อRC4ได้รับการจดทะเบียนเครื่องหมายการค้า ดังนั้น RC4 จึงมักถูกเรียกว่าARCFOURหรือARC4 (ซึ่งหมายถึงRC4 ที่ถูกกล่าวหา ) [ 12 ]เพื่อหลีกเลี่ยงปัญหาเรื่องเครื่องหมายการค้าRSA Securityไม่เคยเผยแพร่อัลกอริทึมอย่างเป็นทางการ อย่างไรก็ตาม Rivest ได้เชื่อมโยงไปยัง บทความ Wikipedia ภาษาอังกฤษเกี่ยวกับ RC4 ในบันทึกย่อของหลักสูตรของเขาเองในปี พ.ศ. 2551 [ 13 ]และยืนยันประวัติของ RC4 และรหัสในเอกสารปี พ.ศ. 2557 [ 14 ]
RC4 กลายเป็นส่วนหนึ่งของโปรโตคอลและมาตรฐานการเข้ารหัสที่ใช้กันทั่วไป เช่นWEPในปี 1997 และWPAในปี 2003/2004 สำหรับการ์ดไร้สาย และSSL ในปี 1995 และ TLSซึ่งเป็นรุ่นต่อจาก SSL ในปี 1999 จนกระทั่งถูกห้ามใช้ใน TLS ทุกเวอร์ชันในปี 2015 โดยRFC 7465เนื่องจากการโจมตี RC4ทำให้ RC4 ที่ใช้ใน SSL/TLS อ่อนแอลงหรือใช้งานไม่ได้ ปัจจัยหลักที่ทำให้ RC4 ประสบความสำเร็จในแอปพลิเคชันที่หลากหลายคือความเร็วและความเรียบง่าย การใช้งานที่มีประสิทธิภาพทั้งในซอฟต์แวร์และฮาร์ดแวร์นั้นพัฒนาได้ง่ายมาก
คำอธิบาย
RC4 สร้างกระแสบิตแบบสุ่มเทียม ( กระแสคีย์ ) เช่นเดียวกับการเข้ารหัสแบบกระแสข้อมูลอื่นๆ กระแสคีย์เหล่านี้สามารถใช้ในการเข้ารหัสโดยการรวมเข้ากับข้อความต้นฉบับโดยใช้การดำเนินการแบบExclusive OR ระดับบิต การถอดรหัสก็ทำในลักษณะเดียวกัน (เนื่องจากการดำเนินการ Exclusive OR กับข้อมูลที่กำหนดเป็นการดำเนินการแบบผกผัน ) วิธีนี้คล้ายกับOne-Time Padแต่ ใช้ บิตแบบสุ่มเทียม ที่สร้างขึ้น แทนที่จะใช้กระแสข้อมูลที่เตรียมไว้ล่วงหน้า
ในการสร้างคีย์สตรีม ระบบเข้ารหัสจะใช้สถานะภายในที่เป็นความลับซึ่งประกอบด้วยสองส่วน:
- การเรียงสับเปลี่ยน ของ ไบต์ที่เป็นไปได้ทั้งหมด 256 ไบต์ (โดยใช้สัญลักษณ์ "S" ด้านล่าง)
- ตัวชี้ดัชนี 8 บิตสองตัว (ระบุด้วย "i" และ "j")
การเรียงสับเปลี่ยนเริ่มต้นด้วยคีย์ ที่มีความยาวแปรผันได้ โดยทั่วไปอยู่ระหว่าง 40 ถึง 2048 บิต โดยใช้ อัลกอริธึม การจัดตารางคีย์ (KSA) เมื่อเสร็จสิ้นขั้นตอนนี้แล้ว กระแสของบิตจะถูกสร้างขึ้นโดยใช้อัลกอริธึมการสร้างเลขสุ่มเทียม (PRGA)
อัลกอริทึมการจัดตารางคีย์ (KSA)
อั ลกอริทึม การจัดตารางคีย์ใช้เพื่อเริ่มต้นการเรียงสับเปลี่ยนในอาร์เรย์ "S" "ความยาวคีย์" ถูกกำหนดให้เป็นจำนวนไบต์ในคีย์และสามารถอยู่ในช่วง 1 ≤ ความยาวคีย์ ≤ 256 โดยทั่วไปจะอยู่ระหว่าง 5 ถึง 16 ซึ่งสอดคล้องกับความยาวคีย์ 40–128 บิต ขั้นแรก อาร์เรย์ "S" จะถูกเริ่มต้นด้วยการเรียงสับเปลี่ยนเอกลักษณ์จากนั้น S จะถูกประมวลผลเป็น 256 รอบในลักษณะเดียวกับ PRGA หลัก แต่ยังมีการผสมไบต์ของคีย์เข้าไปพร้อมกันด้วย โปรดทราบว่าคีย์ที่แตกต่างกันหลายแบบ เช่น 'Text' และ 'TextText' จะนำไปสู่การเข้ารหัสแบบเดียวกัน
สำหรับ i ตั้งแต่ 0 ถึง 255 S[i] := i สิ้นสุดสำหรับ j := 0 สำหรับ i ตั้งแต่ 0 ถึง 255 j := (j + S[i] + key[i mod keylength]) mod 256 สลับค่าของ S[i] และ S[j] สิ้นสุดสำหรับ
อัลกอริทึมการสร้างเลขสุ่มเทียม (PRGA)

PRGA จะทำการปรับเปลี่ยนสถานะและส่งออกไบต์ของคีย์สตรีมไปเรื่อยๆ จนกว่าจะครบจำนวนรอบที่จำเป็น ในแต่ละรอบ PRGA จะดำเนินการดังนี้:
- เพิ่มขึ้นทีละi ;
- ค้นหา องค์ประกอบที่ iของS , S[ i ]และเพิ่มองค์ประกอบนั้นลงในj ;
- สลับค่าของS[ i ]และS[ j ]จากนั้นใช้ผลรวมS[ i ] + S[ j ] (โมดูลัส 256)เป็นดัชนีเพื่อดึงองค์ประกอบที่สามของS (ค่าคีย์สตรีมKด้านล่าง)
- จากนั้นจึงทำการ XORแบบบิตwise กับไบต์ถัดไปของข้อความ เพื่อสร้างไบต์ถัดไปของข้อความที่เข้ารหัสหรือข้อความธรรมดา
แต่ละองค์ประกอบของ S จะถูกสลับกับองค์ประกอบอื่นอย่างน้อยหนึ่งครั้งทุกๆ 256 รอบการทำซ้ำ
i := 0 j := 0 ขณะสร้างเอาต์พุต: i := (i + 1) mod 256 j := (j + S[i]) mod 256 สลับค่าของ S[i] และ S[j] t := (S[i] + S[j]) mod 256 K := S[t] เอาต์พุต K จบในขณะที่
ดังนั้น สิ่งนี้จะสร้างกระแสของK[0], K[1], ...ซึ่งจะถูก XORกับข้อความต้นฉบับเพื่อรับข้อความเข้ารหัสดังนั้นciphertext[ l ] = plaintext[ l ] ⊕ K [ l ]
เครื่องกำเนิดเลขสุ่มแบบ RC4
ระบบปฏิบัติการหลาย ระบบ มีarc4randomAPI ที่มาจากOpenBSDซึ่งให้การเข้าถึงตัวสร้างเลขสุ่มที่เดิมทีใช้ RC4 API นี้ไม่อนุญาตให้มีการกำหนดค่าเริ่มต้น เนื่องจากฟังก์ชันจะเริ่มต้นตัวเองโดยใช้/dev/randomการใช้ RC4 ได้ถูกยกเลิกในระบบส่วนใหญ่ที่ใช้งาน API นี้แล้วหน้าคู่มือสำหรับ arc4random ใหม่มีคำย่อว่า "A Replacement Call for Random" สำหรับ ARC4 เป็นตัวช่วยในการจำ เนื่องจากให้ข้อมูลสุ่มที่ดีกว่า ฟังก์ชัน rand() เดิมซึ่งมีความไม่ปลอดภัยสูง โดยใช้ตัวสร้างเลขสุ่มเทียมเชิงเส้นแบบ congruentialที่มีสถานะภายใน 32 บิต[ 15 ] [ 16 ] [ 17 ]
การโจมตี RC4 หลายครั้งสามารถแยกแยะเอาต์พุตออกจากลำดับสุ่มได้[ 18 ]ส่งผลให้การใช้ ARC4 arc4randomถูกแทนที่ด้วยตัวสร้างเลขสุ่มเทียมที่ดีกว่าในที่สุด:
- ใน OpenBSD 5.5 ซึ่งวางจำหน่ายในเดือนพฤษภาคม 2014
arc4randomได้รับการแก้ไขให้ใช้การเข้ารหัสสตรีมที่เหนือกว่าChaCha20 [ 19 ] [ 20 ] การใช้งาน arc4random ในFreeBSDและNetBSD [ 21 ] [ 22 ]ก็ใช้ ChaCha20 เช่นกัน - โดยทั่วไป Linux ใช้glibcซึ่งไม่มีarc4randomจนกระทั่งปี 2022 แต่ไลบรารีแยกต่างหากอย่าง libbsd นั้นมีฟังก์ชันดังกล่าว โดยได้รับการอัปเดตให้ใช้ ChaCha20 ในปี 2016 [ 23 ]ในปี 2022 glibc ได้เพิ่ม arc4randomเวอร์ชันของตัวเองซึ่งใช้ ChaCha20 เช่นกัน[ 24 ]
- จากข้อมูลในคู่มือที่มาพร้อมกับระบบปฏิบัติการ ใน ระบบปฏิบัติการ macOSและiOS เวอร์ชันปี 2017 Apple ได้เปลี่ยนจาก RC4 เป็น AES ในการใช้งาน arc4random
เครื่องกำเนิดเลขสุ่มแบบใหม่ที่เสนอมักจะถูกเปรียบเทียบกับเครื่องกำเนิดเลขสุ่ม RC4 [ 25 ] [ 26 ]
การดำเนินการ
อัลกอริทึมการเข้ารหัสแบบสตรีมจำนวนมากใช้รีจิสเตอร์เลื่อนป้อนกลับเชิงเส้น (LFSR) ซึ่งแม้จะมีประสิทธิภาพในฮาร์ดแวร์ แต่ก็มีประสิทธิภาพน้อยกว่าในซอฟต์แวร์ การออกแบบ RC4 หลีกเลี่ยงการใช้ LFSR และเหมาะอย่างยิ่งสำหรับการใช้งานในซอฟต์แวร์ เนื่องจากต้องการเพียงการจัดการไบต์เท่านั้น โดยใช้หน่วยความจำ 256 ไบต์สำหรับอาร์เรย์สถานะ S[0] ถึง S[255] หน่วยความจำ k ไบต์สำหรับคีย์ key[0] ถึง key[k−1] และตัวแปรจำนวนเต็ม i, j และ K การลดค่าแบบโมดูลัสของค่าบางค่าโมดูลัส 256 สามารถทำได้โดยใช้การดำเนินการ AND แบบบิตกับ 255 (ซึ่งเทียบเท่ากับการเลือกไบต์ที่มีลำดับต่ำสุดของค่าดังกล่าว)
เวกเตอร์ทดสอบ
เวกเตอร์ทดสอบเหล่านี้ไม่ใช่เวกเตอร์อย่างเป็นทางการ แต่สะดวกสำหรับผู้ที่ต้องการทดสอบโปรแกรม RC4 ของตนเอง คีย์และข้อความต้นฉบับเป็นASCIIส่วนคีย์สตรีมและข้อความที่เข้ารหัสแล้วเป็นเลขฐานสิบหก
| สำคัญ | คีย์สตรีม | ข้อความธรรมดา | ข้อความเข้ารหัส |
|---|---|---|---|
| สำคัญ | EB9F7781B734CA72A719 ... | ข้อความธรรมดา | BBF316E8D940AF0AD3 |
| วิกิ | 6044DB6D41B7 ... | พีเดีย | 1021BF0420 |
| ความลับ | 04D46B053CA87B59 ... | โจมตีตอนรุ่งสาง | 45A01F645FC35B383552544B9BF5 |
ความปลอดภัย
ต่างจากการเข้ารหัสแบบสตรีมสมัยใหม่ (เช่นeSTREAM ) RC4 ไม่ได้ใช้nonce แยกต่างหาก ควบคู่ไปกับคีย์ ซึ่งหมายความว่าหากจะใช้คีย์ระยะยาวเพียงคีย์เดียวในการเข้ารหัสสตรีมหลายรายการอย่างปลอดภัย โปรโตคอลจะต้องระบุวิธีการรวม nonce และคีย์ระยะยาวเพื่อสร้างคีย์สตรีมสำหรับ RC4 แนวทางหนึ่งในการแก้ไขปัญหานี้คือการสร้างคีย์ RC4 "ใหม่" โดยการแฮชคีย์ระยะยาวด้วยnonce อย่างไรก็ตาม แอปพลิเคชันจำนวนมากที่ใช้ RC4 เพียงแค่รวมคีย์และ nonce เข้าด้วยกัน ตารางคีย์ที่อ่อนแอของ RC4 จึงทำให้เกิดการโจมตีด้วยคีย์ที่เกี่ยวข้องเช่นการโจมตี Fluhrer, Mantin และ Shamir (ซึ่งมีชื่อเสียงในการทำลาย มาตรฐาน WEP ) [ 27 ]
เนื่องจาก RC4 เป็นการเข้ารหัสแบบสตรีมจึงมีความยืดหยุ่น มากกว่า การเข้ารหัสแบบบล็อกทั่วไปหากไม่ได้ใช้ร่วมกับรหัสยืนยันข้อความ (MAC) ที่แข็งแกร่ง การเข้ารหัสจะมีความเสี่ยงต่อการโจมตีแบบพลิกบิตการเข้ารหัสนี้ยังมีความเสี่ยงต่อการโจมตีแบบเข้ารหัสแบบสตรีมหากไม่ได้นำไปใช้อย่างถูกต้อง[ 28 ]
อย่างไรก็ตาม เป็นที่น่าสังเกตว่า RC4 ซึ่งเป็นการเข้ารหัสแบบสตรีมนั้น ในช่วงเวลาหนึ่งเป็นการเข้ารหัสทั่วไปเพียงตัวเดียวที่ไม่ได้รับผลกระทบ[ 29 ]จากการโจมตี BEAST ในปี 2011 บนTLS 1.0การโจมตีนี้ใช้ประโยชน์จากจุดอ่อนที่ทราบกันดีในวิธี การใช้ โหมดการเชื่อมโยงบล็อกการเข้ารหัสกับการเข้ารหัสอื่นๆ ทั้งหมดที่รองรับโดย TLS 1.0 ซึ่งล้วนเป็นการเข้ารหัสแบบบล็อก
ในเดือนมีนาคม พ.ศ. 2556 มีการเสนอสถานการณ์การโจมตีใหม่โดย Isobe, Ohigashi, Watanabe และ Morii [ 30 ]รวมถึง AlFardan, Bernstein, Paterson, Poettering และ Schuldt ที่ใช้อคติทางสถิติใหม่ในตารางคีย์ RC4 [ 31 ]เพื่อกู้คืนข้อความธรรมดาด้วยการเข้ารหัส TLS จำนวนมาก[ 32 ] [ 33 ]
การใช้ RC4 ใน TLS นั้นถูกห้ามโดย RFC 7465 ซึ่งเผยแพร่ในเดือนกุมภาพันธ์ 2015
อคติของรูสและการสร้างใหม่ที่สำคัญจากการเรียงสับเปลี่ยน
ในปี พ.ศ. 2538 แอนดรูว์ รูส สังเกตจากการทดลองว่าไบต์แรกของคีย์สตรีมมีความสัมพันธ์กับไบต์สามไบต์แรกของคีย์ และไบต์ไม่กี่ไบต์แรกของการเรียงสับเปลี่ยนหลังจาก KSA มีความสัมพันธ์กับผลรวมเชิงเส้นบางอย่างของไบต์คีย์[ 34 ]อคติเหล่านี้ยังคงไม่ได้รับการอธิบายจนกระทั่งปี พ.ศ. 2550 เมื่อกูตัม พอล สิดเดชวาร์ ราธี และสุภามอย ไมตรา[ 35 ]พิสูจน์ความสัมพันธ์ระหว่างคีย์สตรีมกับคีย์ และในงานอื่น กูตัม พอล และสุภามอย ไมตรา[ 36 ]พิสูจน์ความสัมพันธ์ระหว่างการเรียงสับเปลี่ยนกับคีย์ งานหลังนี้ยังใช้ความสัมพันธ์ระหว่างการเรียงสับเปลี่ยนกับคีย์เพื่อออกแบบอัลกอริทึมแรกสำหรับการสร้างคีย์ขึ้นใหม่อย่างสมบูรณ์จากการเรียงสับเปลี่ยนขั้นสุดท้ายหลังจาก KSA โดยไม่มีข้อสมมติใดๆ เกี่ยวกับคีย์หรือเวกเตอร์เริ่มต้นอัลกอริทึมนี้มีความน่าจะเป็นของความสำเร็จคงที่ในช่วงเวลา ซึ่งเป็นรากที่สองของความซับซ้อนของการค้นหาคีย์แบบครบถ้วน ต่อมา มีการดำเนินการวิจัยอื่นๆ อีกมากมายเกี่ยวกับการสร้างคีย์ขึ้นใหม่จากสถานะภายใน RC4 [ 37 ] [ 38 ] [ 39 ] Subhamoy Maitra และ Goutam Paul [ 40 ]ยังแสดงให้เห็นว่าอคติแบบ Roos ยังคงมีอยู่แม้ว่าจะพิจารณาดัชนีการเรียงสับเปลี่ยนแบบซ้อนกัน เช่นS[S[i]]หรือS[S[S[i]]]อคติประเภทนี้ถูกนำมาใช้ในวิธีการสร้างคีย์ขึ้นใหม่บางวิธีในภายหลังเพื่อเพิ่มโอกาสความสำเร็จ
เอาต์พุตที่มีอคติของ RC4
คีย์สตรีมที่สร้างโดย RC4 มีแนวโน้มไปทางลำดับบางอย่างในระดับที่แตกต่างกัน ทำให้มีความเสี่ยงต่อการโจมตีแบบแยกแยะ การโจมตีที่ดีที่สุดดังกล่าวมาจาก Itsik Mantin และAdi Shamirซึ่งแสดงให้เห็นว่าไบต์เอาต์พุตที่สองของรหัสมีแนวโน้มไปทางศูนย์ด้วยความน่าจะเป็น 1/128 (แทนที่จะเป็น 1/256) ทั้งนี้เนื่องจากข้อเท็จจริงที่ว่าหากไบต์ที่สามของสถานะดั้งเดิมเป็นศูนย์ และไบต์ที่สองไม่เท่ากับ 2 ไบต์เอาต์พุตที่สองจะเป็นศูนย์เสมอ แนวโน้มดังกล่าวสามารถตรวจพบได้โดยการสังเกตเพียง 256 ไบต์[ 18 ]
Souradyuti PaulและBart PreneelจากCOSICแสดงให้เห็นว่าไบต์แรกและไบต์ที่สองของ RC4 ก็มีอคติเช่นกัน จำนวนตัวอย่างที่จำเป็นในการตรวจจับอคตินี้คือ 2 25 ไบต์[ 41 ]
Scott Fluhrerและ David McGrew ยังแสดงการโจมตีที่แยกแยะคีย์สตรีมของ RC4 ออกจากสตรีมแบบสุ่มเมื่อให้เอาต์พุตขนาด 1 กิกะไบต์[ 42 ]
การกำหนดลักษณะที่สมบูรณ์ของขั้นตอนเดียวของ RC4 PRGA ได้รับการดำเนินการโดย Riddhipratim Basu, Shirshendu Ganguly, Subhamoy Maitra และ Goutam Paul [ 43 ]เมื่อพิจารณาการเรียงสับเปลี่ยนทั้งหมด พวกเขาพิสูจน์ว่าการกระจายของเอาต์พุตไม่สม่ำเสมอเมื่อกำหนด i และ j และเป็นผลให้ข้อมูลเกี่ยวกับ j รั่วไหลไปยังเอาต์พุตเสมอ
การโจมตีของ Fluhrer, Mantin และ Shamir
ในปี 2001 Fluhrer , MantinและShamirได้ค้นพบสิ่งใหม่ที่น่าประหลาดใจ: ในบรรดาคีย์ RC4 ที่เป็นไปได้ทั้งหมด สถิติของไบต์แรกๆ ของคีย์สตรีมเอาต์พุตนั้นไม่เป็นแบบสุ่มอย่างมาก ทำให้ข้อมูลเกี่ยวกับคีย์รั่วไหล หากนำค่า nonce และคีย์ระยะยาวมาต่อกันเพื่อสร้างคีย์ RC4 คีย์ระยะยาวนี้สามารถค้นพบได้โดยการวิเคราะห์ข้อความจำนวนมากที่เข้ารหัสด้วยคีย์นี้[ 44 ]ผลกระทบนี้และผลกระทบที่เกี่ยวข้องถูกนำมาใช้เพื่อทำลาย การเข้ารหัส WEP ("wired equivalent privacy") ที่ใช้กับเครือข่ายไร้สาย802.11 ซึ่งทำให้เกิดการแข่งขันเพื่อหามาตรฐานทดแทน WEP ในตลาด 802.11 และนำไปสู่ ความพยายาม ของIEEE 802.11iและWPA [ 45 ]
โปรโตคอลสามารถป้องกันการโจมตีนี้ได้โดยการทิ้งส่วนเริ่มต้นของคีย์สตรีม อัลกอริทึมที่แก้ไขแล้วนี้เรียกว่า "RC4-drop[ n ]" โดยที่nคือจำนวนไบต์คีย์สตรีมเริ่มต้นที่ถูกทิ้ง ค่าเริ่มต้นของ SCAN คือn = 768 ไบต์ แต่ค่าที่ระมัดระวังคือn = 3072 ไบต์[ 46 ]
การโจมตีของ Fluhrer, Mantin และ Shamir ไม่สามารถนำไปใช้กับ SSL ที่ใช้ RC4 ได้ เนื่องจาก SSL สร้างคีย์การเข้ารหัสที่ใช้สำหรับ RC4 โดยการแฮช ซึ่งหมายความว่าเซสชัน SSL ที่แตกต่างกันจะมีคีย์ที่ไม่เกี่ยวข้องกัน[ 47 ]
การโจมตีของไคลน์
ในปี 2548 Andreas Klein ได้นำเสนอการวิเคราะห์การเข้ารหัสแบบสตรีม RC4 ซึ่งแสดงให้เห็นถึงความสัมพันธ์ที่มากขึ้นระหว่างคีย์สตรีม RC4 และคีย์[ 48 ] Erik Tews , Ralf-Philipp WeinmannและAndrei Pychkineได้ใช้การวิเคราะห์นี้เพื่อสร้าง aircrack-ptw ซึ่งเป็นเครื่องมือที่สามารถถอดรหัส RC4 104 บิตที่ใช้ใน WEP 128 บิตได้ภายในเวลาไม่ถึงนาที[ 49 ]ในขณะที่การโจมตีของ Fluhrer, Mantin และ Shamir ใช้ข้อความประมาณ 10 ล้านข้อความ แต่ aircrack-ptw สามารถถอดรหัสคีย์ 104 บิตได้ใน 40,000 เฟรมด้วยความน่าจะเป็น 50% หรือใน 85,000 เฟรมด้วยความน่าจะเป็น 95%
ปัญหาเชิงการจัดเรียง
ปัญหาเชิงการจัดเรียงที่เกี่ยวข้องกับจำนวนอินพุตและเอาต์พุตของการเข้ารหัส RC4 ถูกตั้งขึ้นครั้งแรกโดยItsik MantinและAdi Shamirในปี 2544 โดยที่จากองค์ประกอบทั้งหมด 256 รายการในสถานะปกติของ RC4 หาก ทราบเพียง xจำนวนองค์ประกอบ ( x ≤ 256) เท่านั้น (สามารถถือว่าองค์ประกอบอื่นๆ ว่างเปล่า) จำนวนองค์ประกอบสูงสุดที่สามารถสร้างขึ้นได้อย่างแน่นอนก็คือxใน 256 รอบถัดไป ข้อสันนิษฐานนี้ถูกยุติลงในปี 2547 ด้วยการพิสูจน์อย่างเป็นทางการโดยSouradyuti PaulและBart Preneel [ 50 ]
การโจมตีรอยัลฮอลโลเวย์
ในปี 2556 กลุ่มนักวิจัยด้านความปลอดภัยที่ Information Security Group ที่Royal Holloway มหาวิทยาลัยลอนดอนรายงานการโจมตีที่สามารถมีประสิทธิภาพได้โดยใช้ข้อความที่เข้ารหัสเพียง 2³⁴ ข้อความ [ 51 ] [ 52 ] [ 53 ] แม้ว่าผลลัพธ์นี้ยังไม่ใช่การโจมตีที่ใช้งานได้จริงสำหรับวัตถุประสงค์ส่วนใหญ่ แต่ก็ใกล้เคียงกับการโจมตีดังกล่าวมากพอที่จะนำไปสู่การคาดการณ์ว่ามีความเป็นไปได้ที่หน่วยงานด้านการเข้ารหัสของรัฐบางแห่งอาจมีการโจมตีที่ดีกว่าที่ทำให้ RC4 ไม่ปลอดภัย[ 6 ] เมื่อพิจารณาว่าปริมาณการรับส่งข้อมูล TLSจำนวนมากในปี 2556 ใช้ RC4 เพื่อหลีกเลี่ยงการโจมตีบนการเข้ารหัสแบบบล็อกที่ใช้การเชื่อมโยงบล็อกการเข้ารหัสหากการโจมตีที่ดีกว่าในสมมติฐานเหล่านี้มีอยู่จริง การเข้ารหัส TLS ทั่วไปก็จะไม่ปลอดภัยต่อผู้โจมตีดังกล่าวในสถานการณ์จริงจำนวนมาก[ 6 ]
ในเดือนมีนาคม พ.ศ. 2558 นักวิจัยที่ Royal Holloway ประกาศการปรับปรุงการโจมตีของพวกเขา โดยนำเสนอการโจมตี 2 26ต่อรหัสผ่านที่เข้ารหัสด้วย RC4 ซึ่งใช้ใน TLS [ 54 ]
การโจมตีงานบาร์มิตซ์วาห์
ในการประชุม Black Hat Asia 2015 Itsik Mantin ได้นำเสนอการโจมตี SSL อีกครั้งโดยใช้การเข้ารหัส RC4 [ 55 ] [ 56 ]
การโจมตีสิ้นสุดลงแล้ว
ในปี 2558 นักวิจัยด้านความปลอดภัยจากKU Leuvenได้นำเสนอการโจมตีใหม่ต่อ RC4 ทั้งในTLSและWPA-TKIP [ 57 ] การโจมตีนี้มีชื่อว่า Numerous Occurrence MOnitoring & Recovery Exploit (NOMORE) ซึ่งเป็นการโจมตีประเภทแรกที่ได้รับการสาธิตในทางปฏิบัติ การโจมตีTLS ของพวกเขา สามารถถอดรหัสคุกกี้ HTTP ที่ปลอดภัยได้ ภายใน 75 ชั่วโมง การโจมตี WPA-TKIP สามารถทำได้ภายในหนึ่งชั่วโมงและอนุญาตให้ผู้โจมตีถอดรหัสและแทรกแพ็กเก็ตตามอำเภอใจได้
RC4 รุ่นต่างๆ
ดังที่กล่าวไว้ข้างต้น จุดอ่อนที่สำคัญที่สุดของ RC4 มาจากตารางคีย์ที่ไม่เพียงพอ ไบต์แรกของเอาต์พุตจะเปิดเผยข้อมูลเกี่ยวกับคีย์ ซึ่งสามารถแก้ไขได้โดยการทิ้งส่วนเริ่มต้นบางส่วนของสตรีมเอาต์พุต[ 58 ]วิธีนี้เรียกว่า RC4-drop Nโดยที่Nโดยทั่วไปจะเป็นพหุคูณของ 256 เช่น 768 หรือ 1024
มีการพยายามหลายครั้งเพื่อเสริมความแข็งแกร่งให้กับ RC4 โดยเฉพาะอย่างยิ่ง Spritz, RC4A, VMPCและRC4 +
อาร์ซี4เอ
Souradyuti PaulและBart Preneelได้เสนอ RC4 เวอร์ชันหนึ่ง ซึ่งพวกเขาเรียกว่า RC4A [ 59 ]
RC4A ใช้ชุดอาร์เรย์สถานะสองชุดS1และS2และดัชนีสองตัวj1และj2ทุกครั้งที่ค่า iเพิ่มขึ้น จะมีการสร้างข้อมูลสองไบต์:
- ขั้นแรก จะทำการประมวลผลอัลกอริธึม RC4 พื้นฐานโดยใช้S1และj1แต่ในขั้นตอนสุดท้ายจะค้นหาS1[ i ]+S1[ j1 ]ในS2
- ประการที่สอง การดำเนินการจะถูกทำซ้ำ (โดยไม่ต้องเพิ่มค่าiอีกครั้ง) บนS2และj2และผลลัพธ์ที่ได้คือS1[S2[ i ]+S2[ j2 ]]
ดังนั้น ขั้นตอนวิธีจึงเป็นดังนี้:
การคำนวณทางคณิตศาสตร์ทั้งหมดดำเนินการโดยใช้โมดูลัส 256 i := 0 j1 := 0 j2 := 0 ขณะสร้างเอาต์พุต: i := i + 1 j1 := j1 + S1[i] สลับค่าของ S1[i] และ S1[j1] จะได้ผลลัพธ์เป็น S2[S1[i] + S1[j1] ] j2 := j2 + S2[i] สลับค่าของ S2[i] และ S2[j2] เอาต์พุต S1[S2[i] + S2[j2] ] endwhile
แม้ว่าอัลกอริทึมนี้จะต้องการจำนวนการดำเนินการเท่ากันต่อไบต์เอาต์พุต แต่ก็มีการประมวลผลแบบขนานมากกว่า RC4 ซึ่งอาจส่งผลให้ความเร็วเพิ่มขึ้นได้
แม้ว่าอัลกอริทึมนี้จะแข็งแกร่งกว่า RC4 แต่ก็ยังถูกโจมตีด้วย Alexander Maximov [ 60 ]และทีมงานจาก NEC [ 61 ]พัฒนาวิธีการแยกแยะผลลัพธ์จากลำดับสุ่มที่แท้จริง
วีเอ็มพีซี
Variably Modified Permutation Composition (VMPC) เป็น RC4 รูปแบบอื่นอีกด้วย[ 62 ]โดยใช้ตารางคีย์ที่คล้ายกับ RC4 โดยที่ j := S[(j + S[i] + key[i mod keylength]) mod 256]วนซ้ำ 3 × 256 = 768 ครั้ง แทนที่จะเป็น 256 ครั้ง และมีการวนซ้ำเพิ่มเติมอีก 768 ครั้งเพื่อรวมเวกเตอร์เริ่มต้น ฟังก์ชันการสร้างเอาต์พุตทำงานดังนี้:
การคำนวณทางคณิตศาสตร์ทั้งหมดดำเนินการโดยใช้โมดูลัส 256 i := 0 ขณะสร้างเอาต์พุต: j := S[j + S[i]] เอาต์พุต S[S[S[j]] + 1] สลับ S[i] และ S[j] ( b := S[j]; S[j] := S[i]; S[i] := b) ) i := i + 1 จบในขณะที่
สิ่งนี้ถูกโจมตีในเอกสารเดียวกันกับ RC4A และสามารถแยกแยะได้ภายใน 2 38ไบต์เอาต์พุต[ 63 ] [ 61 ]
อาร์ซี4 +
RC4 +เป็นเวอร์ชันที่แก้ไขของ RC4 โดยมีตารางคีย์สามเฟสที่ซับซ้อนกว่า (ใช้เวลานานกว่า RC4 ประมาณสามเท่า หรือเท่ากับ RC4-drop512) และฟังก์ชันเอาต์พุตที่ซับซ้อนกว่าซึ่งทำการค้นหาเพิ่มเติมสี่ครั้งในอาร์เรย์ S สำหรับเอาต์พุตไบต์แต่ละรายการ ซึ่งใช้เวลานานกว่า RC4 พื้นฐานประมาณ 1.7 เท่า[ 64 ]
การคำนวณเลขคณิตทั้งหมดใช้โมดูลัส 256 << และ >> คือการเลื่อนบิตซ้ายและขวา ⊕ คือการดำเนินการ Exclusive ORขณะสร้างเอาต์พุต: i := i + 1 a := S[i] j := j + a สลับ S[i] และ S[j] ( b := S[j]; S[j] := S[i]; S[i] := b; ) c := S[i<<5 ⊕ j>>3] + S[j<<5 ⊕ i>>3] เอาต์พุต (S[a+b] + S[c⊕0xAA]) ⊕ S[j+b] endwhile
อัลกอริทึมนี้ยังไม่ได้รับการวิเคราะห์อย่างละเอียดถี่ถ้วน
สปริตซ์
ในปี 2014 Ronald Rivest ได้บรรยายและร่วมเขียนบทความ[ 14 ]เกี่ยวกับการออกแบบใหม่ที่เรียกว่า Spritz ตัวเร่งฮาร์ดแวร์ของ Spritz ได้รับการเผยแพร่ใน Secrypt ในปี 2016 [ 65 ]และแสดงให้เห็นว่าเนื่องจากการเรียกใช้แบบซ้อนกันหลายครั้งที่จำเป็นในการสร้างไบต์เอาต์พุต Spritz จึงทำงานค่อนข้างช้าเมื่อเทียบกับฟังก์ชันแฮชอื่นๆ เช่น SHA-3 และการใช้งานฮาร์ดแวร์ที่ดีที่สุดของ RC4 ที่เป็นที่รู้จัก
เช่นเดียวกับ ฟังก์ชันฟองน้ำอื่นๆSpritz สามารถใช้สร้างฟังก์ชันแฮชการเข้ารหัสลับ ตัวสร้างบิตสุ่มแบบกำหนด ( DRBG ) อัลกอริทึมการเข้ารหัสที่รองรับการเข้ารหัสที่ตรวจสอบความถูกต้องพร้อมข้อมูลที่เกี่ยวข้อง (AEAD) เป็นต้น[ 14 ]
ในปี 2016 Banik และ Isobe ได้เสนอการโจมตีที่สามารถแยกแยะ Spritz ออกจากสัญญาณรบกวนแบบสุ่มได้[ 66 ]ในปี 2017 Banik, Isobe และ Morii ได้เสนอวิธีแก้ไขง่ายๆ ที่ลบตัวแยกแยะในไบต์คีย์สตรีมสองไบต์แรก ซึ่งต้องใช้การเข้าถึงหน่วยความจำเพิ่มเติมเพียงครั้งเดียวโดยไม่ทำให้ประสิทธิภาพของซอฟต์แวร์ลดลงอย่างมาก[ 67 ]
โปรโตคอลที่ใช้ RC4
- วีพี
- TKIP (อัลกอริธึมเริ่มต้นสำหรับWPAแต่สามารถตั้งค่าให้ใช้AES-CCMPแทน RC4 ได้)
- การเข้ารหัสโปรโตคอล BitTorrent
- Microsoft Office XP (การใช้งานที่ไม่ปลอดภัยเนื่องจาก nonce ยังคงไม่เปลี่ยนแปลงเมื่อเอกสารได้รับการแก้ไข[ 68 ] )
- การเข้ารหัสแบบจุดต่อจุดของ Microsoft
- การรักษาความปลอดภัยระดับชั้นการขนส่ง / ชั้นซ็อกเก็ตที่ปลอดภัย (เดิมเป็นตัวเลือก และต่อมาการใช้งาน RC4 ถูกห้ามใน RFC 7465)
- เซฟตี้เชลล์ (ตัวเลือกเสริม)
- โปรโตคอลการเข้าถึงเดสก์ท็อประยะไกล (ไม่บังคับ)
- เคอร์เบรอส (ตัวเลือกเสริม)
- กลไกSASL Digest-MD5 (เป็นทางเลือก, ในอดีต , เลิกใช้แล้วใน RFC 6331)
- พีดี
- Skype (ในรูปแบบที่แก้ไขแล้ว) [ 69 ]
ในกรณีที่โปรโตคอลถูกทำเครื่องหมายด้วย "(optionally)" RC4 จะเป็นหนึ่งในชุดรหัสลับหลายชุดที่ระบบสามารถกำหนดค่าให้ใช้งานได้
ดูเพิ่มเติม
- TEAหรือBlock TEAหรือที่รู้จักกันในชื่อeXtended TEAและCorrected Block TEAคือตระกูลของอัลกอริทึมการเข้ารหัสแบบบล็อกซึ่งเช่นเดียวกับ RC4 ถูกออกแบบมาให้ใช้งานได้ง่ายมาก
- มาตรฐานการเข้ารหัสขั้นสูง
- ไซเฟอร์เซเบอร์
อ่านเพิ่มเติม
- Paul, Goutam; Subhamoy Maitra (2011). RC4 Stream Cipher and Its Variants . CRC Press. ISBN 9781439831359.
- Schneier, Bruce (1995). "บทที่ 17 – รหัสลับแบบสตรีมอื่นๆ และตัวสร้างลำดับสุ่มจริง"การเข้ารหัสลับประยุกต์: โปรโตคอล อัลกอริทึม และรหัสต้นฉบับในภาษาซี ( ฉบับที่ 2). Wiley. ISBN 978-0471117094.
ลิงก์ภายนอก
- บทความต้นฉบับเกี่ยวกับอัลกอริธึม RC4 ที่เผยแพร่ในรายชื่อผู้รับจดหมายของ Cypherpunks ( เวอร์ชันที่เก็บถาวร)
- RFC 4345 – โหมด Arcfour ที่ได้รับการปรับปรุงสำหรับโปรโตคอลเลเยอร์การขนส่ง Secure Shell (SSH)
- RFC 6229 – เวกเตอร์ทดสอบสำหรับการเข้ารหัสแบบสตรีม RC4
- RFC 7465 – การห้ามใช้ชุดรหัสลับ RC4
- Kaukonen; Thayer. อัลกอริทึมการเข้ารหัสแบบ Stream Cipher "Arcfour" . IETF . ID draft-kaukonen-cipher-arcfour-03.
- รายการสำหรับ RC4 ใน SCAN (Standard Cryptographic Algorithm Naming)
- การโจมตี RC4 ที่Wayback Machine (เก็บถาวรเมื่อวันที่ 21 กุมภาพันธ์ 2015)
- RSA Security ตอบโต้จุดอ่อนในอัลกอริธึมการจัดลำดับคีย์ของ RC4 ที่Wayback Machine (เก็บถาวรเมื่อวันที่ 18 พฤศจิกายน 2016)
- RC4 ใน WEP
- ความปลอดภัยของอัลกอริทึม WEP ที่Wayback Machine (เก็บถาวรเมื่อวันที่ 19 มกราคม 2020)
- Fluhrer; Mantin; Shamir (ฤดูร้อน–ฤดูใบไม้ร่วง 2002). "การโจมตี RC4 และ WEP" . CryptoBytes . 5 (2). เก็บถาวรจากต้นฉบับ(PostScript)เมื่อวันที่ 2 มกราคม 2015