MARS

**MARS** הוא צופן בלוקים סימטרי שפותח ב-1998 בחברת IBM על ידי צוות מפתחים בראשות דון קופרשמידט שהיה מעורב בפיתוח DES כמועמד לתקן ההצפנה המתקדם. MARS הגיע למקום האחרון מבין חמשת המועמדים המובילים (אחרי RC6). הצופן קומפקטי, מתאים ליישום בתוכנה ובחומרה, מנצל את יכולות המעבד המודרני להשגת מהירות, יעילות וביטחון טובים יותר לעומת אלגוריתמים מדור קודם כמו DES או IDEA ונועד להצפנה מסיבית. MARS פועל על בלוקים בגודל 128 סיביות ומפתח הצפנה בטווח גדלים של 128 - 400 סיביות. כיתר המועמדים המובילים שעלו לגמר הוכרז במהלך התחרות שלא התגלו התקפות מעשיות שמסכנות את ביטחונו. IBM התירה את השימוש בו ומימוש שלו ברישיון חופשי במגבלות מסוימות, למרות היותו מוגן בפטנט וזכויות יוצרים.

## שיקולי פיתוח
השיקולים שהנחו את IBM בפיתוח הצופן כדי לעמוד בדרישות התקן החדש הם:
*ניצול מלא של 'פעולות חזקות' הזמינות במעבדים המודרניים כגון כפל מהיר ב-32 סיביות או הזזה מעגלית לפי ערכים משתנים.
*מבנה ייחודי שהוא תוצר של ניסיון רב שנים. ייחודו נובע מפיצול סבבי הצפנה לשלושה מרכיבים עיקריים; עליון אמצעי ותחתון, השלב האמצעי נחשב לגרעין הקריפטוגרפי שמבצע את ההצפנה, בעוד שהאחרים משמשים כשכבת הגנה. השיטה אומצה מנאור-ריינגלוד ובעיקרה עיטוף של גרעין קריפטוגרפי באמצעות טרנספורמציה לא קריפטוגרפית כלשהי, כדי להקשות על קריפטואנליזה.
*לאפשר ניתוח יעיל של ביטחון מרכיבי האלגוריתם והימנעות מפעולות 'קשות לניתוח'.
*שימוש ברשת פייסטל מסוג 3. סוג של רשת החלפה-תמורה שבכל סבב מילת קלט אחת משפיעה על כל מילות הקלט האחרות (בניגוד לרשת המקורית שבה כל מילה משפיעה על מילה אחת אחרת). לשיטה זו יתרונות על פני קודמתה הן ביעילות והן בביטחון.
*סימטריה בין הצפנה לפענוח. כדי להתמודד עם התקפות המנצלות חוסר סימטריה בין חלק מסבבי ההצפנה (כגון צופנים שבהם הסבב האחרון שונה מהיתר כמו ריינדל), עובדה המאפשרת התקפה שבה 'מקלפים' את השכבה העליונה או התחתונה ומתמקדים בשכבה הפנימית העיקרית.

