RC4

המחשת הצפנת בלוק אחד ב-RC4

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

RC4 פותח על ידי רונלד ריבסט ב-1987 במעבדות 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) של האלגוריתם מורכב משני חלקים:

1. תיבת תמורה $\ S$באורך 256 בתים (כאשר כל 256 הערכים האפשריים מופיעים בה)
2. שני אינדקסים $\ i$ ו-$\ j$.

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

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

$\mathbf {RC4\ KSA:}$ ${\text{For }}i=0{\text{ to }}N-1{\text{ do: }}$ $S[i]=i$ $j=0$ ${\text{For }}i=0{\text{ to }}N-1{\text{ do:}}$ $j=j+S[i]+K[i{\text{ mod }}kLength]$ ${\text{Swap}}(S[i],S[j])$

$\mathbf {RC4\ PRGA:}$ $i=j=0$ $\mathbf {Loop:}$ $i=i+1$ $j=j+S[i]$ ${\text{Swap}}(S[i],S[j])$ ${\text{Return: }}S[S[i]+S[j]]$

${\text{Swap}}(S[x],S[y])$ $t=S[x]$ $S[x]=S[y]$ $S[y]=t$ ‎ ‎ ‎

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

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

RC4("Secret", "Attack at dawn") = 45A01F645FC35B383552544B9BF5

יישומים

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

ביטחון

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

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

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

תהליך הכנת זרם המפתח - KSA

• בתהליך ההכנה הראשוני של RC4 המפתח הסודי המסופק על ידי המשתמש מעורבב בתוך תמורה $S$ באורך 256 בתים שנקראת המצב הפנימי (interenal state) של הצופן. קיימת הטיה סטטיסטית של בתים מהתמורה $S$ למפתח הסודי, כלומר קיים מתאם גבוה בין $S[v]$ עבור $v$ קטן לבין בתים של המפתח.
• קיימת הטיה סטטיסטית של התמורה $S$ הראשונה (המצב הפנימי) מיד לאחר KSA לצירוף כלשהו של בתים מהמפתח הסודי. קיימת נוסחה מפורשת של ההסתברויות שבתים מהתמורה $S$ בכל שלב נוטים לבתים של המפתח הסודי.
• מבחינה תאורטית, קיימת חולשה מובנית בסגנון הערבוב של KSA שגורם לכך שהתמורה $S$ אינה אחידה לגמרי, אלא סובלת מחוסר אקראיות בכמה מקומות, מה שיכול להוביל להתקפת הבחנה.
• בתהליך הכנת זרם המפתח קיימת תופעה מעניינת שנקראת "זוגות אנומליה", מספר הפעמים הצפוי שבהם כל בית בתמורה $S$ זוכה לביקור על ידי האינדקסים $i,j$ אינו אחיד.
• קיימת התנגשות בין מפתחות, שני מפתחות שמפיקים מצב פנימי זהה, ובגלל זה מפתחות הצפנה סודיים שונים יפיקו זרם מפתח זהה (Matsui).
• קיימת מחלקה עצומה של מפתחות חלשים, כך שבידיעת חלק קטן מהמפתח הסודי אפשר לנחש בתים רבים של פלט זרם המפתח. Mironov ניתח כמה בתים מהפלט הראשוני של זרם המפתח סובלים מהטייה והמליץ להיפטר מ-512 הבתים הראשונים.

המצב הפנימי

• פורסמו מספר התקפות לשחזור המצב הפנימי של הצופן מתוך מצב פנימי ידוע. וכן שחזור מפתח ההצפנה מתוך המצב הפנימי.
• אם סיבוכיות שחזור המפתח הסודי מתוך מהתמורה $S$ נמוכה משחזור התמורה $S$ מתוך זרם המפתח, אפשר לשלב את שתיהן יחד להתקפה מוצלחת יותר.
• מקסימוב וחוברטוביץ' פיתחו התקפה תאורטית לשחזור המצב הפנימי בסיבוכיות של $2^{241}$ זמן וזרם מפתח. Golić ו-Morgari פיתחו אלגוריתם הסתברותי לשחזור המצב הפנימי מתוך זרם המפתח באורך $2^{41}$ בזמן של $2^{689}$.

