RC4

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש
המחשת הצפנת בלוק אחד בRC4

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

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

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

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

זרם המפתח כאמור מופק באמצעות אלגוריתם תזמון מפתח (Key Scheduling algorithm). תחילה המערך \ S מאותחל בשלמים 0 עד 255 ולאחר מכן מעובד בעזרת המחולל הפסבדו אקראי המובנה, תוך שימוש בכל סיביות מפתח ההצפנה. המפתח יכול להיות בכל אורך רצוי (בדרך כלל בין 40 ל-256 סיביות). להלן קוד ב-C המתאר את אלגוריתם הכנת המפתח:

int i, j = 0;
for(i = 0; i < 256; i++)
    S[i] = i;
 
for(i = 0; i < 256; i++) {
    j = (j + S[i] + key[i % key_length]) % 256;
    S[i] ^= S[j], S[j] ^= S[i], S[i] ^= S[j]; 
}

זהו פסאדו קוד קל יותר להבנה

for i from 0 to 255
    S[i] := i
endfor
j := 0
for i from 0 to 255
    j := (j + S[i] + key[i mod keylength]) mod 256
    swap values of S[i] and S[j]
endfor

ההצפנה מתבצעת כאמור בית אחר בית, במספר החזרות הנדרש עד להצפנת כל הטקסט הקריא. בכל סבב האלגוריתם מעדכן את מצב הצופן ומפיק בית מפתח אחד כדלהלן: האינדקס \ i מקודם צעד אחד, הערך המצוי בכניסה \ i במערך \ S מוסף ל-\ j, ערכי \ S_i ו-\ S_j מחליפים מקומות ואז מחברים את \ S_i + S_j עם הבית הנוכחי בטקסט הקריא ב-XOR. כאשר כל הפעולות מבוצעות מודולו 256 (גודל בית אחד). כל כניסה במערך \ S מוחלפת לפחות פעם אחת כל 256 סבבים. קוד פשוט של האלגוריתם נראה כדלהלן:

char RC4(char m) {
    i = (i + 1) % 256;
    j = (j + S[i]) % 256;
    S[i] ^= S[j], S[j] ^= S[i], S[i] ^= S[j];
    return m ^ S[(S[i] + S[j]) % 256];
}

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

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

יישומים[עריכת קוד מקור | עריכה]

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

בטיחות[עריכת קוד מקור | עריכה]

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

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

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

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

קישורים חיצוניים[עריכת קוד מקור | עריכה]

  1. ^ Discovery and Exploitation of New Biases in RC4