### הפעולות שבהן משתמש האלגוריתם כוללות
*חיבור, חיסור ו-XOR, בעיקר לערבוב ערכי קלט עם ערכי מפתח (פעולות אילו לא נועדו להשגת ביטחון).
*טבלת חיפוש (Table lookup) הנקראת גם תיבות החלפה (s-box), המספקות את הביטחון העיקרי של הצופן. MARS משתמש בטבלה בגודל 512 כניסות של מילים בגודל 32 סיביות. תיבות ההחלפה תוכננו להשגת אפקט מפולת מהיר ונבחרו בקפידה כדי לעמוד בפני התקפות דיפרנציאליות וליניאריות. חסרונן העיקרי שנדרשות שלוש פקודות מכונה לכל החלפה וכן צריכת זיכרון - מה שעשוי להיות קריטי במעבד קטן.
*הזזה מעגלית (Rotation) קבועה או דינאמית התלויה בקלט. בפעולה זו הסיביות הנפלטות מצד אחד מוחזרות לצד השני. שימוש מסיבי בהזזה מעגלית קיים באלגוריתמים מודרניים אחרים כמו RC6. חסרונן העיקרי הוא שלעיתים תוצאת ההזזה אינה מושפעת מכל סיביות האופרנדים, דבר המוביל לחולשה מסוימת. לדוגמה, אם מספר הפוזיציות להזזה מיוצג על ידי משתנה count בגודל 32 סיביות, הרי שלכל היותר נדרשות שש סיביות מתוכו כדי לייצג את ההזזה (הייצוג הבינארי של הזזה מקסימלית - 32 פוזיציות), ליתר הסיביות אין השפעה. הפתרון אפשרי הוא שילוב עם פעולת כפל.
*פעולת כפל שלמים מודולו 2^w כאשר w מתייחס לגודל מילה בסיביות. כמו בצופן IDEA פעולות אילו מניבים פיזור גבוה ותכונות דיפרנציאליות טובות. בארכיטקטורת מעבדים מודרניים חל צמצום ניכר במספר מחזורי שעון לפעולת כפל. לכן השימוש בהן הופך אטרקטיבי.

## תיאור האלגוריתם
קלט ופלט הצופן הם ארבע מילים בגודל 32 סיביות D_0,D_1,D_2,D_3. המפתח מיוצג על ידי 40 מילים K_0,...,K_{39}. ו-512 תיבות ההחלפה כשהן מחולקות לשתיים דהיינו 256 הכניסות הראשונות נקראות S_0 והאחרונות S_1. כל הפעולות הפנימיות מבוצעות ברמת מילים. את בתי הקלט ממירים למילים לפי סדר בתים קטן (הבית הראשון מכיל את הספרות הפחות משמעותיות של המילה). השלד העיקרי של האלגוריתם מורכב מהפעולות הבאות לפי סדר זה:
*חיבור מפתח.
*שמונה סבבים של ערבוב לפנים ללא מפתח.
*שמונה סבבים של ערבוב לפנים עם מפתח.
*שמונה סבבים של ערבוב לאחור עם מפתח.
*שמונה סבבים של ערבוב לאחור ללא מפתח.
*חיסור מפתח.

אפשר לראות את הסימטריה הרבה של הצופן. הוספת חלק מהמפתח המורחב שנקראת 'הלבנה' (whitening) מסתיימת בפעולה ההפוכה של חיסור המפתח. שני המרכיבים הבאים נקראים 'ערבוב לפנים' (Forward mixing), מטרתם לספק ערבוב מהיר ואפקט מפולת להגנה מפני התקפת גלוי-נבחר, זאת באמצעות הוספת חלק מהמפתח המורחב, פעולות ערבוב והזזה נוספות בין מילות הקלט, שימוש בתיבות ההחלפה כאשר שני בתי קלט b_0,b_2 משמשים אינדקס ל-S_0 והבתים b_1,b_3 ל-S_1, כל זה במבנה מסוג רשת פייסטל. שני המרכיבים האמצעיים נקראים 'גרעין קריפטוגרפי' ומורכבים משישה-עשר סבבים של רשת פייסטל מסוג 3, שכוללת פונקציית הרחבה E (ראה להלן) וקומבינציה של כפל בשלמים עם הזזה מעגלית, גם הם מחולקים לקדמי ואחורי לצורך הסימטריה. שני המרכיבים המסיימים נקראים 'ערבוב לאחור' בהם מתבצעות פעולות הפוכות לפעולות שבוצעו בשלבים הפותחים ובסדר הפוך (כלומר הקלט מוזן בסדר הפוך והאינדקסים לתיבות ההחלפה הפוכים) ולמעשה האפקט הוא ביטול השפעת הערבוב הקדמי על הטקסט המוצפן. הערבוב המסיים נועד להגנה מפני התקפת מוצפן-נבחר. כאמור מטרת פעולות אילו אינה קריפטוגרפית ולא נועדה להסתיר את המידע אלא למנוע מהמתקיף למקד את ההתקפה בגרעין האמצעי על ידי הוספת שכבת הגנה.