מחולל זרם המפתח - PRGA

• התגלו מצבים פנימיים שלעולם לא יופיעו בזרם המפתח (Finney).
• משפט Glimpse מראה שקיימת "דליפה" של מידע בבתי זרם המפתח (Jenkins). בניגוד לצפוי ממחרוזת אקראית באורך $N$, ההסתברות לניחוש בתים אחדים מהמפתח מתוך בתים של המצב היא $2/N$.
• בפלט המפתח קיימים שני סוגים של הטיה; הטיה קצרת-טווח והטיה ארוכת-טווח. כלומר קיימת חולשה (חוסר אקראיות) מובנית בבתי זרם המפתח, במיוחד בבתים הראשונים (למשל הבית השני שסובל מהטיה חמורה). אפשר להימנע מההטייה קצרת הטווח אם נפטרים מ-512 הבתים הראשונים כפי שהומלץ וייושם בחלק מהפרוטוקולים.
• פותחו התקפות נגד RC4 אם וקטור אתחול כפי שנמצא בשימוש WEP.

התקפת הבחנה

התקפת הבחנה (Distinguishing Attack) היא התקפה סטטיסטית על פלט מחולל זרם המפתח. במצב אידיאלי, זרם המפתח אמור להראות על פניו כרצף אקראי לכל דבר. כלומר לא ניתן יהיה להבדילו מרצף אקראי שנוצר ממחולל אקראי אמיתי. מחולל זרם המפתח של RC4 הוא לא יותר מאשר מחולל פסאודו-אקראי שמקבל גרעין התחלתי סודי שהוא המפתח "ומותח" אותו למחרוזת אקראית באורך רצוי. התקפת הבחנה מתמקדת במציאת הבדלים או ניתוח ההסתברות שסיבית 1 או 0 תופיע בפוזיציה מסוימת בהשוואה לזרם אקראי אמיתי. אלגוריתם הבחנה מקבל קלט באורך $n$ בתים שמקורם יכול להיות מזרם המפתח או ממחולל אקראי אמיתי ותפקידו להחזיר תשובה לאיזה סוג מהם הוא משתייך. אם נמצאו הבדלים, עובדה זו כשלעצמה יכולה לפתוח פתח להתקפות ולשבירת הצופן.

• מחקרים מוכיחים כי כלל העדכון של RC4 שהוא $j=j+S[i]$אינו בחירה טובה וקיימת בו חולשה מובנית.
• מבדיקה סטטיסטית שעשו ב-2001 גילו שמיר, איציק מנטין ופלורר שהבתים הראשונים של זרם המפתח של צופן RC4 אינם אקראיים לגמרי ומדליפים מידע לגבי המפתח. נתון זה, אפשר להם לפתח התקפה יעילה כנגד WEP (מערכת אבטחה לרשת אלחוטית). בתחילת 2007 אף פורסמו דרכים חדשות לפיצוחה בזמן קצר מאוד (פחות מדקה) תוך שימוש בכמות לא רבה של טקסט מוצפן. העובדה ש-WEP נפרצה הובילה ביוני 2004 לפיתוח תקן מחמיר יותר הקרוי IEEE 802.11i המשמש בסיס לדור השני באבטחת רשת סלולרית WPA (קיצור של Wi-Fi Protected Access). ב-2011 פורסמו מספר חולשות נוספות של הצופן. שיחד עם חולשות ידועות אחרות מאפשרות התקפה לשחזור מפתח ההצפנה בהינתן 9,800 חבילות מוצפנות בלבד.

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

גרסאות מתקדמות

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

