הצגת המקור של הדף "RC4"

[[קובץ:RC4.svg|שמאל|ממוזער|250px|המחשת הצפנת בלוק אחד ב-RC4]]
'''צופן RC4''' הוא [[צופן זרם]] סינכרוני פשוט וקל ליישום והטמעה ב[[חומרה]] וב[[תוכנה]]. עקב פשטותו הרבה היה בעבר בשימוש נרחב ב[[פרוטוקול קריפטוגרפי|פרוטוקולי]] אבטחה רבים כגון [[SSL]] לאבטחת תעבורת [[רשת מחשבים|הרשת]] וכן [[WEP]], אולם עקב חולשות שהתגלו בו הוא אינו בטוח ואינו מומלץ לשימוש קריפטוגרפי כיום. אף על פי כן הצופן עדיין נתמך בכמה פרוטוקולי אבטחה עקב [[תאימות לאחור]].

RC4 פותח על ידי [[רונלד ריבסט]] ב-[[1987]] במעבדות [[RSA (חברה)|RSA]]. שמו נגזר מראשי התיבות Rivest Cipher 4, אולם לעיתים מפרשים RC כ-Ron's code (הקוד של רון). פיתוחים נוספים שלו הם [[RC5]] וכן [[RC6]] שנמנה בין המועמדים המובלים לתקן ה[[הצפנה]] החדש שבו זכה [[AES]]. 

עד [[1994]] נשמר צופן RC4 כסוד מסחרי עד שפורסם ברבים, תחילה באופן אנונימי ב[[קבוצת דיון|קבוצות דיון]] [[קריפטוגרפיה|קריפטוגרפיות]] ומשם עשה דרכו לרשת ה[[אינטרנט]]. ריבסט לא רשם כל [[פטנט]] על הצופן שלו; השם RC4 הוא סימן מסחרי ומוגן ב[[זכויות יוצרים]], אולם באופן לא רשמי השימוש בצופן מותר, אם כי לא תחת שמו המקורי. היות שמעבדות RSA מעולם לא פרסמו את פרטי ה[[אלגוריתם]] באופן רשמי, יש המכנים אותו ARC4  או ARCFOUR, קיצור ל"Alleged RC4" שפירושו "כביכול RC4".

== הליך ההצפנה ==
צופן RC4 מקבל כקלט טקסט קריא (plaintext) ומפתח (key), כאשר המפתח הסודי יכול להיות בכל אורך רצוי בין 40 ל-256 סיביות. כמו בכל [[צופן זרם]], כדי להצפין את הטקסט הגלוי RC4 מייצר רצף [[סיבית|סיביות]] פסאדו-[[מספר אקראי|אקראי]] הנקרא "זרם מפתח" באמצעות מחולל פסאודו-אקראי (PRG) מובנה. זרם הסיביות האקראי משולב עם הטקסט הקריא בית אחר בית, באמצעות חיבור בינארי ([[או מוציא|XOR]]) בדומה ל[[צופן ורנם]]. פענוח מתבצע בדרך זהה. 

הזיכרון הפנימי או המצב הפנימי (internal state) של האלגוריתם מורכב משני חלקים:

# תיבת [[תמורה (מתמטיקה)|תמורה]] <math>\ S</math>באורך 256 בתים (כאשר כל 256 הערכים האפשריים מופיעים בה)
# שני אינדקסים <math>\ i</math> ו-<math>\ j</math>.

זרם המפתח שבעזרתו מצפינים את המסר מופק באמצעות שימוש באלגוריתם הכנת מפתח – Key Scheduling Algorithm (בקיצור KSA) כדי לערבב את תיבת התמורה <math>S</math>, ולאחר מכן שימוש במחולל הפנימי PRGA כדי לייצר את הזרם הסופי. באלגוריתם הכנת המפתח, תחילה מערך הבתים <math>S</math> מאותחל עם 256 ערכים קבועים ולאחר מכן המערך מעורבב תוך שימוש בכל בתי מפתח ההצפנה, בעזרת טכניקה הקרויה Shuffle (בדומה לערבוב קלפים). התוצאה היא תמורה פסאודו-אקראית שאיתה הצופן מייצר בשלב הבא את זרם המפתח (key stream).

להלן תיאור שתי הפונקציות של הצופן – תהליך ההכנה KSA והמחולל הפנימי PRGA (קיצור של Pseudo-Random Generation Algorithm), כאשר הקלט הוא מערך <math>K</math> באורך <math>kLength</math> בתים המכיל את המפתח הסודי שמסופק על ידי המשתמש. <math>N</math> מייצג את מספר האלמנטים במערך <math>S</math> וכן את הערך המקסימלי של כל אלמנט, בדרך כלל <math>N=256</math>, כלומר 256 כניסות של אלמנטים בגודל בית אחד (<math>2^8</math>).

<div class="mw-content-ltr" align="center">
{| class="wikitable" align="center"
|-
|
:<math>\mathbf{RC4 \ KSA:}</math>
:<math>\text{For }i = 0\text{ to }N - 1\text{ do: }</math>
::<math>S[i] = i</math>
:<math>j = 0</math>
:<math>\text{For }i = 0\text{ to }N - 1\text{ do:}</math>
::<math>j = j + S[i] + K[i\text{ mod }kLength]</math>
::<math>\text{Swap}(S[i], S[j])</math>
||
:<math>\mathbf{RC4 \ PRGA:}</math>
:<math>i = j = 0</math>
:<math>\mathbf{Loop:}</math>
::<math>i = i + 1</math>
::<math>j = j + S[i]</math>
::<math>\text{Swap}(S[i], S[j])</math>
::<math>\text{Return: }S[S[i] + S[j]]</math>
||
:<math>\text{Swap}(S[x],S[y])</math>
::<math>t = S[x]</math>
::<math>S[x]=S[y]</math>
::<math>S[y]=t</math>
: {{D}}
: {{D}}
: {{D}}  
|}
</div>