פונקציית ההרחבה E מקבלת מילה אחת in ומחזירה שלוש מילים out_1,out_2,out_3 באמצעות שתי מילים מהמפתח המורחב k_1,k_2. התהליך מתואר בתרשים ובפסאודו קוד להלן. הפונקציה מבצעת הזזות מעגליות קבועות ותלויות משתנים, החלפות בתיבות s-box, כפל שלמים מודולו 2^w ופעולות XOR. השילוב נעשה באופן שינוצלו היתרונות שבכל אחת מהן, למשל ידוע שבכפל שלמים לסיביות הנמוכות השפעה גדולה יותר על המכפלה מאשר העליונות לכן דואגים לכך שסיביות האינדקס לתיבות ההחלפה יהיו מהגבוהות. וכן הסיביות העליונות של המכפלה חזקות יותר במובן שהן מושפעות מכמעט כל סיביות הקלט.

### תיבות החלפה
בבניית תיבות ההחלפה (s-box) הכניסות חושבו בסגנון פסאודו-רנדומלי ונבדקו שלהם תכונות דיפרנציאליות וליניאריות טובות כדלהלן; עבור i=0,...,102, \ \ j=0,...,4 הכניסה S_{5i+j} מחושבת על ידי הפעלת פונקציית הגיבוב הקריפטוגרפית SHA-1 שמחזירה 4 מילים של 32 סיביות:

S_{5i+j}=\mbox{SHA-1}(5i || c_1 || c_2 || c_3)_j

הסימן "||" מייצג שרשור והערך \mbox{SHA-1}(\cdot)_j הוא המילה ה-j של פלט הפונקציה. הקבועים c_1=\mbox{B7E15162},c_2=\mbox{243F6A88} (בבסיס הקסדצימלי) חושבו מהקבועים המתמטיים פאי ו-e ועבור המשתנה c_3 נבדקו ערכים רבים במטרה למצוא אחד כזה שיניב תוצאה אופטימלית מבחינה קריפטוגרפית. הבדיקות הן: (א) שלא נוצרו במקרה תיבות החלפה המכילות רק אפסים או רק אחדים. (ב) שכל זוג ערכים מקבילים מהתיבות S_0,S_1 יהיו שונים לפחות בשלושה מתוך ארבעת הבתים. (ג) שהתיבות אינן מכילות שני ערכים S_i,S_j, \ (i\ne j) כך שמתקיים S_i=S_j,S_i= \neg S_j או S[i]=-S[j]. (ד) של-S יהיו \textstyle {512 \choose 2} הפרשי XOR שונים וכן 2 \times \textstyle {512 \choose 2} הפרשי חיסור שונים. (ה) שכל זוג כניסות יהיו שונות לפחות בארבע סיביות אחת מהשנייה. באופן דומה בודקים שלתיבות תכונות ליניאריות טובות; הטיית זוגיות נמוכה והטיית סיביות נמוכה וקורלציה נמוכה. התיבות נבדקו עם ערכים שונים של c_3 בבדיקה נמשכה כשבוע ימים ונבדקו מעל 2^{26} ערכים אפשריים עד שנמצא הערך האופטימלי c_3=\mbox{02917D59}.

## פסאודו קוד
ימין|ממוזער|300px|תרשים ערבוב לפנים של צופן מארס
בפסאודו קוד להלן הסימנים "\lll" ו-"\ggg" פירושם הזזה מעגלית בסיביות (bitwise rotation) לימין או לשמאל לפי כיוון החצים והערך לצידם המציין את מספר הפוזיציות שיש להזיז, הסימן \oplus הוא XOR. ארבעת הבתים של D_0 משמשים אינדקסים לתיבות ההחלפה, למשל S_1[2^{nd}\mbox{ byte of }D_0] פירושו שהבית השני של D_0 משמש אינדקס לתיבה המתאימה ב-S_1.

### הצפנה
ימין|ממוזער|300px|הליבה הקריפטוגרפית של צופן מארס, מחולקת לשני חצאים לצורך הסימטריה