קיימים צפני זרם רבים שמנסים לחקות את המבנה של RC4. כלומר פרמוטציה פנימית גדולה שנקראת מצב (state) והיא מורכבת בדרך כלל ממערך אחד או יותר של $N$ אלמנטים כל אחד בגודל $N$, מספר מוגבל של אינדקסים ופעולת חיבור מודולו $N$ לעיתים בתוספת הזזה מעגלית (rotation). להלן כמה מהם: Py, Py6, IA, ISAAC, NGG, GGHN. חלקם הוצעו לפרויקט ECRYPT האירופאי. כל הצפנים המנויים לא עמדו במבחן קריפטואנליזה (התקפת הבחנה) ונפסלו. לעומתם קיימים מספר אלגוריתמים מבוססי RC4 ששרדו קריפטואנליזה, ביניהם ניתן למנות את: IBAA, Pypy, HC-256, VMPC.

באופן כללי היתרונות של צופן RC4 הם:

1. שימוש במערכים המאפשר זיכרון פנימי עצום במחיר מועט.
2. שימוש בפעולה פשוטה, חיבור מודולו $N$ בלבד.
3. עיצוב פשוט ונקי (קל ליישום והטמעה).
4. לא ידוע על התקפה לשחזור המפתח הסודי מלבד כוח גס.

חסרונות:

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

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

RC4A

RC4A הוצע ב-2004 על ידי Bart Preneel ו-Souradyuti Paul כחלופה לאלגוריתם המקורי. האלגוריתם מבצע פחות פעולות פר בית אחד ותומך במקביליות. אחת ההתקפות הידועות נגד RC4 היא התקפת הבחנה המבוססת על רמת מתאם גבוהה בין המצב הפנימי לפלט האלגוריתם. הפתרון שהוצע הוא לגרום לתלות נוספת של הפלט עם משתנים אקראיים נוספים, כך ההסתברות לניחוש מוצלח של בתי המצב הפנימי תוך התבוננות בפלט תהיה נמוכה יותר. על בסיס הרעיון הזה עוצב RC4A. הצופן הוא הרחבה של המחולל הפנימי PRGA של צופן RC4 בעוד שתהליך הכנת המפתח נותר ללא שינוי. לצורך כך משתמשים בשתי תמורות (מערכים) $S_{1},S_{2}$ במקום אחת וכן שני אינדקסים $j_{1},j_{2}$ במקום אחד. הכנת התמורות נעשית על ידי KSA של RC4 לעיל עם שני מפתחות סודיים שונים $k_{1},k_{2}$ (אחד יכול להיות מופק מהשני באמצעות פונקציה פסאודו-אקראית כלשהי כמו RC4). להלן תיאור האלגוריתם:

${\text{Set: }}i=0,j_{1}=j_{2}=0$ $\mathbf {Loop:}$ $i=i+1$ $j_{1}=j_{1}+S_{1}[i]$ ${\text{Swap}}(S_{1}[i],S_{1}[j_{1}])$ ${\text{Output: }}S_{2}[S_{1}[i]+S_{1}[j_{1}]]$ $j_{2}=j_{2}+S_{2}[i]$ ${\text{Swap}}(S_{2}[i],S_{2}[j_{2}])$ ${\text{Output: }}S_{1}[S_{2}[i]+S_{2}[j_{2}]]$

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

VMPC

הצופן Variably Modified Permutation Composition פותח ב-2004 על ידי Bartosz Zoltak והוצע כתחליף ל-RC4. הרעיון מבוסס על פונקציית פלט מורכבת יותר: $P[P[P[x]]+1]$. כאשר $P$ היא פרמוטציה, זאת במטרה להקשות על ניחוש וכן למנוע הטיות סטטיסטיות לא רצויות של זרם המחולל. אלגוריתם ההכנה מקבל מפתח $K$ באורך $c$ בתים וכן וקטור אתחול $V$ באורך $z$ בתים ומערבב את הפרמוטציה הראשונית בהתאם. פלט המחולל הפנימי הוא בית אחר בית עד למספר הבתים הרצוי $L$ שהוא אורך המסר להצפנה בבתים.