ההצפנה מתבצעת על ידי PRGA בית אחר בית במספר החזרות הנדרש עד להצפנת כל הטקסט הקריא. בכל סבב של PRGA האלגוריתם מעדכן את מצב הצופן ומפיק בית אחד של זרם המפתח. האינדקס <math>i</math> מקודם צעד אחד, הערך המצוי באינדקס <math>i</math> במערך <math>S</math> מוסף ל-<math>j</math>, ערכי <math>S_i</math> ו-<math>S_j</math> מחליפים מקומות (Swap) והפלט הוא האיבר <math>S[S_i + S_j]</math> - אותו מחברים בינארית ([[XOR]]) עם בית הטקסט הקריא הנוכחי. כל פעולות החיבור בצופן מבוצעות [[מודולו]] 256 (גודל בית אחד). כל איבר במערך <math>S</math> מוחלפת לפחות פעם אחת כל 256 סבבים.

לדוגמה, אם מפתח ההצפנה הוא "Secret" ומחרוזת הטקסט היא "Attack at dawn" התוצאה תהיה:

<div style="direction: ltr;" align="center">
RC4("Secret", "Attack at dawn") = 45A01F645FC35B383552544B9BF5
</div>

== יישומים ==
צופן RC4 אידיאלי ליישום בתוכנה, במיוחד לאור העובדה שהצופן מטפל במידע בבתים ולא סיביות. הזיכרון הנדרש לצופן הזה נמוך ביותר (רק 256 בתים). ופעולת מודולו 256 אפשר לבצע באמצעות [[פעולה על סיביות|אופרטור בינארי AND]] ולהימנע מחילוק (פעולה בזבזנית יותר) ובמיוחד שבפלטפורמות רבות התקן הוא שפעולת חיבור או כפל בבתים מניבה תוצאה בגבולות בית אחד כאשר התוצאה למעשה נחתכת. כלומר כיוון שהמהדר מבצע מודולו באופן עקיף, אפשר פשוט לבצע פעולות כפל וחיבור רגיל ולהתעלם לחלוטין מהמודולו.

==ביטחון==
לצופן RC4 חסרונות ידועים רבים. זרם המפתח המיוצר באמצעות המחולל הפנימי של האלגוריתם סובל מהטיה קלה ועל כן אינו אקראי לגמרי. ישנה התקפה המנצלת עובדה זו כדי לפצח את הצופן. לכן רצוי לדלג לפחות על 512 הבתים הראשונים שנוצרו על ידי המחולל.

כדי למנוע [[התקפת גלוי-ידוע]] (chosen plaintext attack), צפנים מודרניים מצרפים [[וקטור אתחול]] לצד המפתח כדי להבטיח שהצפנה חוזרת של טקסט קריא זהה, תניב טקסט מוצפן שונה. RC4 אינו מיישם טכניקה זו על כן הזרם המוצפן חלש. כלומר בהינתן טקסט קריא זהה הפלט יהיה תמיד זהה (אם משתמשים באותו מפתח). עובדה זו מהווה נקודת תורפה שניתן לנצלה כדי לתקוף את הצופן. [[שרשור (מחרוזות)|שרשור]] מספר אקראי למפתח הסודי כפי שנעשה בפרוטוקול [[WEP]] בעבר, אינו בטוח ואף הוביל להתקפה מוצלחת. דרך טובה יותר היא למזג את המפתח עם ערך אקראי באמצעות [[פונקציית גיבוב קריפטוגרפית|פונקציית גיבוב]] עם מפתח.

להלן תקציר החולשות והפגמים שהתגלו במרוצת השנים מאז פרסומו של RC4 ב-1994.