**Phase (I)** השלב הפותח שנקרא ערבוב לפנים
#\mbox{For }i=0\mbox{ to }3\mbox{ do:}
##D_i=D_i+K_i
#\mbox{For }i=0\mbox{ to }7\mbox{ do:}
##D_1=D_1\oplus S_0[1^{st}\mbox{ byte of }D_0] + S_1[2^{nd}\mbox{ byte of }D_0]
##D_2=D_2+ S_0[3^{rd}\mbox{ byte of }D_0]
##D_3=D_3\oplus S_1[4^{th}\mbox{ byte of }D_0]
##D_0=D_0 \ggg 24
##\mbox{If }i=0\mbox{ or }4\mbox{ then:} \ D_0=D_0+D_3
##\mbox{If }i=1\mbox{ or }5\mbox{ then:} \ D_0=D_0+D_1
##(D_3,D_2,D_1,D_0) \leftarrow (D_0,D_3,D_2,D_1)


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

ימין|ממוזער|300px|ערבוב לאחור של הצפנת צופן מארס, כל הפעולות הפוכות לפעולות שבוצעו בערבוב הפותח

#### הפונקציה E
קלט: in, k_1,k_2 בגודל 32 סיביות כל אחד. שימו לב שהביטוי S[\mbox{lowest 9 bits of }M] מתייחס לאינדקס בגודל 9 סיביות לטבלה המאוחדת מ-S_0 ו-S_1

#M=in+k_1
#R=(in \lll 13) \times k_2
#L=S[\mbox{lowest 9 bits of }M]
#R = R \lll 5
#M=M \lll \mbox{ lowest 5 bits of }R
#L=L\oplus R
#R=R \lll 5
#L=L\oplus R
#L=L \lll \mbox{ lowest 6 bits of }R


הפלט הוא (L,M,R).


**Phase (II)** גרעין קריפטוגרפי
#\mbox{For }i=0\mbox{ to }15\mbox{ do:}
##(out_1,out_2,out_3)= E(D_0, K_{2i+1},K_{2i+5})
##D_2=D_2 + out_2
##\mbox{If }i 
###D_1=D_1+out_1, \ D_3=D_3\oplus out_3
##\mbox{Else:}
###D_3=D_3+out_1, \ D_1=D_1\oplus out_3
#(D_3,D_2,D_1,D_0) \leftarrow (D_0 \lll 13,D_3,D_2,D_1)

**Phase (III)** השלב המסיים המשלים של השלב הפותח שנקרא ערבוב לאחור.
#\mbox{For }i = 0\mbox{ to }7\mbox{ do:}
##\mbox{If }i = 2\mbox{ or }6\mbox{ then:} \ D_0=D_0-D_3
##\mbox{If }i=3\mbox{ or }7\mbox{ then:} \ D_0=D_0-D_1
##D_1=D_1\oplus S_1[1^{st}\mbox{ byte of }D_0]
##D_2=D_2 - S_0[4^{th}\mbox{ byte of }D_0]
##D_3=D_3 - S_1[3^{rd}\mbox{ byte of }D_0]\oplus S_0[2^{nd}\mbox{ byte of }D_0]
##D_0=D_0 \lll 24
##(D_3,D_2,D_1,D_0) \leftarrow (D_0,D_3,D_2,D_1)
##\mbox{For }i = 0\mbox{ to }3\mbox{ do:}
###D_i=D_i-K_{36+i}

פלט הצופן הוא ארבע המילים (D_3,D_2,D_1,D_0).

### פענוח

**Phase (I)**
#\mbox{For }i=0\mbox{ to }3\mbox{ do:}
##D_i=D_i+K_{36+i}
#\mbox{For }i=7\mbox{ down to }0\mbox{ do:}
##(D_3,D_2,D_1,D_0) \leftarrow (D_2,D_1,D_0,D_3)
##D_0=D_0 \ggg 24
##D_3=D_3\oplus S_0[2^{nd}\mbox{ byte of }D_0] + S_1[3^{rd}\mbox{ byte of }D_0]
##D_2=D_2+ S_0[4^{th}\mbox{ byte of }D_0]
##D_1=D_1\oplus S_1[1^{st}\mbox{ byte of }D_0]
##\mbox{If }i=2\mbox{ or }6\mbox{ then:} \ D_0=D_0+D_3
##\mbox{If }i=3\mbox{ or }7\mbox{ then:} \ D_0=D_0+D_1