$\mathbf {VMPC\ KSA:}$ $s=0$ ${\text{For }}i=0{\text{ to }}255{\text{ do: }}P[n]=n$ ${\text{For }}m=0{\text{ to }}767{\text{ do:}}$ $n=m{\text{ mod }}256$ $s=P[(s+P[n]+K[m{\text{ mod }}c]){\text{ mod }}256]$ ${\text{Swap}}(P[n],P[s])$ ${\text{For }}m=0{\text{ to }}767{\text{ do:}}$ $n=m{\text{ mod }}256$ $s=P[(s+P[n]+V[m{\text{ mod }}z]){\text{ mod }}256]$ ${\text{Swap}}(P[n],P[s])$

$\mathbf {VMPC\ PRGA:}$ $n=0$ ‎ ${\text{Repeat }}L{\text{ times:}}$ $s=P[(s+P[n]){\text{ mod }}256$ ${\text{Output: }}P[(P[P[s]]+1){\text{ mod }}256]$ ${\text{Swap}}(P[n],P[s])$ $n=(n+1){\text{ mod }}256$ ‎ ‎ ‎

RC4+‎

צופן RC4+‎ הוצע ב-2008 על ידי Subhamoy Maitra ו-Goutam Paul כחלופה בטוחה לצופן RC4. הצופן משתמש בטכניקת ערבוב בשלוש שכבות שונות בשילוב עם וקטור אתחול. לאחר השינויים הצופן בטוח יותר אך לא קיימת הוכחה פורמלית לכך. המחקר בתחום יימשך וייתכנו גילויים חדשים. האלגוריתם הבא המקבל מפתח סודי ווקטור אתחול, שניהם באורך שרירותי ומפיק זרם מפתח באורך הרצוי. סימנים מוסכמים: $\oplus$ מייצג XOR וכן $\ll$ מייצג הזזה (Shift) שמאלה, $\gg$ מייצג הזזה ימינה, ${\text{0xAA}}$ קבוע הקסדצימלי (170 בייצוג עשרוני):

$\mathbf {Initializing:}$ ${\text{For }}i=0{\text{ to }}N-1{\text{ do: }}S[i]=i$ $j=0$ ‎ $\mathbf {Layer\ 1:\ Basic\ Scrambling}$ ${\text{For }}i=0{\text{ to }}N-1{\text{ do:}}$ $j=j+S[i]+K[i]$ ${\text{Swap}}(S[i],S[j])$ ‎ $\mathbf {Layer\ 2:\ Scrambilng\ with\ IV}$ ${\text{For }}i=N/2-1{\text{ down to }}0{\text{ do:}}$ $j=(j+S[i])\oplus (K[i]+IV[i])$ ${\text{Swap}}(S[i],S[j])$ ${\text{For }}i=N/2{\text{ to }}N-1{\text{ do:}}$ $j=(j+S[i])\oplus (K[i]+IV[i])$ ${\text{Swap}}(S[i],S[j])$

$\mathbf {Layer\ 3:\ Zigzag\ Scrambling}$ ${\text{For }}y=0{\text{ to }}N-1{\text{ do:}}$ ${\text{If }}y\equiv 0{\text{ mod }}2{\text{ then: }}i=y/2$ ${\text{Else: }}i=N-(y+1)/2$ $j=j+S[i]+K[i]$ ${\text{Swap}}(S[i],S[j])$ ‎ $\mathbf {PRGA+}$ $i=j=0$ $\mathbf {Keystream\ Generation\ Loop:}$ $i=i+1$ $j=j+S[i]$ ${\text{Swap}}(S[i],S[j])$ $t=S[i]+S[j]$ $u=(S[i\gg 3\ \oplus \ j\ll 5]+S[i\ll 5\ \oplus \ j\gg 3])\oplus {\text{0xAA}}$ ${\text{Output: }}(S[t]+S[u])\oplus S[j+S[j]]$

Spritz

Spritz הוא גרסה מתקדמת של RC4 שפותחה ב-2014 על ידי רונלד ריבסט ו-Jacob Schuldt. הצופן עוצב לפי פרדיגמת פונקציית ספוג שהיא מבנה קריפטוגרפי בטוח שיושם בפונקציית הגיבוב Keccak המאפשר הפעלת פרמוטציה פסאודו-אקראית לצורך פרימיטיבים קריפטוגרפיים שונים כמו הצפנה סימטרית, פונקציית גיבוב או אימות מסרים. מבנה הספוג מורכב ממצב פנימי גדול ושני שלבי הפעלה "ספיגה וסחיטה". פונקציית הספיגה מקבלת מפתח הצפנה ווקטור האתחול (אם יש) ומעדכנת את המצב הפנימי בהתאם, פונקציית הסחיטה מספקת זרם פסאודו-אקראי המשמש כמפתח. בצופן Spritz ארבעה מרכיבים עיקריים, אתחול (Init), ערבוב (Shuffle), ספיגה (Absorb) וסחיטה (Squeeze). לאחר אתחול תחילה סופגים את המפתח $K$ על ידי ${\text{Absorb}}(K)$ ואז ההצפנה מתבצעת עם הפונקציית הסחיטה ${\text{Squeeze}}(r)$ המקבלת פרמטר $r$ "וסוחטת" מחרוזת פסאודו-אקראית באורך $r$ בתים אותם מחברים עם המסר המקורי ב-XOR. הצופן עוצב כך שיוכל לתמוך בכל $N$ אבל צריך להבטיח ש-$w$ יהיה זר ל-$N$ לשם כך הפונקציה ${\text{Whip(r)}}$ משתמשת ב-GCD. במקרה ש-$N$ הוא חזקה של 2 (כגון 256) מספיק שיהיה אי זוגי, לכן אפשר להחליף את הלולאה האחרונה בפונקציה ${\text{Whip(r)}}$ במשפט $w=w+2$. וכן יש לזכור שכל פעולות החיבור הן מודולו $N$. להלן תיאור האלגוריתם:

$\mathbf {InitializeState(N)}$ $i=j=k=z=a=0$ $w=1$ ${\text{For }}v=0{\text{ to }}N-1{\text{ do:}}$ $S[v]=v$ ‎ $\mathbf {Absorb(I)}$ ${\text{For }}v=0{\text{ to }}I.length-1$ ${\text{AbsorbByte}}(I[v])$ ‎ $\mathbf {AbsorbByte(b)}$ ${\text{AbsorbNibble}}({\text{low}}(b))$ ${\text{AbsorbNibble}}({\text{high}}(b))$ ‎ $\mathbf {AbsorbNibble(x)}$ ${\text{If }}a=\left\lfloor N/2\right\rfloor {\text{ then Shuffle}}()$ ${\text{Swap}}(S[a],S[\left\lfloor N/2\right\rfloor +x])$ $a=a+1$ ‎ $\mathbf {AbsorbStop()}$ ${\text{If }}a=\left\lfloor N/2\right\rfloor {\text{ then Shuffle}}()$ $a=a+1$ ‎ $\mathbf {Shuffle()}$ ${\text{Whip}}(2N)$ ${\text{Crush}}()$ ${\text{Whip}}(2N)$ ${\text{Crush()}}$ ${\text{Whip}}(2N)$ $a=0$

$\mathbf {Whip(r)}$ ${\text{For }}v=0{\text{ to }}r-1{\text{ do: Update}}()$ ${\text{Do: }}w=w+1$ ${\text{Until GCD}}(w,N)=1$ ‎ $\mathbf {Crush()}$ ${\text{For }}v=0{\text{ to }}\left\lfloor N/2\right\rfloor -1{\text{ do}}$ ${\text{If }}S[v]>S[N-1-v]$ ${\text{Swap}}(S[v],S[N-1-v])$ ‎ $\mathbf {Squeeze(r)}$ ${\text{If }}a>0{\text{ then Shuffle}}()$ $P={\text{ New Array}}(r)$ ${\text{For }}v=0{\text{ to }}r-1$ $P[v]={\text{Drip}}()$ ${\text{Return }}P$ ‎ $\mathbf {Drip()}$ ${\text{If }}a>0{\text{ then Shuffle}}()$ ${\text{Update}}()$ ${\text{Return Output}}()$ ‎ $\mathbf {Update()}$ $i=i+w$ $j=k+S[j+S[i]]$ $k=i+k+S[j]$ ${\text{Swap}}(S[i],S[j])$ ‎ $\mathbf {Output()}$ $z=S[j+S[i+S[z+k]]]$ ${\text{Return }}z$

VMPC-R

אלגוריתם VMPC-R הוא שיפור של VMPC, שפותח על ידי Bartosz Zoltak ב-2004. הוא ניתח מספר אלגוריתמים בסגנון RC4 ומצא חולשות סטטיסטיות ברבים מהם כולל Spritz. הוא מצא שבצופן Spritz של ריבסט ושולדט עבור $N=8$ ההסתברות ש-${\text{Output}}(x)={\text{Output}}(x+2)$ היא $1/N+0.000498$. ההטיה נעשית משמעותית לאחר כמות של $2^{21.9}$ פלטים. כמו כן מצא הטיות סטיסטיות גם במקרה של $N=16$. הוא פיתח לצורך הבדיקה מבחן סטטיסטי חדש שנקרא distant-equalities שבו בודקים את מספר המופעים של האירועים $z_{i}=z_{i+k}$ עבור $k\in \{1,2,...,8\}$ ביחס לצפוי מזרם אקראי אמיתי. אירוע $k$ פירושו ששני מילים במרחק $k$ זה מזה זהים. לאור חולשות שהתגלו ב-VMPC על ידי מקסימוב, פיתח Bartosz Zoltak ב-2013 את הגרסה המשופרת של הצופן לה הוסיף את האות R (ראנדום). לטענתו היא הטובה ביותר האפשרית בסגנון RC4 והפלט שלה עומד בכל המבחנים הסטטיסטיים הידועים. אם כי קצת איטית בהשוואה ל-RC4 המקורי. להלן תיאור האלגוריתם המקבל וקטור אתחול ומפתח הצפנה ומפיק בית אחר בית של מחרוזת פסאודו-אקראית:

$N{\text{ word size e.g. }}N=256$ $a,b,c,d,e,f,n{\text{ are integer variables}}$ $P,S{\text{ are N-element permutations}}$ $+{\text{ denotes addition modulo }}N$ $K{\text{ array of }}k{\text{ integers; }}k\in \{1,...,N\}$ $V{\text{ an IV array of }}v{\text{ elements }}v\in \{1,...,N\}$ $R=\left\lceil k^{2}/(6N)\right\rceil \cdot N$ $i{\text{ is a temprorary counter}}$ ‎ $\mathbf {VMPC} {\text{-}}\mathbf {R\ KSA}$ $a=b=c=d=e=f=n=0$ ${\text{For }}i=0{\text{ to }}N-1{\text{ do}}$ $P[i]=S[i]=i$ ${\text{KsaRound}}(K,k)$ ${\text{KsaRound}}(V,v)$ ${\text{KsaRound}}(K,k)$ $n=S[S[S[c+d]]+1]$ ‎ ‎ ‎ ‎ ‎ ‎ ‎

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

קישורים חיצוניים

• התקפה מעשית כנגד RC4 של איצק מנטין ועדי שמיר
• נקודות תורפה באלגוריתם תיזמון מפתח של RC4, פלורר, מנטין ושמיר מכון ויצמן למדע, 2001
• Using the Fluhrer, Mantin, and Shamir Attack to Break WEP, Stubblefield, Loannidis, and Rubin, מעבדות AT&T
• פריצת WEP 104 bit בפחות מדקה