=== תהליך הכנת זרם המפתח - KSA ===
*בתהליך ההכנה הראשוני של RC4 המפתח הסודי המסופק על ידי המשתמש מעורבב בתוך תמורה <math>S</math> באורך 256 בתים שנקראת המצב הפנימי (interenal state) של הצופן. קיימת הטיה סטטיסטית{{הערה|M. Akgun, P. Kavak and H. Demirci. New Results on the Key Scheduling Algorithm of RC4. Indocrypt 2008. A sketch of this work has been presented in Eurocrypt 2008 Rump Session, available at http://www.iacr.org/conferences/eurocrypt2008v/index.html [last accessed on July 18, 2008].}} של בתים מהתמורה <math>S</math> למפתח הסודי, כלומר קיים [[מתאם]] גבוה בין <math>S[v]</math> עבור <math>v</math> קטן לבין בתים של המפתח{{הערה|A. Roos. A class of weak keys in the RC4 stream cipher. 1995.}}{{הערה|L. R. Knudsen, W. Meier, B. Preneel, V. Rijmen and S. Verdoolaege. Analysis Methods for (Alleged) RCA. ASIACRYPT 1998, pages 327-341, vol. 1514, Lecture Notes in Computer Science, Springer-Verlag.}}{{הערה|S. R. Fluhrer and D. A. McGrew. Statistical Analysis of the Alleged RC4 Keystream Generator. FSE 2000, pages 19-30, vol. 1978, Lecture Notes in Computer Science, Springer-Verlag.}}{{הערה|S. Maitra and G. Paul. New Form of Permutation Bias and Secret Key Leakage in Keystream Bytes of RC4. FSE 2008, pages 253-269, vol. 5086, Lecture Notes in Computer Science, Springer Berlin / Heidelberg.}}.
*קיימת הטיה סטטיסטית{{הערה|G. Paul, S. Rathi and S. Maitra. On Non-negligible Bias of the First Output Byte of RC4 towards the First Three Bytes of the Secret Key. Proceedings of the International Workshop on Coding and Cryptography (WCC) 2007, pages 285-294. To appear in Designs, Codes and Cryptography, special issue of in memory of Hans Dobbertin, DOI 10.1007/s10623-008-9177-7.}}{{הערה|G. Paul and S. Maitra. Permutation after RC4 Key Scheduling Reveals the Secret Key. SAC 2007, pages 360-377, vol. 4876, Lecture Notes in Computer Science, Springer Berlin / Heidelberg.}} של התמורה <math>S</math> הראשונה (המצב הפנימי) מיד לאחר KSA לצירוף כלשהו של בתים מהמפתח הסודי. קיימת נוסחה מפורשת של ההסתברויות שבתים מהתמורה <math>S</math> בכל שלב נוטים לבתים של המפתח הסודי.
*מבחינה תאורטית, קיימת חולשה מובנית{{הערה|G. Paul, S. Maitra and R. Srivastava. On Non-Randomness of the Permutation after RC4 Key Scheduling. Applied Algebra, Algebraic Algorithms, and Error Correcting Codes (AAECC) 2007, pages 100-109, vol. 4851, Lecture Notes in Computer Science, Springer Berlin / Heidelberg.}}{{הערה|S. Paul and B. Preneel. A New Weakness in the RC4 Keystream Generator and an Approach to Improve the Security of the Cipher. FSE 2004, pages 245-259, vol. 3017, Lecture Notes in Computer Science, Springer-Verlag.}} בסגנון הערבוב של KSA שגורם לכך שהתמורה <math>S</math> אינה אחידה לגמרי, אלא סובלת מחוסר אקראיות בכמה מקומות, מה שיכול להוביל להתקפת הבחנה{{הערה|I. Mantin. Analysis of the stream cipher RC4. Master’s Thesis, The Weizmann Institute of Science, Israel, 2001.}}.
*בתהליך הכנת זרם המפתח קיימת תופעה מעניינת שנקראת "זוגות אנומליה", מספר הפעמים הצפוי שבהם כל בית בתמורה <math>S</math> זוכה לביקור על ידי האינדקסים <math>i,j</math> אינו אחיד. 
*קיימת התנגשות בין מפתחות, שני מפתחות שמפיקים מצב פנימי זהה, ובגלל זה מפתחות הצפנה סודיים שונים יפיקו זרם מפתח זהה (Matsui).
*קיימת מחלקה עצומה של מפתחות חלשים{{הערה|D. Wagner. My RC4 weak keys. 26 September, 1995.}}{{הערה|S. R. Fluhrer, I. Mantin and A. Shamir. Weaknesses in the Key Scheduling Algorithm of RC4. SAC 2001, pages 1-24, vol. 2259, Lecture Notes in Computer Science, Springer-Verlag.}}, כך שבידיעת חלק קטן מהמפתח הסודי אפשר לנחש בתים רבים של פלט זרם המפתח. Mironov ניתח כמה בתים מהפלט הראשוני של זרם המפתח סובלים מהטייה והמליץ להיפטר מ-512 הבתים הראשונים.

===המצב הפנימי===
*פורסמו מספר התקפות{{הערה|E. Biham and Y. Carmeli. Efficient Reconstruction of RC4 Keys from Internal States. FSE 2008, pages 270-288, vol. 5086, Lecture Notes in Computer Science, Springer Berlin / Heidelberg.}}{{הערה|G. Paul and S. Maitra. RC4 State Information at Any Stage Reveals the Secret Key. IACR Eprint Server, eprint.iacr.org, number 2007/208, June 1, 2007.}}{{הערה|V. Tomasevic, S. Bojanic and O. Nieto-Taladriz. Finding an internal state of RC4 stream cipher. Information Sciences, pages 1715-1727, vol. 177, 2007.}}{{הערה|S. Paul and B. Preneel. Analysis of Non-fortuitous Predictive States of the RC4 Keystream Generator. IN-DOCRYPT 2003, pages 52-67, vol. 2904, Lecture Notes in Computer Science, Springer-Verlag.}} לשחזור המצב הפנימי של הצופן מתוך מצב פנימי ידוע. וכן שחזור מפתח ההצפנה מתוך המצב הפנימי.
*אם סיבוכיות שחזור המפתח הסודי מתוך מהתמורה <math>S</math> נמוכה משחזור התמורה <math>S</math> מתוך זרם המפתח, אפשר לשלב את שתיהן יחד להתקפה מוצלחת יותר.
*מקסימוב וחוברטוביץ' פיתחו התקפה תאורטית{{הערה|A. Maximov and D. Khovratovich. New State Recovering Attack on RC4 (Full Version). IACR Eprint Server, eprint.iacr.org, number 2008/017, Jan 10, 2008. (To Appear in Crypto 2008 under the title "New State Recovery Attack on RC4").}} לשחזור המצב הפנימי בסיבוכיות של <math>2^{241}</math> זמן וזרם מפתח. Golić ו-Morgari פיתחו אלגוריתם הסתברותי{{הערה|J. Golic. Linear statistical weakness of alleged RC4 keystream generator. EUROCRYPT 1997, pages 226-238, vol. 1233, Computer Science, SpringLecture Notes in er-Verlag.}} לשחזור המצב הפנימי מתוך זרם המפתח באורך <math>2^{41}</math> בזמן של <math>2^{689}</math>.

===מחולל זרם המפתח - PRGA===
*התגלו מצבים פנימיים שלעולם לא יופיעו בזרם המפתח (Finney).
*משפט Glimpse מראה שקיימת "דליפה" של מידע בבתי זרם המפתח (Jenkins). בניגוד לצפוי ממחרוזת אקראית באורך <math>N</math>, ההסתברות לניחוש בתים אחדים מהמפתח מתוך בתים של המצב היא <math>2/N</math>.
*בפלט המפתח קיימים שני סוגים של הטיה; ''הטיה קצרת-טווח'' ו''הטיה ארוכת-טווח''. כלומר קיימת חולשה (חוסר אקראיות) מובנית בבתי זרם המפתח, במיוחד בבתים הראשונים (למשל הבית השני שסובל מהטיה חמורה). אפשר להימנע מההטייה קצרת הטווח אם נפטרים מ-512 הבתים הראשונים כפי שהומלץ וייושם בחלק מהפרוטוקולים.
*פותחו התקפות נגד RC4 אם וקטור אתחול כפי שנמצא בשימוש WEP{{הערה|A. Stubblefield, J. Ioannidis and A. D. Rubin. Using the Fluhrer, Mantin, and Shamir Attack to Break WEP. AT&T Labs Technical Report TD-4ZCPZZ, August 6, 2001.}}{{הערה|E. Tews, R. P. Weinmann and A. Pyshkin. Breaking 104 bit WEP in less than 60 seconds. IACR Eprint Server, eprint.iacr.org, number 2007/120, April 1, 2007 [last accessed on July 18, 2008].}}.

===התקפת הבחנה===
[[התקפת הבחנה]] (Distinguishing Attack) היא התקפה סטטיסטית על פלט מחולל זרם המפתח{{הערה|I. Mantin. Predicting and Distinguishing Attacks on RC4 Keystream Generator. EUROCRYPT 2005, pages 491-506, vol. 3494, Lecture Notes in Computer Science, Springer-Verlag.}}{{הערה|Y. Tsunoo, T. Saito, H. Kubo and T. Suzaki. A Distinguishing Attack on a Fast Software-Implemented RC4-Like Stream Cipher. IEEE Transactions on Information Theory, page 3250-3255, vol. 53, issue 9, September 2007.}}{{הערה|S. Vaudenay and M. Vuagnoux. Passive-Only Key Recovery Attacks on RC4. SAC 2007, pages 344-359, vol. 4876, Lecture Notes in Computer Science, Springer Berlin / Heidelberg.}}. במצב אידיאלי, זרם המפתח אמור להראות על פניו כרצף אקראי לכל דבר. כלומר לא ניתן יהיה להבדילו מרצף אקראי שנוצר ממחולל אקראי אמיתי. מחולל זרם המפתח של RC4 הוא לא יותר מאשר מחולל פסאודו-אקראי שמקבל גרעין התחלתי סודי שהוא המפתח "ומותח" אותו למחרוזת אקראית באורך רצוי. התקפת הבחנה מתמקדת במציאת הבדלים או ניתוח ההסתברות שסיבית 1 או 0 תופיע בפוזיציה מסוימת בהשוואה לזרם אקראי אמיתי. אלגוריתם הבחנה מקבל קלט באורך <math>n</math> בתים שמקורם יכול להיות מזרם המפתח או ממחולל אקראי אמיתי ותפקידו להחזיר תשובה לאיזה סוג מהם הוא משתייך. אם נמצאו הבדלים, עובדה זו כשלעצמה יכולה לפתוח פתח להתקפות ולשבירת הצופן.
*מחקרים מוכיחים כי כלל העדכון של RC4 שהוא <math>j=j+S[i]</math>אינו בחירה טובה וקיימת בו חולשה מובנית.
*מבדיקה [[סטטיסטיקה|סטטיסטית]] שעשו ב-[[2001]] גילו [[עדי שמיר|שמיר]], [[איציק מנטין]] ופלורר{{הערה|I. Mantin and A. Shamir. A Practical Attack on Broadcast RC4. FSE 2001, pages 152-164, vol. 2355, Lecture Notes in Computer Science, Springer-Verlag.}}{{הערה|I. Mantin. A Practical Attack on the Fixed RC4 in the WEP Mode. ASIACRYPT 2005, pages 395-411, volume 3788, Lecture Notes in Computer Science, Springer-Verlag.}} שהבתים הראשונים של זרם המפתח של צופן RC4 אינם אקראיים לגמרי ומדליפים מידע לגבי המפתח. נתון זה, אפשר להם לפתח התקפה יעילה כנגד [[WEP]] (מערכת אבטחה לרשת אלחוטית). בתחילת [[2007]] אף פורסמו דרכים חדשות לפיצוחה בזמן קצר מאוד (פחות מדקה) תוך שימוש בכמות לא רבה של טקסט מוצפן. העובדה ש-WEP נפרצה הובילה ביוני 2004 לפיתוח תקן מחמיר יותר הקרוי [[Institute of Electrical and Electronics Engineers|IEEE]] 802.11i המשמש בסיס לדור השני באבטחת רשת סלולרית [[WPA]] (קיצור של Wi-Fi Protected Access). ב-2011 פורסמו{{הערה|[http://link.springer.com/chapter/10.1007%2F978-3-642-19574-7_5 Discovery and Exploitation of New Biases in RC4]}} מספר חולשות נוספות של הצופן. שיחד עם חולשות ידועות אחרות מאפשרות התקפה לשחזור מפתח ההצפנה בהינתן 9,800 [[חבילת מידע|חבילות]] מוצפנות בלבד.

למרות האמור מערכות רבות בעולם עדיין משתמשות בטכנולוגיה המיושנת בעיקר מסיבות של יעילות ולמרות אמצעי הזהירות שננקטים, מומחים מתריעים על כך שקיימות פרצות חמורות במערכות אלו וישנן אף כאלו שניתן לפרוץ אותן תוך מספר שניות.

==גרסאות מתקדמות==
למרות החולשות שהתגלו בצופן RC4, הוא אטרקטיבי בשל העובדה שהוא נוח ויעיל למימוש בתוכנה. הרוב סבורים שכדאי לעבור לצפני זרם חזקים יותר שנבדקו והתקבלו על ידי [[eSTREAM]] כמו [[HC-128]]. אילו צפני זרם הפועלים בדרך כלל ברמה של מילים בגודל 32 או 64 סיביות והם בטוחים יותר לשימוש, אם כי מעט מורכבים ליישום.

קיימים צפני זרם רבים שמנסים לחקות את המבנה של RC4. כלומר פרמוטציה פנימית גדולה שנקראת מצב (state) והיא מורכבת בדרך כלל ממערך אחד או יותר של <math>N</math> אלמנטים כל אחד בגודל <math>N</math>, מספר מוגבל של אינדקסים ופעולת חיבור מודולו <math>N</math> לעיתים בתוספת [[הזזה מעגלית]] (rotation). להלן כמה מהם: Py, Py6, IA, ISAAC, NGG, GGHN. חלקם הוצעו לפרויקט ECRYPT האירופאי. כל הצפנים המנויים לא עמדו במבחן קריפטואנליזה (התקפת הבחנה) ונפסלו{{הערה|[https://eprint.iacr.org/2005/448 On the (In)security of Stream Ciphers Based on Arrays and Modular Addition]}}. לעומתם קיימים מספר אלגוריתמים מבוססי RC4 ששרדו קריפטואנליזה, ביניהם ניתן למנות את: IBAA, Pypy, HC-256, VMPC.

באופן כללי היתרונות של צופן RC4 הם:
# שימוש במערכים המאפשר זיכרון פנימי עצום במחיר מועט.
# שימוש בפעולה פשוטה, חיבור מודולו <math>N</math> בלבד.
# עיצוב פשוט ונקי (קל ליישום והטמעה).
# לא ידוע על התקפה לשחזור המפתח הסודי מלבד כוח גס.

חסרונות:
# פועל ברמה של בתים בלבד (מה שיכול להוות יתרון במקרים מסוימים), לא יעיל בארכיטקטורת 32 או 64 סיביות.
# קיימות הטיות סטטסטיות בפלט המחולל לעומת זרם אקראי אמיתי (ידוע על התקפות הבחנה מוצלחות נגד הצופן).
# שלב הכנת מפתח אינו אקראי (קיימת הטיה סטטיסטית חמורה בבתים הראשונים).

נעשו מספר מאמצים לתקן את הליקויים של צופן RC4 על מנת ליהנות מפשטותו הרבה מבלי להיחשף לחולשות האמורות. להלן ארבע גרסאות ידועות של אלגוריתם RC4 שהוצעו כתחליף למקורי וחלקן הוכחו כבטוחות יותר.

===RC4A===
RC4A{{הערה|[https://www.iacr.org/archive/fse2004/30170244/30170244.pdf A New Weakness in the RC4 Keystream Generator and an Approach to Improve the Security of the Cipher*]}} הוצע ב-2004 על ידי Bart Preneel ו-Souradyuti Paul כחלופה לאלגוריתם המקורי. האלגוריתם מבצע פחות פעולות פר בית אחד ותומך במקביליות. אחת ההתקפות הידועות נגד RC4 היא התקפת הבחנה המבוססת על רמת מתאם גבוהה בין המצב הפנימי לפלט האלגוריתם. הפתרון שהוצע הוא לגרום לתלות נוספת של הפלט עם משתנים אקראיים נוספים, כך ההסתברות לניחוש מוצלח של בתי המצב הפנימי תוך התבוננות בפלט תהיה נמוכה יותר. על בסיס הרעיון הזה עוצב RC4A. הצופן הוא הרחבה של המחולל הפנימי PRGA של צופן RC4 בעוד שתהליך הכנת המפתח נותר ללא שינוי. לצורך כך משתמשים בשתי תמורות (מערכים) <math>S_1,S_2</math> במקום אחת וכן שני אינדקסים <math>j_1,j_2</math> במקום אחד. הכנת התמורות נעשית על ידי KSA של RC4 לעיל עם שני מפתחות סודיים שונים <math>k_1,k_2</math> (אחד יכול להיות מופק מהשני באמצעות פונקציה פסאודו-אקראית כלשהי כמו RC4). להלן תיאור האלגוריתם:

<div class="mw-content-ltr">
{| align="center"
|-
| 
:<math>\text{Set: }i = 0, j_1=j_2=0</math>
:<math>\mathbf{Loop:}</math>
:#<math>i = i + 1</math>
:#<math>j_1=j_1 + S_1[i]</math>
:#<math>\text{Swap}(S_1[i], S_1[j_1])</math>
:#<math>\text{Output: }S_2[S_1[i] + S_1[j_1]]</math>
:#<math>j_2=j_2 + S_2[i]</math>
:#<math>\text{Swap}(S_2[i], S_2[j_2])</math>
:#<math>\text{Output: }S_1[S_2[i] + S_2[j_2]]</math>

|}
</div>

בכל ריצה של המחולל הפנימי האינדקס <math>i</math> מקודם פעם אחת ונוצרים שני בתים של זרם מפתח, אחד מכל מערך. הפונקציה Swap מתוארת לעיל.

===VMPC===
הצופן Variably Modified Permutation Composition{{הערה|[http://www.vmpcfunction.com/vmpc.pdf VMPC One-Way Function and Stream Cipher]}} פותח ב-2004 על ידי Bartosz Zoltak והוצע כתחליף ל-RC4. הרעיון מבוסס על פונקציית פלט מורכבת יותר: <math>P[P[P[x]]+1]</math>. כאשר <math>P</math> היא פרמוטציה, זאת במטרה להקשות על ניחוש וכן למנוע הטיות סטטיסטיות לא רצויות של זרם המחולל. אלגוריתם ההכנה מקבל מפתח <math>K</math> באורך <math>c</math> בתים וכן וקטור אתחול <math>V</math> באורך <math>z</math> בתים ומערבב את הפרמוטציה הראשונית בהתאם. פלט המחולל הפנימי הוא בית אחר בית עד למספר הבתים הרצוי <math>L</math> שהוא אורך המסר להצפנה בבתים.

<div class="mw-content-ltr">
{| align="center"
|-
| 
:<math>\mathbf{VMPC \ KSA:}</math>
:<math>s=0</math>
:<math>\text{For }i = 0\text{ to }255\text{ do: }P[n] = n</math>

:<math>\text{For }m = 0\text{ to }767\text{ do:}</math>
::<math>n=m\text{ mod }256</math>
::<math>s=P[(s+P[n]+K[m\text{ mod }c])\text{ mod }256]</math>
::<math>\text{Swap}(P[n], P[s])</math>

:<math>\text{For }m = 0\text{ to }767\text{ do:}</math>
::<math>n=m\text{ mod }256</math>
::<math>s=P[(s+P[n]+V[m\text{ mod }z])\text{ mod }256]</math>
::<math>\text{Swap}(P[n], P[s])</math>
|| 
:<math>\mathbf{VMPC \ PRGA:}</math>
:<math>n = 0</math>
:{{D}}
:<math>\text{Repeat }L\text{ times:}</math>
::<math>s = P[(s+P[n])\text{ mod }256</math>
::<math>\text{Output: }P[(P[P[s]]+1)\text{ mod }256]</math>
::<math>\text{Swap}(P[n], P[s])</math>
::<math>n = (n+1)\text{ mod }256</math>
:{{D}}
:{{D}}
:{{D}}
|}
</div>

===RC4+{{D}}===
צופן RC4+{{D}}{{הערה|[https://eprint.iacr.org/2008/396 Analysis of RC4 and Proposal of Additional Layers for Better Security Margin]}} הוצע ב-2008 על ידי Subhamoy Maitra ו-Goutam Paul כחלופה בטוחה לצופן RC4. הצופן משתמש בטכניקת ערבוב בשלוש שכבות שונות בשילוב עם וקטור אתחול. לאחר השינויים הצופן בטוח יותר אך לא קיימת הוכחה פורמלית לכך. המחקר בתחום יימשך וייתכנו גילויים חדשים. האלגוריתם הבא המקבל מפתח סודי ווקטור אתחול, שניהם באורך שרירותי ומפיק זרם מפתח באורך הרצוי. סימנים מוסכמים: <math>\oplus</math> מייצג XOR וכן <math>\ll</math> מייצג הזזה (Shift) שמאלה, <math>\gg</math> מייצג הזזה ימינה, <math>\text{0xAA}</math> קבוע הקסדצימלי (170 בייצוג עשרוני):

<div class="mw-content-ltr">
{| align="center"
|-
|
:<math>\mathbf{Initializing:}</math>
:<math>\text{For }i = 0\text{ to }N-1\text{ do: }S[i]=i</math>
:<math>j=0</math>
:{{D}}
:<math>\mathbf{Layer \ 1: \ Basic \ Scrambling}</math>
:<math>\text{For }i = 0\text{ to }N-1\text{ do:}</math>
::<math>j = j + S[i] + K[i]</math>
::<math>\text{Swap}(S[i], S[j])</math>
:{{D}}
:<math>\mathbf{Layer \ 2: \ Scrambilng \ with \ IV}</math>
:<math>\text{For }i = N/2 - 1\text{ down to }0\text{ do:}</math>
::<math>j = (j + S[i])\oplus(K[i] + IV[i])</math>
::<math>\text{Swap}(S[i], S[j])</math>
:<math>\text{For }i = N/2\text{ to }N - 1\text{ do:}</math>
::<math>j = (j + S[i])\oplus(K[i] + IV[i])</math>
::<math>\text{Swap}(S[i], S[j])</math>
||
:<math>\mathbf{Layer \ 3: \ Zigzag \ Scrambling}</math>
:<math>\text{For }y = 0\text{ to }N - 1\text{ do:}</math>
::<math>\text{If }y\equiv 0\text{ mod }2\text{ then: }i = y/2</math>
::<math>\text{Else: }i = N - (y+1)/2</math>
::<math>j = j + S[i] + K[i]</math>
::<math>\text{Swap}(S[i], S[j])</math>
:{{D}}
:<math>\mathbf{PRGA+}</math>
:<math>i = j = 0</math>
:<math>\mathbf{Keystream \ Generation \ Loop:}</math>
::<math>i = i + 1</math>
::<math>j = j + S[i]</math>
::<math>\text{Swap}(S[i], S[j])</math>
::<math>t = S[i] + S[j]</math>
::<math>u = (S[i\gg 3\ \oplus \ j\ll 5]+S[i\ll 5\ \oplus \ j\gg 3])\oplus\text{0xAA}</math>
::<math>\text{Output: }(S[t]+S[u])\oplus S[j + S[j]]</math>
|}
</div>

===Spritz===
Spritz{{הערה|[http://people.csail.mit.edu/rivest/pubs/RS14.pdf Spritz - a spongy RC4-like stream cipher and hash function]}} הוא גרסה מתקדמת של RC4 שפותחה ב-2014 על ידי [[רונלד ריבסט]] ו-Jacob Schuldt. הצופן עוצב לפי פרדיגמת [[פונקציית ספוג]] שהיא מבנה קריפטוגרפי בטוח שיושם בפונקציית הגיבוב [[Keccak]] המאפשר הפעלת [[תמורה פסאודו-אקראית|פרמוטציה פסאודו-אקראית]] לצורך פרימיטיבים קריפטוגרפיים שונים כמו הצפנה סימטרית, פונקציית גיבוב או אימות מסרים. מבנה הספוג מורכב ממצב פנימי גדול ושני שלבי הפעלה "ספיגה וסחיטה". פונקציית הספיגה מקבלת מפתח הצפנה ווקטור האתחול (אם יש) ומעדכנת את המצב הפנימי בהתאם, פונקציית הסחיטה מספקת זרם פסאודו-אקראי המשמש כמפתח. בצופן Spritz ארבעה מרכיבים עיקריים, אתחול (Init), ערבוב (Shuffle), ספיגה (Absorb) וסחיטה (Squeeze). לאחר אתחול תחילה סופגים את המפתח <math>K</math> על ידי <math>\text{Absorb}(K)</math> ואז ההצפנה מתבצעת עם הפונקציית הסחיטה <math>\text{Squeeze}(r)</math> המקבלת פרמטר <math>r</math> "וסוחטת" מחרוזת פסאודו-אקראית באורך <math>r</math> בתים אותם מחברים עם המסר המקורי ב-XOR. הצופן עוצב כך שיוכל לתמוך בכל <math>N</math> אבל צריך להבטיח ש-<math>w</math> יהיה [[מספר זר|זר]] ל-<math>N</math> לשם כך הפונקציה <math>\text{Whip(r)}</math> משתמשת ב-[[מחלק משותף מקסימלי|GCD]]. במקרה ש-<math>N</math> הוא חזקה של 2 (כגון 256) מספיק שיהיה אי זוגי, לכן אפשר להחליף את הלולאה האחרונה בפונקציה <math>\text{Whip(r)}</math> במשפט <math>w = w + 2</math>. וכן יש לזכור שכל פעולות החיבור הן מודולו <math>N</math>. להלן תיאור האלגוריתם:

<div class="mw-content-ltr">
{| align="center"
|-
| 
:<math>\mathbf{InitializeState(N)}</math>
:<math>i = j = k = z = a = 0</math>
:<math>w = 1</math>
:<math>\text{For }v = 0\text{ to }N - 1\text{ do:}</math>
::<math>S[v] = v</math>
:{{D}}
:<math>\mathbf{Absorb(I)}</math>
::<math>\text{For }v = 0\text{ to }I.length - 1</math>
:::<math>\text{AbsorbByte}(I[v])</math>
:{{D}}
:<math>\mathbf{AbsorbByte(b)}</math>
::<math>\text{AbsorbNibble}(\text{low}(b))</math>
::<math>\text{AbsorbNibble}(\text{high}(b))</math>
:{{D}}
:<math>\mathbf{AbsorbNibble(x)}</math>
::<math>\text{If }a = \left\lfloor N/2\right\rfloor\text{ then Shuffle}()</math>
::<math>\text{Swap}(S[a], S[\left\lfloor N/2\right\rfloor + x ])</math>
::<math>a = a + 1</math>
:{{D}}
:<math>\mathbf{AbsorbStop()}</math>
::<math>\text{If }a = \left\lfloor N/2\right\rfloor\text{ then Shuffle}()</math>
::<math>a = a + 1</math>
:{{D}}
:<math>\mathbf{Shuffle()}</math>
::<math>\text{Whip}(2N)</math>
::<math>\text{Crush}()</math>
::<math>\text{Whip}(2N)</math>
::<math>\text{Crush()}</math>
::<math>\text{Whip}(2N)</math>
::<math>a = 0</math>
|| 
:<math>\mathbf{Whip(r)}</math>
::<math>\text{For }v = 0\text{ to }r - 1\text{ do: Update}()</math>
::<math>\text{Do: }w = w + 1</math>
::<math>\text{Until GCD}(w,N) = 1</math>
:{{D}}
:<math>\mathbf{Crush()}</math>
::<math>\text{For }v = 0\text{ to }\left\lfloor N/2\right\rfloor - 1\text{ do}</math>
::<math>\text{If }S[v] > S[N - 1 - v]</math>
:::<math>\text{Swap}(S[v], S[N - 1 - v])</math>
:{{D}}
:<math>\mathbf{Squeeze(r)}</math>
::<math>\text{If }a > 0\text{ then Shuffle}()</math>
::<math>P =\text{ New Array}(r)</math>
::<math>\text{For }v = 0\text{ to }r - 1</math>
::<math>P[v] = \text{Drip}()</math>
::<math>\text{Return }P</math>
:{{D}}
:<math>\mathbf{Drip()}</math>
::<math>\text{If }a > 0\text{ then Shuffle}()</math>
::<math>\text{Update}()</math>
::<math>\text{Return Output}()</math>
:{{D}}
:<math>\mathbf{Update()}</math>
::<math>i = i + w</math>
::<math>j = k + S[j + S[i]]</math>
::<math>k = i + k + S[j]</math>
::<math>\text{Swap}(S[i], S[j])</math>
:{{D}}
:<math>\mathbf{Output()}</math>
::<math>z = S[j + S[i + S[z + k]]]</math>
::<math>\text{Return }z</math>
|}
</div>

===VMPC-R===
אלגוריתם VMPC-R{{הערה|[http://www.vmpcfunction.com/VMPC-R.pdf VMPC-R Cryptographically Secure Pseudo-Random Number Generator Alternative to RC4]}} הוא שיפור של VMPC, שפותח על ידי Bartosz Zoltak ב-2004. הוא ניתח מספר אלגוריתמים בסגנון RC4 ומצא חולשות סטטיסטיות ברבים מהם כולל Spritz. הוא מצא שבצופן Spritz של ריבסט ושולדט עבור <math>N=8</math> ההסתברות ש-<math>\text{Output}(x)=\text{Output}(x+2)</math> היא <math>1/N+0.000498</math>. ההטיה נעשית משמעותית לאחר כמות של <math>2^{21.9}</math> פלטים. כמו כן מצא הטיות סטיסטיות גם במקרה של <math>N=16</math>. הוא פיתח לצורך הבדיקה מבחן סטטיסטי חדש שנקרא distant-equalities שבו בודקים את מספר המופעים של האירועים <math>z_i=z_{i+k}</math> עבור <math>k\in\{1,2,...,8\}</math> ביחס לצפוי מזרם אקראי אמיתי. אירוע <math>k</math> פירושו ששני מילים במרחק <math>k</math> זה מזה זהים. לאור חולשות שהתגלו ב-VMPC על ידי מקסימוב{{הערה|Alexander Maximov: Two Linear Distinguishing Attacks on VMPC and RC4A and Weakness of RC4 Family of Stream Ciphers. Proceedings of FSE 2005, LNCS, vol. 3557, Springer-Verlag, 2005, pages 342-358}}, פיתח Bartosz Zoltak ב-2013 את הגרסה המשופרת של הצופן לה הוסיף את האות R (ראנדום). לטענתו היא הטובה ביותר האפשרית בסגנון RC4 והפלט שלה עומד בכל המבחנים הסטטיסטיים הידועים. אם כי קצת איטית בהשוואה ל-RC4 המקורי. להלן תיאור האלגוריתם המקבל וקטור אתחול ומפתח הצפנה ומפיק בית אחר בית של מחרוזת פסאודו-אקראית:

<div class="mw-content-ltr" align="center">
{| class="wikitable" align="center"
|-
|
<math>N\text{ word size e.g. }N=256</math>

<math>a,b,c,d,e,f,n\text{ are integer variables}</math>

<math>P,S\text{ are N-element permutations}</math>

<math>+\text{ denotes addition modulo }N</math>

<math>K\text{ array of }k\text{ integers; }k\in\{1,...,N\}</math>

<math>V\text{ an IV array of }v\text{ elements }v\in\{1,...,N\}</math>

<math>R=\left\lceil k^2/(6N)\right\rceil\cdot N</math>

<math>i\text{ is a temprorary counter}</math>
:{{D}}
<math>\mathbf{VMPC}\text{-}\mathbf{R \ KSA}</math>
:<math>a=b=c=d=e=f=n=0</math>
:<math>\text{For }i=0\text{ to }N-1\text{ do}</math>
::<math>P[i]=S[i]=i</math>
:<math>\text{KsaRound}(K,k)</math>
:<math>\text{KsaRound}(V,v)</math>
:<math>\text{KsaRound}(K,k)</math>
:<math>n=S[S[S[c+d]]+1]</math>
{{D}}
{{D}}
{{D}}
{{D}}
{{D}}
{{D}}
{{D}}

||

<math>\mathbf{KsaRound}(M,m)</math>
:<math>i=0</math>
:<math>\text{Repeat R times:}</math>
::<math>a=P[a+f+M[i]]+i; \ \ i=(i+1)\text{ mod }m</math>
::<math>b=P[b+a+M[i]]+i; \ \ i=(i+1)\text{ mod }m</math>
::<math>c=P[c+b+M[i]]+i; \ \ i=(i+1)\text{ mod }m</math>
::<math>d=P[d+c+M[i]]+i; \ \ i=(i+1)\text{ mod }m</math>
::<math>e=P[e+d+M[i]]+i; \ \ i=(i+1)\text{ mod }m</math>
::<math>f=P[f+e+M[i]]+i; \ \ i=(i+1)\text{ mod }m</math>
::<math>\text{Swap}(P[n],P[b]), \ \text{Swap}(S[n],S[e])</math>
::<math>\text{Swap}(P[d],P[f]), \ \text{Swap}(S[a],S[c])</math>
::<math>n=n+1</math>
:{{D}}
<math>\mathbf{VMPC}\text{-}\mathbf{R \ PRNG}</math>
:<math>\text{Loop:}</math>
::<math>a=P[a+c+S[n]], \ b=P[b+a], \ c=P[c+b]</math>
::<math>d=S[d+f+P[n]], \ e=S[e+d], \ f=S[f+e]</math>
::<math>\boldsymbol{\mathbf{Output:}\ S[S[S[c+d]]+1]}</math>
::<math>\text{Swap}(P[n],P[f])</math>
::<math>\text{Swap}(S[n],S[a])</math>
:<math>n=n+1</math>

|}
</div>

== קישורים חיצוניים ==
* [https://web.archive.org/web/20110612074007/http://www.wisdom.weizmann.ac.il/~itsik/RC4/Papers/bc_rc4.ps התקפה מעשית כנגד RC4] של איצק מנטין ועדי שמיר
* [https://web.archive.org/web/20040602051734/http://www.wisdom.weizmann.ac.il/~itsik/RC4/Papers/Rc4_ksa.ps נקודות תורפה באלגוריתם תיזמון מפתח של RC4], פלורר, מנטין ושמיר [[מכון ויצמן למדע]], [[2001]]
* [https://web.archive.org/web/20070209005245/http://www.wisdom.weizmann.ac.il/~itsik/RC4/Papers/wep_attack.ps Using the Fluhrer, Mantin, and Shamir Attack to Break WEP, Stubblefield, Loannidis, and Rubin,] מעבדות [[AT&T]]
* [http://eprint.iacr.org/2007/120.pdf פריצת WEP 104 bit בפחות מדקה]

==הערות שוליים==
{{הערות שוליים|יישור=שמאל}}

{{קריפטוגרפיה}}

[[קטגוריה:צפני זרם]]
[[קטגוריה:רונלד ריבסט]]