**Phase (II)**
#\mbox{For }i=15\mbox{ down to 0 do:}
##(D_3,D_2,D_1,D_0) \leftarrow (D_2,D_1,D_0,D_3)
##D_0=D_0 \ggg 13
##(out_1,out_2,out_3)=E(D_0,K_{2i+4},K_{2i+5})
##D_2=D_2-out_2
##\mbox{If }i 
###D_1=D_1-out_1, \ D_3=D_3\oplus out_3
##\mbox{Else:}
###D_3=D_3-out_1, \ D_1=D_1\oplus out_3

**Phase (III)**
#\mbox{For }i=7\mbox{ down to 0 do:}
##(D_3,D_2,D_1,D_0) \leftarrow (D_2,D_1,D_0,D_3)
##\mbox{If }i=0\mbox{ or 4 then:} \ D_0=D_0-D_3
##\mbox{If }i=1\mbox{ or 5 then:} \ D_0=D_0-D_1
##D_0=D_0 \lll 24
##D_3=D_3\oplus S_1[4^{th}\mbox{ byte of }D_0]
##D_2=D_2 - S_0[3^{rd}\mbox{ byte of }D_0]
##D_1=D_1 - S_1[2^{nd}\mbox{ byte of }D_0]\oplus S_0[1^{st}\mbox{ byte of }D_0]
#\mbox{For }i=0\mbox{ to 3 do:}
##D_i=D_i-K_i


### הרחבת מפתח
הרחבת המפתח נעשית מתוך מפתח צופן k בגודל n מילים של 32 סיביות, טווח ערכים אפשריים הוא 4 \le n \le 14. אותו מרחיבים למפתח K עם 40 מילים. ההרחבה מתבצעת כדלהלן: נתון מערך עזר T שבכניסותיו הראשונות מציבים את מפתח הצופן, מוסיפים את ערכו של n ומרפדים את היתר באפסים. לאחר מכן מבצעים ארבעה סבבים של פעולות הכוללות טרנספורמציה ליניארית וערבוב באמצעות רשת פייסטל מסוג 1. בכל סבב מחלצים עשרה ערכים וכדי להימנע ממפתחות חלשים, עוברים על כל הערכים שהתקבלו וקובעים את שתי הסיביות הפחות חשובות בכל 'מילת-מפתח' המשמשת לכפל ל-"11" וכן מוודים שלא יהיו עשרה אפסים או עשרה אחדים עוקבים באף אחת מהן, להלן פסאודו קוד:

#B=\{\mbox{A4A8D57B}, \ \mbox{ 5B5BD193B}, \ \mbox{ C8A8309B}, \ \mbox{ 73F9A978}\}
#T[0,...,n-1]=k[0,...,n-1], T[n] = n, T[n+1,...,14] = 0
#\mbox{For }j=0\mbox{ to 3 do:}
##\mbox{For }i=0\mbox{ to 14 do:}
###T_i=T_i\oplus((T_{(i-7) \mbox{ mod }15}\oplus T_{(i-2)\mbox{ mod }15}) \lll 3)\oplus (4i+j)
#\mbox{Repeat 4 times:}
##\mbox{For }i=0\mbox{ to 14 do:}
###j=\mbox{low 9 bits of }T_{(i-1) \bmod\ 15}
###T_i=(T_i+S_j) \lll 9
#\mbox{For }i=0\mbox{ to 9 do:}
##K_{10j + i}=T_{4i\mbox{ mod }15}
#\mbox{For }i=5,7,...,35\mbox{ do:} \ \mbox{ (this are the multiplication keys)}
##j=\mbox{least 2 bits of }K_i
##w=K_i \vee 3 \ \mbox{(the 2 lower bits is set to 1)}
##M_l=1\mbox{ Iff }w_l\mbox{ belongs to a sequence of 10 consecutive 1's or 0's, And }
###2 \le l \le 30\mbox{ And Also }w_{l-1}=w_l=w_{l+1}
##r=\mbox{ least 5 bits of }K_{i-1}
##p=B_j \lll r
##K_i=w\oplus (p \wedge M)

בקוד המתואר M נקרא מסכת סיביות (bit mask) כאשר הסיביות M_l מחושבות לפי ערכי w_l. וגודל המסכה הוא לכל היותר l=30. הסמל \vee  הוא האופרטור OR והסמל \wedge  הוא האופרטור AND.

## יעילות וביטחון
בבדיקות שנעשו הגיע צופן MARS למהירות של 28 מגה בקירוב לשנייה בהצפנה ופענוח על מחשב מסוג Pentium-Pro. הסתבר שמהדר בורלנד (שנמנה מבין דרישות התקן) לא הניב ביצועים אופטימליים. הצופן ניתן ליישום יעיל על פלטפורמות שונות הן בחומרה והן בתוכנה, אך נופל בביצועיו לעומת המתחרים האחרים. למעשה קיבל את הניקוד הנמוך ביותר לפי דירוג NIST של חמשת המובילים. להערכת המפתחים עם מפתח 256 סיביות ההתקפה הכי טובה היא 2^{256} על בסיס הערכה זו, מנימוקים קריפטוגרפיים, אין כל סיבה להשתמש במפתחות גדולים יותר. כמו כן ההתקפה הטובה ביותר האפשרית כנגד האלגוריתם (גם ליניארית וגם דיפרנציאלית) היא בסיבוכיות מקום של 2^{128} - שזה מעבר למידע הזמין בעולם. הערכת המפתחים שהאלגוריתם יהיה בטוח לפחות לעשור הקרוב.

ועדת המחקר של האיחוד האירופי לבחירת תקן ההצפנה אירופאי הנקראת NESSIE (מקבילה של NIST) ביקרה את כל המועמדים המובילים לתקן AES בשנים 2000 - 2003 וציינה מספר בעיות בקשר ל-MARS. לדעת הוועדה, טענת המפתחים לגבי ביטחון הצופן מכילה מספר שגיאות ואין בהירות מספקת לגבי תרומתו של המבנה המיוחד (תוספת הסבבים ללא המפתח) לביטחונו, אם כי אין מספיק מידע כדי לפתח התקפה מעשית. קיימות למעשה התקפות תאורטיות (של ביהם ושנייר) על מספר סבבים מצומצם של הצופן שמלמדות שאין הוכחה ברורה ליתרון זה. ניתוח תהליך הרחבת המפתח מאוד איטי ואינו מעיד בהכרח על ביטחונו. במיוחד העובדה ששתי הסיביות הנמוכות של חלקים מהמפתח המשתתפים בכפל שנקבעו ל-"11", משליכה שתמיד יהיו שני קלטים שלא ישתנו בשלב הכפל בלי התחשבות במפתח. המבקרים מסכמים שמבנה MARS היה מורכב מדי להערכה בזמן הקצר של התחרות ואין ביטחון שלא יתגלו חולשות.

### התקפת בומרנג
ההתקפה הטובה ביותר הידועה (נכון לשנת 2000) כנגד צופן MARS היא התקפה דיפרנציאלית של ג'ון קלסי, ברוס שנייר וטדיושי קונו. ההתקפה שנקראת 'בומרנג' מצליחה לפרוץ את MARS באחד-עשר סבבים של הגרעין הקריפטוגרפי בסיבוכיות של 2^{65} טקסטים גלויים נבחרים עם זיכרון 2^{70} ו-2^{229} ניסיונות (הצפנה חלקית - ללא שכבת הערבוב).

## ראו גם
* AES

## הערות שוליים

קטגוריה:צפני בלוקים